\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}

\setlength{\parskip}{0.3cm}
\input{epsf}
\begin{document}
{\footnotesize
\hfill
{\sc Carlos E. Ferreira
}

\hfill
cef@ime.usp.br

\vspace{-0.3cm}
}

\begin{center}
{\large MAC 323 -- Estruturas de Dados  -- 1998}

Recuperação -- Entrega: {\bf 11 de agosto de 1998}

\vspace{0.3cm}

Sistema de Multiprocessamento 
\end{center}

\textbf{
A nota de recuperação da disciplina MAC 323 -- Estruturas de Dados será dada
através da entrega de um projeto sobre o funcionamento de um sistema de
computação de multiprocessamento. O aluno deverá marcar comigo 
por e-mail uma data de apresentação do projeto, na qual darei a nota ao
mesmo. A média final da disciplina será dada pela média ponderada entre a nota
final do semestre (peso 1) e a nota dada a esta apresentação (peso 2). 
}

O objetivo desse projeto \'e simular o funcionamento de um sistema de 
computa\c c\~ao com multiprocessamento. Com este projeto teremos coberto 
uma (pequena) parte dos problemas 
enfrentados quando desejamos implementar um sistema de computa\c c\~ao real, 
e teremos aplicado algumas das estruturas de dados vistas no curso para
resolver os problemas envolvidos. 

\section{Filas das classes} 

Cada processo
executado no computador pertence a uma determinada classe (1 ou 2). 
Cada classe tem permiss\~oes diferentes com rela\c c\~ao ao
limite m\'aximo de tempo de execu\c c\~ao na CPU (em UT: unidades de tempo), 
limite m\'aximo de uso de mem\'oria e 
n\'umero m\'aximo de linhas a serem impressas. Essas restri\c c\~oes 
est\~ao descritas na tabela a seguir: 

\begin{center}
\begin{tabular}{|l|r|r|r|}
\hline
Classe & CPU (UT) & Mem\'oria (MB) & Linhas \\
\hline
1 & 10 &  2 & 500 \\
\hline 
2 & 40 & 16 & 10000 \\
\hline
\end{tabular}
\end{center}

Quando um processo inicia sua execução, ele \'e colocado na fila de sua classe, e
espera l\'a at\'e que haja uma vaga na fila da CPU. Para efeito dessa 
simula\c c\~ao voc\^e deve ``gerar'' aleatoriamente um novo processo a cada 
UT, com probabilidade 70\% que seja de classe 1 e 30\% de classe 2. 
Ao ``criar'' o processo, gere aleatoriamente o tempo de 
CPU, a mem\'oria utilizada e o n\'umero de linhas que esse 
processo ir\'a imprimir (dentro dos limites de sua classe). 

As regras para um processo sair da fila de sua classe e ir para a fila da CPU
s\~ao as seguintes. A fila da CPU comporta no máximo 10 processos. 
Um processo da
classe 1 tem sempre prioridade. Um processo da classe 2 s\'o 
entra na fila da CPU se a fila da classe 1 estiver vazia ou os \'ultimos
4 processos que entraram na fila foram da classe 1. 

\section{Fila da CPU}

Cada processo pode permanecer apenas um determinado tempo rodando na CPU. 
Quando esse tempo \'e ultrapassado, ele \'e suspenso e retorna para a 
\'ultima posi\c c\~ao da fila da CPU. Com isso, um processo com grande 
tempo de execu\c c\~ao necessita de v\'arios ciclos da CPU para ser executado.

A fila da CPU comporta no m\'aximo 
10 processos. O ciclo da CPU ser\'a de 3 UT. A fila da CPU dever\'a 
ser implementada como uma lista circular duplamente ligada com cabe\c ca 
de lista, como descrita em aula.

\section{Fila das impressoras}


O modelo a ser simulado segue o esquema de fila \'unica para as impressoras
(que s\~ao 5), cada impressora com velocidade de 10 linhas por UT. Quando 
uma impressora fica dispon\'\i vel, o primeiro processo da fila passar\'a \`a
impress\~ao, a menos que algum processo j\'a esteja no sistema h\'a mais
de 100 UT.  

Os processos na fila da impressora estar\~ao em duas filas ao mesmo tempo: uma
por ordem de ingresso na fila e outra pelo tempo de perman\^encia no 
sistema. Estas filas devem ser implementadas de modo a permitir que 
inser\c c\~oes em ambas as filas e remo\c c\~ao do primeiro elemento 
de cada fila possam ser feitas em tempo $O(\log n)$ 
(utilize fila de prioridade, como no EP do aeroporto). 


\section{Gerenciamento de memória}

