Qual o objetivo dos algoritmos de substituição de páginas?

O objetivo deste projeto é escrever um programa para simular os principais algoritmos de substituição de páginas usados no gerenciamento da memória virtual. O programa deverá simular os seguintes algoritmos:

• FIFO (First In, First Out)

• OPT (Algoritmo ótimo)

• LRU (Least Recently Used)

O programa deverá receber como parâmetro o número de quadros disponíveis na RAM e ler da entrada padrão (stdin) a sequência de referências às páginas (uma referência por linha), conforme o exemplo a seguir:

simula-vm 4 < referencias.txt

ou

cat referencias.txt | simula-vm 4

Neste exemplo, a memória RAM tem 4 quadros disponíveis e o arquivo referencias.txt contém as referências de acesso às páginas.

O programa deve gerar como saída o número de falta de páginas verificado para cada algoritmo, de acordo com o exemplo a seguir:

    4 quadros,      30 refs: FIFO:    17 PFs, LRU:    15 PFs, OPT:    11 PFs

Atenção: deve ser usada a string de formato abaixo para a impressão do resultado na tela. Não imprima mais nada além disso.

printf ("%5d quadros, %7d refs: FIFO: %5d PFs, LRU: %5d PFs, OPT: %5d PFs\n", ...) ;

Para testar seu código, use os seguintes arquivos, que correspondem às strings de referências usadas no livro do professor (capítulo V - Gerência de Memória):

• Arquivo 1, com resultados mostrados na figura 28 do livro.

• Arquivo 2, com resultados mostrados na figura 31 do livro.

• Arquivo 3, trecho de tracing de acessos à memória do compilador GCC (obtido e adaptado desta página). Este tracing tem 106 referências a 64K páginas. Os seguintes resultados são esperados para este teste:

QuadrosFIFOLRUOPT6438496304161837725698596270310710241450127312604096126012601260

Deve ser entregue ao professor o código-fonte em C do simulador (arquivo simula-vm.c), devidamente comentado.

Em um sistema operacional que usa paginação para gerenciamento de memória, um algoritmo de substituição de página é necessário para decidir qual página deve ser substituída quando uma nova página chega. 

Falha de página - Uma falha de página ocorre quando um programa em execução acessa uma página da memória mapeada no espaço de endereço virtual, mas não carregada na memória física. 

Como a memória física real é muito menor do que a memória virtual, ocorrem falhas de página. Em caso de falha de página, o sistema operacional pode ter que substituir uma das páginas existentes pela página recém-necessária. Diferentes algoritmos de substituição de página sugerem maneiras diferentes de decidir qual página substituir. O objetivo de todos os algoritmos é reduzir o número de falhas de página. 

Algoritmos de substituição de página: 

1. Primeiro a entrar, primeiro a sair (FIFO) - 
Este é o algoritmo de substituição de página mais simples. Nesse algoritmo, o sistema operacional rastreia todas as páginas da memória em uma fila, a página mais antiga está no início da fila. Quando uma página precisa ser substituída, a página na frente da fila é selecionada para remoção. 
Exemplo-1 Considere a sequência de referência de página 1, 3, 0, 3, 5, 6 com 3 quadros de página. Encontre o número de falhas de página. 

Inicialmente, todos os slots estão vazios, então quando 1, 3, 0 veio, eles são alocados para os slots vazios -> 3 falhas de página.  
quando chega o 3, ele já está na memória -> 0 falhas de página.  
Em seguida, 5 vem, não está disponível na memória, portanto, substitui o slot de página mais antigo, ou seja, 1. -> 1 Falha de página.  
6 vem, também não está disponível na memória, portanto, substitui o slot de página mais antigo, ou seja, 3 -> 1 Falha de página.  
Finalmente, quando 3 vêm, ele não está disponível, então substitui 0 1 falha de página 

Belady é anomalia - Belady é anomalia prova que é possível ter mais falhas de página quando se aumenta o número de quadros da página enquanto estiver usando o First In First Out algoritmo de substituição (FIFO) página. Por exemplo, se considerarmos a sequência de referência 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 e 3 slots, obteremos 9 falhas de página no total, mas se aumentarmos os slots para 4, temos 10 falhas de página.

2. Substituição de página ideal - 
neste algoritmo, as páginas são substituídas que não seriam usadas por um longo período de tempo no futuro. 
Exemplo-2: Considere as referências de página 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, com quadro de 4 páginas. Encontre o número de falha de página. 

Inicialmente, todos os slots estão vazios, então quando 7 0 1 2 são alocados para os slots vazios -> 4 falhas de página 
0 já está lá então -> 0 Falha de página.  
quando o 3 vier, ele tomará o lugar do 7 porque não será usado por muito tempo no futuro .—> 1 Falha de página.  
0 já existe, portanto -> 0 Falha de página. . 
4 ocorrerá em 1 -> 1 Falha de página. 

Agora, para a sequência de referência de página adicional -> 0 Falha de página porque eles já estão disponíveis na memória. 
A substituição ideal da página é perfeita, mas não é possível na prática, pois o sistema operacional não pode saber as requests futuras. O uso da substituição de página ideal é estabelecer um benchmark para que outros algoritmos de substituição possam ser analisados ​​em relação a ele.

3. Menos usado recentemente - 
Nesta página de algoritmo será substituída a que for usada menos recentemente. 
Exemplo-3 Considere a sequência de referência de página 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 com 4 quadros de página. Encontre o número de falhas de página. 

Inicialmente, todos os slots estão vazios, então quando 7 0 1 2 são alocados para os slots vazios -> 4 falhas de página, 
0 já é o seu então -> 0 Falha de página.  
quando veio 3, ele tomará o lugar de 7 porque é o menos usado recentemente -> 1 Falha de página 
0 já está na memória, então -> 0 Falha de página . 
4 ocorrerá em 1 -> 1 Falha de página 
Agora para a sequência de referência de página adicional -> 0 Falha de página porque eles já estão disponíveis na memória. 

Perguntas do GATE CS Corner 

Praticar as perguntas a seguir o ajudará a testar seus conhecimentos. Todas as perguntas foram feitas no GATE em anos anteriores ou nos testes de simulação GATE. É altamente recomendável que você os pratique.  

Qual é a finalidade dos algoritmos de substituição?

Qual é a utilidade dos algoritmos de substituição de páginas o que é o algoritmo ótimo?

Quais são os algoritmos de substituição de páginas?

Como é o funcionamento do algoritmo FIFO de substituição de páginas?