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

Эта статья посвящена алгоритмам, специфичным для пейджинга. Краткое описание общих алгоритмов кэширования (например, процессор, диск, база данных, Интернет) см. в разделе Алгоритмы кэширования .

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

Когда страница, которая была выбрана для замены и выгружена, обращается снова, ее необходимо выгрузить (прочитать с диска), а это включает в себя ожидание завершения ввода-вывода. Это определяет качество алгоритма замены страниц: чем меньше время ожидания загрузки страниц, тем лучше алгоритм. Алгоритм замены страниц анализирует ограниченную информацию о доступе к страницам, предоставляемую аппаратным обеспечением, и пытается угадать, какие страницы следует заменить, чтобы минимизировать общее количество промахов страниц, балансируя это с затратами (основное хранилище и время процессора) на сам алгоритм.

Проблема замены страниц является типичной онлайн-проблемой с точки зрения конкурентного анализа в том смысле, что известен оптимальный детерминированный алгоритм.

История

Алгоритмы замены страниц были горячей темой исследований и дискуссий в 1960-х и 1970-х годах. В основном это закончилось разработкой сложных аппроксимаций LRU (наименее используемых в последнее время) и алгоритмов рабочего набора . С тех пор некоторые основные предположения, сделанные традиционными алгоритмами замены страниц, оказались недействительными, что привело к возобновлению исследований. В частности, на производительность алгоритмов замены страниц повлияли следующие тенденции в поведении базового оборудования и программного обеспечения пользовательского уровня:

• Размер первичного хранилища увеличился на несколько порядков. При наличии нескольких гигабайт первичной памяти алгоритмы, требующие периодической проверки каждого кадра памяти, становятся все менее практичными.
• Иерархии памяти стали выше. Стоимость промаха в кэше ЦП гораздо выше. Это усугубляет предыдущую проблему.
• Локальность обращения пользовательского ПО ослабла. В основном это связано с распространением методов объектно-ориентированного программирования , которые отдают предпочтение большому количеству небольших функций, использованием сложных структур данных, таких как деревья и хэш-таблицы , которые имеют тенденцию приводить к хаотичным шаблонам обращения к памяти, а также появлением сборки мусора , которая радикально изменила поведение приложений при доступе к памяти.

Требования к алгоритмам замены страниц изменились из-за различий в архитектуре ядра операционной системы . В частности, большинство современных ядер ОС имеют унифицированные кэши виртуальной памяти и файловой системы, что требует от алгоритма замены страниц выбора страницы среди страниц как виртуальных адресных пространств пользовательских программ, так и кэшированных файлов. Последние страницы имеют специфические свойства. Например, они могут быть заблокированы или иметь требования к порядку записи, налагаемые ведением журнала . Более того, поскольку целью замены страниц является минимизация общего времени ожидания памяти, она должна учитывать требования к памяти, предъявляемые другими подсистемами ядра, которые выделяют память. В результате замена страниц в современных ядрах ( Linux , FreeBSD и Solaris ) имеет тенденцию работать на уровне распределителя памяти ядра общего назначения, а не на более высоком уровне подсистемы виртуальной памяти.

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

Алгоритмы замены могут быть локальными или глобальными.

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

Замена локальных страниц предполагает некоторую форму разделения памяти, которая определяет, сколько страниц должно быть назначено данному процессу или группе процессов. Наиболее популярными формами секционирования являются алгоритмы фиксированного секционирования и сбалансированного набора, основанные на модели рабочего набора . Преимущество локальной замены страниц заключается в ее масштабируемости: каждый процесс может обрабатывать ошибки своих страниц независимо, что приводит к более стабильной производительности этого процесса. Однако глобальная замена страниц более эффективна в целом по системе.

Определение страниц, на которые ссылаются и которые изменяются.

См. также: Виртуальная память и Таблица страниц.

