Perguntas e Respostas sobre Alocação de Memória do SO # 3
Question:Quando ocorre uma falha de página? Explique várias estratégias / algoritmos de substituição de página.
Answer:Na técnica de gerenciamento de memória de paginação sob demanda, se uma página solicitada para execução não estiver presente na memória principal, ocorre uma falha de página. Para carregar a página solicitada na memória principal, um quadro de página livre é pesquisado na memória principal e alocado. Se nenhum quadro de página estiver livre, o gerenciador de memória terá que liberar um quadro trocando seu conteúdo para o armazenamento secundário e, assim, abrir espaço para a página necessária. Para trocar páginas, muitos esquemas ou estratégias são usados.
Várias estratégias / algoritmos de substituição de página
The Optimal Page Replacement Algorithm- Este algoritmo substitui a página que não será usada por um longo período de tempo. No momento em que ocorre a falha de página, algum conjunto de páginas fica na memória. Uma dessas páginas será referenciada na próxima instrução. Outras páginas podem não ser referenciadas até 10.100 ou talvez 1000 instruções. Essas informações podem ser armazenadas com cada página no PMT (Tabela do mapa da página).
P # base Deslocamento MISC 1 10 2 NADA 3 1000 ... 10 100 O algoritmo de página ideal simplesmente remove a página com o maior número de instruções, o que implica que ela será necessária em um futuro mais distante. esse algoritmo foi introduzido há muito tempo e é difícil de implementar porque requer conhecimento futuro do comportamento do programa. No entanto, é possível implementar a substituição de página ideal na segunda execução usando as informações de referência de página coletadas na primeira execução.
NRU(Not Recently Used) Page Replacement Algorithm- Este algoritmo requer que cada página tenha dois bits de status adicionais 'R' e 'M' chamados bit de referência e bit de mudança, respectivamente. O bit de referência (R) é automaticamente definido como 1 sempre que a página é referenciada. O bit de mudança (M) é definido como 1 sempre que a página é modificada. Esses bits são armazenados no PMT e atualizados a cada referência de memória. Quando ocorre uma falha de página, o gerenciador de memória inspeciona todas as páginas e as divide em 4 classes com base nos bits R e M.
Class 1: (0,0) - nem usado recentemente nem modificado - a melhor página para substituir.
Class 2: (0,1) - não usada recentemente, mas modificada - a página precisará ser escrita antes da substituição.
Class 3: (1,0) - usado recentemente, mas limpo - provavelmente será usado novamente em breve.
Class 4: (1,1) - usado e modificado recentemente - provavelmente será usado novamente e será necessário escrever antes de substituí-lo.
Este algoritmo remove uma página aleatoriamente da classe não vazia de menor número.
Vantagens:
É fácil de entender.
É eficiente para implementar.
FIFO (First in First out) Page Replacement Algorithm- É um dos algoritmos de substituição de página mais simples. A página mais antiga, que ficou mais tempo na memória, é escolhida e substituída. Este algoritmo é implementado com a ajuda da fila FIFO para manter as páginas na memória. Uma página é inserida na extremidade posterior da fila e substituída na frente da fila.
Na fig., O fio de referência é 5, 4, 3, 2, 5, 4, 6, 5, 4, 3, 2, 6 e há 3 quadros vazios. As primeiras 3 referências (5, 4, 3) causam falhas de página e são colocadas em quadros vazios. A próxima referência (2) substitui a página 5 porque a página 5 foi carregada primeiro e assim por diante. Após 7 falhas de página, a próxima referência é 5 e 5 já está na memória, portanto, nenhuma falha de página para esta referência. Da mesma forma para a próxima referência 4. As marcas + mostram o recebimento de uma página, enquanto o círculo mostra a página escolhida para remoção.
Vantagens
FIFO é fácil de entender.
É muito fácil de implementar.
Desvantagem
Nem sempre é bom em desempenho. Pode substituir uma página ativa para trazer uma nova e, portanto, pode causar uma falha de página dessa página imediatamente.
Outro efeito colateral inesperado é a anomalia FIFO ou anomalia de Belady. Essa anomalia diz que a taxa de falha de página pode aumentar à medida que o número de quadros de página alocados aumenta.
Por exemplo, a figura a seguir apresenta o mesmo rastreamento de página, mas com uma memória maior. Aqui, o número do quadro da página é 4.
Aqui, as falhas de página são 10 em vez de 9.
LRU(Least Recently Used) Algorithm- O algoritmo menos usado recentemente (LRU) substitui a página que não foi usada por um longo período de tempo. É baseado na observação de que as páginas que não foram usadas por muito tempo provavelmente permanecerão sem uso por muito tempo e serão substituídas.
Inicialmente, 3 quadros de página estão vazios. As primeiras 3 referências (7, 0, 1) causam falhas de página e são trazidas para esses quadros vazios. A próxima referência (2) substitui a página 7. Como a próxima referência de página (0) já está na memória, não há falha de página. Agora, para a próxima referência (3), a substituição LRU vê que, dos três quadros na memória, a página 1 foi usada menos recentemente e, portanto, é substituída. E assim o processo continua.
Vantagens
O algoritmo de substituição de página LRU é silenciosamente eficiente.
Não sofre da anomalia de Belady.
Desvantagens
Sua implementação não é muito fácil.
Sua implementação pode exigir assistência substancial de hardware.