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

Алгоритм замещения страниц — это метод управления виртуальной памятью, используемый операционными системами для определения того, какую страницу памяти следует выгрузить из оперативной памяти (ОЗУ) на диск (в файл подкачки или область свопинга) при необходимости освободить место для новой страницы. Алгоритмы замещения страниц являются ключевым компонентом механизма подкачки (paging), который позволяет системе выполнять программы, размер которых превышает объём доступной физической памяти, и обеспечивает изоляцию процессов.

¶История и предпосылки

Развитие алгоритмов замещения страниц связано с появлением систем виртуальной памяти в 1960-х годах. Первые реализации, такие как в системе Atlas (Манчестерский университет, 1962), использовали простые эвристики. С ростом сложности вычислительных задач и увеличением разрыва между скоростью процессора и временем доступа к диску, эффективность алгоритмов стала критически важной. В 1966 году Лесли Белфорд и Питер Деннинг сформулировали принцип локальности ссылок, который лёг в основу многих современных алгоритмов. С тех пор было разработано десятки алгоритмов, от простейших (FIFO) до сложных, учитывающих историю обращений (LRU, ARC).

¶Классификация алгоритмов

Алгоритмы замещения страниц делятся на несколько категорий в зависимости от используемой информации и подхода к принятию решений.

¶По типу используемой информации

Без информации о будущем (онлайн-алгоритмы): Принимают решение на основе текущего состояния памяти и истории обращений. Примеры: FIFO, LRU, Clock.
С использованием информации о будущем (офлайн-алгоритмы): Требуют знания последовательности будущих обращений, что на практике невозможно. Используются как эталон для сравнения (алгоритм Белади).
Гибридные: Комбинируют элементы разных подходов, например, учитывают частоту обращений и давность (LFU, ARC).

¶По способу учёта истории

Счётчиковые: Ведётся подсчёт количества обращений к странице (LFU, MFU).
Стековые: Хранят порядок обращений, вытесняя самую старую (LRU).
Кольцевые: Используют биты доступа и циклический просмотр (Clock, Second Chance).

¶Основные алгоритмы

¶Алгоритм Белади (Optimal)

Теоретический алгоритм, который вытесняет страницу, к которой обращение произойдёт позже всех в будущем. Разработан Ласло Белади в 1966 году. Служит эталоном для оценки других алгоритмов — ни один практический алгоритм не может превзойти его по числу ошибок страниц (page faults). На практике нереализуем, так как требует предсказания будущих обращений.

¶Алгоритм FIFO (First-In, First-Out)

Самый простой алгоритм: вытесняется страница, которая дольше всех находится в памяти. Реализуется с помощью очереди. Недостаток — возможен эффект Белади, когда увеличение числа кадров памяти парадоксально увеличивает количество ошибок страниц. Пример: в системе с 3 кадрами последовательность обращений 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 даёт 9 ошибок при 3 кадрах и 10 ошибок при 4 кадрах.

¶Алгоритм LRU (Least Recently Used)

Вытесняется страница, к которой не обращались дольше всех. Основан на принципе локальности: если страница не использовалась долго, то, вероятно, не понадобится и в ближайшем будущем. Реализация требует поддержки стека или счётчиков времени. Существует несколько аппроксимаций, например, алгоритм Clock (Second Chance), который использует бит доступа (reference bit) и циклический просмотр. LRU считается одним из наиболее эффективных практических алгоритмов, но его точная реализация дорога (аппаратно или программно). В современных ОС (Linux, Windows) используются приближённые варианты, такие как LRU-2 или LIRS.

¶Алгоритм LFU (Least Frequently Used)

Вытесняется страница с наименьшей частотой обращений. Требует ведения счётчика обращений для каждой страницы. Недостаток — «загрязнение» памяти страницами, которые были популярны в прошлом, но больше не нужны. Для решения этой проблемы применяют модификации, например, LFU с экспоненциальным затуханием (aging).

¶Алгоритм Clock (Second Chance)

Аппроксимация LRU, используемая во многих ОС (в том числе в ядре Linux). Страницы организованы в кольцевой список. Каждая страница имеет бит доступа (R). При необходимости замещения указатель (рука часов) движется по кругу:

Если бит R = 0, страница вытесняется.
Если бит R = 1, он сбрасывается в 0, и указатель переходит к следующей странице.

Если все биты установлены, алгоритм делает полный оборот, сбрасывая их, и вытесняет первую встреченную страницу. Вариант Clock с дополнительным битом модификации (Dirty bit) называется NUR (Not Used Recently).

¶Алгоритм ARC (Adaptive Replacement Cache)

Разработан в IBM Research (2003) для кэширования данных. Комбинирует LRU и LFU, адаптивно переключаясь между ними в зависимости от паттерна доступа. Использует четыре списка: два для недавно использованных страниц и два для часто используемых. ARC считается одним из лучших алгоритмов для сбалансированных нагрузок и применяется в системах хранения данных (ZFS, некоторые СУБД).

¶Применение в операционных системах

В современных ОС алгоритмы замещения страниц реализованы на уровне ядра. В Linux используется алгоритм, основанный на Clock (точнее, его вариант — «алгоритм двух очередей» или LIRS в некоторых версиях). В Windows (NT) применяется модифицированный LRU с учётом приоритетов процессов и рабочих наборов. В macOS (XNU) используется алгоритм, близкий к LRU, с поддержкой сжатия памяти (memory compression). Выбор алгоритма зависит от типа нагрузки (интерактивная, серверная, научные вычисления) и аппаратных особенностей (размер кэша, скорость диска).

¶Критерии оценки

Эффективность алгоритма замещения страниц оценивается по нескольким метрикам:

Количество ошибок страниц (page faults): Чем меньше, тем лучше.
Коэффициент промахов (miss ratio): Доля обращений, вызывающих ошибку страницы.
Накладные расходы (overhead): Время, затрачиваемое на выполнение алгоритма (обновление структур данных, поиск).
Устойчивость к эффекту Белади: Способность не увеличивать число ошибок при увеличении числа кадров.
Адаптивность: Способность подстраиваться под изменяющийся паттерн доступа.

¶Интересные факты

Эффект Белади, открытый в 1969 году, опроверг интуитивное предположение, что больше памяти всегда лучше. Он проявляется только для алгоритмов, не удовлетворяющих свойству стека (например, FIFO, но не LRU).
Алгоритм LRU может быть реализован аппаратно с помощью ассоциативной памяти (CAM) — в суперскалярных процессорах для кэша данных.
В системах реального времени (RTOS) часто используют простые алгоритмы (FIFO) из-за предсказуемости времени выполнения, даже ценой производительности.
Алгоритм ARC был запатентован IBM, что привело к юридическим спорам с разработчиками ZFS (OpenZFS) в 2007 году, но позже патент был признан недействительным в некоторых юрисдикциях.

¶Источники

Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание), 2015.
Silberschatz A., Galvin P.B., Gagne G. «Operating System Concepts» (10th edition), 2018.
Belady L.A. «A Study of Replacement Algorithms for a Virtual-Storage Computer», IBM Systems Journal, 1966.
Megiddo N., Modha D.S. «ARC: A Self-Tuning, Low Overhead Replacement Cache», USENIX FAST, 2003.
Документация ядра Linux: «Memory Management» (kernel.org/doc).