Современные компьютеры общего назначения и некоторые встроенные процессоры поддерживают виртуальную память . Каждый процесс имеет собственное виртуальное адресное пространство. Таблица страниц сопоставляет подмножество виртуальных адресов процесса с физическими адресами. Кроме того, в большинстве архитектур таблица страниц содержит бит «доступа» и бит «грязи» для каждой страницы в таблице страниц. ЦП устанавливает бит доступа, когда процесс читает или записывает память на этой странице. ЦП устанавливает грязный бит, когда процесс записывает память на этой странице. Операционная система может изменять биты доступа и «грязные» биты. Операционная система может обнаруживать доступ к памяти и файлам следующими способами:

• Очистив бит доступа на страницах, присутствующих в таблице страниц процесса. Через некоторое время ОС сканирует таблицу страниц в поисках страниц, для которых бит доступа установлен ЦП. Это быстро, поскольку бит доступа устанавливается автоматически процессором, и неточно, поскольку ОС не получает немедленно уведомление о доступе и не имеет информации о порядке, в котором процесс обращался к этим страницам.
• Путем удаления страниц из таблицы страниц процесса без обязательного удаления их из физической памяти. Следующий доступ к этой странице обнаруживается немедленно, поскольку он вызывает ошибку страницы . Это медленно, поскольку ошибка страницы включает в себя переключение контекста на ОС, программный поиск соответствующего физического адреса, изменение таблицы страниц и переключение контекста обратно на процесс, и точно, поскольку доступ обнаруживается сразу после его возникновения.
• Непосредственно, когда процесс выполняет системные вызовы, которые потенциально получают доступ к кэшу страниц, например read и write в POSIX.

Предварительная очистка

Большинство алгоритмов замены просто возвращают целевую страницу в качестве результата. Это означает, что если целевая страница загрязнена (то есть содержит данные, которые необходимо записать в стабильное хранилище, прежде чем страницу можно будет вернуть), необходимо инициировать ввод-вывод для отправки этой страницы в стабильное хранилище (чтобы очистить страницу). ). На заре виртуальной памяти время, затрачиваемое на очистку, не вызывало особого беспокойства, поскольку виртуальная память впервые была реализована в системах с полнодуплексными каналами к стабильному хранилищу, и очистка обычно перекрывалась подкачкой. С другой стороны, современное аппаратное обеспечение не поддерживает полнодуплексную передачу, и очистка целевых страниц становится проблемой.

Чтобы справиться с этой ситуацией, предварительной очистки применяются различные политики . Предварительная очистка — это механизм, который запускает ввод-вывод на грязных страницах, которые (вероятно) скоро будут заменены. Идея состоит в том, что к тому моменту, когда предварительно очищенная страница действительно будет выбрана для замены, ввод-вывод завершится и страница станет чистой. Предварительная очистка предполагает, что можно определить страницы, которые будут заменены в дальнейшем . Слишком активная предварительная очистка может привести к потере пропускной способности ввода-вывода из-за записи страниц, которые успеют повторно загрязниться, прежде чем будут выбраны для замены.

Проблема (h,k)-страницы

Проблема (h,k)-пейджинга является обобщением модели проблемы пейджинга: пусть h,k — положительные целые числа такие, что $h\leq k$. Мы измеряем производительность алгоритма с помощью кеша размером $h\leq k$ относительно теоретически оптимального алгоритма замены страниц . Если $h<k$, мы предоставляем оптимальный алгоритм замены страниц со строго меньшим ресурсом.

Проблема (h,k)-пейджинга — это способ измерения эффективности онлайн-алгоритма путем сравнения его с производительностью оптимального алгоритма, в частности, с отдельной параметризацией размера кэша онлайн-алгоритма и оптимального алгоритма.

Алгоритмы маркировки

Алгоритмы маркировки — это общий класс алгоритмов пейджинга. Для каждой страницы мы связываем ее с битом, называемым ее меткой. Изначально мы устанавливаем все страницы как немаркированные. На этапе (периоде работы или последовательности запросов) запросов страниц мы отмечаем страницу, когда она впервые запрашивается на этом этапе. Алгоритм маркировки — это такой алгоритм, который никогда не распечатывает отмеченную страницу.

Если ALG — алгоритм разметки с кешем размера k, а OPT — оптимальный алгоритм с кешем размера h, где $h\leq k$, то ALG ${\tfrac {k}{k-h+1}}$-конкурентоспособный. Таким образом, каждый алгоритм маркировки достигает ${\tfrac {k}{k-h+1}}$-конкурентное соотношение.

