Алгоритм CLOCK

Алгоритм CLOCK — это алгоритм вытеснения страниц из кэша (или виртуальной памяти), реализующий политику «Вторая попытка» (Second Chance) и являющийся приближением к идеальному алгоритму LRU (Least Recently Used — наименее используемый давно). Алгоритм был предложен в 1968 году Фернандо Корбато и используется в операционных системах для управления страничной памятью, а также в системах кэширования баз данных и файловых системах. Основная цель CLOCK — минимизировать количество страничных ошибок (page faults) при ограниченном объёме физической памяти, обеспечивая компромисс между точностью LRU и вычислительной эффективностью.

История

Алгоритм CLOCK был разработан как ответ на практические ограничения алгоритма LRU. В классическом LRU для каждой страницы необходимо хранить временную метку последнего обращения, что требует сортировки или поиска по всем страницам при вытеснении, что дорого с точки зрения процессорного времени и памяти. В 1968 году Фернандо Корбато, работая над операционной системой Multics, предложил упрощённую реализацию «Второй попытки», использующую биты обращения (reference bits) и указатель, движущийся по кольцевому буферу. Название «CLOCK» возникло из-за визуальной аналогии: указатель вращается по кругу, как часовая стрелка. Позднее алгоритм был адаптирован для ядра Linux (вариант CLOCK-Pro) и других современных ОС.

Принцип работы

Алгоритм CLOCK основан на кольцевом буфере, в котором хранятся записи о страницах. Каждая запись содержит:

• Бит обращения (R) — устанавливается в 1 при каждом обращении к странице (аппаратно или программно).
• Бит модификации (M) — опционально, для учёта «грязных» страниц, которые нужно записать на диск.

Указатель (hand) последовательно обходит буфер по часовой стрелке. При необходимости освободить место для новой страницы алгоритм выполняет следующие шаги:

1. Проверка текущей страницы под указателем.
2. Если бит R = 1, то сбрасывается в 0 (даётся «вторая попытка»), указатель сдвигается на следующую страницу, и шаг повторяется.
3. Если бит R = 0, страница считается кандидатом на вытеснение. Если страница была модифицирована (M=1), она сначала записывается на диск, после чего удаляется из кэша.

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

Пример работы

Рассмотрим кэш из 4 страниц (A, B, C, D) с начальными битами R=0. Указатель стоит на A.

1. Обращение к A: R(A)=1. Указатель на B.
2. Обращение к C: R(C)=1. Указатель на D.
3. Требуется загрузить новую страницу E. Указатель на D: R(D)=0 → вытесняем D, загружаем E с R(E)=0. Указатель на A.
4. Обращение к B: R(B)=1. Указатель на C.

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

Классификация и варианты

Алгоритм CLOCK имеет несколько модификаций, адаптированных под разные задачи:

CLOCK с учётом модификаций (CLOCK-M)

Добавляет бит модификации (M). При вытеснении предпочтение отдаётся страницам с R=0 и M=0 (неизменённым), чтобы избежать лишних операций ввода-вывода. Если таких нет, вытесняются страницы с R=0 и M=1 (с предварительной записью на диск).

CLOCK-Pro

Разработан в 2005 году для ядра Linux. Включает два указателя: один для «горячих» страниц (часто используемых), другой для «холодных». Использует счётчики обращений и временные метки, что приближает точность к LRU, сохраняя низкую накладную стоимость.

2Q (Two Queue)

Вариант, разделяющий страницы на две очереди: A1 (первая попытка) и Am (часто используемые). Страницы, получившие вторую попытку, перемещаются в Am. Реализует ту же идею, но с двумя списками вместо кольца.

Алгоритм «Вторая попытка» (Second Chance)

Базовый вариант, где указатель движется по линейному списку (не обязательно кольцевому). CLOCK является его кольцевой реализацией.

Характеристики

Преимущества

• Низкая вычислительная сложность: O(1) на шаг (проверка и сброс бита), O(n) в худшем случае при полном обходе.
• Простота реализации: не требует сортировки или сложных структур данных.
• Адаптивность: автоматически реагирует на изменение паттернов доступа, давая «второй шанс» недавно использованным страницам.
• Эффективность по памяти: для каждой страницы нужен только 1 бит (R), что значительно меньше, чем хранение временных меток в LRU.

Недостатки

• Приближённость к LRU: в некоторых сценариях (например, при циклическом доступе к большему числу страниц, чем размер кэша) может работать хуже, чем LRU, из-за «зацикливания» указателя.
• Зависимость от размера кэша: при очень малом кэше (2–4 страницы) эффективность снижается, так как указатель быстро обходит буфер.
• Отсутствие учёта частоты обращений: страница, к которой обратились один раз, может быть вытеснена так же, как и страница с множеством обращений, если бит R был сброшен.

Применение

Алгоритм CLOCK широко применяется в операционных системах и системах управления базами данных (СУБД):

• Ядро Linux: начиная с версии 2.6.28, используется модификация CLOCK-Pro для управления страничной памятью. В более ранних версиях применялся классический CLOCK.
• Windows NT: в ранних версиях использовался алгоритм «Вторая попытка» (Second Chance), близкий к CLOCK.
• СУБД PostgreSQL: для кэширования буферов (shared buffers) применяется вариант CLOCK с учётом модификаций (CLOCK-M).
• Файловые системы: в некоторых реализациях кэша страниц (например, в ZFS) используются алгоритмы, основанные на CLOCK.

Критика

Основная критика алгоритма CLOCK связана с его неоптимальностью в условиях высокой локальности обращений. В ситуациях, когда программа последовательно обращается к большому набору данных, превышающему размер кэша, CLOCK может вытеснять страницы, которые будут использованы в ближайшее время, что приводит к «трепетанию» (thrashing). Кроме того, в многопроцессорных системах сброс бита R требует синхронизации, что увеличивает накладные расходы. В современных системах CLOCK часто заменяется более сложными алгоритмами, такими как ARC (Adaptive Replacement Cache) или LIRS (Low Inter-reference Recency Set), которые лучше адаптируются к изменяющимся паттернам доступа.

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

• Название «CLOCK» было дано из-за того, что указатель движется по кругу, как стрелка часов, а биты обращения сбрасываются, как «тиканье».
• В 1970-х годах алгоритм CLOCK использовался в операционной системе Multics, одной из первых многопользовательских систем с разделением времени.
• В некоторых реализациях бит R заменяется на счётчик (например, 2-битный), что позволяет различать страницы с одним и несколькими обращениями.

Источники

• Корбато, Ф. Дж. (1968). «A Paging Experiment with the Multics System». MIT Project MAC.
• Таненбаум, Э. С. (2015). «Современные операционные системы». 4-е издание. Глава 3: Управление памятью.
• Jiang, S., Zhang, X. (2005). «CLOCK-Pro: An Effective Improvement of the CLOCK Replacement». Proceedings of the USENIX Annual Technical Conference.
• Официальная документация ядра Linux: «Page Replacement Policy» (Documentation/vm/page_replacement.rst).