Como funciona a substituição de páginas (page replacement), e o que causa thrashing?

Question

IT Interview Practice · Accepted Answer

Quando a RAM física enche mas os processos precisam de mais páginas, o OS precisa **despejar (evict)** uma página residente para abrir espaço — escrevendo-a no **swap** (disco) se ela estiver suja (dirty). Qual página despejar é a decisão de **page replacement**, e errar nela destrói o desempenho.

## Políticas de substituição

O ótimo teórico é despejar a página que será usada mais adiante no futuro (**OPT de Bélády**) — impossível, já que você não vê o futuro. Então aproximamos com o **LRU (least recently used)**: despejar a página não usada há mais tempo. O LRU verdadeiro precisa de um timestamp a cada acesso (caro demais), então os kernels reais usam o **algoritmo clock (second-chance)**:

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

O clock dá resultados parecidos com LRU a um custo O(1). O Linux o refina ainda mais com **listas LRU active/inactive**.

## Working set e thrashing

O **working set** de um processo é o conjunto de páginas que ele usa ativamente dentro de uma janela de tempo. O paging funciona bem *desde que os working sets combinados caibam na RAM*. Quando não cabem:

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

O thrashing é um precipício, não uma ladeira: passe um pouco do limite e o throughput desaba porque quase todo acesso dá miss. Sintomas: CPU quase ociosa mas o I/O de disco saturado, e a latência explodindo.

## Corrigindo / evitando

- **Adicionar RAM** ou **reduzir a carga** (menos processos concorrentes) para os working sets caberem.
- O scheduler pode **suspender e fazer swap out** de processos inteiros para encolher a demanda (medium-term scheduling).
- O **OOM killer** do Linux é o último recurso — matar um processo em vez de entrar em thrash para sempre.
- Melhorar a **locality** para que o próprio working set seja menor.

## Por que isso importa

Isto amarra toda a história da memória e é uma pergunta senior favorita porque o thrashing é um modo de falha real em produção: um serviço que vai bem com N usuários cai do precipício em N+1 quando seu working set excede a RAM. Reconhecer a assinatura (paging pesado, disco saturado, CPU travada) e conhecer as alavancas (RAM, load shedding, locality — e que o swap transforma uma escassez de memória em uma catástrofe de latência) é a diferença entre diagnosticá-lo em minutos e ficar encarando uma máquina misteriosamente congelada.

Políticas de substituição

Working set e thrashing

Corrigindo / evitando

Por que isso importa

Perguntas relacionadas