LRU — это алгоритм маркировки, а FIFO — не алгоритм маркировки.

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

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

Если ALG — консервативный алгоритм с кешем размера k, а OPT — оптимальный алгоритм с кешем размером $h\leq k$, то ALG ${\tfrac {k}{k-h+1}}$-конкурентоспособный. Таким образом, каждый консервативный алгоритм достигает ${\tfrac {k}{k-h+1}}$-конкурентное соотношение.

LRU, FIFO и CLOCK — консервативные алгоритмы.

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

Существует множество алгоритмов замены страниц:

Теоретически оптимальный алгоритм замены страниц

Теоретически оптимальный алгоритм замены страниц (также известный как OPT, алгоритм ясновидения или Белади ) оптимальная политика замены страниц — это алгоритм, который работает следующим образом: когда страницу необходимо заменить, операционная система заменяет страницу, следующее использование которой произойдет дальше всего в будущем. Например, страница, которая не будет использоваться в течение следующих 6 секунд, будет заменена страницей, которая будет использоваться в течение следующих 0,4 секунды.

Этот алгоритм не может быть реализован в операционной системе общего назначения, поскольку невозможно надежно вычислить, сколько времени пройдет до того, как страница будет использована, за исключением случаев, когда все программное обеспечение, которое будет работать в системе, известно заранее и поддается использованию. статический анализ шаблонов ссылок на память или только класс приложений, допускающий анализ во время выполнения. Несмотря на это ограничение, алгоритмы существуют. Это может обеспечить почти оптимальную производительность — операционная система отслеживает все страницы, на которые ссылается программа, и использует эти данные, чтобы решить, какие страницы заменять и выгружать при последующих запусках. Этот алгоритм может обеспечить почти оптимальную производительность, но не при первом запуске программы и только в том случае, если шаблон обращения к памяти программы относительно последователен при каждом запуске.

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

Недавно не использовался

Алгоритм замены недавно использованных страниц (NRU) — это алгоритм, который предпочитает сохранять в памяти страницы, которые недавно использовались. Этот алгоритм работает по следующему принципу: когда на страницу ссылаются, для этой страницы устанавливается бит ссылки, отмечая ее как ссылочную. Аналогично, когда страница модифицируется (записывается), устанавливается модифицированный бит. Установка битов обычно выполняется аппаратно, хотя это можно сделать и на программном уровне.

Через определенный фиксированный интервал времени срабатывает прерывание таймера и очищает ссылочный бит всех страниц, поэтому только страницы, на которые имеются ссылки в пределах текущего интервала таймера, помечаются ссылочным битом. Когда страницу необходимо заменить, операционная система делит страницы на четыре класса:

3. указанный, измененный

2. ссылка, не измененная

1. не упоминается, изменено

0. не упоминается, не изменяется

Хотя кажется невозможным, чтобы страница была изменена, но на нее не было ссылки, это происходит, когда на странице класса 3 бит ссылки очищается прерыванием таймера. Алгоритм NRU выбирает для удаления случайную страницу из самой низкой категории. Таким образом, из четырех вышеупомянутых категорий страниц алгоритм NRU заменит страницу, на которую нет ссылки и которые не будут изменены, если такая страница существует. Обратите внимание, что этот алгоритм подразумевает, что измененная, но не вызываемая ссылками (в пределах последнего интервала таймера) страница менее важна, чем неизмененная страница, на которую часто ссылаются.

NRU — это алгоритм маркировки, поэтому он ${\tfrac {k}{k-h+1}}$-конкурентоспособный.

Первый вошел, первый вышел

Самый простой алгоритм замены страниц — это алгоритм FIFO. Алгоритм замены страниц в порядке поступления (FIFO) — это алгоритм с низкими издержками, который не требует особого учета со стороны операционной системы . Идея очевидна из названия — операционная система отслеживает все страницы в памяти в очереди, причем самые последние поступления располагаются сзади, а самые старые — впереди. Когда страницу необходимо заменить, выбирается страница в начале очереди (самая старая страница). Хотя метод FIFO дешев и интуитивно понятен, на практике он работает плохо. Таким образом, он редко используется в неизмененном виде. В этом алгоритме наблюдается аномалия Белади . Проще говоря, при страничном сбое заменяется кадр, который находился в памяти дольше всего.

