algoritmo

Sistemas Operacionais

Gerenciamento de Memória Virtual
Algoritmos de Paginação
Norton Trevisan Roman
Marcelo Morandini
Jó Ueyama

Apostila baseada nos trabalhos de Kalinka Castelo Branco, Antônio Carlos
Sementille, Luciana A. F. Martimiano e nas transparências fornecidas no site de compra do livro "Sistemas Operacionais Modernos"
1

Algoritmos de Troca de Página


Ótimo;



NRU;



FIFO;



Segunda Chance;



Relógio;



LRU;



Working set;



WSClock;



Veremos cada um em detalhes 2

Algoritmos de Troca de Página


Algoritmo ótimo


Cada página é marcada com o número de instruções que serão executadas antes que a página seja referenciada


Retira da memória a página que tem menos chance de ser referenciada (maior número de instruções faltantes)



Praticamente impossível de se saber;



Impraticável;



Usado em simulações para comparação com outros algoritmos;
3

Algoritmos de Troca de Página


Algoritmo Not Recently Used Page
Replacement (NRU)


Para auxiliar o S.O. a coletar estatísticas de página de uso:


02 bits associados a cada página → R(eferenciada) e
M(odificada)


Classe 0 (00) → não referenciada, não modificada;



Classe 1 (01) → não referenciada, modificada;



Classe 2 (10) → referenciada, não modificada;



Classe 3 (11) → referenciada, modificada;



Referenciada → lida ou escrita



Modificada → escrita
4

Algoritmos de Troca de Página


Algoritmo Not Recently Used Page
Replacement (NRU)


Para auxiliar o S.O. a coletar estatísticas de página de uso:




R e M são atualizados a cada referência à memória;


Armazenados em cada entrada da tabela de página



Seu valor é determinado pelo hardware

Quando um processo é iniciado, ambos R e M são
0 para todas suas páginas


Periodicamente, o bit R é limpo para diferenciar as páginas que não foram