Как работает замещение страниц, и что вызывает thrashing?

Question

IT Interview Practice · Accepted Answer

Когда физическая RAM заполняется, а процессам нужно больше страниц, ОС должна **вытеснить (evict)** резидентную страницу, чтобы освободить место — записав её в **swap** (диск), если она грязная (dirty). Какую страницу вытеснить — это решение о **замещении страниц (page replacement)**, и ошибка здесь рушит производительность.

## Политики замещения

Теоретический оптимум — вытеснять страницу, которая понадобится дальше всех в будущем (**OPT Беледи, Bélády's OPT**) — невозможен, ведь будущее не видно. Поэтому мы приближаем **LRU (least recently used)**: вытеснять страницу, дольше всех не использовавшуюся. Настоящему LRU нужна метка времени на каждое обращение (слишком дорого), поэтому реальные ядра используют **алгоритм 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 даёт результаты, похожие на LRU, за O(1). Linux уточняет его ещё сильнее с помощью **списков LRU active/inactive**.

## Working set и thrashing

**Working set** процесса — это набор страниц, которые он активно использует в пределах временного окна. Paging работает нормально, *пока совокупные working set'ы помещаются в RAM*. Когда нет:

```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 — это обрыв, а не склон: чуть перешагни предел, и throughput обрушивается, потому что почти каждое обращение промахивается. Симптомы: CPU почти простаивает, но I/O диска насыщен, а задержка взрывается.

## Как исправить / избежать

- **Добавить RAM** или **снизить нагрузку** (меньше одновременных процессов), чтобы working set'ы поместились.
- Планировщик может **приостановить и выгрузить (swap-out)** целые процессы, чтобы уменьшить спрос (среднесрочное планирование, medium-term scheduling).
- **OOM killer** в Linux — крайнее средство: убить процесс, чем вечно буксовать.
- Улучшить **locality**, чтобы сам working set стал меньше.

## Почему это важно

Это связывает всю историю о памяти воедино и является излюбленным senior-вопросом, потому что thrashing — реальный режим отказа в production: сервис, который в порядке при N пользователях, срывается с обрыва при N+1, когда его working set превышает RAM. Распознавание сигнатуры (интенсивный paging, насыщенный диск, застопорившийся CPU) и знание рычагов (RAM, сброс нагрузки, locality — и что swap превращает нехватку памяти в катастрофу задержки) — это разница между диагностикой за минуты и разглядыванием загадочно зависшей машины.

Политики замещения

Working set и thrashing

Как исправить / избежать

Почему это важно

Похожие вопросы