Алгоритм замены страниц FIFO используется операционной системой OpenVMS с некоторыми изменениями. Частичный второй шанс предоставляется за счет пропуска ограниченного количества записей с действительными ссылками на таблицы перевода. Кроме того, страницы перемещаются из рабочего набора процессов в общесистемный пул, из которого их можно восстановить, если они еще не использовались повторно.

FIFO — консервативный алгоритм, поэтому он ${\tfrac {k}{k-h+1}}$-конкурентоспособный.

Второй шанс

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

Как следует из названия, «Второй шанс» дает каждой странице «второй шанс» — старая страница, на которую была ссылка, вероятно, используется, и ее не следует заменять новой страницей, на которую не было ссылки.

Часы

Clock — более эффективная версия FIFO, чем Second-chance, поскольку страницы не нужно постоянно перемещать в конец списка, но он выполняет ту же общую функцию, что и Second-Chance. Алгоритм часов хранит в памяти круговой список страниц, при этом «рука» (итератор) указывает на последний просмотренный кадр страницы в списке. Когда происходит ошибка страницы и пустых кадров не существует, бит R (ссылка) проверяется в местоположении руки. Если R равен 0, новая страница помещается на место страницы, на которую указывает «рука», и стрелка перемещается на одну позицию. В противном случае бит R очищается, затем увеличивается стрелка часов, и процесс повторяется до тех пор, пока страница не будет заменена. Этот алгоритм был впервые описан в 1969 году Фернандо Х. Корбато .

Варианты часов

• GCLOCK: обобщенный алгоритм замены страницы часов.
• Clock-Pro хранит циклический список информации о недавно использованных страницах, включая все страницы M в памяти, а также самые последние страницы M, которые были выгружены. Эта дополнительная информация на выгружаемых страницах, как и аналогичная информация, поддерживаемая ARC , помогает ему работать лучше, чем LRU, в больших циклах и однократном сканировании.
• WSчасы. Объединив алгоритм Clock с концепцией рабочего набора (т. е. набора страниц, которые, как ожидается, будут использоваться этим процессом в течение некоторого интервала времени), можно повысить производительность алгоритма. На практике алгоритм «старения» и алгоритм «WSClock», вероятно, являются наиболее важными алгоритмами замены страниц.
• Clock with Adaptive replace (CAR) — алгоритм замены страниц, имеющий производительность, сравнимую с ARC , и существенно превосходящий LRU и CLOCK. Алгоритм CAR является самонастраивающимся и не требует никаких магических параметров, указываемых пользователем.

CLOCK — консервативный алгоритм, поэтому он ${\tfrac {k}{k-h+1}}$-конкурентоспособный.

Последний раз использовался

Алгоритм замены наименее недавно используемых страниц (LRU), хотя и похож по названию на NRU, отличается тем, что LRU отслеживает использование страниц за короткий период времени, тогда как NRU просто просматривает использование за последний тактовый интервал. LRU исходит из того, что страницы, которые наиболее интенсивно использовались в последних нескольких инструкциях, скорее всего, будут активно использоваться и в следующих нескольких инструкциях. Хотя LRU в теории может обеспечить почти оптимальную производительность (почти такую ​​же, как адаптивный кэш замены ), его реализация на практике обходится довольно дорого. Существует несколько методов реализации этого алгоритма, которые пытаются снизить стоимость, сохраняя при этом как можно большую производительность.

Самым дорогим методом является метод связанного списка, который использует связанный список, содержащий все страницы в памяти. В конце этого списка находится страница, которая использовалась реже всего, а в начале — страница, которая использовалась в последний раз. Цена этой реализации заключается в том, что элементы списка придется перемещать при каждом обращении к памяти, а это очень трудоемкий процесс.

Другой метод, требующий аппаратной поддержки, заключается в следующем: предположим, что аппаратное обеспечение имеет 64-битный счетчик, который увеличивается при каждой инструкции. При каждом обращении к странице она получает значение, равное счетчику во время доступа к странице. Всякий раз, когда страницу необходимо заменить, операционная система выбирает страницу с наименьшим счетчиком и заменяет ее.

