Seu navegador não oferece leitura em voz alta. Você pode ler o guia normalmente.
A memória virtual permite que um programa use mais memória do que a física disponível, mantendo na memória principal apenas as partes em uso e guardando o restante em disco. Em provas, o tema aparece de duas formas: conceitos (paginação, falta de página) e cálculo (quantas faltas ocorrem com determinado algoritmo de substituição). Todas as contagens abaixo foram conferidas por simulação.
Conceitos de base
- Paginação: o espaço de endereçamento do processo é dividido em blocos de tamanho fixo chamados páginas; a memória física é dividida em blocos do mesmo tamanho, as molduras (quadros ou frames).
- Tabela de páginas: mapeia cada página do processo à moldura em que está (ou indica que não está na memória).
- Falta de página (page fault): o processo referencia uma página que não está na memória. O sistema busca a página no disco, e se não houver moldura livre, escolhe uma página para retirar. É esse sorteio que os algoritmos de substituição disciplinam.
- Endereço lógico: composto de número da página e deslocamento dentro dela. A tradução usa a tabela de páginas; um cache de traduções, o TLB, acelera esse processo.
- Thrashing: quando há páginas de menos para o conjunto de trabalho, o sistema passa mais tempo trocando páginas do que executando.
Exemplo de tradução: com páginas de 1.024 bytes, o endereço lógico 3.000 está na página 2 (3.000 dividido por 1.024, parte inteira) com deslocamento 952 (3.000 menos 2 x 1.024).
Os três algoritmos
| Algoritmo | Critério para escolher a vítima |
|---|---|
| FIFO | a página que está há mais tempo na memória |
| LRU | a página menos recentemente usada |
| Ótimo (OPT) | a página que só será usada mais tarde (ou nunca); exige conhecer o futuro |
O ótimo serve de referência teórica: nenhum algoritmo realizável faz menos faltas. LRU aproxima o ótimo usando o passado como previsão do futuro; FIFO ignora o uso.
Exemplo resolvido: três molduras
Cadeia de referências: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 (12 acessos). Memória com 3 molduras, inicialmente vazia. “F” marca falta.
FIFO
| Acesso | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Falta? | F | F | - | F | F | F | F | - | F | - | F | F |
| Memória (da mais antiga à mais nova) | 2 | 2,3 | 2,3 | 2,3,1 | 3,1,5 | 1,5,2 | 5,2,4 | 5,2,4 | 2,4,3 | 2,4,3 | 4,3,5 | 3,5,2 |
Total: 9 faltas. No FIFO, acertos não alteram a ordem da fila.
LRU
| Acesso | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Falta? | F | F | - | F | F | - | F | - | F | F | - | - |
| Memória (da menos à mais recente) | 2 | 2,3 | 3,2 | 3,2,1 | 2,1,5 | 1,5,2 | 5,2,4 | 2,4,5 | 4,5,3 | 5,3,2 | 3,2,5 | 3,5,2 |
Total: 7 faltas. No LRU, um acerto move a página para a posição “mais recente”. É assim que o acesso ao 2 no terceiro passo o salva da retirada depois.
Ótimo
Total: 6 faltas. No acesso ao 5 (quinto passo), as páginas 2, 3 e 1 estão na memória; o 1 nunca mais é usado, então sai. Depois, ao chegar o 4, a página 2 será usada no futuro mais distante entre as candidatas que saem, e assim por diante.
| Algoritmo | Faltas |
|---|---|
| FIFO | 9 |
| LRU | 7 |
| Ótimo | 6 |
A ordem FIFO maior ou igual a LRU maior ou igual a ótimo é típica, mas nem sempre vale para FIFO versus LRU, como se vê a seguir.
Anomalia de Belady
Intuitivamente, mais molduras deveriam significar menos faltas. Com o FIFO, nem sempre. Com a cadeia 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, a simulação deu:
| Molduras | FIFO | LRU | Ótimo |
|---|---|---|---|
| 3 | 9 | 10 | 7 |
| 4 | 10 | 8 | 6 |
O FIFO piorou ao receber uma moldura a mais (de 9 para 10 faltas). Esse fenômeno é a anomalia de Belady. LRU e ótimo são algoritmos de pilha e não sofrem dela. Note também que, com 3 molduras, o FIFO (9) foi melhor que o LRU (10) nessa cadeia: a hierarquia FIFO pior que LRU não é lei.
Aproximações do LRU
LRU exato é caro de implementar, então os sistemas usam aproximações:
- Segunda chance (relógio): FIFO com um bit de referência; se a página mais antiga foi usada recentemente, ganha nova chance.
- NRU: classifica as páginas pelos bits de referência e de modificação.
- Envelhecimento: contadores que registram o uso recente.
Páginas modificadas (“sujas”) custam mais para retirar, pois precisam ser gravadas em disco antes.
Passo a passo para a prova
- Liste os acessos em colunas.
- Mantenha o conteúdo da memória após cada acesso.
- Marque falta apenas quando a página não estiver presente.
- Aplique a regra de vítima só quando todas as molduras estiverem cheias.
- Conte as faltas e confira com o número de colunas marcadas.
Erros comuns
- Contar o preenchimento inicial das molduras vazias como “sem falta”: cada primeira referência a uma página é uma falta.
- No LRU, esquecer de atualizar a recência quando há acerto.
- No FIFO, atualizar a ordem após um acerto.
- Achar que mais molduras sempre diminuem as faltas.
- Confundir a ordem de chegada com a ordem de uso.
Fontes e atualização
Não há norma oficial brasileira sobre sistemas operacionais; o conteúdo segue a literatura clássica. As contagens vieram da simulação das cadeias de referência indicadas. Confira no enunciado o estado inicial da memória e o critério de desempate.
Próximos passos
- Veja o processador em escalonamento: FCFS, SJF e Round Robin.
- Revise a memória em hardware e software: conceitos básicos.
- Entenda armazenamento em sistema binário, bits, bytes e unidades.