Substituição de Páginas

Algoritmos de Substituição de Páginas
Igor Gustavo Hoelscher
Renan Arend
Rogério Corrêa Medeiros

2

Introdução
 No momento em que ocorre uma page fault o sistema operacional precisa escolher uma página a ser removida da memória a fim de liberar espaço para que uma nova página seja carregada.
 Outros problemas na computação são análogos à esse: como por exemplo os blocos carregados na memória cache de um computador ou as páginas armazenadas na cache de um servidor web.
 O algoritmo ótimo que resolveria esse problema precisa saber quando as páginas serão referenciadas novamente, o que implica em um sistema não causal e é impossível de se realizar.

quarta-feira, 12 de março de
2013

3

O Algoritmo NRU
 NRU (Not Recently Used – não usada recentemente).
 Usa dois bits de status: bit R (referenciado) e bit M (modificado).
 Quando o processo inicia, suas páginas ainda não estão presentes na memória. Assim que uma delas é referenciada, o bit R é colocado em 1.
 Em seguida, se esta página é modificada, o bit M é colocado em 1.
 Ao ocorrer uma page fault o sistema operacional separa todas as páginas em quatro categorias:
 Classe 0: não referenciada, não modificada.
 Classe 1: não referenciada, modificada.
 Classe 2: referenciada, não modificada.
 Classe 3: referenciada, modificada. quarta-feira, 12 de março de
2013

4

O Algoritmo NRU
Como uma página pode ter sido modificada mas não referenciada
(Classe 1)? Por que essa página é de uma classe de ordem menor a uma página referenciada, mas não modificada?
 O NRU então remove uma página aleatória da classe mais baixa que não esteja vazia.
 Entre as vantagens está a baixa complexidade de entendimento e implementação e a boa aproximação para o algoritmo ótimo.

quarta-feira, 12 de março de
2013

5

O Algoritmo Segunda Chance
 FIFO + bit R.
 Inspeciona o bit R da página mais velha.

 Se for 0, ela é velha e não foi usada recentemente: é trocada.