Algoritmos de Substituição de Páginas em Sistemas Operacionais

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.