Sistemas Operacionais

Aula 15: Memória Virtual: performance

Referências

Capítulo 9: 9.5 a 9.7

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.

Escolha uma página vítima na memória principal;
Escreva-a no disco;
Use esta página para guardar a página referenciada recentemente.

É 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 ?

Implementa-se um bit limpo/sujo, inicialmente limpo.
Escritas à página tornam-a suja.
A página só é escrita no disco se estiver suja.

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:

Aleatoriamente
Através de monitoração da execução de programas reais.

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

Simples
Não muito eficiente.

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.

Não é factível
Mas, assim como SJF, pode ser aproximada...

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 guardar a hora de acesso à cada página e escolher aquela mais antiga.

``Basta'' ???

Política LRU

Implementação complicada:

Associa-se com cada item na tabela de páginas o tempo de acesso:
- A cada acesso incrementa-se-o;
- Quando uma página for removida, efetua-se uma busca na tabela de páginas.

Caro!

Outra implementação usa uma pilha de páginas:

LRU não sofre da anomalia de Belady.

Aproximações de LRU

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

Um bit de referência: setado quando a página é acessada.

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

Basta inicializar o bit de referência com 0 e deixar o hardware setá-lo quando a página for acessada.
Quando formos repor uma página, escolher uma com bit de referência 0.

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:

Guarde um byte para cada página na memória;
Periodicamente (e.g. a cada interrupção do relógio) SHR o byte de cada página e & o bit de referência no bit mais significativo:

Bytes de Referência

Desta forma uma página com byte de referência 00000000 não foi acessada nos últimos 8 ciclos;
Uma página com byte 11111111 foi acessada em todos os últimos 8 ciclos.

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

FIFO modificado;
Escolha uma página a ser removida usando FIFO;
Mas antes de remove-la veja seu bit de referência:
- Se for 0 (página não foi acessada), remova-a.
- Se for 1, zere-o e de uma segunda chance à pobre da página.

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

Pode degenerar para FIFO se todos os bits de referência estiverem setados.

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:

(sem ref., limpa): Não foi usada nem modificada, ótima para remover.
(sem ref., suja): Não foi usada mas sim modificada. Não tão boa quanto à anterior pois tem que gravar.
(ref, limpa): Foi usada, mas pelo menos não tem que ser escrita.
(ref., suja): Usada e tem que escrever; deixa por último.

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

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

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.

Define-se D, seu tamanho;
A janela de trabalho WS(t) consiste das últimas D referências a páginas de memória.
O tamanho médio do WS de um programa, dado D define o número de frames a ser alocado ao processo.

Working Set

Como definir D ?

Através de monitoração do comportamento de um conjunto de programas.

Como alocar frames a processos ?

Informalmente: assume-se que o processo vai usar n frames, mas não se garante.
Formalmente: Não permite a utilização de mais de n frames.

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

Ou seja, o processo vai usar, na média n/T % da memória principal.

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.

Desta forma todos os processos que estão executando o farão de forma ``confortá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.

Ou seja, haverão referências a páginas ausentes com frequência:

localidade > disponibilidade

Com isto o número de page faults aumenta significativamente, e a performance diminui.

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

Soa familiar ?