O que você vai aprender
Explicar a paginação por demanda e o tratamento de uma falta de página.
Comparar algoritmos de substituição (FIFO, LRU, ótimo) e a anomalia de Belady.
Relacionar a hierarquia de memória e a localidade ao desempenho da cache.
Reconhecer o thrashing e por que paginação é evitada em tempo real.
Como rodar um programa maior que a RAM?
Você tem 8 GB de RAM, mas abre um editor de vídeo, um navegador com 40 abas e uma máquina virtual — somados, pedem 20 GB. Por que nada trava? Porque o SO mantém na RAM apenas as páginas realmente em uso e guarda o resto no disco, trazendo-as quando necessário.
A memória virtual é essa ilusão: cada processo enxerga um espaço de endereçamento gigante, e o SO, com a MMU, decide o que fica na RAM e o que dorme no disco. É a continuação direta da Aula 8 — agora os bits de presente/ausente entram em ação.
O que veremos nesta aula
por demanda→Falta de
página→Algoritmos de
substituição→Hierarquia
e cache
Veremos como o disco vira extensão da RAM, qual página remover quando a RAM enche, e por que a cache — outra camada da hierarquia — depende do mesmo princípio: a localidade.
Memória virtual e paginação por demanda
Paginação por demanda. Uma página só é carregada na RAM quando é efetivamente acessada — nunca antes.
No início, quase nenhuma página do processo está na RAM. Cada primeiro acesso a uma página dispara uma falta de página que a traz do disco. Programas grandes "ganham vida aos poucos".
O custo de uma falta de página
Uma falta de página (page fault) é barata de detectar (a MMU faz na hora), mas cara de resolver. O fluxo: a MMU gera exceção; o SO encontra a página no disco; se a RAM está cheia, escolhe uma vítima para despejar; lê a página nova; atualiza a tabela; reexecuta a instrução.
O gargalo é o disco. Um acesso à RAM leva ~100 ns; uma falta que toca um HDD leva milhões de nanossegundos. Por isso a taxa de faltas precisa ser baixíssima: até uma falta a cada milhão de acessos já degrada o desempenho perceptivelmente.
FIFO em ação (3 quadros)
Sequência de referências 1, 2, 3, 4, 1, 2, 5 com 3 quadros, usando FIFO (✗ = falta):
| Ref. | 1 | 2 | 3 | 4 | 1 | 2 | 5 |
|---|---|---|---|---|---|---|---|
| Quadro A | 1✗ | 1 | 1 | 4✗ | 4 | 4 | 5✗ |
| Quadro B | — | 2✗ | 2 | 2 | 1✗ | 1 | 1 |
| Quadro C | — | — | 3✗ | 3 | 3 | 2✗ | 2 |
São 7 faltas em 7 referências. A página mais antiga (a primeira a entrar) é sempre a primeira a sair, independentemente de estar em uso.
Passo a passo: tratando uma falta de página
Algoritmos de substituição
| Algoritmo | Critério | Observação |
|---|---|---|
| FIFO | A mais antiga sai | Simples; sofre a anomalia de Belady |
| LRU | A menos recentemente usada | Boa aproximação do ótimo; cara de implementar exata |
| Ótimo (OPT) | A que será usada mais tarde | Ideal teórico; irrealizável (exige ver o futuro) |
Por que LRU funciona e FIFO falha
O LRU aposta na localidade temporal: o que você usou há pouco, provavelmente usará de novo. Logo, remover a página menos recentemente usada costuma acertar. O LRU faz parte dos chamados algoritmos de pilha, que nunca sofrem a anomalia de Belady.
O FIFO ignora o uso: pune a página mais antiga mesmo que ela seja a mais quente. Por isso pode tomar péssimas decisões — e exibir a contraintuitiva anomalia de Belady. Na prática, SOs usam aproximações baratas do LRU, como o algoritmo do relógio (clock/segunda chance), que usa o bit de "acessado" da tabela de páginas.
A bancada e o depósito
A hierarquia de memória
| Nível | Latência típica | Capacidade | Gerido por |
|---|---|---|---|
| Registradores | ~0,3 ns | bytes | Compilador |
| Cache L1/L2/L3 | 1–40 ns | KB a dezenas de MB | Hardware |
| RAM | ~100 ns | GB | SO (MMU) |
| SSD | ~50–100 µs | TB | SO (swap/FS) |
| HDD | ~10 ms | TB | SO (swap/FS) |
A localidade salvando o desempenho
endereço→Dado vizinho/recente
provável→Está na cache
(hit)→Acesso
rapidíssimo
Thrashing e o conjunto de trabalho
Conjunto de trabalho (working set). Conjunto de páginas que um processo usa ativamente numa janela de tempo. Se a RAM não comporta os working sets somados, vem o thrashing.
A curva é traiçoeira: o desempenho cresce com mais processos até um pico e então despenca quando o thrashing começa. A defesa do SO é controlar o grau de multiprogramação — suspender processos para que os working sets caibam na RAM.
Verifique seu entendimento
Por que o algoritmo ótimo (OPT) é impossível de implementar em um SO real?
Por que RTOS desliga o swap
Em um servidor, uma falta de página ocasional é só uma pausa imperceptível. Em um sistema de tempo real que controla um airbag ou um marca-passo, ela seria fatal: uma página despejada para o disco e trazida de volta adiciona milissegundos imprevisíveis a uma operação que deveria levar microssegundos.
Por isso, sistemas de tempo real rígido geralmente desabilitam a paginação para disco (no Linux, usa-se mlockall para fixar páginas na RAM). Toda a memória crítica fica residente, garantindo latência limitada e determinística. Previsibilidade vence capacidade.
Confusões frequentes
• Achar que "mais quadros sempre reduzem faltas" — no FIFO, a anomalia de Belady mostra o contrário.
• Confundir falta de página (página no disco) com falta de TLB (tradução não cacheada, mas página na RAM).
• Pensar que LRU e ótimo são a mesma coisa — LRU olha o passado; ótimo olha o futuro.
• Tratar a cache como "gerida pelo SO" — as caches L1/L2/L3 são de hardware; o SO gere RAM e swap.
Como contar faltas sem errar
Revele a resposta
O que é a anomalia de Belady e por que LRU não sofre dela?
Revisão relâmpago
Para onde isso leva
Esta aula amarra hardware e SO de ponta a ponta:
- Os bits "ausente" e "dirty" vêm da tabela de páginas da Aula 8.
- O swap usa o disco da Aula 11; substituir e escrever de volta envolve E/S.
- A localidade reaparece na E/S com buffers (Aula 10) e na cache de disco.
- Desligar o swap é requisito do tempo real (Aula 12).
Resumo da aula
Atividade em grupo · Caçando faltas de página
Em trios, comparem algoritmos de substituição na mesma sequência.
Roteiro
- Usem a sequência de referências 7,0,1,2,0,3,0,4,2,3 com 3 quadros.
- Calculem o número de faltas para FIFO e LRU à mão.
- Confiram no simulador de substituição de páginas.
- Tentem reproduzir a anomalia de Belady no FIFO aumentando os quadros.
Mini-quiz · Aula 9
20 questões sobre esta aula. Escolha e veja a explicação na hora.
📌 Resumo — leve isto para a prova
- A memória virtual usa paginação por demanda; faltas trazem páginas do disco.
- FIFO sofre a anomalia de Belady; LRU e ótimo, não (algoritmos de pilha).
- A hierarquia de memória troca velocidade por capacidade/custo.
- A localidade torna cache e TLB eficazes; thrashing destrói desempenho e determinismo.
- Em tempo real, a paginação para disco é desabilitada para garantir prazos.