Jak działa zastępowanie stron i co powoduje thrashing?

Question

IT Interview Practice · Accepted Answer

Gdy fizyczny RAM się zapełnia, ale procesy potrzebują więcej stron, OS musi **wyeksmitować (evict)** rezydującą stronę, by zrobić miejsce — zapisując ją do **swap** (dysk), jeśli jest brudna (dirty). To, którą stronę wyeksmitować, to decyzja **zastępowania stron (page replacement)**, a pomyłka rujnuje wydajność.

## Polityki zastępowania

Teoretyczne optimum to eksmisja strony używanej najdalej w przyszłości (**OPT Béládyego**) — niemożliwe, bo nie widać przyszłości. Więc przybliżamy **LRU (least recently used — najdawniej używana)**: eksmituj stronę najdłużej nieużywaną. Prawdziwe LRU wymaga znacznika czasu przy każdym dostępie (zbyt kosztowne), więc prawdziwe kernele używają **algorytmu 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 wyniki podobne do LRU przy koszcie O(1). Linux udoskonala go dalej **listami LRU active/inactive**.

## Working set a thrashing

**Working set** procesu to zbiór stron, których aktywnie używa w oknie czasowym. Paging działa dobrze, *dopóki połączone working sety mieszczą się w RAM*. Gdy się nie mieszczą:

```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 to urwisko, nie zbocze: przekrocz limit odrobinę, a przepustowość się załamuje, bo niemal każdy dostęp chybia. Objawy: CPU bliskie bezczynności, ale I/O dysku nasycone, a opóźnienia eksplodują.

## Naprawianie / unikanie

- **Dodaj RAM** albo **zmniejsz obciążenie** (mniej równoczesnych procesów), by working sety się zmieściły.
- Scheduler może **zawiesić i wyswapować** całe procesy, by skurczyć zapotrzebowanie (medium-term scheduling).
- **OOM killer** Linuxa to ostateczność — zabij proces, zamiast thrashować w nieskończoność.
- Popraw **lokalność (locality)**, by sam working set był mniejszy.

## Dlaczego to ważne

To spina całą historię o pamięci i jest ulubionym pytaniem senior, bo thrashing to prawdziwy produkcyjny tryb awarii: usługa, która radzi sobie przy N użytkownikach, spada z urwiska przy N+1, gdy jej working set przekracza RAM. Rozpoznanie sygnatury (intensywny paging, nasycony dysk, zatrzymane CPU) i znajomość dźwigni (RAM, zrzucanie obciążenia, lokalność — oraz to, że swap zamienia niedobór pamięci w katastrofę opóźnień) to różnica między zdiagnozowaniem tego w kilka minut a wpatrywaniem się w tajemniczo zamrożoną maszynę.

Polityki zastępowania

Working set a thrashing

Naprawianie / unikanie

Dlaczego to ważne

Powiązane pytania