Hvordan fungerer page replacement, og hva forårsaker thrashing?

Question

IT Interview Practice · Accepted Answer

Når fysisk RAM fylles opp men prosesser trenger flere pages, må OS-et **kaste ut (evict)** en resident page for å gjøre plass — og skrive den til **swap** (disk) hvis den er skitten (dirty). Hvilken page som skal kastes ut er beslutningen om **page replacement**, og å ta feil her ødelegger ytelsen.

## Utskiftingsstrategier

Det teoretiske optimum er å kaste ut pagen som brukes lengst inn i framtiden (**Béládys OPT**) — umulig, siden du ikke kan se framtiden. Så vi tilnærmer **LRU (least recently used)**: kast ut pagen som har vært ubrukt lengst. Ekte LRU trenger et tidsstempel ved hvert aksess (for kostbart), så virkelige kerneler bruker **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 gir LRU-lignende resultater til O(1)-kostnad. Linux forbedrer den ytterligere med **active/inactive LRU-lister**.

## Working set og thrashing

En prosess' **working set** er settet med pages den aktivt bruker innenfor et tidsvindu. Paging fungerer fint *så lenge de kombinerte working settene får plass i RAM*. Når de ikke gjør det:

```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 et stup, ikke en skråning: gå litt over grensen og throughputen kollapser fordi nesten hvert aksess bommer. Symptomer: CPU nær inaktiv, men disk-I/O mettet, og latency som eksploderer.

## Å fikse / unngå det

- **Legg til RAM** eller **reduser last** (færre samtidige prosesser) så working settene får plass.
- Scheduleren kan **suspendere og swappe ut** hele prosesser for å krympe etterspørselen (medium-term scheduling).
- Linux sin **OOM killer** er siste utvei — drep en prosess i stedet for å thrashe for alltid.
- Forbedre **locality** så selve working settet blir mindre.

## Hvorfor det er viktig

Dette knytter hele minnehistorien sammen og er et yndet senior-spørsmål fordi thrashing er en reell feilmodus i produksjon: en tjeneste som er grei ved N brukere faller utfor stupet ved N+1 når working settet overstiger RAM. Å kjenne igjen signaturen (tung paging, mettet disk, stanset CPU) og kjenne spakene (RAM, lastavlastning, locality — og at swap gjør en minnemangel om til en latency-katastrofe) er forskjellen mellom å diagnostisere det på minutter og å stirre på en mystisk frossen maskin.

Utskiftingsstrategier

Working set og thrashing

Å fikse / unngå det

Hvorfor det er viktig

Relaterte spørsmål