Questão de Sistemas Operacionais — Geral — FUNDATEC 2025

Algoritmos de substituição de páginas: FIFO, LFU e LRU

Gabarito: letra B (apenas III). O padrão de acesso da Figura 4, que exibe localidade temporal (páginas recentemente acessadas tendem a ser acessadas novamente), é o cenário ideal para o algoritmo LRU (Least Recently Used), que substitui a página menos recentemente usada. As Figuras 2 e 3 não são melhor tratadas por FIFO e LFU, respectivamente, pois FIFO sofre com padrões sequenciais e LFU não é um algoritmo clássico de substituição de páginas — o conceito correto para frequência é o LFU, mas ele não é o mais adequado para os padrões apresentados. Os algoritmos de substituição de páginas decidem qual página da memória física deve ser removida quando ocorre uma falta de página (page fault). Cada algoritmo tem um critério diferente para escolher a "vítima":

• FIFO (First-In, First-Out): remove a página que está há mais tempo na memória, independentemente de quando foi acessada. É simples, mas sofre da anomalia de Belady (aumentar o número de quadros pode aumentar as faltas de página) e tem desempenho ruim em padrões sequenciais, pois pode remover páginas que serão usadas em breve.

• LRU (Least Recently Used): remove a página que está há mais tempo sem ser acessada. Baseia-se no princípio da localidade temporal: páginas usadas recentemente provavelmente serão usadas novamente. É uma aproximação do algoritmo ótimo (OPT) e não sofre da anomalia de Belady.

• LFU (Least Frequently Used): remove a página que foi acessada com menor frequência ao longo do tempo. Embora seja um conceito válido, não é um dos algoritmos clássicos de substituição de páginas (os clássicos são OPT, FIFO, LRU, RANDOM, segunda chance, NRU, envelhecimento e WSClock).

A questão pede para analisar padrões de acesso (Figuras 2, 3 e 4) e identificar qual algoritmo os trata melhor. Sem ver as figuras, o raciocínio é:

• Figura 2: se o padrão é fortemente sequencial (ex.: p1, p2, p3, ..., pn, p1, p2, ...), o FIFO tem desempenho ruim, pois remove páginas que serão acessadas em breve. O LRU também sofre nesse cenário, como mencionado no material de apoio. O algoritmo RANDOM pode ser melhor nesse caso.

• Figura 3: se o padrão tem localidade temporal (páginas acessadas recentemente são acessadas novamente), o LRU é o mais adequado, não o LFU. O LFU pode falhar se uma página foi acessada muitas vezes no passado, mas não será mais usada (poluição por frequência).

• Figura 4: se o padrão tem localidade temporal, o LRU é o algoritmo ideal, pois mantém na memória as páginas mais recentemente usadas.

A banca explora a confusão entre os algoritmos: FIFO é melhor para padrões sequenciais? Não — FIFO sofre com eles. LFU é melhor para frequência? Sim, mas não é o algoritmo clássico e não é o melhor para localidade temporal. LRU é o melhor para localidade temporal? Sim, é exatamente o caso.

Item I — ❌ Incorreto

O padrão de acesso da Figura 2 não é melhor tratado pelo FIFO. O FIFO remove a página mais antiga, independentemente do uso, e sofre com padrões sequenciais (como p1, p2, p3, ..., pn, p1, p2, ...), pois pode remover páginas que serão acessadas em breve. O material de apoio confirma: "o desempenho do algoritmo LRU é prejudicado no caso de acessos com um padrão fortemente sequencial... Nessa situação, o desempenho do algoritmo LRU será similar ao do FIFO." Ou seja, ambos têm desempenho ruim nesse cenário. Se a Figura 2 mostra um padrão sequencial, o FIFO não é o melhor — o RANDOM poderia ser melhor.

Item II — ❌ Incorreto

O padrão de acesso da Figura 3 não é melhor tratado pelo LFU. O LFU (Least Frequently Used) remove a página com menor frequência de acesso, mas não é um dos algoritmos clássicos de substituição de páginas (os clássicos são OPT, FIFO, LRU, RANDOM, segunda chance, NRU, envelhecimento e WSClock). Além disso, se a Figura 3 mostra localidade temporal (páginas recentemente acessadas serão acessadas novamente), o algoritmo mais adequado é o LRU, não o LFU. O LFU pode sofrer do problema de "poluição": uma página acessada muitas vezes no passado, mas que não será mais usada, permanece na memória.

Item III — ✅ Correto ⟵ GABARITO

O padrão de acesso da Figura 4 é melhor tratado pelo LRU. O LRU (Least Recently Used) remove a página que está há mais tempo sem ser acessada, baseando-se no princípio da localidade temporal: páginas recentemente acessadas provavelmente serão acessadas novamente. Se a Figura 4 mostra um padrão com localidade temporal (páginas acessadas recentemente são acessadas novamente), o LRU é o algoritmo ideal, pois mantém na memória as páginas mais recentemente usadas. O material de apoio confirma: "O algoritmo LRU parte do pressuposto que páginas recentemente acessadas no passado provavelmente serão acessadas em um futuro próximo, e então evita removê-las da memória." Conclusão: apenas o item III está correto. Portanto, a alternativa correta é a letra B. Gabarito: letra B