¿Cómo funciona el reemplazo de páginas, y qué causa el thrashing?

Question

IT Interview Practice · Accepted Answer

Cuando la RAM física se llena pero los procesos necesitan más páginas, el OS debe **expulsar (evict)** una página residente para hacer sitio — escribiéndola en **swap** (disco) si está sucia (dirty). Qué página expulsar es la decisión de **page replacement**, y equivocarse arruina el rendimiento.

## Políticas de reemplazo

El óptimo teórico es expulsar la página que se usará más lejos en el futuro (**OPT de Bélády**) — imposible, ya que no puedes ver el futuro. Así que aproximamos **LRU (least recently used — la menos usada recientemente)**: expulsar la página que lleva más tiempo sin usarse. El LRU verdadero necesita un timestamp en cada acceso (demasiado costoso), así que los kernels reales usan el **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)
         ▲___________|
```

El clock da resultados parecidos a LRU con coste O(1). Linux lo refina aún más con **listas LRU active/inactive**.

## Working set y thrashing

El **working set** de un proceso es el conjunto de páginas que usa activamente dentro de una ventana de tiempo. El paging funciona bien *mientras los working sets combinados quepan en RAM*. Cuando no:

```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
```

El thrashing es un precipicio, no una pendiente: pásate un poco del límite y el throughput se desploma porque casi todo acceso hace miss. Síntomas: CPU casi ociosa pero I/O de disco saturada, y latencia disparándose.

## Cómo arreglarlo / evitarlo

- **Añade RAM** o **reduce la carga** (menos procesos concurrentes) para que los working sets quepan.
- El scheduler puede **suspender y hacer swap out** de procesos enteros para reducir la demanda (medium-term scheduling).
- El **OOM killer** de Linux es el último recurso — matar un proceso antes que hacer thrashing para siempre.
- Mejora la **locality** para que el propio working set sea más pequeño.

## Por qué es importante

Esto ata toda la historia de la memoria y es una pregunta senior favorita porque el thrashing es un modo de fallo real en producción: un servicio que va bien con N usuarios cae por un precipicio en N+1 cuando su working set excede la RAM. Reconocer la firma (paging intenso, disco saturado, CPU estancada) y conocer las palancas (RAM, load shedding, locality — y que el swap convierte una escasez de memoria en una catástrofe de latencia) es la diferencia entre diagnosticarlo en minutos y quedarse mirando una máquina misteriosamente congelada.

Políticas de reemplazo

Working set y thrashing

Cómo arreglarlo / evitarlo

Por qué es importante

Preguntas relacionadas