Из-за затрат на реализацию можно рассмотреть алгоритмы (подобные приведенным ниже), похожие на LRU, но предлагающие более дешевую реализацию.

Одним из важных преимуществ алгоритма LRU является то, что он поддается полному статистическому анализу. Было доказано, например, что LRU никогда не может привести к увеличению количества ошибок страниц более чем в N раз, чем алгоритм OPT, где N пропорционально количеству страниц в управляемом пуле.

С другой стороны, слабость LRU заключается в том, что его производительность имеет тенденцию ухудшаться при многих довольно распространенных эталонных шаблонах. Например, если в пуле LRU имеется N страниц, приложение, выполняющее цикл над массивом из N + 1 страниц, будет вызывать ошибку страницы при каждом доступе. Поскольку циклы в больших массивах являются обычным явлением, было приложено много усилий для модификации LRU, чтобы он лучше работал в таких ситуациях. Многие из предлагаемых модификаций LRU пытаются обнаружить шаблоны зацикливания и переключиться на подходящий алгоритм замены, такой как «Самый последний использованный» (MRU).

Варианты LRU

1. ЛРУ-К удаляет страницу, К-й последний доступ к которой находится дальше всего в прошлом. Например, LRU-1 — это просто LRU, тогда как LRU-2 удаляет страницы в соответствии со временем их предпоследнего доступа. LRU-K значительно превосходит LRU в отношении локальности во времени.
2. АРК ​ Алгоритм расширяет LRU, сохраняя историю недавно удаленных страниц и использует ее для изменения предпочтения недавнего или частого доступа. Он особенно устойчив к последовательному сканированию.
3. 2-й квартал Алгоритм улучшает алгоритмы LRU и LRU/2. Имея две очереди: одну для элементов горячего пути, а другую для элементов медленного пути, элементы сначала помещаются в очередь медленного пути, а после второго доступа к элементам, помещенным в элементы горячего пути. Поскольку ссылки на добавленные элементы сохраняются дольше, чем в алгоритмах LRU и LRU/2, он имеет лучшую очередь горячего пути, что повышает скорость попадания в кеш.

Сравнение ARC с другими алгоритмами (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) можно найти в Megiddo & Modha 2004.

LRU — это алгоритм маркировки, поэтому он ${\tfrac {k}{k-h+1}}$-конкурентоспособный.

случайный

Алгоритм случайной замены заменяет случайную страницу в памяти. Это устраняет накладные расходы на отслеживание ссылок на страницы. Обычно он работает лучше, чем FIFO, а для циклических обращений к памяти он лучше, чем LRU, хотя на практике LRU обычно работает лучше. OS/390 использует глобальную аппроксимацию LRU и возвращается к случайной замене, когда производительность LRU ухудшается, а процессор Intel i860 использовал политику случайной замены (Rhodehamel 1989). ).

Не часто используется (NFU)

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

Основная проблема NFU заключается в том, что он отслеживает частоту использования без учета продолжительности использования. Таким образом, в многопроходном компиляторе страницы, которые интенсивно использовались во время первого прохода, но не нужны во втором проходе, будут иметь преимущество над страницами, которые сравнительно мало используются во втором проходе, поскольку у них более высокие счетчики частоты. Это приводит к плохой производительности. Существуют и другие распространенные сценарии, в которых NFU будет работать аналогичным образом, например, при загрузке ОС. К счастью, существует аналогичный и лучший алгоритм, и его описание приведено ниже.

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

Старение

Алгоритм старения является потомком алгоритма NFU с модификациями, позволяющими учитывать временной интервал использования. Вместо того, чтобы просто увеличивать счетчики ссылок на страницы, уделяя одинаковое внимание ссылкам на страницы независимо от времени, счетчик ссылок на странице сначала сдвигается вправо (делится на 2), а затем добавляется бит ссылки слева от этого двоичного числа. Например, если страница ссылалась на биты 1,0,0,1,1,0 за последние 6 тактов, ее счетчик, на который ссылаются, будет выглядеть следующим образом в хронологическом порядке: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. Ссылки на страницы, сделанные ближе к настоящему времени, имеют большее влияние, чем ссылки на страницы давным-давно. Это гарантирует, что страницы, на которые ссылаются позже, хотя и реже, будут иметь более высокий приоритет по сравнению со страницами, на которые чаще ссылались в прошлом. Таким образом, когда страницу необходимо заменить, будет выбрана страница с наименьшим счетчиком.

