Aula 11 · U7 · Gerência de memória virtual

Objetivos da aula

O que você vai aprender

Explicar a paginação por demanda e calcular o custo de uma falta de página.

Simular FIFO, LRU e ótimo à mão e explicar 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.

1 · Motivação

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 10: lá a MMU detectava a falta de página; hoje vemos o que o SO faz com ela — e quanto ela custa.

2 · Analogia

A bancada e o depósito

🧰 Analogia

Sua bancada (RAM) cabe poucas ferramentas; o depósito no fundo (disco) guarda o resto. Quando precisa de uma ferramenta que está no depósito, você anda até lá (falta de página, lento) e, se a bancada está cheia, devolve alguma. Qual? Uma regra diz: a que está há mais tempo na bancada (FIFO) — mesmo que seja o martelo que você usa o dia todo. Outra diz: a que você não toca há mais tempo (LRU).

Na oficina	No computador
bancada: pouco espaço, tudo à mão	RAM, dividida em quadros
depósito no fundo: grande e longe	disco (a área de swap)
uma ferramenta	uma página
andar até o depósito	falta de página (page fault)
escolher o que devolver	algoritmo de substituição (escolhe a vítima)

Guarde esta tabela: boa parte da aula é uma dessas linhas vista de perto.

3 · Mapa

O que veremos nesta aula

Paginação
por demanda→Falta de página
e seu custo→Algoritmos de
substituição→Hierarquia
e localidade→Thrashing

Veremos como o disco vira extensão da RAM, quanto custa ir buscá-lo, qual página remover quando a RAM enche e por que tudo isso só funciona graças à localidade — o mesmo princípio da cache.

4 · Conceito

Memória virtual e paginação por demanda

Memória virtual. Ilusão de uma memória maior que a RAM física, mantendo no disco (área de swap) as páginas não usadas e trazendo-as sob 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".

Quem controla tudo isso são três bits de cada entrada da tabela de páginas, que você conheceu na Aula 10:

Página	Quadro	P · presente	M · modificada	A · acessada	Onde está
0	5	1	0	1	na RAM
1	—	0	—	—	no disco (swap)
2	2	1	1	0	na RAM, alterada
3	—	0	—	—	no disco (ainda não carregada)

P = 0 → acessar a página gera falta de página.
M = 1 → a página foi escrita; se for escolhida para sair, precisa ser gravada no disco antes. Com M = 0 basta descartá-la: a cópia do disco ainda vale.
A → o hardware liga a cada acesso; é o bit que o algoritmo do relógio usa para imitar o LRU.

5 · Interativo

Passo a passo: tratando uma falta de página

Passo 1 · hardware (MMU)

A CPU acessa um endereço cuja página tem P = 0. A MMU interrompe a instrução no meio e gera a exceção de falta de página.

Passo 2 · SO

O núcleo assume e confere se o acesso é válido — endereço fora do processo é erro (no Linux, falha de segmentação), não falta. Sendo válido, localiza a página no disco.

Passo 3 · SO

Se não há quadro livre, o algoritmo de substituição escolhe uma página vítima — o assunto do resto da aula.

Passo 4 · SO + disco

Se a vítima tem M = 1, ela é gravada no disco primeiro; com M = 0, é só descartada. Enquanto o disco trabalha, o processo fica bloqueado e a CPU atende outro.

Passo 5 · SO + disco

A página nova é lida para o quadro, a entrada passa a ter P = 1 e o número do quadro, e a instrução que falhou é executada de novo — o programa nem percebe.

6 · Explicação

O custo de uma falta de página

Detectar a falta é barato (a MMU faz na hora); resolver é caro, porque quase sempre envolve o disco. Para medir o estrago usa-se o tempo efetivo de acesso (EAT, de effective access time) — a mesma ideia da conta da TLB na Aula 10:

