Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorítimos de substituição de páginas (Algorítimo de substituição de…
Algorítimos de substituição de páginas
Quando ocorre uma falta de página, o sistema ope-racional tem de escolher uma página para remover da memória a fim de abrir espaço para a que está chegando
Se a página a ser removida foi modificada enquanto estava na memória, ela precisa ser reescrita para o disco a fim de atualizar a cópia em disco
Se, no entanto, ela não tiver sido modificada, a cópia em disco já está atualizada, portanto não é preciso reescrevê-la
A página a ser lida simplesmente sobrescreve a página que está sendo removida.
é possível escolher uma página ao acaso para ser descartada a cada falta de página
o desempenho do sistema será muito melhor se for escolhida uma página que não é intensamente usada
Algorítimo ótimo de substituição de páginas
O algoritmo de substituição de página melhor possível é fácil de descrever, mas impossível de implementar de fato
Ele funciona deste modo: no momento em que ocorre uma falta de página, há um determinado conjunto de páginas na memória
Cada página pode ser rotulada com o número de instruções que serão executadas antes de aquela página ser referenciada pela primeira vez
Esse algoritmo é irrealizável
No momento da falta de página, o sistema operacional não tem como saber quando cada uma das páginas será referenciada em seguida
não tem uso para sistemas práticos
Algorítimo de substituição de páginas não usadas recentemente (NRU)
A fim de permitir que o sistema operacional colete estatísticas de uso de páginas úteis, a maioria dos computadores com memória virtual tem dois bits de status, R e M, associados com cada página
R
colocado sempre que a página é referenciada (lida ou escrita)
M
colocado quando a página é escrita (isto é, modificada)
bits estão contidos em cada entrada de tabela de página
esses bits precisam ser atualizados em cada referência de memória, então é essencial que eles sejam atualizados pelo hardware
Quando um processo é inicializado, todas as entradas de tabela de páginas são marcadas como não presentes na memória
algoritmo NRU
(Not Recently Used— não usada recentemente) remove uma página ao acaso de sua classe de ordem mais baixa que não esteja vazia
Algorítimo de substituição de páginas primeiro a entrar, primeiro a sair (FIFO)
algoritmo de paginação de baixo custo
O sistema operacional mantém uma lista de todas as páginas atualmente na memória
com a chegada mais recente no fim e a mais antiga na frente.
Em uma falta de página, a página da frente é removida e a nova página acrescentada ao fim da lista
Algorítimo de substituição de páginas Segunda Chance
procura por uma página antiga que não esteja referenciada no intervalo de relógio mais recente.
Se todas as páginas foram referenciadas, a segunda chance degenera-se em um FIFO puro
é desnecessariamente ineficiente, pois ele está sem-pre movendo páginas em torno de sua lista
Algorítimo de substituição de páginas do relógio
mantem todos os quadros de páginas em uma lista circular na forma de um relógio
Quando ocorre uma falta de página, a página indi-cada pelo ponteiro é inspecionada.
Algorítimo de substituição de páginas usadas menos recentemente (LRU)
quando ocorre uma falta de página, joga-se fora aquela que não tem sido usada há mais tempo
teoricamente realizável
não é nem um pouco barato
é necessário que seja mantida uma lista encadeada de todas as páginas na memória
página mais recentemente usada na frente
menos recentemente usada na parte de trás.
dificuldade
lista precisa ser atualizada a cada referência de memória
cada entrada da tabela de páginas também deve ter um campo grande o suficiente para conter o contador
Quando ocorre uma falta de página, o sistema operacional examina todos os contadores na tabela de página para encontrar a mais baixa. Essa página é a usada menos recentemente.
Simulação do LRU em software
Quando ocorre uma falta de página, é removida a página cujo contador é o mais baixo
Embora o algoritmo de LRU anterior seja (em princípio) realizável, poucas máquinas, se é que existe alguma, têm o hardware necessário.
Em vez disso, é necessária uma solução que possa ser implementada em software
Uma possibilidade é o algoritmo de substituição de páginas não usadas frequentemente (NFU — Not Frequently Used).
A implementação exige um contador de software associado com cada página, de início zero.
A cada interrupção de relógio, o sistema operacional percorre todas as páginas na memória
Para cada página, o bit R, que é 0 ou 1, é adicionado ao contador
Os contadores controlam mais ou menos quão frequentemente cada página foi referenciada
Quando ocorre uma falta de página, aquela com o contador mais baixo é escolhida para substituição