Clock sweep¶

Clock sweep — это алгоритм управления кэш-памятью, относящийся к классу алгоритмов замещения страниц (или блоков) в операционных системах, базах данных и других системах, где используется кэширование. Он представляет собой эволюционное развитие алгоритма «Вторая попытка» (Second Chance) и является приближением к идеальному алгоритму LRU (Least Recently Used — наименее недавно использовавшийся), но с меньшими накладными расходами на аппаратную реализацию. Clock sweep работает по принципу циклического просмотра (сканирования) страниц, используя специальный бит доступа (reference bit) для определения, какие страницы были недавно использованы и, следовательно, должны быть сохранены в кэше.

¶История и происхождение

Алгоритм Clock sweep был разработан в 1968 году в рамках проекта Multics в Массачусетском технологическом институте (MIT). Его создание было вызвано необходимостью эффективного управления памятью в многозадачных операционных системах, где количество страниц памяти значительно превышало размер физической памяти. Идея алгоритма была впервые описана в статье «Virtual Memory, Processes, and Sharing in Multics» (1968) авторства Фернандо Корбато и других разработчиков. В отличие от более ранних алгоритмов, таких как FIFO (First In, First Out), Clock sweep учитывал частоту использования страниц, что значительно уменьшало количество ошибок страничного обмена (page faults).

В 1970-х годах алгоритм был адаптирован для использования в операционной системе Unix, где он стал основой для управления виртуальной памятью. Впоследствии Clock sweep и его модификации (например, Clock-Pro) были внедрены в ядра Linux, FreeBSD и Windows NT. В современных системах, таких как Linux (начиная с версии 2.6.28), используется усовершенствованная версия алгоритма — Clock-Pro, которая решает проблему сканирования (scan resistance) и лучше работает с большими объёмами данных.

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

Clock sweep основан на циклическом обходе страниц в кэше, напоминающем движение стрелки часов (отсюда название). Каждая страница имеет бит доступа (reference bit), который устанавливается в 1 при каждом обращении к странице (чтении или записи). Алгоритм работает следующим образом:

1. Инициализация: Все страницы в кэше имеют бит доступа, изначально равный 0.
2. Циклический обход: Стрелка (указатель) последовательно движется по кругу, проверяя каждую страницу.
3. Проверка бита доступа:

• Если бит доступа равен 1, он сбрасывается в 0, и стрелка переходит к следующей странице.
• Если бит доступа равен 0, страница считается кандидатом на вытеснение (замещение).

1. Вытеснение: При необходимости освободить место для новой страницы, алгоритм продолжает обход, пока не найдёт страницу с битом 0. Эта страница вытесняется, а на её место загружается новая.
2. Обновление бита: После загрузки новой страницы её бит доступа устанавливается в 1.

Таким образом, страница, к которой обращались недавно, получает «второй шанс»: её бит сбрасывается, и она остаётся в кэше. Если к странице не обращались в течение одного полного оборота стрелки, её бит остаётся 0, и она становится кандидатом на вытеснение.

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

Рассмотрим кэш из 4 страниц (A, B, C, D). Изначально все биты доступа равны 0. Стрелка указывает на страницу A.

1. Обращение к странице A: бит A устанавливается в 1.
2. Обращение к странице C: бит C устанавливается в 1.
3. Необходимо загрузить новую страницу E. Стрелка начинает обход:

• Проверка A: бит = 1 → сбрасывается в 0, стрелка переходит к B.
• Проверка B: бит = 0 → страница B вытесняется, на её место загружается E, бит E = 1.

1. Стрелка останавливается на следующей странице после B (в данном случае C).

¶Классификация и модификации

Clock sweep относится к классу алгоритмов с приближением к LRU, которые используют биты доступа для уменьшения аппаратных затрат. В отличие от точного LRU, который требует отслеживания времени последнего обращения для каждой страницы (что дорого в реализации), Clock sweep использует только один бит, что делает его эффективным для аппаратного и программного обеспечения.

¶Основные модификации

• Clock-Pro: Разработан в 2005 году Соном Чжоном и другими исследователями. Улучшает устойчивость к сканированию — ситуации, когда происходит последовательное чтение большого объёма данных, что в классическом Clock sweep приводит к вытеснению часто используемых страниц. Clock-Pro использует два бита: бит доступа и бит истории (history bit), что позволяет лучше различать часто и редко используемые страницы.
• N-Chance Clock: Вариант, где каждая страница имеет несколько битов доступа (например, 2 или 3). Это позволяет более точно оценивать частоту использования, но увеличивает накладные расходы.
• WSClock (Working Set Clock): Комбинация Clock sweep и модели рабочего множества (working set). Алгоритм учитывает не только бит доступа, но и время последнего использования, что позволяет точнее определять, какие страницы действительно нужны процессу.
• Clock with Dirty Bit: В системах с кэшированием записи (write-back) добавляется бит «грязной» страницы (dirty bit). Если страница была изменена, её вытеснение требует записи на диск, что увеличивает время. Алгоритм может отдавать приоритет вытеснению чистых страниц.

