Kako deluje zamenjava strani (page replacement) in kaj povzroča thrashing?

Question

IT Interview Practice · Accepted Answer

Ko se fizični RAM napolni, procesi pa potrebujejo več strani, mora OS **izgnati (evict)** rezidenčno stran, da naredi prostor — in jo zapisati v **swap** (disk), če je umazana (dirty). Katero stran izgnati, je odločitev **zamenjave strani (page replacement)**, in če jo zgrešimo, uničimo zmogljivost.

## Politike zamenjave

Teoretični optimum je izgnati stran, ki bo uporabljena najdlje v prihodnosti (**Béládyjev OPT**) — nemogoče, ker prihodnosti ne moremo videti. Zato približamo **LRU (least recently used — najdlje neuporabljena)**: izženi stran, ki je bila najdlje neuporabljena. Pravi LRU potrebuje časovni žig ob vsakem dostopu (predrago), zato resnični kerneli uporabljajo **algoritem 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 daje LRU-podobne rezultate s ceno O(1). Linux ga dodatno izboljša z **aktivnimi/neaktivnimi seznami LRU**.

## Working set in thrashing

**Working set** procesa je nabor strani, ki jih dejavno uporablja v časovnem oknu. Paging deluje v redu, *dokler se skupni working seti prilegajo v RAM*. Ko se ne:

```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 je pečina, ne klanec: prekorači mejo za malo in throughput se sesuje, ker skoraj vsak dostop zgreši. Simptomi: CPU skoraj v prostem teku, a diskovni V/I nasičen, in latenca eksplodira.

## Kako ga popraviti / se mu izogniti

- **Dodaj RAM** ali **zmanjšaj obremenitev** (manj sočasnih procesov), da se working seti prilegajo.
- Scheduler lahko **ustavi in izloči (swap out)** cele procese, da zmanjša povpraševanje (srednjeročno razvrščanje).
- Linuxov **OOM killer** je zadnja možnost — ubij proces, namesto da bi večno thrashal.
- Izboljšaj **lokalnost (locality)**, da je working set sam manjši.

## Zakaj je to pomembno

To poveže celotno zgodbo o pomnilniku in je priljubljeno senior vprašanje, ker je thrashing resničen način odpovedi v produkciji: storitev, ki je pri N uporabnikih v redu, pri N+1 pade s pečine, ko njen working set preseže RAM. Prepoznati podpis (močan paging, nasičen disk, ustavljen CPU) in poznati vzvode (RAM, odmetavanje obremenitve, lokalnost — in da swap pomanjkanje pomnilnika spremeni v katastrofo latence) je razlika med diagnozo v nekaj minutah in strmenjem v skrivnostno zamrznjen stroj.

Politike zamenjave

Working set in thrashing

Kako ga popraviti / se mu izogniti

Zakaj je to pomembno

Povezana vprašanja