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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблема (h,k)-пагинации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. ссылается, изменяет

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

1. не указано, изменено

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

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

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

Первый пришел, первый ушел

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

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

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

Второй шанс

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

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

Часы

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

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

GCLOCK: Обобщенный алгоритм замены страницы часов. ^[10]
Clock-Pro хранит циклический список информации о недавно использованных страницах, включая все страницы M в памяти, а также самые последние страницы M, которые были выгружены. Эта дополнительная информация о выгруженных страницах, как и аналогичная информация, поддерживаемая ARC , помогает ему работать лучше, чем LRU, на больших циклах и одноразовых сканированиях. ^[11]
WSclock. ^[12] Объединив алгоритм Clock с концепцией рабочего набора (т. е. набора страниц, которые, как ожидается, будут использоваться этим процессом в течение некоторого интервала времени), можно улучшить производительность алгоритма. На практике алгоритм «старения» и алгоритм «WSClock» являются, вероятно, наиболее важными алгоритмами замены страниц. ^[13]^[14]
Clock with Adaptive Replacement (CAR) — это алгоритм замены страниц, производительность которого сопоставима с ARC , и который существенно превосходит как LRU, так и CLOCK. ^[15] Алгоритм 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 пытаются обнаружить шаблоны ссылок цикла и переключиться на подходящий алгоритм замены, например Most Recently Used (MRU).

Варианты LRU

LRU-K ^[16] вытесняет страницу, K-й из которой последний доступ находится дальше всего в прошлом. Например, LRU-1 — это просто LRU, тогда как LRU-2 вытесняет страницы в соответствии со временем их предпоследнего доступа. LRU-K значительно улучшает LRU в отношении локальности во времени.
Алгоритм ARC ^[17] расширяет LRU, сохраняя историю недавно вытесненных страниц и используя ее для изменения предпочтений на недавний или частый доступ. Он особенно устойчив к последовательному сканированию.
Алгоритм 2Q ^[18] улучшает алгоритм LRU и LRU/2. Имея две очереди, одну для элементов горячего пути, а другую для элементов медленного пути, элементы сначала помещаются в очередь медленного пути, а после второго доступа к элементам помещаются в элементы горячего пути. Поскольку ссылки на добавленные элементы хранятся дольше, чем в алгоритме LRU и LRU/2, он имеет лучшую очередь горячего пути, которая повышает частоту попаданий в кэш.

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

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

Случайный

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

Нечасто используемый (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)$

из  collections.abc  импортировать  последовательностьdef  simulation_aging ( Rs :  Sequence ,  k :  int )  ->  None :  # Моделирование старения  print ( " t | R-биты (0- {length} ) | Счетчики для страниц 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$ и отдельные значения счетчика для каждой страницы в двоичном представлении. ^[21] $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 >>> simulation_aging ( Rs , k ) t | R-биты (0-5) | Счетчики для страниц 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, а общий эффект имеет сходство с алгоритмом Second-Chance, описанным ранее.

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

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

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

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

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

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

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

«Модель рабочего набора» не является алгоритмом замены страниц в строгом смысле (на самом деле это своего рода среднесрочный планировщик ) ^{[ необходимо разъяснение ]}

Ссылки

