Алгоритмы замещения страниц
Вступление
Физической RAM не хватает на все виртуальные страницы всех процессов. ОС выгружает редко используемые страницы на диск (swap, pagefile) и загружает обратно по запросу — page fault.
Когда нужно освободить фрейм (физическую страницу), возникает вопрос: какую жертву выбрать? От ответа зависит, будете ли вы постоянно читать диск (thrashing) или работать почти в RAM.
Базовая теория — в механизмах распределения памяти и управлении памятью в Linux. Здесь — обзор алгоритмов с разбором и сравнением.
Связано: подсистема I/O (диск медленный), аппаратная поддержка MMU (раздел про TLB и таблицы страниц).
Контекст — demand paging
Подкачка по требованию: страница попадает в RAM только при первом обращении (или при явном prefetch). При нехватке фреймов:
- Выбрать жертву (victim page).
- Если страница изменена (dirty) — записать на диск (медленно).
- Загрузить нужную страницу в освобождённый фрейм.
- Обновить таблицу страниц, возобновить процесс.
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:
- Смотрим голову очереди FIFO.
- Если R = 0 — выгружаем.
- Если R = 1 — сбрасываем R, страницу в конец очереди, смотрим следующую.
Даёт "недавно тронутым" страницам отсрочку — шаг к LRU без полного учёта времени.
Clock (часы)
Страницы на кольцевой списке, указатель "стрелка часов":
- Обход по кругу; R=0 → victim; R=1 → обнулить R, идти дальше.
- Эквивалентен Second Chance с кольцом вместо очереди.
Плюсы: простой, O(1) амортизированно на выбор, работает в ядрах.
Минус: не различает "два обращения" и "тысячу обращений" за интервал.
NRU (Not Recently Used)
Аппаратура ведёт биты R (referenced) и M (modified). Периодически (по таймеру) ОС сбрасывает R у страниц, которые не трогали с прошлого цикла.
Классификация для выбора жертвы (упрощённо):
| R | M | Действие |
|---|---|---|
| 0 | 0 | выгрузить первой |
| 0 | 1 | выгрузить второй попыткой |
| 1 | 0 | сбросить R, "вторая попытка" |
| 1 | 1 | сбросить R, отложить |
NRU — недорогая аппроксимация "недавно использованных" без полного LRU.
Алгоритм старения (aging)
Программный счётчик старения в записи страницы: раз в такт таймера сдвигают регистр вправо и добавляют бит R. Чем меньше значение — тем дольше страница не использовалась. Выгружают страницу с наименьшим счётчиком.
На практике в ядрах чаще Clock и аппаратные R/M, но aging удобен для ручного счёта в симуляторах.
WSClock
WSClock сочетает рабочий набор и часы:
- записи страниц процесса — кольцевой список со стрелкой;
- параметр k — максимальный "возраст" страницы в рабочем наборе (в виртуальном времени процесса);
- при page fault обходят список: R=1 → обнулить R и идти дальше; R=0 и возраст > k → кандидат на замещение;
- если M=0 — чистая страница, можно перезаписать сразу;
- если M=1 — запускают асинхронный сброс на диск и продолжают обход (ограничивая число параллельных записей).
WSClock и aging часто упоминают как практичные реализации в учебниках; в Linux близкие идеи — reclaim и active/inactive списки.
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-backed и anonymous).
- kswapd — фоновый reclaim при нехватке памяти.
- swappiness — насколько охотно вытеснять анонимные страницы процесса по сравнению с file-backed кэшем файлов.
- NUMA reclaim — локальность к узлу — см. Механизмы распределения памяти в ОС.
Точный "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 — нет.
Связь с остальным курсом
- Механизмы распределения памяти в ОС — страницы, TLB, таблицы.
- Подсистема ввода-вывода в ОС — диск как узкое место подкачки.
- Планирование процессора — классические алгоритмы — при thrashing планировщик не спасает.
- Управление памятью в Linux —
vmstat,swappiness, OOM killer.
Чек-лист самопроверки — вопросы по LRU, Clock, thrashing.
Практический симптом thrashing
Если после запуска "тяжелого" приложения система резко теряет отзывчивость, а диск постоянно активен, это часто признак нехватки RAM и агрессивной подкачки.
Быстрые действия:
- уменьшить одновременную нагрузку,
- проверить настройки памяти и лимиты,
- посмотреть динамику swap in/out,
- сопоставить поведение с профилем приложения.
Это помогает связать теорию алгоритмов замещения с реальным администрированием рабочих станций и серверов.