\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}
\input{epsf}

\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 5710 -- Estruturas de Dados}
\end{center}

\begin{center}
{\bf Primeiro semestre de 1999}
\end{center}

\begin{center}
{\large  Exercício-Programa Substitutivo -- Entrega: {\bf 1 de julho de 1999}}

\vspace{0.3cm}
Gerencimento de memória 
\end{center}

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. Nesse exerc\'\i cio--programa vamos implementar
um sistema de gerenciamento de mem\'oria. O objetivo {\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 v\~ao aprender no ano 
que vem). 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. 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 at\'e que seja poss\'\i vel alocar uma \'area daquele 
tamanho. Os tamanhos dos blocos requisitados podem variar (s\~ao 
estabelecidos pelos processos). 

A entrada do seu programa dever\'a ser um arquivo com o seguinte formato. Na
primeira linha é dada a quantidade inicial de bytes 
dispon\'\i veis. A seguir, vêm diversas linhas, e em cada uma delas, um pedido
da seguinte forma: 

\begin{verbatim}
R n
D n
\end{verbatim}
Se o pedido foi um 'R' o processo est\'a alocando os $n$ Kbytes (onde $n$ é um
número inteiro), se for um 'D', ele est\'a devolvendo. 

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 Kbytes (ou MBytes) 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$ & $B_1$ & $P_2$ & $K_2$ & $B_2$ & $P_3$ \\
\hline
\end{tabular}
\]

\begin{itemize}
\item $P_1, P_2$ e $P_3$ são ponteiros para os nós filhos; 
\item $K_1$ e $K_2$ são as chaves deste nó (tamanhos de segmentos contíguos de
memória disponíveis); 
\item $B_1$ e $B_2$ são as posições de memória em que estes segmentos iniciam. 
\end{itemize}

\vspace{0.5cm}

Observe o exemplo abaixo.
$$ \epsffile{epsubf1.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, pedimos um bloco de 53 kbytes. 

$$ \epsffile{epsubf2.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 exerc\'\i cio--programa 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. Voc\^e 
dever\'a fazer um pequeno relat\'orio mostrando o desempenho do seu sistema
para os testes que voc\^e fez (por exemplo, quantas vezes foi necess\'ario 
fazer o rearranjo, quantos processos ficaram suspensos esperando mem\'oria, 
etc). Durante a execu\c c\~ao emita mensagens informando ao usu\'ario 
qual o estado do gerenciador. 

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