Kaip veikia puslapių pakeitimas ir kas sukelia thrashing?

Question

IT Interview Practice · Accepted Answer

Kai fizinė RAM prisipildo, bet procesams reikia daugiau puslapių, OS turi **išstumti (evict)** rezidentinį puslapį, kad atlaisvintų vietą — įrašydama jį į **swap** (diską), jei jis nešvarus (dirty). Kurį puslapį išstumti yra **puslapių pakeitimo (page replacement)** sprendimas, ir klaida jame sugriauna našumą.

## Pakeitimo politikos

Teorinis optimumas yra išstumti puslapį, kuris bus panaudotas toliausiai ateityje (**Bélády OPT**) — neįmanoma, nes ateities nematyti. Todėl apytiksliai naudojame **LRU (least recently used)**: išstumk puslapį, ilgiausiai nenaudotą. Tikras LRU reikalauja laiko žymės kiekviename kreipimesi (per brangu), todėl tikri kernel naudoja **clock (second-chance) algoritmą**:

```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 duoda į LRU panašius rezultatus su O(1) kaina. Linux jį dar patobulina **active/inactive LRU sąrašais**.

## Working set ir thrashing

Proceso **working set** yra puslapių, kuriuos jis aktyviai naudoja per laiko langą, aibė. Paging veikia gerai, *kol bendri working sets telpa RAM*. Kai netelpa:

```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 yra uola, o ne nuolydis: peržengk ribą truputį, ir throughput sugriūva, nes beveik kiekvienas kreipimasis prašauna (miss). Simptomai: CPU beveik dyka, bet disko I/O prisotintas, o latency sprogsta.

## Kaip tai spręsti / išvengti

- **Pridėk RAM** arba **sumažink apkrovą** (mažiau lygiagrečių procesų), kad working sets tilptų.
- Scheduler gali **sustabdyti ir swap-out** ištisus procesus, kad sumažintų paklausą (medium-term scheduling).
- Linux **OOM killer** yra paskutinė priemonė — nužudyti procesą, o ne thrash amžinai.
- Pagerink **locality**, kad pats working set būtų mažesnis.

## Kodėl tai svarbu

Tai suriša visą atminties istoriją ir yra mėgstamas senior klausimas, nes thrashing yra realus production gedimo režimas: servisas, kuris tvarkoje su N naudotojų, nukrinta nuo uolos ties N+1, kai jo working set viršija RAM. Atpažinti požymį (intensyvus paging, prisotintas diskas, sustojęs CPU) ir žinoti svertus (RAM, apkrovos mažinimas, locality — ir kad swap paverčia atminties trūkumą latency katastrofa) yra skirtumas tarp diagnozavimo per minutes ir spoksojimo į paslaptingai užšalusią mašiną.

Pakeitimo politikos

Working set ir thrashing

Kaip tai spręsti / išvengti

Kodėl tai svarbu

Susiję klausimai