ALGORITIMOS DE SUBSTITUIÇÃO DE PÁGINAS

ALGORITIMOS DE SUBSTITUIÇÃO DE PÁGINAS

Quando ocorre um Page Fault, o S.O. deve escolher que página remover para abrir espaço em memória.
Se a página foi alterada (bit Modified setado) é preciso salvá-la em disco. Senão foi, basta sobreescrevê-la. É melhor não escolher para remoção uma página que é usada freqüentemente, pois ela pode ter que voltar para a memória logo.
Troca ótima de página
Substituir a página para a qual falta mais tempo até ser necessária novamente
Marcar p/ cada página, quantas instruções faltam p/ que ela seja referenciada
Solução ótima, mas inviável!

Algoritmo NRU – Not Recently Used
- Ou seja, algoritmo de substituição da página “não usada recentemente”
- Na maioria dos computadores com memória virtual, as entradas nas tabelas de páginas têm 2 bits de status
Reference bit (R) ; Modified bit (M)
- Algoritmo
Quando o processo é iniciado, os bits R e M das páginas são zerados
Bits são sempre alterados quando a página é referenciada/modificada
Periodicamente o bit R é zerado (por exemplo, a cada tique de clock)
Quando acontece um Page fault, o S.O. inspeciona todas as páginas que encontram-se na memória e as separa em categorias...

Algoritmo NRU – Not Recently Used
- Páginas são classificadas
Classe 0: Not referenced, not modified (R=0 , M=0)
Classe 1: Not referenced, modified (R=0 , M=1)
Classe 2: referenced, not modified (R=1 , M=0)
Classe 3: referenced, modified (R=1 , M=1)
- O S.O. remove uma das páginas (aleatoriamente) da classe mais baixa não vazia.
- Vantagens
Algoritmo fácil de entender e implementar Desempenho adequado.

Algoritmo FIFO
- Mantem-se uma lista encadeada de páginas ordenada pela chegada das páginas à memória.
- Quando ocorre um Page Fault, a página no início da lista (que é a mais antiga) é a escolhida para a troca.
- Vantagem:
Baixo custo
- Desvantagem:
A página mais antiga pode ser também uma página usada muito freqüentemente.
- Não empregado!

Algoritimo SC -