O que você vai aprender
Explicar a paginação por demanda e a falta de página.
Aplicar os algoritmos de substituição FIFO, LRU e ótimo.
Reconhecer thrashing e o conceito de working set.
Rodar o que não cabe na RAM
Como um computador com 8 GB de RAM roda programas que, somados, pedem 20 GB? A resposta é a memória virtual: dar a cada processo a ilusão de uma memória enorme, usando o disco como extensão.
Quase nenhum processo usa todo o seu espaço de endereçamento de uma vez. A memória virtual aproveita isso para manter na RAM apenas as partes em uso, deixando o resto no disco.
O percurso da aula
demanda→Falta de
página→Substituição
(FIFO/LRU/ótimo)→Thrashing +
working set
Construímos a partir da paginação da aula 9: trazemos páginas só quando necessário, lidamos com a falta de página, escolhemos vítimas de substituição e diagnosticamos o thrashing.
Memória virtual e paginação por demanda
Paginação por demanda. Uma página só é trazida do disco quando, e se, for referenciada.
Cada entrada da tabela de páginas ganha um bit de validade: ligado se a página está na RAM, desligado se está só no disco.
O que acontece em um page fault
Quando o processo acessa uma página com bit inválido, ocorre uma falta de página (page fault):
à página→Bit válido?→Falta: buscar
no disco→Atualizar tabela
e continuar
FIFO sobre uma cadeia de referências
Cadeia 7, 0, 1, 2, 0, 3 com 3 quadros, algoritmo FIFO (F = falta):
Stepper: LRU passo a passo
Algoritmos de substituição
Um bom algoritmo minimiza as faltas de página futuras escolhendo bem a vítima.
FIFO, LRU e ótimo
| Algoritmo | Regra | Observação |
|---|---|---|
| FIFO | Remove a página mais antiga (que entrou primeiro) | Simples; sofre a anomalia de Belady |
| LRU | Remove a menos recentemente usada | Boa aproximação do ótimo; cara de implementar exata |
| Ótimo | Remove a que será usada mais tarde no futuro | Mínimo teórico de faltas; impossível na prática |
A mesa de estudo lotada
Mais quadros, mais faltas?
Intuitivamente, mais quadros deveriam dar menos faltas. No FIFO isso pode falhar: a anomalia de Belady mostra cadeias em que aumentar o número de quadros aumenta as faltas.
O ciclo de atendimento da falta
livre?→Não: escolher
vítima→Salvar vítima
(se suja) + carregar
Thrashing e working set
Working set. Conjunto de páginas que um processo usa ativamente em uma janela de tempo recente.
O thrashing surge quando há processos demais para quadros de menos: cada processo perde páginas do seu working set e gera faltas constantes. Reduzir o grau de multiprogramação alivia o problema.
Check: diagnóstico de thrashing
A CPU está quase ociosa, mas o disco trabalha sem parar e o sistema está lentíssimo. O que está acontecendo?
O servidor que travou ao abrir mais abas
Um servidor com pouca RAM roda bem com 10 processos. Ao subir para 40, a vazão despenca e a CPU fica em 5%. Diagnóstico: thrashing — os working sets somados não cabem na RAM.
Soluções: adicionar RAM, reduzir o número de processos simultâneos (controle do grau de multiprogramação) ou suspender processos para devolver quadros aos demais. O modelo do working set ajuda a decidir quantos processos cabem.
Armadilhas frequentes
- Achar que o LRU sofre a anomalia de Belady — ele não sofre (é algoritmo de pilha).
- Contar como acerto a primeira referência a uma página: a primeira é sempre falta.
- Confundir "menos recentemente usada" (LRU) com "mais antiga na memória" (FIFO).
- Pensar que o ótimo é implementável: ele exige conhecer o futuro das referências.
Para acertar as contas de faltas
- Desenhe os quadros após cada referência e marque F na falta.
- Para o ótimo, olhe à frente na cadeia e escolha a vítima cuja próxima utilização está mais longe.
- Para o LRU, mantenha a ordem de uso; para o FIFO, a ordem de entrada.
- Lembre: o ótimo dá sempre o menor número possível de faltas para a cadeia.
Reveal: por que LRU é caro?
Por que implementar LRU exato é custoso, e como o SO contorna isso?
Revisão relâmpago
Amarrando com o curso
- Gerência de memória (aula 9): a paginação é a base; aqui acrescentamos o disco como extensão.
- E/S e disco (aula 12): faltas de página geram acessos a disco; o escalonamento de disco importa.
- Escalonamento (aula 5): o grau de multiprogramação afeta diretamente o thrashing.
- Processos (aula 3): um processo em falta de página bloqueia esperando a E/S.
O essencial sobre memória virtual
Conte as faltas você mesmo
Use o simulador de substituição de páginas abaixo.
Informe uma cadeia de referências e o número de quadros, e compare FIFO, LRU e ótimo lado a lado. Conte as faltas de página de cada um e tente reproduzir a anomalia de Belady no FIFO aumentando os quadros.
Atividade em grupo · Contando faltas de página
Em grupos, apliquem os algoritmos de substituição à mão.
Roteiro
- Usem a cadeia de referências 7,0,1,2,0,3,0,4,2,3 com 3 quadros.
- Calculem o número de faltas para FIFO, LRU e ótimo.
- Comparem qual teve menos faltas e por quê.
- Confiram no simulador e tentem provocar a anomalia de Belady no FIFO.
Mini-quiz · Aula 10
20 questões sobre esta aula. Escolha e veja a explicação na hora.
📌 Resumo — leve isto para a prova
- Memória virtual executa processos maiores que a RAM usando o disco como extensão.
- Paginação por demanda traz páginas só quando referenciadas; faltas custam acesso a disco.
- FIFO (com anomalia de Belady), LRU (aproximável) e ótimo (referência teórica) escolhem a vítima.
- Algoritmos de pilha como LRU não sofrem a anomalia de Belady; o dirty bit evita gravações desnecessárias.
- Thrashing é paginação excessiva; manter o working set na RAM e controlar a multiprogramação o evitam.