Следующий код Python имитирует алгоритм старения. Счетчики $V_{i}$ инициализируются значением 0 и обновляются, как описано выше, через $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$, используя операторы арифметического сдвига .

from collections.abc import Sequence

def simulate_aging(Rs: Sequence, k: int) -> None:
    # Simulate aging
    print(" t  |  R-bits (0-{length})        |  Counters for pages 0-{length}".format(length=len(Rs)))
    Vs = [0] * len(Rs[0])
    for t, R in enumerate(Rs):
        Vs[:] = [R[i] << (k - 1) | V >> 1
                 for i, V in enumerate(Vs)]
        print("{:02d}  |  {}  |  [{}]".format(t, R,
                                              ", ".join(["{:0{}b}".format(V, k)
                                                         for V in Vs])))

В данном примере R-битов для 6 страниц за 5 тактов функция печатает следующий вывод, в котором перечислены R-биты для каждого такта t и отдельные значения счетчика. $V_{i}$ для каждой страницы в двоичном представлении.

>>> Rs = [[1,0,1,0,1,1], [1,1,0,0,1,0], [1,1,0,1,0,1], [1,0,0,0,1,0], [0,1,1,0,0,0]]
>>> k = 8
>>> simulate_aging(Rs, k)
 t  |  R-bits (0-5)        |  Counters for pages 0-5
00  |  [1, 0, 1, 0, 1, 1]  |  [10000000, 00000000, 10000000, 00000000, 10000000, 10000000]
01  |  [1, 1, 0, 0, 1, 0]  |  [11000000, 10000000, 01000000, 00000000, 11000000, 01000000]
02  |  [1, 1, 0, 1, 0, 1]  |  [11100000, 11000000, 00100000, 10000000, 01100000, 10100000]
03  |  [1, 0, 0, 0, 1, 0]  |  [11110000, 01100000, 00010000, 01000000, 10110000, 01010000]
04  |  [0, 1, 1, 0, 0, 0]  |  [01111000, 10110000, 10001000, 00100000, 01011000, 00101000]

Обратите внимание, что старение отличается от LRU в том смысле, что старение может отслеживать ссылки только в последних 16/32 (в зависимости от разрядности целых чисел процессора) временных интервалах. Следовательно, две страницы могут ссылаться на счетчики 00000000, даже если к одной странице обращались 9 интервалов назад, а к другой — 1000 интервалов назад. Вообще говоря, знания использования в течение последних 16 интервалов достаточно для принятия правильного решения о том, какую страницу заменить. Таким образом, старение может обеспечить почти оптимальную производительность за умеренную цену.

Алгоритм замены страниц наибольшего расстояния (LDF)

Основная идея этого алгоритма — это локальность ссылки, используемая в LRU, но разница в том, что в LDF локализация основана на расстоянии, а не на используемых ссылках. В LDF замените страницу, которая находится на самом большом расстоянии от текущей страницы. Если две страницы находятся на одинаковом расстоянии, то страница, следующая за текущей при вращении против часовой стрелки, будет заменена.

Детали реализации

Методы для аппаратного обеспечения без ссылочного бита

Многие из рассмотренных выше методов предполагают наличие ссылочного бита, связанного с каждой страницей. Некоторое оборудование не имеет такого бита, поэтому его эффективное использование требует методов, которые хорошо работают без него.

Одним из ярких примеров является VAX оборудование под управлением OpenVMS . Эта система знает, была ли страница изменена, но не обязательно, была ли она прочитана. Этот подход известен как кэширование вторичных страниц. Страницы, удаленные из рабочих наборов (обычно из частной памяти процесса), помещаются в списки специального назначения, оставаясь в физической памяти в течение некоторого времени. Удаление страницы из рабочего набора технически не является операцией замены страницы, но фактически идентифицирует эту страницу как кандидата. Страница, резервное хранилище которой все еще действует (содержимое которой не загрязнено и не нуждается в сохранении иным образом), помещается в конец списка свободных страниц. Страница, требующая записи в резервное хранилище, будет помещена в список измененных страниц. Эти действия обычно запускаются, когда размер списка свободных страниц падает ниже регулируемого порога.

