\documentclass[12pt]{amsart}
\usepackage[portuges]{babel}
\usepackage{boxedminipage}
\usepackage[latin1]{inputenc}
% uncomment next line to get pdf files with hyperlinks
%\usepackage[pdftex,bookmarks=true]{hyperref}
\input{defmath}
\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\acl{\textbf{ACL2}}
\newtheorem{qst}{Questão}
\title{Sistemas operacionais\\
The sound and the fury}

\author{Raul H.C. Lopes}
\date{13/03/2003}

\begin{document}

\maketitle
\section{Introdu\cao}
Esta prova tem a dura\cao\ de três horas. Ela deve ser resolvida 
individualmente, sendo admitidas consultas a material próprio.

A leitura da prova faz parte do processo de avalia\cao.

As questões têm todas o mesmo peso.


\section{As questões}

\subsection{Gerência de memória}

  Nesta se\cao, considere um sistema de computa\cao\ que possui 
espaço de  endereçamento por processo de $2^{32}$ bytes e que trabalha com
páginas $2^{12}$ bytes. Considere os seguintes dados do sistema:
\begin{itemize}
  \item Tempo de transferência de um bloco de $2^{12}$ bytes do disco
para memória é de $28 ms$.
  \item Acesso a memória: 133 Mb/s.
  \item Velocidade do processador: 200 milhões de instruções por segundo.
  \item Tempo de acesso a qualquer item que está na TLB é nulo.
\end{itemize}

\begin{qst}
  Assumindo que o sistema não use memória virtual, descreva a implementa\cao\
e compare o desempenho de um sistema de aloca\cao\ de memória que:

\begin{enumerate}
  \item não use pagina\cao.
  \item use pagina\cao\ com tabela de páginas direta.
  \item use pagina\cao\ com tabela de páginas invertida.
\end{enumerate}

Como o uso de \emph{TLB} e hash pode alterar o desempenho do seu sistema?

\end{qst}


\begin{qst}
  Assumindo que o sistema use memória virtual, escolha um algoritmo eficiente 
de \emph{page replacement} e identifique todos os casos possíveis que
um acesso ao espaço lógico do processo pode gerar, avalie o desempenho do seu 
sistema em cada caso e o tempo médio de acesso a memória obtido pelo processo.
\end{qst}

\subsection{Sincronização de processos}
\begin{qst}
  Proponha um algoritmo de exclusão mútua para $n$ processos que use como 
mecanismo básico de sincroniza\cao\ uma instru\cao\ atômica que troca
o valor de duas variáveis. Discute seu algoritmo em rela\cao\ a:
exclusão mútua, deadlock, liveness.

\end{qst}

\begin{qst}
  Prove que o algoritmo de Lamport, chamado \emph{bakery algorithm}, apresenta
as propriedades desejáveis de um algoritmo de exclusão mútua, mas pode
ser muito caro ou até inviável em termos de implementa\cao.
\end{qst}


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

\bibliographystyle{amsplain}


\end{document}

