Come funziona il rimpiazzo delle pagine, e cosa causa il thrashing?

Question

IT Interview Practice · Accepted Answer

Quando la RAM fisica si riempie ma i processi hanno bisogno di più pagine, l'OS deve **sfrattare (evict)** una pagina residente per fare spazio — scrivendola su **swap** (disco) se è dirty. Quale pagina sfrattare è la decisione di **rimpiazzo delle pagine (page replacement)**, e sbagliarla rovina le performance.

## Politiche di rimpiazzo

L'ottimo teorico è sfrattare la pagina usata più lontano nel futuro (**OPT di Bélády**) — impossibile, dato che non puoi vedere il futuro. Quindi approssimiamo con **LRU (least recently used)**: sfratta la pagina non usata da più tempo. Il vero LRU richiede un timestamp a ogni accesso (troppo costoso), quindi i kernel reali usano l'**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)
         ▲___________|
```

Clock dà risultati simili a LRU con costo O(1). Linux lo affina ulteriormente con **liste LRU active/inactive**.

## Working set e thrashing

Il **working set** di un processo è l'insieme delle pagine che usa attivamente in una finestra temporale. Il paging funziona bene *finché la somma dei working set entra in RAM*. Quando non ci sta:

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

Il thrashing è un dirupo, non una discesa: supera di poco il limite e il throughput collassa perché quasi ogni accesso fa miss. Sintomi: CPU quasi inattiva ma I/O del disco saturo, e latenza che esplode.

## Correggerlo / evitarlo

- **Aggiungi RAM** o **riduci il carico** (meno processi concorrenti) così che i working set entrino.
- Lo scheduler può **sospendere e swap-out** interi processi per ridurre la domanda (medium-term scheduling).
- L'**OOM killer** di Linux è l'ultima risorsa — uccidere un processo piuttosto che fare thrash all'infinito.
- Migliora la **locality** così che il working set stesso sia più piccolo.

## Perché è importante

Questo lega insieme l'intera storia della memoria ed è una domanda senior prediletta perché il thrashing è un vero modo di fallimento in produzione: un servizio che va bene a N utenti cade dal dirupo a N+1 quando il suo working set supera la RAM. Riconoscere la firma (paging intenso, disco saturo, CPU in stallo) e conoscere le leve (RAM, load shedding, locality — e che lo swap trasforma una carenza di memoria in una catastrofe di latenza) è la differenza tra diagnosticarlo in pochi minuti e fissare una macchina misteriosamente congelata.

Politiche di rimpiazzo

Working set e thrashing

Correggerlo / evitarlo

Perché è importante

Domande correlate