EAT = (1 − p) × t_RAM + p × t_falta
p = fração dos acessos que dão falta (adimensional, de 0 a 1) · t_RAM = tempo de um acesso à RAM (ns) · t_falta = tempo para tratar uma falta, dominado pelo disco (ns).

Com valores típicos — t_RAM = 100 ns, falta em HDD ≈ 10 ms = 10.000.000 ns, falta em SSD ≈ 100 µs = 100.000 ns:

Taxa de faltas p	Swap em HDD	Swap em SSD
1 em 1.000	≈ 10.100 ns — 101× mais lento	≈ 200 ns — 2× mais lento
1 em 100.000	≈ 200 ns — 2× mais lento	≈ 101 ns — 1% mais lento
1 em 1.000.000	≈ 110 ns — 10% mais lento	≈ 100,1 ns — 0,1% mais lento

A conta da primeira linha (HDD): 0,999 × 100 + 0,001 × 10.000.000 = 99,9 + 10.000 ≈ 10.100 ns.

🔑

Leia a primeira linha devagar: uma falta a cada mil acessos deixa a memória cerca de 100 vezes mais lenta num HDD. Para perder menos de 10%, a taxa precisa ficar abaixo de 1 em 1 milhão. É por isso que a escolha da vítima importa tanto — e por isso o swap em SSD dói bem menos.

7 · Conceito

Algoritmos de substituição

Substituição de páginas. Política que decide qual página remover da RAM quando é preciso espaço para uma nova. O objetivo é minimizar o número total de faltas de página.

A diferença entre os algoritmos está no que cada um consulta para escolher a vítima:

Algoritmo	O que consulta	Quem sai	Observação
FIFO	a ordem de chegada	a que entrou primeiro	Simples; ignora o uso e sofre a anomalia de Belady
LRU	o último uso (passado)	a usada há mais tempo	Boa aproximação do ótimo; cara de implementar exata
Ótimo (OPT)	o próximo uso (futuro)	a que vai demorar mais para voltar	Ideal teórico; irrealizável — serve de régua
Relógio (segunda chance)	o bit A	a primeira com A = 0, girando em círculo; quem tem A = 1 ganha outra chance (A volta a 0)	Aproximação barata do LRU, usada na prática

8 · Exemplo

Os três algoritmos na mesma cadeia

Cadeia 1, 2, 3, 1, 4, 1, 2, 4, 5, 4 com 3 quadros. Repare na página 1: é a mais usada — o martelo da analogia. Em cada coluna, em negrito, a página que acabou de entrar (✗ = falta) ou que acabou de ser usada (✓ = acerto).

FIFO — 8 faltas

Posição	1	2	3	4	5	6	7	8	9	10
Pede a página	1	2	3	1	4	1	2	4	5	4
Quadro 1	1✗	1	1	1✓	4✗	4	4	4✓	5✗	5
Quadro 2	—	2✗	2	2	2	1✗	1	1	1	4✗
Quadro 3	—	—	3✗	3	3	3	2✗	2	2	2
Sai	—	—	—	—	1	2	3	—	4	1

O momento decisivo é a posição 5: o FIFO expulsa a página 1, que tinha acabado de ser usada na posição 4, só porque ela foi a primeira a chegar. Na posição 6 ela é pedida de novo: falta. Para o FIFO, o acerto da posição 4 não mudou nada.

Agora é a sua vez: faça o LRU e o ótimo no papel e só depois abra.

LRU — quantas faltas? (abra depois de tentar)

LRU — 6 faltas

Posição	1	2	3	4	5	6	7	8	9	10
Pede a página	1	2	3	1	4	1	2	4	5	4
Quadro 1	1✗	1	1	1✓	1	1✓	1	1	5✗	5
Quadro 2	—	2✗	2	2	4✗	4	4	4✓	4	4✓
Quadro 3	—	—	3✗	3	3	3	2✗	2	2	2
Sai	—	—	—	—	2	—	3	—	1	—

Na posição 5 o LRU olha o último uso: 2 (pos. 2), 3 (pos. 3), 1 (pos. 4). Sai a 2 — e a página 1 fica, por isso a posição 6 é acerto.

