Jak funguje výměna stránek (page replacement) a co způsobuje thrashing?

Question

IT Interview Practice · Accepted Answer

Když se fyzická RAM zaplní, ale procesy potřebují víc stránek, OS musí **vystěhovat (evict)** rezidentní stránku, aby udělal místo — a zapsat ji do **swapu** (na disk), pokud je špinavá (dirty). Kterou stránku vystěhovat, je rozhodnutí o **výměně stránek (page replacement)**, a špatná volba zničí výkon.

## Strategie výměny

Teoretické optimum je vystěhovat stránku, která bude použita nejdále v budoucnosti (**Béládyho OPT**) — nemožné, protože do budoucnosti nevidíte. Proto aproximujeme **LRU (least recently used)**: vystěhovat stránku nejdéle nepoužitou. Pravé LRU potřebuje časovou značku při každém přístupu (příliš nákladné), takže skutečné kernely používají **algoritmus 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 dává výsledky podobné LRU za cenu O(1). Linux to dále zjemňuje pomocí **aktivních/neaktivních LRU seznamů**.

## Working set a thrashing

**Working set** procesu je množina stránek, které aktivně používá v časovém okně. Paging funguje dobře, *dokud se kombinované working sety vejdou do RAM*. Když 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 útes, ne svah: překročte limit jen o kousek a throughput se zhroutí, protože téměř každý přístup je miss. Příznaky: CPU téměř nečinné, ale I/O disku saturované a latence exploduje.

## Jak to opravit / se tomu vyhnout

- **Přidat RAM** nebo **snížit zátěž** (méně souběžných procesů), aby se working sety vešly.
- Scheduler může **pozastavit a odswapovat** celé procesy, aby zmenšil poptávku (medium-term scheduling).
- **OOM killer** Linuxu je poslední možnost — raději zabít proces, než navždy thrashovat.
- Zlepšit **lokalitu**, aby byl samotný working set menší.

## Proč je to důležité

Tohle spojuje celý příběh paměti dohromady a je oblíbenou senior otázkou, protože thrashing je reálný produkční režim selhání: služba, která je v pořádku při N uživatelích, spadne z útesu při N+1, když její working set překročí RAM. Rozpoznání charakteristiky (silný paging, saturovaný disk, zaseknuté CPU) a znalost pák (RAM, shazování zátěže, lokalita — a že swap mění nedostatek paměti v latenční katastrofu) je rozdíl mezi diagnózou během minut a zíráním na záhadně zamrzlý stroj.

Strategie výměny

Working set a thrashing

Jak to opravit / se tomu vyhnout

Proč je to důležité

Související otázky