Алгоритмы замещения страниц

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору Инженеру

Вступление

Физической RAM не хватает на все виртуальные страницы всех процессов. ОС выгружает редко используемые страницы на диск (swap, pagefile) и загружает обратно по запросу — page fault.

Когда нужно освободить фрейм (физическую страницу), возникает вопрос: какую жертву выбрать? От ответа зависит, будете ли вы постоянно читать диск (thrashing) или работать почти в RAM.

Базовая теория — в механизмах распределения памяти и управлении памятью в Linux. Здесь — обзор алгоритмов с разбором и сравнением.

Связано: подсистема I/O (диск медленный), аппаратная поддержка MMU (раздел про TLB и таблицы страниц).

---

Контекст — demand paging

Подкачка по требованию: страница попадает в RAM только при первом обращении (или при явном prefetch). При нехватке фреймов:

1. Выбрать жертву (victim page).
2. Если страница изменена (dirty) — записать на диск (медленно).
3. Загрузить нужную страницу в освобождённый фрейм.
4. Обновить таблицу страниц, возобновить процесс.

Page fault бывает мягким (страница в памяти, обновить права) и тяжёлым (чтение с диска).

---

Что оптимизируем

Метрика	Смысл
Hit ratio	Доля обращений без обращения к диску
Fault rate	Page faults на единицу времени
Thrashing	Система тратит больше времени на подкачку, чем на полезную работу

Идеальный алгоритм минимизирует faults — но нужен прогноз будущего, которого у ОС нет.

---

OPT — оптимальный (Belady)

Идея: выгрузить страницу, которая дольше всего не понадобится в будущем.

• Минимум page faults среди всех алгоритмов (доказано).
• Нереализуем в реальной ОС — будущие обращения неизвестны.
• Используется как эталон для сравнения в учебниках и симуляторах.

Аномалия Белади (Belady's anomaly): для FIFO иногда больше фреймов → больше faults (не для стека OPT/LRU).

---

FIFO — First-In, First-Out

Выгружается страница, которая дольше всего в памяти (очередь по времени загрузки).

Плюсы: простота, низкий overhead.

Минусы:

• игнорирует частоту использования — активная страница может быть старой в очереди;
• возможна аномалия Белади;
• часто хуже LRU на практике.

Иногда используется как основа для Clock.

---

LRU — Least Recently Used

Выгружается страница, к которой давнее всего не обращались.

Плюсы: хорошо приближает локальность; обычно лучше FIFO.

Минусы реализации:

• точный LRU требует учёта каждого обращения — дорого;
• на практике — приближения.

Аппаратная помощь

В записи таблицы страниц часто есть биты:

• referenced (R) — к странице обращались с момента последней «очистки»;
• modified (M / dirty) — страница изменена.

ОС периодически сбрасывает R, наблюдая, кто снова получил 1 — это недавно использованные.

---

Second Chance (второй шанс)

Вариант FIFO с битом R:

1. Смотрим голову очереди FIFO.
2. Если R = 0 — выгружаем.
3. Если R = 1 — сбрасываем R, страницу в конец очереди, смотрим следующую.

Даёт «недавно тронутым» страницам отсрочку — шаг к LRU без полного учёта времени.

---

Clock (часы)

Страницы на кольцевой списке, указатель «стрелка часов»:

• Обход по кругу; R=0 → victim; R=1 → обнулить R, идти дальше.
• Эквивалентен Second Chance с кольцом вместо очереди.

Плюсы: простой, O(1) амортизированно на выбор, работает в ядрах.

Минус: не различает «два обращения» vs «тысяча».

Enhanced Clock

Учитывают dirty (M):

• предпочитают выгрузить чистую страницу (не нужна запись на диск).
• порядок поиска: (R=0, M=0) → (R=0, M=1) → … — меньше дорогих записей.

---

NFU и aging (приближение LRU в учебниках)

Not Frequently Used — программный счётчик старения без аппаратного R: периодически сдвигают биты использования. Реже в продакшен-ядрах, чаще в курсах.

---

Рабочий набор (working set)

Working set процесса — множество страниц, к которым он обращался за последние Δ единиц времени.

Идея политики:

• если процессу не хватает RAM для working set → thrashing;
• ОС может ограничить число фреймов процесса или приостановить его (в классических моделях).

На практике Linux использует cgroups memory.limit и поведение reclaim, а не явный working set model из 1970-х — но интуиция та же: «сколько страниц процессу реально нужно сейчас».

---

Глобальная и локальная замена

Политика	Суть
Локальная	Жертву выбирают среди страниц того же процесса
Глобальная	Среди всех фреймов системы

Глобальная даёт гибкость (один процесс простаивает — отдать RAM другому), но один процесс может «вымыть» кэш остальных.

Современные ядра в основном глобальный reclaim с приоритетами (кто «более reclaimable»).

---

Сравнительная таблица

Алгоритм	Реализуем	Учёт локальности	Запись на диск	Типичное качество
OPT	Нет (эталон)	Идеально	Умно	Лучший теоретически
FIFO	Да	Нет	Любая жертва	Слабое
LRU (точный)	Дорого	Да	Предпочтение clean	Хорошее
Second Chance	Да	Частично	Как FIFO+	Среднее+
Clock	Да	Частично	Enhanced — лучше	Хорошее в ядрах
Random	Да	Нет	Случайно	Среднее, простое

---

Что в Linux и Windows

Linux

• Активный / неактивный списки страниц (LRU-подобные классы: active, inactive, file vs anon).
• kswapd — фоновый reclaim при нехватке памяти.
• swappiness — склонность вытеснять анонимные страницы (процесс) vs file-backed (кэш файлов).
• NUMA reclaim — локальность к узлу — см. 5116.

Точный «LRU» на всех страницах невозможен при миллионах страниц; приближение + биты R/M в MMU.

Windows

• Working set процесса (мин/макс в диспетчере задач — упрощённо).
• Standby / modified списки страниц.
• SuperFetch (предзагрузка на основе статистики) — эвристика, не OPT.

---

Thrashing — как распознать

Симптомы:

• диск постоянно активен при «простое» CPU;
• резкое падение throughput;
• si/so в vmstat (swap in/out) высокие;
• latency приложений растёт в разы.

Лечение (упрощённо):

• добавить RAM;
• уменьшить число тяжёлых процессов;
• настроить лимиты памяти (cgroups, Job Objects);
• проверить утечки памяти в приложении.

---

Упражнение (учебное)

Последовательность обращений к страницам (номера):
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
При 3 фреймах посчитайте faults для FIFO и для LRU (вручную на бумаге). Сравните с OPT «с подглядыванием в будущее».

Так вы увидите, почему LRU ближе к OPT, а FIFO — нет.

---

Связь с остальным курсом

1. 5116 — страницы, TLB, таблицы.
2. 5120 — диск как узкое место подкачки.
3. 5117 — при thrashing планировщик не спасает.
4. 5112 — vmstat, swappiness, OOM killer.

Чек-лист самопроверки — вопросы по LRU, Clock, thrashing.

---