\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}}
\def\AIO{\emph{assyncio}}
\def\clone{\textbf{\_clone}}
\title{Trabalho 1: \\ Um pacote de threads}

\author{Raul H.C. Lopes}

\begin{document}
\maketitle
\section{Descrição}

Implemente um pacote de threads para o Linux. Seu pacote deverá
contemplar políticas de escalonamento de CPU e sincronização de processos.
Use o pacote \emph{QuickThreads}, fornecido no mesmo \emph{tarball} que 
este documento. Não será permitido o uso de nenhum procedimento da 
\emph{pthreads} ou de qualquer outra \emph{library} que não seja \emph{QuickThreads}.

\section{Roteiro}
\begin{enumerate}
\item Leia os documentos \emph{README} e \emph{doc/qt.ps} do pacote \emph{QuickThreads}.
\item Veja exemplo de um \emph{thread scheduler} contido no mesmo
pacote (em \emph{stp.c}) e exemplo de uso em \emph{meas.c}.
\item Proponha uma política de escalonamento multi-nível que implemente
ao menos \emph{FCFS}, \emph{SJB} e \emph{RR}. Sua política multi-nível
deverá evitar \emph{starvation} e deverá permitir o escalonamento de processos
do seu \emph{kernel} em tempo real.
 
\item Estabeleça um conjunto de primitivas de sincronização para seu pacote,
baseadas em comunica\cao\ entre processos.

 
\item Implemente os exemplos definidos na se\cao\ \ref{testing} para
validar o seu trabalho.

\end{enumerate}

\subsection{O que entregar}
O seu trabalho consistirá em um artigo escrito em  \LaTeX\ 
(não é \emph{noweb}), fontes do escalonador, dos programas de valida\cao\ e
do \emph{test driver}, além de \emph{Makefile}.

\section{Testes para valida\cao}
\label{testing}
A valida\cao\ do seu escalonador será realizada através de um conjunto de
testes sobre problemas clássicos de sincroniza\cao\ de processos. Você
escolherá dentre três tipos de testes para validar seu pacote de threads.

\subsection{Obrigatório}
Todos os pacotes deverão implementar input/output padrão (equivalente de
\emph{stdio}), usando um processo concorrente com o escalonador
para realizar I/O assíncrono. Siga o roteiro:


\begin{enumerate}
\item 
Use a primitiva \clone\ para criar um processo, denominado \AIO\
que compartilhe
memória com seu escalonador. 
\item Todo input/output de threads do seu pacote deverá realizado através de
\AIO.
\item Invente um mecanismo de sincroniza\cao\ e comunica\cao\ entre os
processos de seu escalonador e o processo \AIO.
\end{enumerate}

Todos os pacotes implementarão seu próprio pacote de memória dinâmica,
substituindo a dupla \emph{malloc/free}. Implemente ao menos:
\begin{itemize}
  \item um processo no pacote, que será escalonado em tempo real, e que
alocará ao início um grande bloco de memória do Linux;
  \item esse processo aceitará pedidos de aloca\cao\ ou libera\cao\ de memória
