3^{\underline{\mathbf{a}}} Questão: Considere 3 frames e a sequência de acessos: 7,1,0,2,1,1,3,4,2, 3, 0, 3, 2
(a) Quantos page faults ocorreram usando o algoritmo LFU (Least Frequently Used)?
(b) Explique detalhadamente o critério de substituição do LFU. Há alguma limitação dessa abordagem?
Passo 1
O enunciado pede duas coisas:
(a) Calcular quantos page faults ocorrem usando o algoritmo LFU para uma memória com 3 frames e a sequência de acessos
7,1,0,2,1,1,3,4,2,3,0,3,2.
(b) Explicar detalhadamente o critério de substituição do LFU e apontar limitações dessa abordagem.
Informações relevantes dadas:
Número de frames: 3.
Sequência de acessos (em ordem): \;7,\;1,\;0,\;2,\;1,\;1,\;3,\;4,\;2,\;3,\;0,\;3,\;2.
Algoritmo a usar: LFU (Least Frequently Used).
O enunciado não especifica critério de desempate entre páginas com mesma frequência — eu escolherei um desempate explícito e explicarei o porquê mais adiante.
Passo 2
Breve e didática explicação do que é LFU e da convenção de desempate que vou usar:
LFU (Least Frequently Used) mantém, para cada página residente na memória, um contador de quantas vezes essa página foi acessada enquanto estava na memória. Quando ocorre falta de página (page fault) e não há frames livres, LFU substitui (remove) a página com o menor contador de frequência.
Como o enunciado não diz como desempatar quando duas (ou mais) páginas têm a mesma frequência, eu vou adotar a convenção prática e bastante usada: desempatar por LRU (Least Recently Used) entre as páginas que têm a menor frequência. Ou seja, entre as páginas com menor contador, removemos a que foi usada há mais tempo.
Justificativa da escolha: é uma política razoável e simples para simular LFU; outras alternativas existem (FIFO entre os com menor frequência, remover a de menor número de cargas, etc.), mas preciso escolher uma para obter um resultado único. Se você usar outra regra de desempate o número de faults pode mudar; eu explicarei isso quando for relevante.
Inicialização: toda página quando carregada no frame começa com contador de frequência igual a 1 naquele acesso (porque acabou de ser acessada). A cada acesso a uma página residente, incrementamos seu contador em 1 e atualizamos sua marcação de tempo de último uso (para o desempate LRU).
Agora vou simular passo a passo cada acesso, mostrando o conteúdo dos frames, os contadores de frequência e as decisões de substituição.
Passo 3
Acesso 1: página 7.
Estado inicial: frames vazios.
7 não está na memória → page fault.
Carrego 7 em um frame; contador de 7 passa a 1; tempo de último uso: passo 1.
Frames após o passo: \{7(f=1, \text{último}=1)\}ú.
Page faults acumulados: 1.
Passo 4
Acesso 2: página 1.
1 não está na memória → page fault.
Carrego 1 em frame livre; 1 tem f=1; último uso passo 2.
Não há frames livres. Contadores atuais: 7(f=1,\text{último}=1)ú, 1(f=1,\text{último}=2)ú, 0(f=1,\text{último}=3)ú.
Todas têm mesma frequência mínima 1. Usamos desempate LRU: escolher a que tem menor valor de “último uso” → 7 (último uso no passo 1) é a menos recentemente usada.
Evict 7; carregar 2 com f=1; último uso de 2 = passo 4.
Resumo da simulação e esclarecimentos finais sobre o processo:
Contagem final de page faults obtida com LFU (usando desempate LRU) = 10.
Observe que o desempate LRU foi usado sempre que havia várias páginas com a menor frequência; se você adotasse outro critério de desempate (por exemplo, FIFO entre as de menor frequência), a sequência de substituições poderia mudar e, em consequência, o número final de page faults poderia mudar também.
Durante a simulação, sempre que uma página residente é acessada, seu contador é incrementado imediatamente. Quando uma página é carregada após um page fault, sua frequência inicia em 1 (contando o acesso que a trouxe).
Passo 17
Explicação detalhada do critério de substituição do LFU e suas limitações (a aula que você pediu):
Critério do LFU:
Para cada página mantemos um contador f(p) que indica “quantas vezes a página p foi acessada enquanto estava residente”.
Quando ocorre page fault e existe frame livre, carregamos a nova página com f=1.
Quando ocorre page fault e não há frame livre, removemos a página com menor f(p). Em caso de empate entre várias páginas com o mesmo f, deve-se escolher uma regra de desempate (LRU, FIFO, aleatória, etc.). Na simulação acima escolhemos LRU como desempate.
Após cada acesso a uma página residente, incrementamos seu contador f(p) em 1 e atualizamos seu tempo de último uso (se aplicável).
Limitações e problemas práticos do LFU:
“Efeito de burst único” / poluição por acessos antigos: se uma página foi muito acessada no passado e acumulou alto f, ela tende a permanecer na memória mesmo que não seja mais útil; isso causa pouca capacidade de adaptação a mudanças recentes no padrão de acessos.
Starvation de páginas novas: uma página recém-carregada tem baixo contador e pode ser constantemente substituída antes de ter chance de aumentar seu contador — principalmente se houver muitas páginas com contadores médios e algumas com altos contadores fixos.
Crescimento ilimitado de contadores: se você simplesmente incrementa contadores indefinidamente, os números podem ficar grandes; na prática é preciso normalizar (ex.: decaimento/aging) ou usar contadores limitados.
Complexidade de implementação: LFU precisa de estruturas para manter contadores e para localizar a página com menor contador rapidamente (por exemplo, heaps, buckets por frequência, listas encadeadas). Isso pode custar mais em tempo e memória que algoritmos simples como LRU puro.
Sensibilidade ao desempate: o comportamento final depende de como você desempata frequências iguais — isto pode afetar performance.
Mitigações comuns:
Aging (decaimento de frequências): periodicamente reduzir todos os contadores (por exemplo, dividir por 2) para dar mais peso aos acessos recentes; isso transforma LFU em algo mais responsivo a mudanças.
Limitar contador máximo e usar buckets de frequência para eficiência.
Em resumo: LFU é bom quando padrões de acesso tendem a ser repetitivos e estáveis (favorita páginas que realmente são frequentemente usadas), mas tem problemas quando o padrão muda ou quando páginas tiverem picos de uso passageiros.
Resposta
(a) 10 page faults.
(b) LFU substitui a página com menor contagem de acessos (contador de frequência); em caso de empate usei desempate por LRU. Limitações: não reage bem a mudanças recentes (páginas frequentemente usadas no passado “prendem” o frame), risco de starvation de páginas novas, necessidade de aging/normalização dos contadores e maior overhead de implementação.