\documentclass[12pt]{amsart}
\usepackage{boxedminipage}
\usepackage[latin1]{inputenc}
% uncomment next line to get pdf files with hyperlinks
%\usepackage[pdftex,bookmarks=true]{hyperref}
\def\cao{\c c\~ao}
\def\cc{\c c}
\def\coes{\c c\~oes}
\def\ii{\'{\i}}
\def\stdin{\emph{stdin}}
\def\stdout{\emph{stdout}}
\def\sqn{seqüência}
\def\ibf#1{\item\textbf{#1}}
\def\K{$<\!\!key\!\!>$}
\def\R{$<\!\!reg\!\!>$}
\def\NL{$<\!\!nl\!\!>$}
\def\btree{\emph{B-tree}}
\def\castle{\emph{Castelo}}
\title{Trabalho 0: \\ Concorrência em leitura/escrita}

\author{Raul H.C. Lopes}

\begin{document}

\maketitle
\section{Introdu\cao}
O obejtivo do trabalho consiste em estudar varia\coes\ sobre o problema
de \emph{readers-and-writers.} Para implementar este trabalho você
deverá dominar os conceitos de:
\begin{itemize}
  \item comunica\cao\ e sincroniza\cao\ via rendez-vous;
  \item comunica\cao\ e sincroniza\cao\ via monitores e objetos protegidos;
  \item concorrência no problema de leitua concorrente, escrita exclusiva;
  \item árvore B.

\end{itemize}

As  se\coes\ a seguir detalham o trabalho, que deve ser implementado em
Ada. O trabalho demandará dedica\cao\ sua em:
\begin{itemize}
  \item conceber um algoritmos para trabalhar com árvore que maximizem
o acesso concorrente;
  \item especificar os teste de consistência e desempenho dos mesmos.
\end{itemize}

Se você se sente desanimado por este trabalho ou pelo curso de \textbf{SO},
lembre-se que você está se formando em \textbf{Ciência da Computa\cao} e que
como tal sua habilidade principal deveria ser estudar algoritmos.
Eu divido as atividades de cientistas da computa\cao\ em três
grupos:
\begin{itemize}
  \item Investiga\cao\ de algoritmos e computabilidade.
  \item Engenharia de artefatos, quando o profissional usa blocos prontos para 
produzir 
utilidades do dia-a-dia, uma atividade nobre e útil.
 \item ``Engenharia'' de nomes, quando o ``profissional'' se dedica à atividade
de criar nomes novos para bois velhos, ou, como Dijkstra disse uma vez,
criar nomes para montros que não consegue enfrentar na esperança de que,
devidamente nomeado, o montro se submeta; os gregos faziam isso há 2.000 anos,
muitos livros de IA fazem isso até hoje.
\end{itemize}

Eu ofereço cursos direcionados para o primeiro time. 
Respeito o segundo grupo, mas aviso que, 
dado que este é um curso de \textbf{Ciência da Computa\cao}, investiga\cao\
de algoritmos é o preço a pagar pelo título que adquirirão.


Leia a última
se\cao\ deste texto sobre as regras de execu\cao\ e prazos de entrega do
trabalho. A próxima se\cao\ descreve o tabalho.

\section{O tabalho}
\label{pratico}
Implemente ao menos os seguintes algoritmos para acesso concorrente
a uma árvore B:
\begin{itemize}
  \item pesquisa de um item;
 \item inser\cao\ de novo item;
  \item exclusão de item;
  \item lista de  itens em ordem crescente.
\end{itemize}


Use uma das variantes de árvore B apresentadas em \cite{dek:taocp:iii}, que
contém dicas excelentes sobre otimiza\cao\ de espaço e desempenho. Mas,
note que os algoritmos ali apresentados são seqüenciais.

\subsection{Os tipos de arquivos a indexar}

Sua árvore indexará arquivos estruturados em registros, cada um composto
de strings separados pelo caracter\ ':' (dois pontos). Arquivo indexado e 
índice residirão em disco.

\subsection{Os programas a implementar}
Implemente no mínimo:
\begin{itemize}
  \item Pacote para acesso concorrente a árvore B 
que use tasks e rendez-vous;
  \item Programa interativo para teste do pacote acima;
  \item  Pacote para acesso concorrente a árvore B 
que use tasks e objetos protegidos;
  \item Programa interativo para teste do pacote que usa objetos protegidos.
\end{itemize}

Os programas interativos terão as seguintes características:
\begin{itemize}
  \ibf{Linha de commando:} com dois argumentos: o nome do arquivo a indexar
e o nome do índice a gerar;
  \ibf{\stdin:} lotes de opera\coes. Um lote de opera\coes\ é uma \sqn\ 
não vazia de linhas terminada por asterisco ($*$). Cada lote define um
conjunto de \sqn s de opera\coes\ que devem ser processados concorrentemente. 
Cada \sqn\ de opera\coes\ é apresentada em uma linha de \stdin.
Repetindo:
\begin{itemize}
  \item lotes são separados por asterisco ($*$): o fim de um lote é marcado
por uma linha contendo apenas asterisco seguido de \emph{newline};
  \item lotes são processados concorrentemente;
  \item lotes são compostos por \sqn s de opera\coes;
  \item cada \sqn\ de opera\coes\ é terminado por \emph{newline} 
(uma \sqn\ por linha
de \stdin);
  \item as opera\coes\ de uma  \sqn\ são processadas seqüencialmente (mas,
concorrentemente com as opera\coes\ das outras \sqn s do mesmo lote;)
  \item o processamento de novo lote só começa depois que o
lote anterior foi inteiramente processado.
  \item Uma \sqn\ de opera\coes\ contém opera\coes\ separadas por asterisco. 
  \item Uma
opera\cao\ pertence a um dos seguintes tipos:

\begin{trivlist}
  \item \emph{S:\K}

Encontre registro com chave \emph{\K}. Seu programa deverá produzir
no output:
\begin{itemize}
\item caso encontre a chave no índice:

  \begin{verbatim}
    S:<key>:<reg><nl>
  \end{verbatim}


\item caso não encontre a chave no índice:

  \begin{verbatim}
    S:<key>:<nl>
  \end{verbatim}

\end{itemize}

onde \K\ é a chave procurada, \R\ é seu registro no arquivo, \NL\ é
\emph{newline}.
  \item \emph{D:\K}

Exclua chave \K\ do índice. 

Seu programa não produzirá no output.


  \item \emph{I:key:reg}
   

Adicione chave \emph{\K} ao índice e registro \emph{\R} ao arquivo 
de dados.

Seu programa não produzirá output.

  \item \emph{L:\K}

Lista em ordem crescente, para  todas as chaves maiores do que \emph{\K},
a chave e o registro associado. Os pare chave e registro serão listados
no \stdout como:

\begin{verbatim}
  <key>:<reg><nl>
\end{verbatim}
\end{trivlist}
\end{itemize}
\end{itemize}

\subsection{Otimizando...}

Seu programa poderá otimizar:
\begin{itemize}
  \item \emph{throughput};
  \item \emph{turnaround time};
  \item \emph{response time.}
\end{itemize}

\subsection{Testes}

Especifique testes que validem seu programa em termos de ausência de erros
e desempenho. Implemente programas  que executem os seus testes e
coletem  os  resultados.

 
\subsection{O que entregar}
O seu trabalho consistirá em um arquivo(s) \LaTeX\ que conterá(ão) e 
documentará(ão):
 
\begin{itemize}
  \item o fonte de cada programa/pacote;
  \item a especifica\cao\ completa de todos os testes usados para testar
a consistência de 
seus programas, incluindo programas auxiliares (o uso de ferramentas 
para auxílio à automatiza\cao\ de teste será valorizado;)
  \item os resultados dos testes de consistência;
  \item especifica\cao\ dos testes de desempenho e resultados obtidos.
\end{itemize}

Você deverá entregar um \emph{tarball} contendo \emph{makefile} e fontes
do \LaTeX.


\section{Regras para execu\cao\ do trabalho}
O trabalho substitui parte do peso das provas, logo valem as seguintes
observa\coes:

\begin{itemize} 
\item Este trabalho poderá ser executado em grupos de até 2 alunos. No entanto,
valem as seguintes observa\coes:
\begin{itemize}
  \item Os próximos tabalhos dependem deste;
  \item Se durante a execu\cao\ deste trabalho ou do próximo ficar
claro que um dos elementos do grupo não trabalhou (famoso parasita
no vácuo do bobo), eu anulo o trabalho do grupo.
\end{itemize}

Moral da história: se seu colega de grupo se candidatar a parasita no seu
vácuo (ou em outra posi\cao\ mais delicada e incômoda), afaste-o do grupo e eu
terei prazer em exterminá-lo.

\item Trabalhos individuais valerão mais: terão peso $1.4$ na nota final, 
reduzindo o peso da médias das provas em $1.4$.

\item Você pode trocar 
idéias
com colegas, mas cuidado com o nível de troca. Plágio neste curso é
considerado falta gravíssima: $d>1$ plágios anulam $2^d$ trabalhos/provas.

\item O trabalho é seu e não do professor. Eu darei referências e dicas, mas
cabe a você desenvolver algoritmos, implementar programas, definir casos
de teste, suar, apanhar, sofrer...
\end{itemize}

\subsection{Linguagem de programa\cao}
Os pacotes de árvore B concorrente deverão ser implementados em Ada.


\subsection{O produto}
O produto a ser entregue consiste em documento \LaTeX\ de onde será possível
extrair todos os fontes necessários para compilar os programas e executar
os testes. O seu documento deverá conter:

\begin{itemize}
  \item descri\cao\ dos algoritmos de cada programa, com referências para 
as fontes dos mesmos;
 \item fontes dos  programas;
 \item especifica\coes\ de testes, bem como suas implementa\coes\ e resultados.
 \item especifica\coes\ de testes de desempenho, bem como suas implementa\coes\
e resultados obtidos;
 \item compara\coes\ entre resultados.
\end{itemize}

Você poderá apresentar sua documenta\cao\ distribuída por vários documentos
\LaTeX. Mas, garanta que as referências cruzadas entre documentos
estão corretas e aprenda a usar o pacote \emph{hyperref} do \LaTeX\ para
criar links entre documentos. Aliás, se seu Linux/FreeBSD tiver 
o pacote \emph{teTeX-doc} instalado, você poderá ver 
documenta\cao\ sobre os pacotes
\LaTeX\ disponíveis na sua instala\cao\ em:
 
 \centerline{\bf /usr/share/texmf/doc/index.html}
 
Qualidade de documento (que contribui para a nota final), inclui o uso
competente do \LaTeX\ para gerar, por exemplo: referências cruzadas,
referências bibliográficas (use \emph{bibtex}), equa\coes\ e tabelas 
decentemente formatadas. Por exemplo, índice remissivo de símbolos
principais dos programas é extremamente bem-vindo. O documento ideal
deveria ter a cara do \TeX book \cite{dek:textheprogram}. 
 

\subsection{Testes}

É bem-vindo e recomendado o uso de ferramentas de auxílio a teste automático
como: \emph{aunit}, \emph{expect},
\emph{dejagnu}, etc.

\textbf{Im\-portante:} testes bem especificados são baseados
em condi\coes\ de corre\cao\ formal de algoritmos: testes de loops, por 
exemplo, garantem progresso, término, segurança (propriedade invariante.)
Em resumo, valida\cao\ por teste nao elimina a necessidade de conhecer os 
fundamentos de prova formal de corre\cao\ de programas. A avalia\cao\ da 
qualidade dos seus testes levará isso em conta.


\subsection{Arquivo submetido}
\label{arquivo}
Você submeterá um aquivo de nome \\
\centerline{\bf tp0.tar.gz} \\

Eu usarei os seguintes comandos para obter seus programas compilados e
seu documento em formato \emph{PDF}:

\begin{verbatim}

     > gzip -dc tp0.tar.gz | tar -xf -
     > make pdf
     > make compile
     > make consist
     > make perform

\end{verbatim}

a \sqn\ acima gerará ao menos:
\begin{itemize}
  \item programa de nome

\centerline{\bf rvbtree}

que testará o pacote de \btree, usando rendez-vous.

\item programa de nome

\centerline{\bf pobtree}

que testará o pacote de \btree, usando objetos protegidos.

\item arquivo \emph{PDF} de nome

\centerline{\bf article.pdf}

que conterá o documento básico sobre o trabalho, contendo, possivelmente,
links para outros documentos.

\item arquivo com resultados de teste de consistência em formato a ser
especificado.

\item arquivo com resultados de teste de desmpenho em formato a ser 
especificado.

\end{itemize}



\subsection{Data de entrega}
O prazo final para entrega do trabalho será definido em acordo com a turma.
Em princípio, proponho 14/02/2003. É importante que as seguintes restri\coes\
sejam obedecidas:
\begin{itemize}
  \item Haverá 3 trabalhos práticos que poderão ser feitos em grupo, e um 
trabalho individual. Além disso, o último trabalho só poderá ser feito
por quem fizer o segundo. 
  \item O último trabalho deve ser entregue ao final da última semana de aula.
  \item entre a entrega de cada trabalho deverão transcorrer, ao menos, 10
dias.
\end{itemize}

Importante: são 4 trabalhos e talvez isso pareça carga excessiva. Mas, ninguém
é obrigado a fazer qualquer um deles.

\subsection{Novos detalhamentos}
Fique atento à minha página para: novos detalhes sobre os trabalhos e dicas
sobre o uso de ferramentas úteis, como: \LaTeX, ferramentas de teste,
\emph{make}, programas para extra\cao\ automática de fontes de programas
contidos em documentos \LaTeX.

 
\section{A atribui\cao\ de nota}

Cada pacote implementado (juntamente com seu programa de teste) poderá 
receber até $4.6$ pontos, independentemente de desempenho. Além disso,
o trabalho poderá ganhar $1.0$ por ausência total de erros e $0.4$ por
melhor desempenho geral. Total: $10.6$ pontos em $10$!


\subsection{Nota básica por pacote}
A nota básica por pacote atribuirá  pontos de acordo com
a tabela \ref{basica}. 

\begin{table}
  \begin{tabular}{|l|l|}\hline
    Verifica\cao\ de consistência & $1.8$ \\
    Verifica\cao\ de desempenho & $0.6$ \\
    Documenta\cao\ & $0.2$ \\
    Qualidade de pacote & $0.4$ \\
    Desempenho em concorrência & $1.6$ \\ \hline
  \end{tabular}
\vspace*{0.2cm}

\caption{Itens básicos por pacote}\label{basica}
\end{table}

Detalhes dos itens avaliados seguem:
\begin{itemize}
  \ibf{Verifica\cao\ de consistência:} Levará em conta qualidade dos testes
especificados para dete\cao\ de erros. Serão valorizados baseados em 
condi\coes\ de corre\cao\ dos algoritmos. A especifica\cao\ deverá conter:
\begin{itemize}
  \item o teste realizado e sua justificativa;
  \item o resultado esperado;
  \item resultado obtido.
\end{itemize}

  \ibf{Verifica\cao\ de desempenho:} Cada trabalho deve apresentar um conjunto 
de testes verificando o desempenho do mesmo em diferentes circunstâncias.

  \ibf{Documenta\cao:} Este item, embora tendo pouco peso aparente, um 
grande peso implícito. Fatos:
\begin{itemize}
  \item Só serão corrgidos algoritmos e  programas que estejam documentados.
Se o aluno usar um algoritmo revolucionário e não apontar claramente para isso,
poderá nem ter o trabalho corrigido.
  \item Testes não especificados serão considerados como nulos.
\end{itemize}

Além disso, a documenta\cao\ deve providenciar acesso fácil a instru\coes\ de
uso dos programas e todas as suas características importantes.

  \ibf{Qualidade do pacote:} Qualidade do pacote como implementa\cao\ de um 
ADT.
  \ibf{Desempenho em concorrência:}
Cada pacote participará de competi\cao\ para avalia\cao\ de desempenho
em concorrência em quatro classes:
\begin{itemize}
 \ibf{best throughtput;}
 \ibf{best turnaround time;}
 \ibf{best response time;}
 \ibf{variance in response time.}
\end{itemize}
Cada classe avaliará o pacote nos itens:
\begin{itemize}
  \item Busca concorrente;
  \item Busca e inser\cao\ concorrentes;
  \item Busca e exclusão concorrentes;
  \item Lista concorrente de todos os ítens. 
\end{itemize}
Em cada item avalidado (quatro itens vezes quatro classes dando 16 itens),
o vencedor ganha $0.1$.
\end{itemize}

\subsection{Itens adicionais}
Pontos poderão ser adicionados ou retirados de acordo com a tabela \ref{extra}.

\begin{table}
  \begin{tabular}{|l|l|}\hline
    Consistência geral & $1.0$ \\
    Best hacker prize & $0.4$ \\
    Especifica\cao\ inconsistente & $-1.0$ cada \\ \hline
  \end{tabular}
\vspace*{0.2cm}
\caption{Itens adicionais de pontua\cao}\label{extra}
\end{table}

Esses itens estão detalhados a seguir:
\begin{itemize}
  \ibf{Consistência geral:} Todo trabalho que contiver os dois pacotes
implementados e respectivos programas de teste recebe $1.0$ de bônus.
No entanto, cada erro detectado descontará $0.1$ desse bônus.
  \ibf{Best hacker prize:} O vencedor de todas a classes de ganha $0.4$.
  \ibf{Especifica\cao\ inconsistente:} cada caso de teste especificado na
documenta\cao\ que apresente resultado obtido nos testes do \castle\ diferentes
do que estiver contido na documenta\cao\ retira $1.0$ da nota final do 
trabalho. Moral da história: coloca na documenta\cao\ só o que você testou.

\end{itemize}


\subsection{Crime e puni\cao}
Serão anulados:
\begin{itemize}
  \item trabalhos enquadrados como plágios, com con\sqn s graves para outros
trabalhos porque $d>1$ plágios ao longo semestre anulam $2^d$ trabalhos;
  \item trabalhos em grupo em que um dos componentes do grupo seja 
enquadrado como parasita no vácuo;
  \item trabalhos que apresentem qualquer erro no processo de descompactação,
compilaçao, ou geração de documentos: siga estritamente as regras da se\cao\
\ref{arquivo}. 
\end{itemize}



\bibliography{abbrev,analysis,formal,algorithms,program,string}

\bibliographystyle{amsplain}


\end{document}