¶Характеристики и производительность

Clock sweep обладает рядом характеристик, которые делают его популярным в операционных системах:

• Низкие накладные расходы: Требуется только один бит на страницу и циклический обход, что легко реализуется в аппаратуре и программном обеспечении.
• Приближение к LRU: В среднем Clock sweep даёт количество ошибок страничного обмена, близкое к LRU, особенно при равномерном распределении обращений.
• Устойчивость к циклическим паттернам: В отличие от FIFO, Clock sweep не страдает от проблемы «анисового кольца» (Belady’s anomaly), когда увеличение размера кэша приводит к росту числа ошибок.
• Недостатки: При неравномерном распределении обращений (например, когда одна страница используется очень часто, а другие — редко) Clock sweep может вытеснять часто используемые страницы, если они не были посещены в течение одного оборота. Также алгоритм чувствителен к размеру кэша: при большом количестве страниц время обхода увеличивается.

¶Сравнение с другими алгоритмами

¶Применение

Clock sweep и его модификации широко используются в различных областях:

• Операционные системы: В ядрах Linux (алгоритм Clock-Pro), FreeBSD, Windows NT (алгоритм с dirty bit). Используется для управления виртуальной памятью, кэшем файловой системы и буфером страниц.
• Базы данных: В системах управления базами данных (СУБД), таких как PostgreSQL и MySQL, для управления буферным пулом (buffer pool). Clock sweep позволяет эффективно кэшировать часто запрашиваемые страницы данных.
• Кэширование веб-контента: В прокси-серверах и CDN (Content Delivery Network) для кэширования часто запрашиваемых веб-страниц и файлов. Например, в Squid Cache используется модификация Clock sweep.
• Аппаратные системы: В кэш-памяти процессоров (L1, L2, L3) для управления строками кэша. Аппаратная реализация Clock sweep проста и экономична.

¶Критика и ограничения

Несмотря на популярность, Clock sweep имеет ряд критических замечаний:

• Проблема сканирования: При последовательном чтении большого объёма данных (например, при сканировании таблицы в базе данных) алгоритм может вытеснять все страницы, включая часто используемые, так как каждая страница получает бит 1 при первом обращении, но затем сбрасывается при обходе. Это приводит к резкому росту числа ошибок страничного обмена.
• Чувствительность к размеру кэша: При малом размере кэша (например, 4-8 страниц) Clock sweep может вести себя как FIFO, так как время обхода слишком мало для накопления информации о частоте использования.
• Отсутствие учёта частоты: В классической версии алгоритм не различает страницы, к которым обращались один раз и много раз. Это может приводить к вытеснению часто используемых страниц, если они не были посещены в течение одного оборота.

Для устранения этих недостатков были разработаны модификации, такие как Clock-Pro и WSClock, которые добавляют дополнительные биты или учитывают историю обращений.

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

• Название «Clock sweep» происходит от визуального представления алгоритма: стрелка, движущаяся по кругу, напоминает часовую стрелку, а сброс битов доступа — как «стирание» отметок.
• В операционной системе Linux алгоритм Clock-Pro был внедрён в 2008 году (ядро 2.6.28) и заменил предыдущую версию, основанную на LRU, что позволило улучшить производительность при работе с большими объёмами данных.
• Алгоритм Clock sweep используется не только в компьютерных системах, но и в некоторых аппаратных реализациях кэш-памяти, например, в процессорах Intel Core (начиная с архитектуры Nehalem).

¶Источники

• Корбато, Ф. Дж., и др. «Virtual Memory, Processes, and Sharing in Multics». Communications of the ACM, 1968.
• Деннинг, П. Дж. «The Working Set Model for Program Behavior». Communications of the ACM, 1968.
• Чжон, С., и др. «Clock-Pro: An Effective Replacement Algorithm for the Linux Kernel». Proceedings of the 2005 USENIX Annual Technical Conference.
• Тауб, М. «Операционные системы: проектирование и реализация». 3-е издание, 2006.
• Документация ядра Linux: «Page Replacement in Linux». kernel.org, 2023.