5^{\underline{\mathbf{a}}} Questão: Considere a sequência de acessos com 3 frames: 4,2,4,2,5,4,4,1, 3, 4, 6, 7
(a) Calcule o número de page faults para os algoritmos: FIFO, LRU, Ótimo e LFU. (b) Compare os resultados obtidos. (c) Qual algoritmo apresentou melhor desempenho nesse cenário? Isso significa que ele sempre será o melhor? Justifique.
Passo 1
O que o exercício pede e os dados que temos.
Sequência de referências de páginas (peguei isso do enunciado): 4,2,4,2,5,4,4,1,3,4,6,7.
Número de frames disponível (memória física): 3.
Perguntas:
(a) Calcular o número de page faults para os algoritmos FIFO, LRU, Ótimo e LFU.
(b) Comparar os resultados obtidos.
(c) Dizer qual algoritmo apresentou melhor desempenho nesse cenário e discutir se isso significa que ele sempre será o melhor (justifique).
Observação: não foi dada regra de desempate no enunciado para LFU; vou usar o critério comum de desempate: quando há empate de frequência, desempato usando LRU (ou seja, entre os com menor frequência eu retiro o menos recentemente usado). Vou explicitar isso quando aplicar LFU.
Passo 2
Explicação do algoritmo FIFO e simulação passo a passo.
Conceito do FIFO: “First-In, First-Out”. Mantemos uma fila com a ordem de chegada das páginas aos frames. Quando ocorrer falta de página (page fault) e não houver frame livre, removemos a página que entrou primeiro (a mais antiga), e colocamos a nova no fim da fila. É simples: não olha uso futuro nem uso recente, só ordem de chegada.
Inicialmente todos os 3 frames estão vazios. Vou listar cada referência, o conteúdo dos frames depois do acesso e indicar se houve page fault (PF).
Referência \,1: não há frame livre. Ordem de chegada (fila) atual é: 4 entrou primeiro, depois 2, depois 5. FIFO remove 4. frames [1,\;2,\;5]. PF. (PFs = 4).
Referência \,4: FIFO remove o mais antigo restante que é 5. frames [1,\;3,\;4]. PF. (PFs = 6).
Referência \,6: remove o mais antigo restante que é 1. frames [6,\;3,\;4]. PF. (PFs = 7).
Referência \,7: remove o próximo mais antigo que é 3. frames [6,\;7,\;4]. PF. (PFs = 8).
Passo 3
Resultado final para FIFO.
Número total de page faults com FIFO: \,8.
Passo 4
Explicação do algoritmo LRU e simulação passo a passo.
Conceito do LRU: “Least Recently Used”. Ao precisar substituir, escolhe-se a página que foi usada há mais tempo (a menos recentemente usada). LRU tenta capturar localidade temporal: páginas recentemente usadas tendem a ser reutilizadas em breve.
Procedimento de simulação: manteremos para cada página o tempo (ou ordem) do último acesso e, em falta de páginas livres, removeremos a de menor tempo de uso (a menos recente).
Referência \,4: frames [4,\;-,\;-]. PF. Último uso 4:t_1. (PFs = 1).
Referência \,2: frames [4,\;2,\;-]. PF. Último uso 2:t_2. (PFs = 2).
Referência \,4: frames [4,\;2,\;-]. Hit. Atualiza último uso 4:t_3.
Referência \,2: frames [4,\;2,\;-]. Hit. Atualiza último uso 2:t_4.
Referência \,5: frames [4,\;2,\;5]. PF. Último uso 5:t_5. (PFs = 3).
Referência \,4: hit. Atualiza 4:t_6.
Referência \,4: hit. Atualiza 4:t_7.
Referência \,1: falta e não há frame livre. Últimos usos: 4:t_7, 2:t_4, 5:t_5. Menos recentemente usado é 2 (último uso em t_4). Substitui 2. frames [4,\;1,\;5]. PF. (PFs = 4).
Explicação do algoritmo Ótimo (Belady) e simulação.
Conceito do Ótimo: substitui, no momento de falta, a página cuja próxima referência no futuro está mais distante (ou que nunca mais será usada). É o menor número possível de page faults, mas requer conhecimento do futuro — por isso é apenas um ideal/limite inferior para algoritmos online.
Regras de desempate: se houver várias páginas que nunca mais serão usadas, podemos escolher qualquer uma; elas são equivalentes para o número total de faults no futuro imediato — porém vou escolher consistentemente uma delas quando necessário.
Simulação (olhando para o restante da sequência a cada passo):
\,4: frames [4,\;-,\;-]. PF. (PFs = 1).
\,2: frames [4,\;2,\;-]. PF. (PFs = 2).
\,4: hit.
\,2: hit.
\,5: frames [4,\;2,\;5]. PF. (PFs = 3).
\,4: hit.
\,4: hit.
\,1: falta. Olhando para o futuro (próximas referências são 3,4,6,7), verificamos: 4 reaparece em breve (no passo 10), 2 não reaparece, 5 não reaparece. Páginas com próxima ocorrência mais distante ou inexistente são 2 e 5; ambas nunca reaparecem, então evito 4 e substituo uma entre 2 ou 5. Escolho substituir 2. frames [4,\;1,\;5]. PF. (PFs = 4).
\,3: falta. Futuro restante 4,6,7. Dentre 4,1,5: 4 reaparece, 1 e 5 não reaparecem. Substituo uma que não reaparece; escolho 1. frames [4,\;3,\;5]. PF. (PFs = 5).
\,4: hit.
\,6: falta. Futuro restante 7. Dentre 4,3,5: nenhum reaparece depois do passo 11 (todos são não reutilizados). Substituo qualquer; escolho substituir 5. frames [4,\;3,\;6]. PF. (PFs = 6).
\,7: falta. Substituo uma das existentes; PF. (PFs = 7).
Passo 7
Resultado final para Ótimo.
Número total de page faults com o algoritmo Ótimo: \,7.
Passo 8
Explicação do algoritmo LFU e simulação passo a passo.
Conceito do LFU: “Least Frequently Used”. Ao substituir, remove-se a página com menor contador de acessos (frequência). Contagens são acumuladas ao longo do processo (normalmente desde o início); páginas com mais referências são preferidas a permanecer. Problema conhecido: pode punir páginas populares no passado que não sejam mais usadas (stale) — implementação pode usar janelamento, envelhecimento, etc., mas aqui usamos a versão simples.
Critério de desempate: quando duas ou mais páginas tiverem a menor frequência, desempatarei usando LRU (retirar a menos recentemente usada entre os de menor frequência).
Simulação: mantenho contadores de frequência f(\cdot).
Número total de page faults com LFU (com desempate LRU): \,7.
Passo 10
Comparação dos resultados (resumo final).
FIFO: \,8 page faults.
LRU: \,7 page faults.
Ótimo: \,7 page faults.
LFU: \,7 page faults.
Observação de comparação: LRU, Ótimo e LFU empataram com \,7 faults; FIFO teve desempenho pior (mais faults).
Passo 11
Qual foi o melhor e se sempre será o melhor — interpretação e justificativa.
Melhor desempenho neste cenário: empate entre LRU, Ótimo e LFU (todos com \,7 faults).
Isso não significa que qualquer um desses sempre será o melhor em todo cenário:
O algoritmo Ótimo é ideal (menor número possível) mas é impossível de implementar online porque requer conhecer todas as referências futuras. Ele funciona como limite inferior de faults.
LRU costuma funcionar bem quando existe localidade temporal (páginas usadas recentemente são usadas de novo em breve). Mas há sequências (padrões específicos, por exemplo acessos cíclicos maiores que o número de frames) onde LRU pode ter desempenho ruim — e em alguns casos FIFO pode até superar LRU.
LFU favorece páginas com alta frequência passada; isso é bom se frequências refletem relevância futura, mas LFU pode ser ruim se uma página foi muito usada no passado e depois deixa de ser usada (stale), mantendo-a na memória por causa do contador. Sem políticas de envelhecimento, LFU pode reter páginas inúteis.
Conclusão: o fato de LRU, Ótimo e LFU empatarem aqui é específico desta sequência; não há garantia de que qualquer um deles seja sempre melhor; escolha de algoritmo depende do padrão de acesso e restrições (conhecimento do futuro, custo de manutenção de estruturas, necessidade de envelhecimento em LFU etc.).
Resposta
(a) FIFO: \,8; LRU: \,7; Ótimo: \,7; LFU: \,7.
(b) LRU, Ótimo e LFU empataram com \,7 page faults; FIFO teve pior desempenho com \,8 faults.
(c) Melhor neste cenário: empate entre LRU, Ótimo e LFU (todos \,7). Isso não significa que qualquer um deles será sempre o melhor — o Ótimo exige conhecimento do futuro (não aplicável online), LRU funciona bem quando há localidade temporal, e LFU pode falhar sem envelhecimento (retenção de páginas “stale”); a escolha ideal depende do padrão de acessos.