\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\\
Prova 0.0 \\ An Outcast of the Islands}

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

\begin{document}

\maketitle
\section{Introdu\cao}
Esta primeira parcial da prova $0$ avalia conceitos de comunica\cao\ de
processos e escalonamento de CPU.
A prova é individual. Você pode consultar as suas nostas de aula e seu
livro. Todas as questões têm o mesmo peso.

\section{As questões}

\begin{qst}
Assuma que existe uma estrutura de heap com as seguintes opera\coes:
\begin{itemize}
  \ibf{addcredit(heap\_t h, int pid, int c)}

Incrementa crédito de \emph{pid} de \emph{c}. Se \emph{pid} for igual
a $-1$ soma $c$ ao crédito de   todos os processos.

  \ibf{popfirst(heap\_t h)}

Retorna o processo com crédito mais elevado.

  \ibf{getfirst(heap\_t h, int *pid, int *c)}

Retorna \emph{pid} e crédito do processo com maior crédito em $h$.
\end{itemize}

Considere que:
\begin{itemize}
\item um escalonador dispõe como única estrutura de dados para escalonar
o processador um \emph{heap\_t} para armazenar 
processos em estado \emph{ready};
\item a cada processo (em estado \emph{run} ou \emph{ready}) está associado
um crédito que  pode periodicamente ser incrementado;
\item o escalonador é preemptivo.
\end{itemize}

\begin{enumerate}
  \item Assumindo que processos 
em \emph{ready} têm periodicamente seu crédito 
incrementado de $a$ e
um processo em \emph{run} tem seu crédito periodicamento incrementado $b$:
\begin{itemize}
  \item Que algoritmo de escalonamento você obtém se $a>b>0$? Prove.
  \item Que algoritmo de escalonamento você obtém se $a<b<0$? Prove.
\end{itemize}
\end{enumerate}

\end{qst}

\begin{qst}
Assuma que você vai implementar uma árvore B concorrente armazenada em disco
e que o acesso a disco é feito através de um servidor de nós 
que não compartilha
memória com processo algum e que oferece como únicas opera\coes\ 
para recupera\cao\ e escrita de nós:
\begin{itemize}
  \ibf{acquireNode}: dada identifica\cao\ de um nó, lê o nó do disco e
retorna-o, bloqueando o acesso a esse nó por $i$ unidades de tempo.
  \ibf{commitNode}: dada identifica\cao\ do nó, grava-o no disco.
\end{itemize}

\begin{enumerate}
  \item Proponha mecanismo para que processos possam tranferir e receber nós
do servidor.
  \item Mostre que é possível ter um algoritmo simples de contagem de
tempo e usar as opera\coes\ acima implementar uma
polítca \emph{Shortest Job First} na aquisi\cao\ de nós? Discuta qualidades
e desvantagens da mesma. Proponha melhorias ainda usando as mesmas opera\coes.
\end{enumerate}
\end{qst}


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

\bibliographystyle{amsplain}


\end{document}