Страницы для удаления из рабочего набора могут выбираться по существу случайным образом с ожиданием, что в случае неудачного выбора будущая ссылка может извлечь эту страницу из списка свободных или измененных до того, как она будет удалена из физической памяти. Страница, на которую ссылаются таким образом, будет удалена из списка «Свободные» или «Измененные» и возвращена в рабочий набор процесса. Модифицированный список страниц дополнительно предоставляет возможность записывать страницы во резервное хранилище группами по несколько страниц, что повышает эффективность. Эти страницы затем можно будет поместить в список бесплатных страниц. Последовательность страниц, которая попадает в начало списка свободных страниц, напоминает результаты работы механизма LRU или NRU, а общий эффект имеет сходство с алгоритмом второго шанса, описанным ранее.

Другой пример используется ядром Linux на ARM . Недостаток аппаратной функциональности компенсируется предоставлением двух таблиц страниц — таблиц страниц, собственных для процессора, без ссылочных и «грязных» битов , и таблиц страниц, поддерживаемых программным обеспечением с наличием необходимых битов. Эмулируемые биты в таблице, поддерживаемой программным обеспечением, устанавливаются в результате ошибок страницы. Чтобы получить ошибки страницы, очистка эмулируемых битов во второй таблице отменяет некоторые права доступа к соответствующей странице, что реализуется путем изменения собственной таблицы.

Кэш страниц в Linux

Linux использует единый страничный кеш для

• brk и анонимный mmapред -регионы. Сюда входит куча и стек программ пользовательского пространства . Он написан для замены при выгрузке.
• Неанонимный (с файловым обеспечением) mmapрегионы ред. Если физическая страница присутствует в памяти и не изменяется конфиденциально, она используется совместно с файловым кешем или буфером.
• Общая память, полученная через shm_open.
• в Файловая система tmpfs памяти; написано для замены при выгрузке.
• Файловый кэш в том числе; записывается в базовое блочное хранилище (возможно, через буфер, см. ниже) при выгрузке.
• Кэш блочных устройств , называемый в Linux «буфером» (не путать с другими структурами, также называемыми буферами, например теми, которые используются для каналов и буферов, используемых внутри Linux); записывается в базовое хранилище при выгрузке.

Единый страничный кэш работает с блоками страниц наименьшего размера, поддерживаемыми ЦП (4 КиБ в ARMv8 , x86 и x86-64 ), при этом некоторые страницы следующего большего размера (2 МБ в x86-64 ) называются «огромными страницами». Линукс. Страницы в страничном кэше разделены на «активный» и «неактивный» набор. Оба набора хранят список страниц LRU. В основном случае, когда к странице обращается программа пользовательского пространства, она помещается в заголовок неактивного набора. При повторном доступе к нему он перемещается в активный список. Linux перемещает страницы из активного набора в неактивный набор по мере необходимости, чтобы активный набор был меньше неактивного набора. Когда страница перемещается в неактивный набор, она удаляется из таблицы страниц любого адресного пространства процесса без выгрузки из физической памяти. Когда страница удаляется из неактивного набора, она выгружается из физической памяти. Размер «активного» и «неактивного» списка можно запросить из /proc/meminfo в полях «Активный», «Неактивный», «Активный(анон)», «Неактивный(анон)», «Активный(файл)» и «Неактивный(файл)».

Рабочий набор

Основная статья: Рабочий набор

Рабочий набор процесса — это набор страниц, которые, как ожидается, будут использоваться этим процессом в течение некоторого интервала времени.

«Модель рабочего набора» не является алгоритмом замены страниц в строгом смысле слова (на самом деле это своего рода среднесрочный планировщик ).

Дальнейшее чтение

