Hoe werkt page replacement, en wat veroorzaakt thrashing?

Question

IT Interview Practice · Accepted Answer

Wanneer fysiek RAM volloopt maar processen meer pages nodig hebben, moet het OS een resident page **evicten** om ruimte te maken — die naar **swap** (schijf) schrijvend als hij dirty is. Welke page te evicten is de **page replacement**-beslissing, en het verkeerd doen verwoest de performance.

## Replacement-policies

Het theoretische optimum is de page evicten die het verst in de toekomst gebruikt wordt (**Bélády's OPT**) — onmogelijk, want je kunt de toekomst niet zien. Dus benaderen we **LRU (least recently used)**: evict de page die het langst ongebruikt is. Echte LRU heeft een timestamp bij elke toegang nodig (te duur), dus echte kernels gebruiken het **clock (second-chance)-algoritme**:

```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 geeft LRU-achtige resultaten tegen O(1)-kosten. Linux verfijnt het verder met **active/inactive LRU-lijsten**.

## Working set en thrashing

De **working set** van een proces is de verzameling pages die het binnen een tijdvenster actief gebruikt. Paging werkt prima *zolang de gecombineerde working sets in RAM passen*. Wanneer dat niet zo is:

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

Thrashing is een klif, geen helling: ga een beetje over de limiet en de throughput stort in omdat bijna elke toegang mist. Symptomen: CPU bijna idle maar schijf-I/O verzadigd, en de latency explodeert.

## Het oplossen / vermijden

- **Voeg RAM toe** of **verlaag de belasting** (minder gelijktijdige processen) zodat de working sets passen.
- De scheduler kan hele processen **pauzeren en uitswappen** om de vraag te verkleinen (medium-term scheduling).
- De **OOM killer** van Linux is het laatste redmiddel — dood een proces liever dan voor altijd te thrashen.
- Verbeter de **locality** zodat de working set zelf kleiner wordt.

## Waarom het belangrijk is

Dit knoopt het hele geheugenverhaal samen en is een favoriete seniorvraag omdat thrashing een echte production-faalvorm is: een service die prima is bij N gebruikers valt van een klif bij N+1 wanneer zijn working set het RAM overschrijdt. De signatuur herkennen (zware paging, verzadigde schijf, stilgevallen CPU) en de hefbomen kennen (RAM, load shedding, locality — en dat swap een geheugentekort in een latency-catastrofe verandert) is het verschil tussen het in minuten diagnosticeren en staren naar een mysterieus bevroren machine.

Replacement-policies

Working set en thrashing

Het oplossen / vermijden

Waarom het belangrijk is

Gerelateerde vragen