Ótimo — quantas faltas? (abra depois de tentar)

Ótimo — 5 faltas

Posição	1	2	3	4	5	6	7	8	9	10
Pede a página	1	2	3	1	4	1	2	4	5	4
Quadro 1	1✗	1	1	1✓	1	1✓	1	1	5✗	5
Quadro 2	—	2✗	2	2	2	2	2✓	2	2	2
Quadro 3	—	—	3✗	3	4✗	4	4	4✓	4	4✓
Sai	—	—	—	—	3	—	—	—	1	—

Na posição 5 o ótimo olha o futuro: a 1 volta na posição 6, a 2 na 7 e a 3 nunca mais. Sai a 3. Nenhum algoritmo faz menos de 5 faltas nesta cadeia — mas, para isso, foi preciso conhecer o futuro.

💡

Placar com 3 quadros: FIFO 8 · LRU 6 · ótimo 5. Digite a mesma cadeia na bancada abaixo e use ▶ próximo passo: ela escreve o raciocínio de cada decisão.

9 · Explicação

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 (segunda chance), que usa o bit A da tabela de páginas.

Como usar a bancada: avance com ▶ e, a cada falta, leia o que o algoritmo consultou. Troque de algoritmo no meio do caminho — o passo é mantido, e você compara as escolhas no mesmo ponto da cadeia. Clicar numa coluna leva direto àquele passo.

10 · Aprofundamento

A anomalia de Belady em números

Intuição: mais memória, menos faltas. Quase sempre é verdade — mas não para o FIFO. Na cadeia 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5:

Quadros	FIFO	LRU	Ótimo
3	9	10	7
4	10 ⚠️ subiu	8	6

Com um quadro a mais, o FIFO passou de 9 para 10 faltas. Essa é a anomalia de Belady. LRU e ótimo só melhoram com mais quadros.

⚠️

Repare também: com 3 quadros, nesta cadeia o LRU (10) perde para o FIFO (9). A cadeia é um ciclo sem localidade — justamente o caso em que a aposta do LRU falha. Nenhum algoritmo realizável vence em toda cadeia; só o ótimo, que olha o futuro.

Na bancada acima, clique em 🧪 cadeia da anomalia de Belady: a tabela "Mais quadros, menos faltas?" mostra a subida. O porquê está na seção "Revele a resposta", mais adiante.

11 · Comparação

A hierarquia de memória

Nível	Latência típica	Se 1 ns fosse 1 segundo	Capacidade	Gerido por
Registradores	~0,3 ns	0,3 s — um piscar de olhos	bytes	Compilador
Cache L1/L2/L3	1–40 ns	1 a 40 s	KB a dezenas de MB	Hardware
RAM	~100 ns	1 min 40 s	GB	SO (MMU)
SSD	~50–100 µs	14 a 28 horas	TB	SO (swap/FS)
HDD	~10 ms	quase 4 meses	TB	SO (swap/FS)

💡

Os degraus não são iguais: da RAM para o SSD o tempo se multiplica por 500 a 1.000, e do SSD para o HDD por mais 100 a 200. Na escala humana, uma falta de página em HDD é esperar quatro meses por algo que, na RAM, levaria menos de dois minutos. Cada nível de baixo é maior e mais barato por byte; a arte é manter os dados quentes nos níveis de cima.

12 · Exemplo

A localidade na prática: percorrer uma matriz

Acesso a
endereço→Dado vizinho/recente
provável→Está na cache
(hit)→Acesso
rapidíssimo

🔑

A cache só funciona por causa da localidade: temporal (o que foi usado tende a ser reusado) e espacial (vizinhos tendem a ser usados juntos). É o mesmo princípio que faz a TLB, o LRU e o swap funcionarem.

Os dois trechos abaixo fazem exatamente as mesmas 16,8 milhões de somas (4096 × 4096); só muda a ordem:

