Hvordan fungerer page replacement, og hvad forårsager thrashing?

Question

IT Interview Practice · Accepted Answer

Når fysisk RAM fyldes op, men processer har brug for flere pages, må OS'et **smide en resident page ud (evict)** for at gøre plads — og skrive den til **swap** (disk), hvis den er dirty. Hvilken page der skal smides ud, er **page replacement**-beslutningen, og at ramme forkert ødelægger performance.

## Replacement-politikker

Det teoretiske optimum er at smide den page ud, der bruges længst ude i fremtiden (**Béládys OPT**) — umuligt, da man ikke kan se fremtiden. Så vi tilnærmer **LRU (least recently used)**: smid den page ud, der har været ubrugt længst. Ægte LRU kræver et tidsstempel ved hver adgang (for dyrt), så rigtige kerner bruger **clock- (second-chance-)algoritmen**:

```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 giver LRU-lignende resultater til O(1)-omkostning. Linux forfiner den yderligere med **active/inactive LRU-lister**.

## Working set og thrashing

En proces' **working set** er det sæt pages, den aktivt bruger inden for et tidsvindue. Paging fungerer fint, *så længe de samlede working sets kan være i RAM*. Når de ikke kan:

```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 er en klippe, ikke en skråning: gå lidt over grænsen, og throughput kollapser, fordi næsten hver adgang misser. Symptomer: CPU nær idle, men disk-I/O mættet, og latency eksploderer.

## At rette / undgå det

- **Tilføj RAM** eller **reducér belastningen** (færre samtidige processer), så working sets kan være der.
- Scheduleren kan **suspendere og swappe hele processer ud** for at mindske efterspørgslen (medium-term scheduling).
- Linux' **OOM killer** er sidste udvej — dræb en proces frem for at thrashe for evigt.
- Forbedr **locality**, så selve working set'et bliver mindre.

## Hvorfor det betyder noget

Dette binder hele hukommelseshistorien sammen og er et yndet seniorspørgsmål, fordi thrashing er en reel produktionsfejltilstand: en tjeneste, der er fin ved N brugere, falder ud over klippen ved N+1, når dens working set overstiger RAM. At genkende signaturen (tung paging, mættet disk, gået-i-stå CPU) og kende håndtagene (RAM, load shedding, locality — og at swap forvandler en hukommelsesmangel til en latency-katastrofe) er forskellen mellem at diagnosticere det på minutter og at stirre på en mystisk frossen maskine.

Replacement-politikker

Working set og thrashing

At rette / undgå det

Hvorfor det betyder noget

Relaterede spørgsmål