através de primitivas \emph{request(n)} (pedido de $n$ bytes de memória),
e \emph{release} (pedido de libera\cao\ de bloco;
  \item este processo será escalonado em tempo real, sendo dirigido por evento;
  \item ele poderá implementar política SJN 
(atende primeiro quem requisita menos) ou FCFS, ou os dois: compara\coes\ 
serão valorizadas.
  \item use algoritmos como \emph{best fit} para implementar a
aloca\cao\ de memória.
\end{itemize}

\subsection{Opcional nível 0}
Implemente uma árvore B concorrente em disco (como especificada no TP0) 
para validar seu pacote.

\subsubsection{Mínimo}
As seguintes restri\coes\ devem ser seguidas:
\begin{itemize}
  \item Todo input/output para disco deve ser mapeada em memória, usando 
algoritmos de pagina\cao\ em memória virtual.
 \item Um processo (criado via \clone) será responsável pela
realiza\cao\ de acesso a disco.
 \item Um processo de tempo real do seu escalonador resolverá eventuais 
problemas de \emph{page-fault}.
\end{itemize}

\subsubsection{Peso}

Esta alternativa tem peso $3$ na avalia\cao.

\subsubsection{Férias}

Mesmo que você nao implemente esta alternativa agora, você poderá fazê-lo
até o dia 30/04 e o resultado poderá ser usado para corrigir sua nota,
desde que você não tenha sido reprovado no período normal. IMPORTANTE:
só será realizada corre\cao\ de nota para quem tiver sido aprovado no
período normal.

\subsection{Opcional nível 1}
Implemente uma árvore B concorrente, armazenada em memória, como
especificada no TP0.

\subsubsection{Restri\coes}

A seguintes restri\coes\ devem ser seguidas:
\begin{itemize}
  \item Todo input/output padrão será realizado através de \AIO.
  \item A aloca\cao\ de memória dinâmica será realizada
pelo seu pacote de threads.
\end{itemize}

\subsubsection{Peso}
Esta alternativa tem peso dois na avalia\cao.

\subsection{Opcional nível 2}
Implemente programas para resolver os seguintes problemas:
\begin{enumerate}
  \ibf{Roller Coaster}: Existe um linha de ônibus com $C$ carros 
circulando, todos
realizando o mesmo trajeto e obedecendo às restri\coes:
\begin{itemize}
  \item todos os passageiros embarcam no mesmo ponto;
  \item um carro só sai do ponto se tiver $p$ passgeiros embarcados;
  \item cada passageiro é modelado por um processo que
eventualmente requisita entrada em um carro;
  \item cada carro é modelado por um processo que demora um tempo
randômico maior do que zero para dar uma volta completa na linha.
\end{itemize}

Escreva um program que simula a sincronaizacao de um número arbitrário
de carros e passageiros.

 \ibf{Jantar dos canibais}: Numa tribo de canibais todos comem do mesmo 
caldeirão, onde são cozinhados picadinhos de missionários metidos (ok...
todo missionário é metido!) Cada canibal vive em três estados: dorme,
caça missionários, come. Se um canibal encontra o caldeirão vazio (cada 
caldeirão serve $c$ por\coes), ele
acorda o cozinheiro, que vive em dois estados: dorme, cozinha. 
Implemente um simulador para essa vida tribal chata. Considere melhorar o 
padrão de vida tribo,
criando um bordel onde são admitidos no máximo $b$ canibais normais. Considere
também a existência de canibais tarados: cada um vale por dois normais. Admita
que com um bordel na área o cozinheiro também pode melhorar seu padrão de
vida. Lembre-se: você deve definir e implementar condi\coes\ de
exclusão mútua, \emph{liveness} e ausência de \emph{deadlock}, inclusive
no bordel. Ah! Quanto mais realístico, melhor.

 \ibf{Acesso concorrente a fila}: Dada uma lista encadeada de itens, as 
seguintes opera\coes\ são admissíveis: 
\begin{itemize}
  \ibf{insert}: insere item ao final da lista;
  \ibf{delete}: exclui item qualquer;
  \ibf{search}: procura item.
\end{itemize}

Implemente um processo que mantém um lista com essas opera\coes\ e que maximiza
o acesso concorrente a ela. Implemente simulador que teste esse pacote.

\end{enumerate}

\subsubsection{Restri\coes}

A seguintes restri\coes\ devem ser seguidas:
\begin{itemize}
  \item Todo input/output padrão será realizado através de \AIO.
\end{itemize}


\subsubsection{Peso}
Esta alternativa tem peso um na avalia\cao.

\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,
vale a velha regra: se durante a execu\cao\ deste trabalho ficar
claro que um dos elementos do grupo não trabalhou (famoso parasita
no vácuo do bobo), eu anulo o trabalho do grupo.

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 multiplicado por
$1.5$.


\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}
Você poderá usar \emph{C/C++} e, eventualmente, linguagens de script.



\section{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 tp1.tar.gz} \\

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

\begin{verbatim}

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

\end{verbatim}

\subsection{Entrega}
O prazo final para entrega do trabalho é 05/04/2003, 9 horas, via e-mail, 
que conterá:
\begin{itemize}
  \ibf{Subject}: OS
  \ibf{corpo da mensagem}: identific\cao\ dos autores;
  \ibf{attachment}: o arquivo \emph{tp1.tar.gz} 
\end{itemize}

Cuidado! Não erre. Não há tempo para novas submissões.
 

 



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

\bibliographystyle{amsplain}


\end{document}

