36 lines
2.7 KiB
TeX
36 lines
2.7 KiB
TeX
O problema consiste em simular um gerenciador de cache e determinar o número mínimo de falhas de página. Como a sequência completa de requisições é conhecida previamente, podemos utilizar uma estratégia gulosa para resolver o problema.
|
|
|
|
\subsection*{Representação do estado}
|
|
|
|
\begin{itemize}
|
|
\item A memória principal (cache) é representada por um conjunto (\textit{hash set}), que armazena os identificadores das páginas atualmente carregadas, permitindo consultas em tempo constante.
|
|
\item O histórico futuro de cada página é mapeado em vetores, registrando todos os índices (momentos no tempo) em que cada página será requisitada.
|
|
\item Um vetor de ponteiros auxiliares acompanha qual a próxima ocorrência futura correspondente para cada página.
|
|
\end{itemize}
|
|
|
|
\subsection*{Estratégia de solução usando Algoritmo Guloso}
|
|
|
|
A estratégia ótima dita que, quando a cache estiver cheia e ocorrer uma falha, a página a ser substituída deve ser aquela que demorará mais tempo para ser referenciada novamente no futuro.
|
|
|
|
\begin{enumerate}
|
|
\item Leia a capacidade da cache ($k$) e o tamanho da sequência de requisições ($v$).
|
|
\item Faça um pré-processamento da sequência de páginas:
|
|
\begin{itemize}
|
|
\item Armazene a sequência original em um vetor.
|
|
\item Para cada página lida, adicione o índice atual à sua respectiva lista de referências futuras.
|
|
\end{itemize}
|
|
\item Inicialize a cache vazia, o controle de progresso das referências futuras e o contador de falhas (\textit{misses}).
|
|
\item Percorra a sequência de requisições passo a passo:
|
|
\begin{itemize}
|
|
\item Se a página atual \textbf{não} estiver na cache, ocorreu uma falha de página. Incremente o contador de \textit{misses}.
|
|
\item Se a cache já estiver cheia (tamanho igual a $k$) no momento da falha, é necessário eleger uma página residente para remoção:
|
|
\begin{itemize}
|
|
\item Inspecione todas as páginas atualmente na cache.
|
|
\item Se alguma página não possuir mais requisições futuras, ela é a candidata ideal e deve ser escolhida para remoção imediata.
|
|
\item Caso contrário, compare a próxima requisição de todas e encontre aquela que vai demorar mais tempo para aparecer de novo (índice mais distante no futuro), removendo-a.
|
|
\end{itemize}
|
|
\item Insira a nova página na cache.
|
|
\item Ao final de cada iteração, independentemente de ter ocorrido acerto ou falha, avance o ponteiro de ocorrências da página que acabou de ser processada.
|
|
\end{itemize}
|
|
\item Ao término da simulação, imprima o total de falhas contabilizadas.
|
|
\end{enumerate} |