A remoção de uma página ocorre quando a tabela de página está cheia e, em um acesso à memória, não encontramos a página desejada na tabela de páginas. Isto gera um page fault, que busca diretamente esta página na memória. Ao encontrá-la, esta página é carregada na tabela de páginas no lugar de uma outra página, como ilustrado abaixo. A escolha da página que irá sair da memória é o alvo de estudo deste tópico.
Pelo diagrama acima, podemos observar que a remoção de uma página deve ocorrer quando a memória estiver cheia e não encontrarmos a página na TLB.Os algoritmos são:
Algoritmo Ótimo:
Este algoritmo é apenas teórico. Foi proposto por Belady em 1966 e exemplifica a situação ideal, em que minimizamos a quantidade de faltas de página. A idéia do algoritmo é remover a página que levará mais tempo para ser acessada. Portanto, o algoritmo precisa ter conhecimento dos instantes ou intervalos de tempo em que a memória será acessada.
Como é impossível prever os instantes em que as informções serão exigidas, este algoritmo não é realizável na prática.
Por apresentar a melhor aproximação com o cenário ideal, este algoritmo é utilizado como referência para comparação com os demais algoritmos.
Algoritmo NRU:
Este algoritmo é simples para se entender e implementar, e apresenta uma performance que pode ser adequada.
Utilizamos 2 bits para classificar as páginas e, em seguida, removê-las de acordo com sua classificação. O primeiro bit é o de referência e o segundo bit refere-se à modificação. Setamos o bit de referência se a página é referenciada para leitura ou escrita. E setamos o bit de modificação quando modificamos a página.
Quando um dos bits é setado, ele permanece em 1 até que o sistema operacional o resete no software.
Em seguida, classificamos as páginas como:
-Classe 0: não referenciada, não modificada
-Classe 1: não referenciada, modificada
-Classe 2: referenciada, não modificada
-Classe 3: referenciada, modificada
Ao remover uma página, buscamos a página que possui o menor número de classe, de acordo com a classificação acima. Nesta busca, zeramos os bits de referência.
Algoritmo FIFO:
O algoritmo é implementado com o auxílio de uma fila. Utilizando a idéia de First In First Out, este algoritmo é simples de se entender e implementar. Ele apenas remove da memória, a página que foi carregada a mais tempo na memória.
Como este algoritmo não considera a frequência de uso das páginas, ele não reflete adequadamente as páginas que devem permanecer na memória, podendo resultar em perda de desempenho.
Um exemplo desta falta de adequação é observado no evento conhecido como Anomalia de Belady, em que a quantidade de faltas de página aumenta quando adicionamos memória.
Mais informações sobre a Anomalia de Belady podem ser obtidas em http://en.wikipedia.org/wiki/Belady%27s_anomaly.
Algoritmo da Segunda Chance:
Com o objetivo de adequar a fila às páginas acessadas com maior frequência, realizou-se uma alteração no Algoritmo FIFO.
Com o algoritmo da Segunda Chance, se uma página existente na memória for acessada, ela passa para o final da fila. Deste modo, as páginas que são frequentemente utilizadas não estarão no final da fila e não serão removidas.
Contudo, este algoritmo apresenta uma ineficiência, já que é necessário deslocar parte da fila, sempre que uma página pertencente a fila for acessada.
Algoritmo Clock:
Como solução para o problema de ineficiência encontrado no algoritmo de Segunda Chance, utilizamos o algoritmo Clock. Neste algoritmo, as páginas são mantidas em uma lista circular e controlados por um bit R.
Se o bit de controle indica R=0, então a página pode ser removida.
Se o bit de controle indica R=1, então colocamos R=0 e deslocamos o ponteiro.
Inserimos a nova página no local da página removida e deslocamos o ponteiro para a próxima da lista circular.
Algoritmo LRU:
O algoritmo Least Recently Used remove a página menos recentemente utilizada. Esta idéia surgiu da observação que páginas intensamente acessadas possuem maior probabilidade de serem acessadas novamente do que páginas que são pouco referenciadas.
O algoritmo LRU é realizável, mas não é barato. Para implementar o LRU, devemos manter uma lista ligada de todas as páginas na memória, com a página mais recentemente utilizada na frente da lista e as páginas menos recentemente utilizadas atrás na lista. Desse modo, a dificuldade reside em atualizar esta lista em todas as referências à memória.
Algoritmo WS:
Este algoritmo possui a mesma idéia do algoritmo de LRU. Ao invés de remover a página que foi utilizada menos recentemente, este algoritmo define um tempo de vida, tal que se a página não for referenciada por um tempo maior ou igual ao tempo de vida definido, a página pode ser removida da memória.
Cada página guarda o tempo de seu último acesso, que será utilizado para calcular seu tempo de vida, e o bit de referência R.
A cada acesso, temos 3 situações possíveis:
R = 1: setamos o tempo de último acesso para o tempo atual e setamos R=0
R = 0: se o tempo de vida desta página for maior que o tempo de vida definido pelo algoritmo, então removemos esta página, inserindo a nova página neste local. Se o tempo de vida desta página for menor do que o tempo de vida definido pelo algoritmo, então setamos R=1 e passamos para a próximoa página.
Esta situação pode ser observada pela seguinte figura:
Referencias:
http://en.wikipedia.org/wiki/Belady%27s_Min#Belady.27s_Algorithm
http://en.wikipedia.org/wiki/Page_replacement_algorithm
http://en.wikipedia.org/wiki/Cache_algorithms
Nenhum comentário:
Postar um comentário