^ Белл, Джон. «Конспект курса операционных систем: виртуальная память». Университет Иллинойса в Чикагском инженерном колледже . Архивировано из оригинала 23 сентября 2018 года . Получено 21 июля 2017 года .
^ ab Jones, Douglas W. "22C:116 Lecture Notes". University of Iowa Department of Computer Science . Архивировано из оригинала 30 июня 2012 г. Получено 18 марта 2008 г.
^ Torrez, Paul; et al. "CS111 Lecture 11 notes". UCLA Computer Science Department . Архивировано из оригинала 9 января 2009 г.
^ Bahn, Hyokyung; Noh, Sam H. (12–14 февраля 2003 г.). Пересмотр характеристики поведения веб-ссылок: доказательства дихотомизированного управления кэшем . Международная конференция по информационным сетям 2003 г. Чеджу, Южная Корея: Springer-Verlag. стр. 1018–1027. doi :10.1007/978-3-540-45235-5_100. ISBN 978-3-540-40827-7.
^ Джейн, Аканкша; Лин, Кэлвин (2016). Назад в будущее: использование алгоритма Белади для улучшенной замены кэша (PDF) . Международный симпозиум по компьютерной архитектуре (ISCA). Сеул, Южная Корея: IEEE. doi :10.1109/ISCA.2016.17.
^ Зильбершатц, Абрахам; Гэлвин, Питер Баер; Ганье, Грег (14 декабря 2004 г.). Концепции операционных систем (7-е изд.). Хобокен, Нью-Джерси, США: John Wiley & Sons. стр. 339. ISBN 0-47169-466-5. OCLC 56913661.
^ Справка VMS — Параметры системы, TBSKIPWSL
^ Таненбаум, Эндрю С. (2001). Современные операционные системы (2-е изд.). Аппер Сэддл Ривер, Нью-Джерси, США: Prentice-Hall. стр. 218 (4.4.5). ISBN 978-0-13-031358-4. LCCN 00051666. OCLC 45284637. OL 24214243M.
^ Корбато, Фернандо Дж. (1969). «Эксперимент по пейджингу с системой Multics» (PDF) . Сборник: In Honor of PM Morse . MIT Press . стр. 217–228.
^ Смит, Алан Джей (сентябрь 1978 г.). «Последовательность и предварительная выборка в системах баз данных». ACM Transactions on Database Systems . 3 (3). Нью-Йорк, штат Нью-Йорк, США: ACM: 223–247. doi : 10.1145/320263.320276 . S2CID 11611563.
^ Цзян, Сун; Чэнь, Фэн; Чжан, Сяодун (10–15 апреля 2005 г.). CLOCK-Pro: эффективное улучшение замены CLOCK (PDF) . Ежегодная техническая конференция USENIX 2005 г. Анахайм, Калифорния, США: Ассоциация USENIX. стр. 35. Архивировано (PDF) из оригинала 12 июня 2019 г. . Получено 24 марта 2009 г. .
^ Карр, Ричард В.; Хеннесси, Джон Л. (14–16 декабря 1981 г.). WSCLOCK — простой и эффективный алгоритм управления виртуальной памятью (сжатый PDF) . Восьмой симпозиум ACM по принципам операционных систем. Пасифик-Гроув, Калифорния, США: ACM. стр. 87–95. doi :10.1145/800216.806596. ISBN 0-89791-062-1. Архивировано из оригинала 10 июня 2007 года.
^ Готтлиб, Аллан. "WSClock". New York University Computer Science Department . Архивировано из оригинала 30 июля 2012 года . Получено 12 июня 2019 года .
^ Таненбаум, Эндрю С. «Алгоритмы замены страниц». InformIT . Архивировано из оригинала 10 сентября 2012 г. Получено 12 июня 2019 г.
^ Bansal, Sorav & Modha, Dharmendra S. (31 марта – 2 апреля 2004 г.). CAR: Clock with Adaptive Replacement (PDF) . 3rd USENIX Conference on File and Storage Technologies (FAST '04). Сан-Франциско, Калифорния, США: Ассоциация USENIX. стр. 187–200. CiteSeerX 10.1.1.105.6057 . Архивировано (PDF) из оригинала 31 июля 2004 г.
^ O'Neil, Elizabeth J.; et al. (25–28 мая 1993 г.). Алгоритм замены страниц LRU-K для буферизации диска базы данных (PDF) . Международная конференция ACM SIGMOD 1993 года по управлению данными. Вашингтон, округ Колумбия, США: ACM. стр. 297–306. CiteSeerX 10.1.1.18.1434 . doi :10.1145/170035.170081. ISBN 0-89791-592-5. Архивировано (PDF) из оригинала 6 сентября 2019 года.
^ Megiddo, Nimrod & Modha, Dharmendra S. (31 марта – 2 апреля 2003 г.). ARC: самонастраивающийся кэш с низкими накладными расходами (PDF) . 2-я конференция USENIX по технологиям хранения файлов и хранения (FAST '03). Сан-Франциско, Калифорния, США: Ассоциация USENIX. стр. 115–130. Архивировано (PDF) из оригинала 8 февраля 2010 г.
^ Джонсон, Теодор; Шаша, Деннис (12–15 сентября 1994 г.). 2Q: Алгоритм замены управления буфером с низкими накладными расходами и высокой производительностью (PDF) . 20-я Международная конференция по сверхбольшим базам данных. Сантьяго-де-Чили, Чили: Morgan Kaufmann. С. 439–450. ISBN 1-55860-153-8. Архивировано (PDF) из оригинала 17 марта 2020 г. . Получено 31 июля 2005 г. .
^ Megiddo, Nimrod & Modha, Dharmendra S. (2004). "Outperforming LRU with an Adaptive Replacement Cache Algorithm" (PDF) . Компьютер . 37 (4). IEEE Computer Society: 58. CiteSeerX 10.1.1.231.498 . doi :10.1109/MC.2004.1297303. S2CID 5507282. Архивировано (PDF) из оригинала 21 октября 2012 г. . Получено 20 сентября 2013 г. .
^ Rhodehamel, Michael W. (2–4 октября 1989 г.). Интерфейс шины и пейджинговые устройства микропроцессора i860 . Международная конференция IEEE 1989 года по проектированию компьютеров: СБИС в компьютерах и процессорах. Кембридж, Массачусетс, США: IEEE. стр. 380–384. doi :10.1109/ICCD.1989.63392. ISBN 0-8186-1971-6. Регистрационный номер INSPEC 3719504.
^ Таненбаум, Эндрю С.; Бос, Герберт (2015). Современные операционные системы (4-е изд.). Бостон, Массачусетс, США: Пирсон. п. 215. ИСБН 978-0-13-359162-0. ОЛ 25620855М.
^ См. объяснение в начале /mm/workingset.c в исходном коде Linux.
^ Корбет, Джонатан Корбет (2 мая 2012 г.). «Лучшая балансировка активных/неактивных списков». LWN.net .

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

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