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
Ótimo
seleciona para substituição uma página que não será mais referenciada no futuro ou aquela que levará o maior intervalo de tempo para ser novamente utilizada
utilizada apenas como modelo comparativo na análise de outros algoritmos de substituição
simulação para comparação com outros algoritmos
Aleatório
não utiliza critério algum de seleção
todas as páginas alocadas na memória principal têm a mesma chance de serem selecionadas, inclusive os frames que são frequentemente referenciados
raramente implementada,
devido a baixa eficiência
Objetivo
selecionar os frames que
tenham as menores chances de serem referenciados em um futuro próximo
caso contrário, o frame poderia retornar diversas vezes para a memória principal, gerando vários page faults e acessos à memória secundária
A partir do princípio da localidade
tenta prever o comportamento futuro das aplicações em função do comportamento passado, avaliando o número de vezes que uma página foi referenciada, o momento em que foi carregada para a memória principal e o intervalo de tempo da última referência
FIFO (First-In-First-Out)
seleciona a página que está há mais tempo na memória principal
LRU (Least-Recently-Used)
seleciona a página na memória principal que está há mais tempo sem ser referenciada
é necessário que cada página tenha associado o
momento do último acesso, que deve ser atualizado a cada referência a um frame
quando for necessário substituir uma página, o sistema fará uma busca por um frame que esteja há mais tempo sem ser referenciado
elevado custo de implementação
NRU (Not-Recently-Used)
semelhante ao LRU
Implementação
é necessário um bit adicional conhecido como bit de referência (BR)
O bit indica se a página foi utilizada recentemente e está presente em cada entrada da tabela de páginas
FIFO circular (clock)
utiliza como base o FIFO, porém as páginas alocadas na
memória estão em uma estrutura de lista circular, semelhante a um relógio
implementação
existe um ponteiro que guarda a posição da página mais antiga na lista, cada página possui associado um bit de referência, indicando se a página foi recentemente referenciada
quando é necessário substituir uma página, o sistema verifica se o frame apontado tem o bit de referência desligado
FIFO com buffer de páginas
combina uma lista de páginas alocadas (LPA)
com uma lista de páginas livres (LPL)
algoritmo de substituição de páginas simples e eficiente, sem o custo de outras implementações
LFU (Least-Frequently-Used)
seleciona a página menos referenciada
mantém um contador com o número de referências para cada página na memória principal
raramente implementado
