Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Substituição de Páginas - Coggle Diagram
Algoritmos de Substituição de Páginas
Selecionam os frames que
tenham as menores chances de serem referenciados em um futuro próximo;
Princípio da localidade
Quanto mais sofisticado o algoritmo de substituição, maior overhead para o sistema operacional implementá-lo.
Ótimo
Seleciona uma página que não será mais referenciada ou levará mai tempo
Modelo comparativo na análise de outros algoritmos
Não é possível implementar
Não se conhece o comportamento futuro das aplicações
Aleatório
Sem critério de seleção
Consome poucos recursos mas tem baixa eficiência
FIFO (First-In-First-Out)
Seleciona a página que está há mais tempo na memória principal.
Pode usar estrutura de fila ou associar a cada página o momento em que foi carregada
Raramente implementado sem outro mecanismo para minimizar o problema de seleção de páginas que são referenciadas constantemente
LFU (Least-Frequently-Used)
Seleciona a página menos referenciada
através de um contador do número de referências para cada página na memória principal.
raramente implementado, serve de base para outros algoritmos
Pode não ser muito eficiente
FIFO circular (clock)
As páginas alocadas na memória estão em uma estrutura de lista circular
Implementado na maioria dos sistemas Unix.
um ponteiro guarda a posição da página
mais antiga na lista
Cada página possui associado um bit de referência,
Tenta-se encontrar o bit 0, caso todos sejam bit 1 ele escolhe a mais antiga
É possível melhorar a eficiência utilizando o bit de modificação
FIFO com buffer de páginas
Combina uma lista de páginas alocadas (LPA)
com uma lista de páginas livres (LPL).
LPA organiza todas as páginas que estão
sendo utilizadas na memória principal
LPL organiza todos os frames livres da memória principal,
Seleciona o frame em uso há mais tempo na memória
Simples e eficiente, sem o custo de outras implementações.
NRU (Not-Recently-Used)
Semelhante ao LRU, porém mais simples
É necessário um bit de referência (BR).
Indica se a página foi utilizada recentemente e está
presente em cada entrada da tabela de páginas.
torna-se mais eficiente se o bit de modificação for utilizado em conjunto com o bit de referência.
LRU (Least-Recently-Used)
Seleciona a página que está há mais tempo sem ser referenciada.
Cada página deve ter associado o
momento do último acesso ou existir uma lista ordenada
Pouco empregada na prática devido ao seu elevado custo de implementação.