6. ALGORITMOS DE MUDANÇA DE PÁGINA
Quando é detectada uma falta de página, o SO deve escolher uma das páginas atualmente residentes na memória para ser removida, de forma a liberar um quadro de página para a colocação da página faltante. Devemos remover uma página não muito utilizada, pois caso contrário, teria em pouco tempo uma referência para a página e ocorreria um page-fault e a necessidade de recarregar esta página, além de escolher outra para ser removida. Métodos de escolha da página a ser removida:
1. Mudança Ótima de Página: o método consiste em determinar para cada página presente na memória, quantas instruções serão executadas antes que a página seja referenciada e retirar a página que for demorar mais tempo para ser novamente referenciada. Mas este método não pode ser implementado numa situação real, pois exigiria conhecimento de situações futuras, portanto é utilizado apenas em simulações, onde temos um controle completo das execuções dos processos, para fins de comparação de algum algoritmo com o algoritmo ótimo.
2. Mudança da Página não Recentemente Usada: esse método seleciona para retirar uma página que não tenha sido recentemente utilizada. Temos 2 bits associados a cada página na memória: R: indica se a página foi referenciada (lida) e M: indica se a página foi modificada (escrita). Quando é realizada uma referência à página, os bits são alterados automaticamente por hardware. Todos os bits são colocados em 0 quando uma página é carregada na memória. A cada tic tac do relógio, o SO coloca todos os bits R das páginas em 0, quando ocorre um page fault, temos as seguintes categorias de páginas:
- classe 0: R=0 e M=0
- classe 1: R=0 e M=1
- classe 2: R=1 e M=0
- classe 3: R=1 e M=1
Escolhe para ser retirada a página que pertencer a classe mais baixa, no momento da ocorrência do page fault. Vantagem é a simples implementação. Quando o hardware não possui os bits R e M, o SO pode simular esses bits através da utilização dos mecanismos de proteção de páginas, da seguinte forma: inicialmente marca-se todas as páginas como ausentes, e quando uma página é referenciada, é gerado um page fault então o SO marca essa página como presente, mas permite apenas leitura e também marca em uma tabela interna o bit R simulado para essa página. Quando uma escrita for tentada nessa página, uma interrupção de acesso inválido será gerada, e o SO poderá marcar a página como de leitura e escrita e também marca em uma tabela interna o bit M simulado para essa página.
3. Mudança da Página “Primeira a Entrar, Primeira a Sair”: neste caso mantém-se uma fila de páginas referenciadas. Ao entrar uma nova página, ela entra no fim da fila substituindo a que estava colocada no início da fila. O problema é que pode retirar páginas que apesar de estarem a muito tempo na memória, estão sendo amplamente utilizadas. Para resolver isso, utilizamos dois bits R e M e então: verifica os bits R e M da página mais antiga, se for classe 0 essa página é escolhida para ser retirada, senão, continua procurando na fila, se não achar nenhum classe 0 prossegue para as classes seguintes (1, 2 e 3). E outra solução seria o algoritmo conhecido como segunda chance: verifica o bit R da página mais velha se for zero, utiliza essa página, senão põe 0 em R e coloca a página no fim da fila e prossegue analisando a fila até encontrar uma página com R=0.
4. Mudança da Página Menos Recentemente Utilizada (LRU): páginas muito utilizadas nas instruções mais recentes provavelmente permanecerão muito utilizadas nas próximas instruções e páginas não utilizadas a tempo provavelmente não serão utilizadas por bastante tempo. Esse algoritmo consiste em: quando ocorre um page fault, retira a página que a mais tempo não é referenciada. O problema é a implementação dispendiosa (manter uma lista de todas as páginas na memória – as mais recentemente utilizadas no início – e a lista deve ser alterada a cada referência na memória) e esta implementação por software é inviável em termos de tempo de execução. Vejamos duas implementações por hardware:
1) Manter um contador C no processador que deve ser incrementado a cada instrução executada e cada entrada na tabela de páginas tem associado um campo e depois de cada referência a memória, o contador é armazenado na entrada correspondente à página referenciada; quando ocorre um page fault, escolhemos a página com o menor valor no campo de armazenamento do contador (a página que foi referenciada a mais tempo).
2) para n quadros de página, temos uma matriz n x n de bits: quando a página i é referenciada, colocamos em 1 todos os bits da linha i da tabela e logo após, colocamos em 0 todos os bits da coluna i da tabela; quando ocorre um page fault, retiramos a página que apresentar o menor número em sua linha.
5. Simulando LRU em software: desenvolveu-se uma aproximação para LRU chamada NFU (não freqüentemente utilizada), realizada por software da seguinte forma: um contador é mantido para cada página, a cada interrupção de relógio, o bit R correspondente a cada uma das páginas é somado a esse contador e quando ocorre um page fault, escolhe-se a página com menor valor nesse contador. O problema é que se uma página é intensivamente utilizada durante um certo tempo, ela tende a permanecer na memória, mesmo quando não for mais necessária (pois o contador adquiriu um valor alto). Para solucionar temos uma alteração – algoritmo de aging: os contadores são deslocados de 1 bit à direita antes de somar R, e R é somado ao bit mais significativo do contador. Temos duas diferenças em relação ao algoritmo de LRU: não consegue saber qual a referencia mais recente com intervalos menores que um tic tac e o número de bits é finito e quando chega a zero, não consegue distinguir as páginas mais antigas. Em geral 8 bits é suficiente para determinar que uma página não é mais necessária (uma página não referenciada a 9 tic tacs, não pode ser distinguida de uma não referenciada a 1000 tic tacs, neste caso).
6. Considerações de Projeto para Sistemas de Paginação
- Modelo de Conjunto Ativo (Working Set): Num sistema puro de paginação (paginação por demanda), o sistema começa sem nenhuma página na memória e elas vão sendo carregadas na medida em que forem necessárias. Podemos melhorar essa estratégia, para isso devemos considerar a existência na grande maioria dos processos de uma localidade de referências, isto é, os processos mantêm em cada uma das fases de sua execução, referências a frações pequenas do total do número de páginas necessárias a ele. Então surge o conceito de conjunto ativo, que é o conjunto de páginas correntemente em uso de um dado processo. Se todo o conjunto ativo de um processo estiver na memória principal, ele executará sem gerar page faults. Mas se não houver espaço para todo o conjunto ativo de um processo, este gerará muitos page faults, ocasionando a diminuição do seu tempo de execução devido a necessidade de constantes trocas de páginas entre memória e disco. Temos o conceito de thrashing que ocorre quando um processo gera muitos page faults em poucas instruções. Devemos determinar qual é o working set do processo e carregá-lo na memória antes de permitir a execução do processo. Este é o chamado modelo do conjunto ativo. Pré-paginação é o ato do carregamento adiantado das páginas (antes da ocorrência do page fault para as mesmas). Considerações com relação aos tamanhos dos working set: se a soma total dos working set de todos os processos residentes em memória é maior que a quantidade de memória disponível, então ocorre thrashing. (OBS: os processos residentes na memória são aqueles que o escalonador de baixo nível utiliza para a seleção do atualmente em execução. O escalonador em alto nível é o responsável pela troca dos processos residentes em memória a certo intervalo de tempo). Então devemos escolher os processos residentes em memória de forma que a soma de seus working set não seja maior que a quantidade de memória disponível. Para determinar quais as páginas de um processo que fazem parte de seu working set, pode-se utilizar o algoritmo de aging, considerando como parte do working set apenas as páginas que apresentarem ao menos um bit em 1 em seus primeiros n bits, isto é, qualquer página que não seja referenciada por n tic tacs consecutivos é retirada do working set do processo.
- Rotinas de Alocação Local X Global: vamos ver de que forma a memória será alocada entre os diversos processos executáveis que competem por ela. Alocação local: a quantidade de memória destinada a cada processo é fixa. Quando é gerado um page fault em um dado processo, retiramos uma das páginas do próprio processo, para a colocação da página requerida. Alocação global: a alocação de memória muda dinamicamente. Quando um page fault é gerado, escolhe para retirar uma das páginas da memória, não importa a qual processo ela esteja alocada. Os algoritmos globais apresentam maior eficiência, pois: se o working set de um processo aumenta, a estratégia local tende a gerar thrashing e se o working set de um processo diminui, a estratégia local tende a desperdiçar memória. Uma solução para o sistema decidir dinamicamente qual o tamanho do working set do processo em cada instante seria realizar a monitoração pelos bits de aging. O problema é que o working set de um processo pode mudar em pouco tempo, enquanto que as indicações de aging só mudam a cada tic tac do relógio. Uma solução melhor é a utilização de um algoritmo de alocação por freqüência de falta de página (PFF). Esta técnica é baseada no fato de que a taxa de falta de páginas para um dado processo decresce com o aumento do número de quadros de página alocados para esse processo.
- Tamanho da Página: considerações a favor de páginas pequenas: na média, metade da página final de qualquer segmento é desperdiçada (fragmentação interna); um programa que consista em processos pequenos pode executar utilizando menos memória quando o tamanho da página é pequeno. Considerações a favor de páginas grandes: quanto menor o tamanho da página, maior o tamanho da tabela de páginas; quando uma página precisa ser carregada na memória, temos um acesso ao disco, com os correspondentes tempos de busca e espera de setor, além do de transferência. Se já transferimos uma quantidade maior de bytes a cada acesso, diminuímos a influência dos dois primeiros fatores do tempo, aumentando a eficiência; se o processador central precisa alterar registradores internos referente à tabela de páginas a cada chaveamento de processo, então páginas maiores necessitarão menos registradores, o que significa menor tempo de chaveamento de processos.
- Considerações de implementação de Sistemas de Paginação: a seguir vamos ver os fatos que complicam um pouco o gerenciamento de Sistemas de Paginação:
i) Bloqueamento de Páginas na Memória: Quando um processo bloqueia aguardando a transferência de dados de um dispositivo para um buffer, um outro processo é selecionado para execução. Se este outro processo gera um page fault, existe a possibilidade de que a página escolhida para ser retirada seja justamente aquela onde se encontra o buffer que estava aguardando a transferência do dispositivo. Se o dispositivo tentar então transferir para esse buffer, ele pode estragar a nova informação carregada pelo page fault. Soluções para o problema: impedir que a página que contem o buffer seja retirada da memória; realizar as transferências de dispositivos sempre para buffers internos do kernel e, após terminada a transferência, destes para o buffer do processo.
ii) Páginas Compartilhadas: diversos processos podem estar, em um dado momento, utilizando o mesmo programa. Para evitar duplicação de informações na memória, é conveniente que essas informações comuns sejam armazenadas em páginas que são compartilhadas pelos processos que as utilizam. O problema é: algumas partes não podem ser compartilhadas como, por exemplo, os textos que estão sendo editados em um mesmo editor. A solução é saber quais as páginas que são apenas de leitura, permitindo que estas sejam compartilhadas e impedindo o compartilhamento das páginas que são de leitura e escrita. Um problema mais difícil de resolver seria: suponha dois processos A e B compartilhando o código de um editor e A termina a edição e portanto sai da memória algumas de suas páginas (as que correspondem ao código do editor) não poderão ser retiradas devido a serem compartilhadas, pois se isto ocorresse, seriam gerados muitos page fault para o processo B, o que representaria muita sobrecarga para o sistema; se um processo é enviado para o disco (swap) temos uma situação semelhante ao caso do término de um deles (como acima). A solução para isto é manter alguma forma de estrutura de dados que indique qual das páginas residentes estão sendo compartilhadas (este processo não é simples).