Sistemas Operacionais

Aula 15: Memória Virtual: performance

Referências

E se encher a memória ?

Usamos a memória principal toda, mas acessos à páginas que não estão na memória continuam.

É necessária uma política de reposição de páginas.

Uma Otimização

Mas e se a página não tiver sido modificada ?

Análise de Políticas de Reposição

Nomenclatura: page: página virtual
frame: página física

Dada uma sequência de acessos à páginas, como o algoritmo se comporta ?

Sequência pode ser calculada:

Exemplo:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Política FIFO

Retira-se a página que está à mais tempo na memória

Por exemplo:

Sofre da anomalia de Belady:

As vezes, dando-se mais memória aumenta o número de page faults!

Política Ótima

Retira-se a página que não vai ser usada por mais tempo.

Política Least Recently Used

A política ótima olha para o futuro;

De modo similar podemos olhar para o passado e escolher para remoção aquela página que foi usada há mais tempo.

Exemplo:

``Basta'' ???

Política LRU

Implementação complicada:

Caro!
LRU não sofre da anomalia de Belady.

Aproximações de LRU

Muitos processadores fornecem um auxílio na implementação de LRU:

Usando recursos do hardware podemos implementar LRU-like muito mais eficiente:

Eficiente, mas e quando todas as páginas tiverem sido acessadas ?

Mais Bits de Referência

Podemos melhorar a precisão do método anterior:

Bytes de Referência

A página com menor valor do byte de referência pode ser removida.

O número de bits de história guardados pode variar.

Algoritmo da Segunda Chance

Fácil de implementar; Melhor que FIFO; mas...

Segunda Chance ao Segunda Chance

Um algoritmo segunda chance mais sofisticado leva em conta também o bit limpo/sujo da página:

Páginas podem ser:

Escolhe-se a página a remover na ordem 1 a 4.

Usado no Macintosh! (oh, oh... mau sinal...)

Outros Algoritmos

Implementação cara (muito embora aproximações sejam possíveis), e não aproximam a política ótima muito bem.

Apesar disto, alguns ``leading researchers'' resolveram implementá-las no Linux. Suas conclusões serão pu-blicadas no fim do semestre...

Modelo de Working-Set

A janela de trabalho é uma medida de localidade.

Working Set

Como definir D ?

Como alocar frames a processos ?

Informalmente, o working set de um processo define o número médio de frames alocadas a cada instante durante sua execução:

Quantos Processos rodar ?

O SO deve permitir a execução simultânea de até m processos de tal forma que a soma de seus working sets não seja maior do que o número de frames disponível.

E se houverem mais processos ?

Thrashing!

Neste caso cada processo terá disponível para si um número de frames menor do que seu working set.

localidade > disponibilidade

Ou seja, gasta-se mais tempo decidindo o que fazer do que fazendo...