Em um sistema operacional o gerenciamento da mem\'oria \'e um dos aspectos
mais fundamentais, e organiz\'a-lo de forma eficiente \'e muito importante
para o desempenho do sistema. O objetivo aqui {\bf n\~ao} \'e mostrar 
a estrutura utilizada nos sistemas mais modernos (e, de fato, a estrutura
mostrada n\~ao \'e a mais utilizada, como voc\^es podem 
ver em livros de Sistemas Operacionais \cite{T}). Bons algoritmos de gerenciamento de mem\'oria s\~ao tema de 
pesquisa interessante, envolvendo problemas como partilhamento da mem\'oria, 
coleta de lixo, etc. (veja o cap\'\i tulo 12 do livro \cite{AHU}). 

A seguir descrevemos o esquema de gerenciamento de mem\'oria a ser 
implementado.

O sistema ser\'a de multiprocessamento, ou seja, diversos processos 
compartilhar\~ao a mem\'oria. No início do processamento toda a memória (256MB)
está disponível. O sistema n\~ao \'e capaz de manipular 
peda\c cos n\~ao cont\'\i guos de mem\'oria. Assim, se um processo 
deseja uma quantidade de mem\'oria que n\~ao est\'a dispon\'\i vel no 
momento, 
fica suspenso (volta para o fim da fila da CPU) at\'e que seja 
poss\'\i vel alocar uma \'area daquele 
tamanho. Os tamanhos dos blocos requisitados podem variar (s\~ao 
estabelecidos pelos processos -- gerados aleatoriamente). Assim, na fila
da CPU teremos processos que est\~ao executando (e portanto ocupando uma
parte da mem\'oria) e outros que est\~ao suspensos at\'e que haja mem\'oria
suficiente para executar. 

Os peda\c cos dispon\'\i veis de mem\'oria estar\~ao armazenados em 
uma \'arvore 2-3 (uma B-\'arvore em que armazenamos no m\'aximo 2 
elementos por n\'o), em que a chave ser\'a o tamanho em bytes do 
segmento (no caso em que dois segmentos t\^em o mesmo tamanho, use 
o menor endere\c co de in\'\i cio do segmento para desempate). 
Assim, cada n\'o da \'arvore 2-3 ter\'a o seguinte formato: 

\vspace{0.5cm}
\[
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
$P_1$ & $K_1$ & $[I_1, F_1]$ & $P_2$ & $K_2$ & $[I_2, F_2]$ & $P_3$ \\
\hline
\end{tabular}
\]

\vspace{0.5cm}

Observe o exemplo abaixo.
$$ \epsffile{pr4f1.eps} $$

Quando requisitamos uma por\c c\~ao de mem\'oria, que \'e poss\'\i vel 
de se satisfazer no momento, uma remo\c c\~ao e, em 
geral, uma inser\c c\~ao ser\~ao necess\'arias. Veja o exemplo a seguir, em 
que alocamos o bloco requerido do menor bloco dispon\'\i vel maior que 
o pedido feito. 

Ex.: Usando a \'arvore do exemplo anterior, um processo requisita
um bloco de 53 kbytes. 

$$ \epsffile{pr4f2.eps} $$

Quando um bloco \'e devolvido, em geral \'e muito ineficiente tentar 
junt\'a-lo com blocos vizinhos, pois isso acarreta remo\c c\~oes 
e inser\c c\~oes na \'arvore. Assim, faremos esse rearranjo apenas quando 
tivermos algum pedido que n\~ao p\^ode ser satisfeito. 

Seu projeto pode implementar outras estrat\'egias para 
escolha do bloco de que alocar a mem\'oria requisitada, e pode utilizar 
a estrutura que desejar para facilitar o rearranjo de mem\'oria. 


\section{Saída do programa}

A saída do seu programa deverá ser clara. A cada instante deverá ser fácil ver
quantos processos estão em cada uma das filas, quais processos estão ocupando a
CPU e as impressoras, qual o estado da memória, etc. 

Ao finalizar a execução de um processo, as 
seguintes informa\c c\~oes deverão ser impressas: 
\begin{itemize}
\item[(a)] caracter\'\i sticas do processo (classe, tempo de CPU, n\'umero de linhas); 
\item[(b)] tempo total de perman\^encia no sistema; 
\item[(c)] tempo gasto nas filas; 
\item[(d)] raz\~ao entre o tempo \'util (tempo de execu\c c\~ao na CPU) e tempo total de perman\^encia no sistema;
\end{itemize}
Ao 
t\'ermino da execu\c c\~ao, imprima o n\'umero total de processos executados, 
assim como m\'edia dos itens (b), (c) e (d) em cada classe. E  execução deve
continuar até que uma tecla ``Pare'' seja acionada. 

Lembre-se que a sa\'\i da e documenta\c c\~ao do seu programa tamb\'em ser\~ao
avaliadas para efeito de nota. 

\begin{thebibliography}{9}
\bibitem{AHU} A.V. Aho, J.E. Hopcroft, J.D. Ullman, {\em Data Structures and 
Algorithms}, Addison-Wesley (1985). 

\bibitem{T} Tanenbaum, {\em Operating Systems: Design and Implementation},
Prentice-Hall, Englewood Cliffs (1987). 
 
\end{thebibliography}
\end{document}