Miten page replacement toimii, ja mikä aiheuttaa thrashingin?

Question

IT Interview Practice · Accepted Answer

Kun fyysinen RAM täyttyy mutta prosessit tarvitsevat lisää sivuja, OS:n on **häädettävä (evict)** residentti sivu tehdäkseen tilaa — kirjoittaen sen **swapiin** (levylle), jos se on likainen (dirty). Kumpi sivu häädetään, on **page replacement** -päätös, ja sen väärin tekeminen tuhoaa suorituskyvyn.

## Korvauspolitiikat

Teoreettinen optimi on häätää sivu, jota käytetään kauimpana tulevaisuudessa (**Béládyn OPT**) — mahdotonta, koska et näe tulevaisuuteen. Joten approksimoimme **LRU:ta (least recently used)**: häädä sivu, jota on käytetty pisimpään sitten. Todellinen LRU tarvitsee aikaleiman jokaisella haulla (liian kallista), joten todelliset kernelit käyttävät **clock (second-chance) -algoritmia**:

```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 antaa LRU:n kaltaisia tuloksia O(1)-kustannuksella. Linux hienosäätää sitä edelleen **active/inactive LRU -listoilla**.

## Working set ja thrashing

Prosessin **working set** on sivujen joukko, jota se aktiivisesti käyttää tietyn aikaikkunan sisällä. Paging toimii hyvin *niin kauan kuin yhdistetyt working setit mahtuvat RAM:iin*. Kun ne eivät mahdu:

```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 on jyrkänne, ei rinne: ylitä raja hieman, ja throughput romahtaa, koska lähes jokainen haku missaa. Oireet: CPU lähes joutilaana mutta levy-I/O saturoituneena, ja latenssi räjähtää.

## Korjaaminen / välttäminen

- **Lisää RAM:ia** tai **vähennä kuormaa** (vähemmän samanaikaisia prosesseja), jotta working setit mahtuvat.
- Scheduler voi **keskeyttää ja swapata ulos** kokonaisia prosesseja kysynnän kutistamiseksi (medium-term scheduling).
- Linuxin **OOM killer** on viimeinen keino — tapa prosessi sen sijaan että thrashaisit ikuisesti.
- Paranna **localityä**, jotta working set itsessään on pienempi.

## Miksi se on tärkeää

Tämä sitoo koko muistitarinan yhteen ja on suosikki senior-kysymys, koska thrashing on todellinen tuotannon vikatila: palvelu, joka on kunnossa N käyttäjällä, putoaa jyrkänteeltä N+1:llä, kun sen working set ylittää RAM:in. Tunnusmerkin tunnistaminen (raskas paging, saturoitunut levy, pysähtynyt CPU) ja vipujen tietäminen (RAM, kuorman keventäminen, locality — ja se, että swap muuttaa muistivajeen latenssikatastrofiksi) on ero sen välillä, diagnosoitko sen minuuteissa vai tuijotatko salaperäisesti jäätynyttä konetta.

Korvauspolitiikat

Working set ja thrashing

Korjaaminen / välttäminen

Miksi se on tärkeää

Aiheeseen liittyvät kysymykset