Algoritmos de Substituição de Páginas: FIFO, Clock, NRU, LRU, NFU, Aging e WSCLOCK

Resumo

O documento apresenta os principais algoritmos de substituição de páginas usados em sistemas operacionais para gerir a memória virtual. Descreve o funcionamento do FIFO, do Relógio (Clock), do NRU, do LRU, do NFU, do Envelhecimento (Aging) e do WSCLOCK, indicando os bits e estruturas que cada um utiliza. O estudante fica a perceber como cada algoritmo escolhe a moldura a remover e quais são as suas vantagens e limitações.

Pontos-chave

FIFO remove a moldura de página que está no início da fila, pois foi a primeira a entrar.
O algoritmo do Relógio usa o bit R e um ponteiro sobre uma lista circular: molduras com R=1 recebem uma segunda oportunidade (R passa a 0) até encontrar uma com R=0.
O NRU classifica as molduras pelos bits R e M e remove uma moldura da menor classe, escolhida aleatoriamente em caso de empate; tem baixa complexidade.
O LRU remove a página menos recentemente usada, mas exige atualizar a lista a cada referência à memória, o que pode degradar o desempenho.
No NFU e no Aging, cada moldura tem um contador; no Aging os contadores são deslocados 1 bit para a direita a cada interrupção de relógio e a moldura com menor contador é substituída.
O WSCLOCK combina o algoritmo do Relógio com o conceito de conjunto de trabalho, usando a idade da página (tempo virtual atual menos instante do último uso) comparada com T e o bit M.

Teste-se

Algoritmos de Substituição de Páginas

FIFO (First-In, First-Out)

É mantida uma lista ordenada de molduras de página (MP). A MP que será removida, caso necessário, é a que estiver no início da fila. A nova página entrará no fim da lista.

Algoritmo do Relógio (Clock)

Utiliza o bit R (Referência) como critério para a substituição da moldura de página.

É mantida uma lista circular e um ponteiro é usado para a próxima moldura candidata à substituição.
Se a moldura apontada estiver com o bit R igual a 1, o bit é alterado para 0 e o ponteiro avança para a próxima moldura até que encontre uma moldura com o bit R igual a 0.

NRU (Not Recently Used)

Utiliza os bits R (Referência) e M (Modificado) da tabela de páginas.
Esquema de Classe: Quando for realizar uma substituição, inspecionam-se os bits R e M, e remove-se a moldura que estiver na menor classe.
- Se houver mais de uma moldura na menor classe, a remoção é feita de forma aleatória.
Vantagem: Baixa complexidade e implementação fácil.

LRU (Least Recently Used)

Mantém uma lista encadeada de todas as molduras, onde as MPs usadas recentemente são inseridas no início da lista e a menos usada recentemente fica no fim da lista.

Remove sempre a MP do fim da lista.
Problema: Necessita atualizar a lista a cada referência à memória, o que pode resultar em desempenho ruim.

NFU (Not Frequently Used)

Utiliza o bit R (Referência) da Tabela de Páginas.

Mantém um contador associado a cada MP, inicialmente em 0.
A cada interrupção de relógio, o Sistema Operacional (SO) percorre todas as MPs somando o valor do bit R no contador de cada moldura. Após somar, o bit R é zerado.
Substitui a moldura com o menor contador. Em caso de empate, a remoção é feita de forma aleatória.

Algoritmo de Envelhecimento (Aging)

A cada interrupção de relógio, os contadores são deslocados 1 bit para a direita. O bit R de cada MP é adicionado ao bit mais à esquerda do contador correspondente.

Quando ocorre uma substituição, a MP que tiver o menor contador é substituída.

WSCLOCK (Working Set Clock)

Baseado no algoritmo do Relógio.

Quando ocorre uma falta de página, a moldura de página que estiver sendo apontada é examinada primeiro.
Se R=1, ela foi referenciada antes da interrupção de relógio atual, então não é candidata à remoção.
- Zera o bit R, copia o tempo virtual atual para o instante do último uso e avança o ponteiro.
Se R=0:
- idade = tempo virtual atual - instante do último uso
- Se idade > T e M = 0, remove a MP.
- Se idade > T e M = 1, escalona a escrita no disco da moldura de página e avança o ponteiro.
Se o ponteiro deu uma volta completa:
- Se pelo menos uma escrita foi escalonada, o ponteiro irá encontrar uma MP com M = 0.

Perguntas frequentes

Qual é a diferença entre o algoritmo do Relógio e o FIFO?

O FIFO remove sempre a página que está há mais tempo na memória, sem considerar o seu uso. O algoritmo do Relógio usa o bit R para dar uma segunda oportunidade às páginas referenciadas recentemente, percorrendo a lista circular com um ponteiro.

Qual é a principal desvantagem do LRU?

O LRU necessita de atualizar a lista encadeada a cada referência à memória, o que pode resultar em desempenho ruim.

Qual é a vantagem do NRU?

O NRU tem baixa complexidade e uma implementação fácil, pois utiliza apenas os bits R e M da tabela de páginas.