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).
  1. Referência \,4: frames [4,\;-,\;-]. PF (carregou 4). (PFs = 1).
  2. Referência \,2: frames [4,\;2,\;-]. PF (carregou 2). (PFs = 2).
  3. Referência \,4: frames [4,\;2,\;-]. Hit (nenhum PF).
  4. Referência \,2: frames [4,\;2,\;-]. Hit.
  5. Referência \,5: frames [4,\;2,\;5]. PF (preencheu o 3.º frame). (PFs = 3).
  6. Referência \,4: frames [4,\;2,\;5]. Hit.
  7. Referência \,4: frames [4,\;2,\;5]. Hit.
  8. 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).
  9. Referência \,3: fila restante em ordem: 2 (entrou antes), 5, 1. FIFO remove 2. frames [1,\;3,\;5]. PF. (PFs = 5).
  10. Referência \,4: FIFO remove o mais antigo restante que é 5. frames [1,\;3,\;4]. PF. (PFs = 6).
  11. Referência \,6: remove o mais antigo restante que é 1. frames [6,\;3,\;4]. PF. (PFs = 7).
  12. 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).
  1. Referência \,4: frames [4,\;-,\;-]. PF. Último uso 4:t_1. (PFs = 1).
  2. Referência \,2: frames [4,\;2,\;-]. PF. Último uso 2:t_2. (PFs = 2).
  3. Referência \,4: frames [4,\;2,\;-]. Hit. Atualiza último uso 4:t_3.
  4. Referência \,2: frames [4,\;2,\;-]. Hit. Atualiza último uso 2:t_4.
  5. Referência \,5: frames [4,\;2,\;5]. PF. Último uso 5:t_5. (PFs = 3).
  6. Referência \,4: hit. Atualiza 4:t_6.
  7. Referência \,4: hit. Atualiza 4:t_7.
  8. 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).
  9. Referência \,3: falta. Últimos usos atuais: 4:t_7, 1:t_8, 5:t_5. Menos recente é 5 (t_5). Substitui 5. frames [4,\;1,\;3]. PF. (PFs = 5).
  10. Referência \,4: hit. Atualiza 4:t_{10}.
  11. Referência \,6: falta. Últimos usos: 4:t_{10}, 1:t_8, 3:t_9. Menos recente é 1 (t_8). Substitui 1. frames [4,\;6,\;3]. PF. (PFs = 6).
  12. Referência \,7: falta. Últimos usos: 4:t_{10}, 6:t_{11}, 3:t_9. Menos recente é 3 (t_9). Substitui 3. frames [4,\;6,\;7]. PF. (PFs = 7).

Passo 5

Resultado final para LRU.
  • Número total de page faults com LRU: \,7.

Passo 6

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):
  1. \,4: frames [4,\;-,\;-]. PF. (PFs = 1).
  2. \,2: frames [4,\;2,\;-]. PF. (PFs = 2).
  3. \,4: hit.
  4. \,2: hit.
  5. \,5: frames [4,\;2,\;5]. PF. (PFs = 3).
  6. \,4: hit.
  7. \,4: hit.
  8. \,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).
  9. \,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).
  10. \,4: hit.
  11. \,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).
  12. \,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).
Inicialmente todos f são 0.
  1. Referência \,4: frames [4,\;-,\;-]. PF. f(4)=1. (PFs = 1).
  2. Referência \,2: frames [4,\;2,\;-]. PF. f(2)=1. (PFs = 2).
  3. Referência \,4: hit. f(4)=2.
  4. Referência \,2: hit. f(2)=2.
  5. Referência \,5: frames [4,\;2,\;5]. PF. f(5)=1. (PFs = 3).
  6. Referência \,4: hit. f(4)=3.
  7. Referência \,4: hit. f(4)=4.
  8. Referência \,1: falta. Frequências atuais: f(4)=4, f(2)=2, f(5)=1. Menor frequência é 1 (página 5), então evito 4 e 2 e removo 5. frames [4,\;2,\;1]. PF. f(1)=1. (PFs = 4).
  9. Referência \,3: falta. Frequências: f(4)=4, f(2)=2, f(1)=1. Menor é 1 (página 1), removo 1. frames [4,\;2,\;3]. PF. f(3)=1. (PFs = 5).
  10. Referência \,4: hit. f(4)=5.
  11. Referência \,6: falta. Frequências: f(4)=5, f(2)=2, f(3)=1. Menor é 1 (página 3); removo 3. frames [4,\;2,\;6]. PF. f(6)=1. (PFs = 6).
  12. Referência \,7: falta. Frequências: f(4)=5, f(2)=2, f(6)=1. Menor é 1 (página 6); removo 6. frames [4,\;2,\;7]. PF. f(7)=1. (PFs = 7).

Passo 9

Resultado final para LFU.
  • 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.

Exercícios relacionados