// int m[4096][4096]; 64 MB — em C, guardada linha após linha // A: por linha for (i = 0; i < N; i++) for (j = 0; j < N; j++) soma += m[i][j]; // B: por coluna for (j = 0; j < N; j++) for (i = 0; i < N; i++) soma += m[i][j];

A: m[i][j] e m[i][j+1] são vizinhos na memória (4 bytes). Cada linha de cache de 64 bytes traz 16 inteiros que serão usados em seguida, e cada página de 4 KB atende 1.024 acessos seguidos.
B: cada acesso pula uma linha inteira da matriz (4096 × 4 B = 16 KB). Cai em outra linha de cache e em outra página a cada passo — a cache e a TLB quase não acertam.

Medido num PC com Intel Core i7-2600 (Linux, gcc -O1): A levou 0,01 s e B, 0,24 s — cerca de 20 vezes mais lento. O número muda de máquina para máquina e com o compilador (sem otimização, -O0, a diferença ficou em cerca de 6 vezes), mas, numa matriz maior que a cache, a versão por coluna perde.

Programa completo para medir no seu computador

#include <stdio.h> #include <time.h> #define N 4096 static int m[N][N]; /* 64 MB */ static double agora(void){ struct timespec t; clock_gettime(CLOCK_MONOTONIC,&t); return t.tv_sec+t.tv_nsec/1e9; } int main(void){ for(int i=0;i<N;i++) for(int j=0;j<N;j++) m[i][j]=i+j; /* toca tudo antes de medir */ long soma=0; double t0; t0=agora(); for(int i=0;i<N;i++) for(int j=0;j<N;j++) soma+=m[i][j]; printf("por linha : %.3f s\n",agora()-t0); t0=agora(); for(int j=0;j<N;j++) for(int i=0;i<N;i++) soma+=m[i][j]; printf("por coluna: %.3f s\n",agora()-t0); printf("(soma=%ld)\n",soma); /* usa a soma: o compilador não pode jogar os laços fora */ return 0; }

Compile com gcc -O1 matriz.c -o matriz e rode ./matriz algumas vezes.

13 · Aprofundamento

Thrashing e o conjunto de trabalho

Thrashing. Estado em que há páginas demais competindo por pouca RAM: o sistema passa mais tempo paginando (movendo páginas entre RAM e disco) do que executando trabalho útil.
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.

O thrashing se alimenta sozinho:

RAM curta para
os working sets→Muitas
faltas→Processos esperando
o disco; CPU ociosa→Escalonador ingênuo
admite mais processos→Ainda menos RAM
por processo

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.

14 · Interativo

Verifique seu entendimento

Na cadeia 1, 2, 3, 1, 4, 1… com 3 quadros, por que o FIFO teve falta na posição 6?

O FIFO só olha a ordem de chegada. A página 1 chegou primeiro, então saiu primeiro — o uso na posição 4 não conta. O LRU, na mesma situação, mantém a página 1 e acerta a posição 6.

Por que o algoritmo ótimo (OPT) é impossível de implementar em um SO real?

OPT remove a página cujo próximo uso está mais distante no futuro. Como o SO não conhece o futuro do programa, OPT serve apenas como referência teórica para comparar os algoritmos reais.

15 · Caso prático

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.

Em muitos microcontroladores a questão nem se coloca: sem MMU não há memória virtual nem o que paginar — só a proteção por regiões da MPU, vista na Aula 10.

16 · Erros comuns

Confusões frequentes

⚠️

Erros comuns nesta aula:
• Achar que "mais quadros sempre reduzem faltas" — no FIFO, a anomalia de Belady mostra o contrário.
• Achar que um acerto mexe na fila do FIFO — não mexe; só o LRU reordena a cada uso.
• 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.

17 · Dicas

Como contar faltas sem errar

✅

