Wie funktioniert Page Replacement und was verursacht Thrashing?

Question

IT Interview Practice · Accepted Answer

Wenn der physische RAM sich füllt, Prozesse aber mehr Pages brauchen, muss das OS eine residente Page **verdrängen (evict)**, um Platz zu schaffen — und sie in den **Swap** (Disk) schreiben, falls sie dirty ist. Welche Page verdrängt wird, ist die **Page-Replacement**-Entscheidung, und sie falsch zu treffen ruiniert die Performance.

## Replacement-Strategien

Das theoretische Optimum ist, die Page zu verdrängen, die am weitesten in der Zukunft benutzt wird (**Béládys OPT**) — unmöglich, da man die Zukunft nicht sehen kann. Also nähern wir **LRU (Least Recently Used)** an: die Page verdrängen, die am längsten unbenutzt ist. Echtes LRU braucht einen Timestamp bei jedem Zugriff (zu teuer), daher verwenden echte Kernel den **Clock- (Second-Chance-)Algorithmus**:

```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 liefert LRU-ähnliche Ergebnisse zu O(1)-Kosten. Linux verfeinert es weiter mit **Active/Inactive-LRU-Listen**.

## Working Set und Thrashing

Das **Working Set** eines Prozesses ist die Menge der Pages, die er innerhalb eines Zeitfensters aktiv nutzt. Paging funktioniert gut, *solange die kombinierten Working Sets in den RAM passen*. Wenn nicht:

```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 ist eine Klippe, kein Hang: geh ein wenig über das Limit, und der Throughput bricht zusammen, weil fast jeder Zugriff einen Miss verursacht. Symptome: CPU nahe Leerlauf, aber Disk-I/O gesättigt, und die Latenz explodiert.

## Beheben / Vermeiden

- **RAM hinzufügen** oder **Last reduzieren** (weniger gleichzeitige Prozesse), damit die Working Sets passen.
- Der Scheduler kann ganze Prozesse **suspendieren und auslagern (swap out)**, um die Nachfrage zu verkleinern (Medium-Term Scheduling).
- Der **OOM Killer** von Linux ist der letzte Ausweg — einen Prozess killen, statt für immer zu thrashen.
- **Lokalität** verbessern, sodass das Working Set selbst kleiner wird.

## Warum es wichtig ist

Dies verbindet die gesamte Speichergeschichte und ist eine beliebte Senior-Frage, weil Thrashing ein echter Produktions-Fehlermodus ist: ein Service, der bei N Nutzern in Ordnung ist, stürzt bei N+1 von der Klippe, sobald sein Working Set den RAM überschreitet. Die Signatur zu erkennen (starkes Paging, gesättigte Disk, stockende CPU) und die Stellhebel zu kennen (RAM, Load Shedding, Lokalität — und dass Swap einen Speichermangel in eine Latenzkatastrophe verwandelt) ist der Unterschied zwischen einer Diagnose in Minuten und dem ratlosen Anstarren einer mysteriös eingefrorenen Kiste.

Replacement-Strategien

Working Set und Thrashing

Beheben / Vermeiden

Warum es wichtig ist

Ähnliche Fragen