• Вонг, Кин-Юнг (23 января 2006 г.). «Политика замены веб-кэша: прагматичный подход». Сеть IEEE . 20 (1). ИИЭР: 28–34. дои : 10.1109/MNET.2006.1580916 . ISSN   0890-8044 . S2CID   17969287 . Регистрационный номер INSPEC 8964134.
• Ахо, Альфред В.; Деннинг, Питер Дж.; Уллман, Джеффри Д. (январь 1971 г.). «Принципы оптимальной замены страниц» . Журнал АКМ . 18 (1). Нью-Йорк, штат Нью-Йорк, США: ACM: 80–93. дои : 10.1145/321623.321632 . S2CID   3154537 .
• Таненбаум, Эндрю С. (1997). Операционные системы: проектирование и реализация (2-е изд.). Река Аппер-Сэддл, Нью-Джерси, США: Прентис-Холл. ISBN  0-13-638677-6 . LCCN   96037153 . ОЛ   998396М .
• Таненбаум, Эндрю С. (2001). Современные операционные системы (2-е изд.). Река Аппер-Сэддл, Нью-Джерси, США: Прентис-Холл. ISBN  978-0-13-031358-4 . LCCN   00051666 . OCLC   45284637 . ОЛ   24214243М . Интернет-отрывок об алгоритмах замены страниц: Алгоритмы замены страниц .
• Гласс, Гидеон; Цао, Пей (15–18 июня 1997 г.). Адаптивная замена страниц на основе поведения ссылок на память . 1997 Международная конференция ACM SIGMETRICS по измерению и моделированию компьютерных систем . Сиэтл, Вашингтон, США: ACM. стр. 115–126. дои : 10.1145/258612.258681 . ISBN  0-89791-909-2 . Также доступен в расширенной форме как Гласс, Гидеон; Цао, Пей (1997). «Технический отчет 1338» . Кафедра компьютерных наук Университета Висконсин-Мэдисон .
• Ким, Чон Мин; и др. (17–21 октября 2000 г.). Высокопроизводительная унифицированная схема управления буфером с низкими издержками, использующая последовательные и циклические ссылки (PDF) . 4-й симпозиум Usenix по проектированию и внедрению операционных систем (OSDI'2000) . Том. 4. Сан-Диего, Калифорния, США: Ассоциация USENIX. Архивировано (PDF) из оригинала 18 сентября 2004 г.
• Смарагдакис, Яннис; Каплан, Скотт; Уилсон, Пол (1–4 мая 1999 г.). ЭЭЛРУ: простая и эффективная адаптивная замена страниц (PDF) . 1999 Международная конференция ACM SIGMETRICS по измерению и моделированию компьютерных систем . Атланта, Джорджия, США: ACM. стр. 122–133. дои : 10.1145/301453.301486 . ISBN  1-58113-083-Х . Архивировано (PDF) из оригинала 4 марта 2016 г.
• Цзян, Сун; Чжан, Сяодун (15–19 июня 2002 г.). LIRS: замена набора последних ссылок с низкой межсправочной информацией (PDF) . 2002 Международная конференция ACM SIGMETRICS по измерению и моделированию компьютерных систем . Марина Дель Рей, Калифорния, США: ACM. стр. 31–42. дои : 10.1145/511334.511340 . ISBN  1-58113-531-9 . Архивировано (PDF) из оригинала 12 июня 2019 года.
• Ли, Донхи; и др. (1–4 сентября 1997 г.). Реализация и оценка эффективности политики замены LRFU . 23-я конференция Euromicro «Новые рубежи информационных технологий» . Будапешт, Венгрия: Компьютерное общество IEEE. стр. 106–111. дои : 10.1109/EMSCNT.1997.658446 . ISBN  0-8186-8215-9 . Регистрационный номер INSPEC 5856800.
• Чжоу, Юаньюань; Филбин, Джеймс; Ли, Кай (25–30 июня 2001 г.). Алгоритм многоочередной замены буферных кэшей второго уровня (PDF) . 2001 Ежегодная техническая конференция USENIX . Бостон, Массачусетс, США: Ассоциация USENIX. стр. 91–104. ISBN  1-880446-09-Х . Архивировано (PDF) из оригинала 24 ноября 2005 г.