Questão de Sistemas Operacionais — Gerência de Memória (Paginação, Virtual, etc.) — INSTITUTO AOCP 2024

Algoritmo de substituição de páginas LRU

Gabarito: letra B. O algoritmo LRU (Least Recently Used — menos recentemente usado) escolhe para remoção a página que não é referenciada há mais tempo, baseando-se no princípio da localidade de referência: páginas usadas recentemente provavelmente serão usadas em breve. A alternativa B descreve exatamente esse critério, e é a única que corresponde corretamente ao funcionamento do LRU.

O LRU é um dos algoritmos clássicos de substituição de páginas em sistemas de memória virtual. Quando ocorre uma falta de página (page fault) e não há quadros livres na memória física, o sistema operacional precisa escolher uma página "vítima" para ser removida e dar lugar à página requisitada. O LRU parte da hipótese de que páginas acessadas recentemente no passado provavelmente serão acessadas em um futuro próximo, e portanto evita removê-las. Essa hipótese geralmente se verifica na prática, sobretudo quando os processos respeitam o princípio da localidade de referência — ou seja, quando um processo tende a acessar um conjunto pequeno de páginas em um determinado intervalo de tempo.

O critério de seleção do LRU é a data do último acesso: a página que está há mais tempo sem ser referenciada é a escolhida para sair. Isso contrasta com outros algoritmos, como o FIFO (First-In, First-Out), que remove a página que entrou na memória há mais tempo, independentemente de quando foi usada pela última vez. O LRU também difere do algoritmo ótimo (OPT), que escolheria a página que levará mais tempo para ser novamente necessária — mas esse algoritmo é teórico e não implementável, pois exigiria conhecimento do futuro. O LRU é considerado um algoritmo de pilha, pois o conjunto de páginas na memória após uma sequência de referências é um subconjunto do que estaria presente com mais quadros, uma propriedade que ajuda a evitar certos comportamentos anômalos.

Na prática, o LRU pode ser implementado com uma lista encadeada onde cada página referenciada é movida para o final da lista, e a página no início da lista é a candidata à remoção. No entanto, essa implementação tem custo alto, pois cada referência exige atualização da lista. Por isso, na prática, muitos sistemas usam aproximações do LRU, como o algoritmo do relógio (clock) ou o NRU (Not Recently Used), que se baseiam em bits de referência. O desempenho do LRU é prejudicado em padrões de acesso fortemente sequenciais, onde seu comportamento se aproxima do FIFO.

A pegadinha desta questão está em confundir o LRU com outros algoritmos: a alternativa A descreve o FIFO, a C descreve o algoritmo ótimo, a D descreve o LFU (Least Frequently Used) e a E descreve o algoritmo aleatório. A banca explora exatamente essa confusão entre os critérios de cada algoritmo. Guarde a fronteira entre eles: o que decide é o critério de escolha da página vítima — tempo de entrada (FIFO), tempo desde o último uso (LRU), frequência de uso (LFU), previsão de uso futuro (ótimo) ou aleatoriedade (RANDOM).

Alternativa A — ❌ Incorreta

Esta alternativa descreve o algoritmo FIFO (First-In, First-Out), que remove a página que entrou na memória há mais tempo, sem considerar quando ela foi usada pela última vez. O LRU, ao contrário, considera o tempo desde o último acesso, não o tempo de entrada. A confusão entre "entrou há mais tempo" e "não é referenciada há mais tempo" é a pegadinha clássica desta questão.

Alternativa B — ✅ Correta ⟵ GABARITO

Esta é a definição correta do LRU. O algoritmo escolhe para remoção a página que não é referenciada há mais tempo, ou seja, a página cujo último acesso foi o mais antigo. A alternativa também menciona que é um algoritmo de pilha, o que é uma propriedade correta do LRU: o conjunto de páginas na memória após uma sequência de referências é um subconjunto do que estaria presente com mais quadros, o que evita certas anomalias.

Alternativa C — ❌ Incorreta

Esta alternativa descreve o algoritmo ótimo (OPT), que escolheria para sair a página que levará mais tempo para ser novamente necessária. Esse algoritmo é teórico e não implementável, pois exigiria conhecimento do futuro. O LRU não tem como prever o futuro; ele apenas usa o passado como indicativo.

Alternativa D — ❌ Incorreta

Esta alternativa descreve o LFU (Least Frequently Used), que remove a página que foi menos frequentemente referenciada no passado. O LRU, por sua vez, considera a recência do último acesso, não a frequência de acessos. Uma página pode ter sido acessada muitas vezes no passado, mas se não foi acessada recentemente, será a vítima do LRU.

Alternativa E — ❌ Incorreta

Esta alternativa descreve o algoritmo aleatório (RANDOM), que escolhe uma página aleatoriamente para remoção, sem considerar o histórico de uso. O LRU, ao contrário, baseia-se justamente no histórico de uso (data do último acesso) para tomar a decisão. O algoritmo aleatório pode ser útil em padrões de acesso sequenciais, onde LRU e FIFO têm desempenho ruim, mas não é o que a questão pede.

Gabarito: letra B — o LRU remove a página que não é referenciada há mais tempo.