Kako funkcionira zamjena stranica i što uzrokuje thrashing?

Question

IT Interview Practice · Accepted Answer

Kada se fizički RAM napuni, a procesi trebaju više stranica, OS mora **izbaciti (evict)** rezidentnu stranicu kako bi oslobodio mjesto — zapisujući je u **swap** (disk) ako je prljava (dirty). Koju stranicu izbaciti je odluka **zamjene stranica (page replacement)**, i pogrešan izbor uništava performanse.

## Politike zamjene

Teoretski optimum je izbaciti stranicu koja će se koristiti najdalje u budućnosti (**Béládyjev OPT**) — nemoguće, jer ne možete vidjeti budućnost. Zato aproksimiramo **LRU (least recently used)**: izbacite stranicu najdulje nekorištenu. Pravi LRU treba vremensku oznaku pri svakom pristupu (preskupo), pa pravi kerneli koriste **clock (second-chance) algoritam**:

```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-slične rezultate uz O(1) trošak. Linux ga dodatno profinjuje **active/inactive LRU listama**.

## Working set i thrashing

**Working set** procesa je skup stranica koje aktivno koristi unutar vremenskog prozora. Paging radi dobro *sve dok kombinirani working setovi stanu u RAM*. Kada ne stanu:

```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 litica, ne padina: prijeđite malo preko granice i throughput se uruši jer gotovo svaki pristup promašuje. Simptomi: CPU gotovo besposlen, ali disk I/O zasićen, i latencija eksplodira.

## Popravak / izbjegavanje

- **Dodajte RAM** ili **smanjite opterećenje** (manje istovremenih procesa) da working setovi stanu.
- Scheduler može **suspendirati i swapati van** cijele procese kako bi smanjio potražnju (medium-term scheduling).
- Linuxov **OOM killer** je zadnje utočište — ubiti proces radije nego thrashati zauvijek.
- Poboljšajte **lokalnost** kako bi sam working set bio manji.

## Zašto je to važno

Ovo povezuje cijelu priču o memoriji i omiljeno je senior pitanje jer je thrashing stvarni način kvara u produkciji: servis koji je dobar pri N korisnika pada s litice pri N+1 kad njegov working set premaši RAM. Prepoznati potpis (intenzivan paging, zasićen disk, zaustavljen CPU) i znati poluge (RAM, load shedding, lokalnost — te da swap pretvara nedostatak memorije u katastrofu latencije) razlika je između dijagnoze u nekoliko minuta i zurenja u tajanstveno zamrznuti stroj.

Politike zamjene

Working set i thrashing

Popravak / izbjegavanje

Zašto je to važno

Povezana pitanja