Ao simular substituição à mão: desenhe uma coluna por referência e uma linha por quadro, como nas tabelas desta aula. Marque a falta (✗) toda vez que a página pedida não estiver em nenhuma linha; a nova página ocupa a linha da vítima. Para FIFO, mantenha a fila da ordem de chegada (acerto não mexe nela); para LRU, anote a posição do último uso de cada página; para o ótimo, procure à frente na cadeia quando cada página volta. Confira na bancada com ▶ próximo passo — ela escreve o raciocínio de cada passo e revela rapidamente seus erros de contagem.

18 · Interativo

Revele a resposta

O que é a anomalia de Belady e por que LRU não sofre dela?

A anomalia de Belady é o fenômeno em que aumentar o número de quadros aumenta o número de faltas no FIFO — o oposto do esperado. Ela ocorre porque o FIFO não respeita a propriedade de inclusão: o conjunto de páginas com N quadros não é necessariamente subconjunto do conjunto com N+1 quadros. LRU e OPT são "algoritmos de pilha": garantem essa inclusão, então mais quadros nunca pioram, e a anomalia jamais aparece.

19 · Flashcards

Revisão relâmpago

Paginação por demandavirar

A página só é trazida à RAM quando efetivamente acessada.

Anomalia de Beladyvirar

No FIFO, mais quadros podem aumentar as faltas; LRU e OPT não sofrem disso.

Localidadevirar

Temporal (reuso do recente) e espacial (uso de vizinhos); base de cache, TLB e LRU.

Thrashingvirar

Páginas demais, RAM de menos: o sistema pagina mais do que computa.

Working setvirar

Conjunto de páginas ativamente usadas numa janela de tempo.

Relógio (segunda chance)virar

Aproxima o LRU com o bit A: quem tem A = 1 ganha outra chance; sai a primeira com A = 0.

EATvirar

(1 − p) × t_RAM + p × t_falta. Uma falta em mil, com HDD, deixa a memória ~100× mais lenta.

20 · Conexões

Para onde isso leva

Esta aula amarra hardware e SO de ponta a ponta:

Os bits P, M e A e a própria falta de página vêm da tabela de páginas e da MMU da Aula 10.
O swap mora no disco da Aula 12: HDD × SSD e a ordem das requisições pesam no custo de cada falta.
A localidade reaparece na E/S com buffers e cache de disco (Aula 13).
Desligar o swap é requisito do tempo real, cujo escalonamento você viu na Aula 9 e que a Aula 13 aprofunda.

21 · Síntese

Resumo da aula

🔑

A memória virtual usa paginação por demanda: páginas só entram na RAM quando acessadas, e o disco serve de extensão. Cada falta custa caro — uma em mil, com HDD, deixa a memória ~100× mais lenta. Quando a RAM enche, um algoritmo de substituição escolhe a vítima — FIFO (simples, ignora o uso, sofre Belady), LRU (olha o passado e aproxima o ótimo), ótimo (olha o futuro; só serve de régua) ou relógio (a aproximação usada na prática). A hierarquia de memória troca velocidade por capacidade, e a localidade torna cache e TLB eficazes. Thrashing arruína o desempenho; em tempo real, a paginação para disco é proibida.

Mão na massa · colaborativo

Atividade em grupo · Caçando faltas de página

Em trios, comparem algoritmos de substituição na mesma sequência.

⏱️ 25 min👥 trios🧩 laboratório

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.

FIFOrastreia a fila de páginas

LRUrastreia o uso recente

Conferentevalida no simulador

📤 Entrega: Contagem de faltas para FIFO e LRU + um exemplo de anomalia de Belady.

Teste seu conhecimento

Mini-quiz · Aula 11

20 questões sobre esta aula. Escolha e veja a explicação na hora.

0/20

📌 Resumo — leve isto para a prova

A memória virtual usa paginação por demanda; faltas trazem páginas do disco.
EAT = (1 − p) × t_RAM + p × t_falta: uma falta em mil, com HDD, deixa a memória ~100× mais lenta.
FIFO olha a chegada, LRU o passado, o ótimo o futuro; 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.