Алгоритм замены страницы - Page replacement algorithm

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

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

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

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

История

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

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

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

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

Алгоритмы замены могут быть местный или же Глобальный.

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

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

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

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

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

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

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

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

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

Предварительный пейджинг

Смотрите также: Пейджинг

Некоторые системы используют пейджинг по запросу - ожидание фактического запроса страницы перед ее загрузкой в ​​ОЗУ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. упомянутые, измененные

2. упомянутые, не измененные

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

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

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

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

Первым пришел-первым вышел

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

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

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

Второй шанс

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

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

Часы

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

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

• GCLOCK: Обобщенный алгоритм замены страницы часов.^[9]
• Clock-Pro хранит круговой список информации о недавно использованных страницах, включая все M страниц в памяти, а также самые последние M страниц, которые были выгружены. Эта дополнительная информация на выгружаемых страницах, как и аналогичная информация, поддерживаемая ARC, помогает работать лучше, чем LRU при больших циклах и одноразовых сканированиях.^[10]
• WSclock.^[11] Комбинируя алгоритм Clock с концепцией рабочего набора (т.е. набора страниц, которые, как ожидается, будут использоваться этим процессом в течение некоторого интервала времени), производительность алгоритма может быть улучшена. На практике, вероятно, наиболее важными алгоритмами замены страниц являются алгоритм «старения» и алгоритм «WSClock».^[12][13]
• Часы с адаптивной заменой (CAR) - это алгоритм замены страниц, производительность которого сопоставима с ARC, и существенно превосходит LRU и CLOCK.^[14] Алгоритм CAR самонастраивается и не требует заданных пользователем магических параметров.

ЧАСЫ - консервативный алгоритм, поэтому он ${\displaystyle {\dfrac {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

1. LRU-K^[15] удаляет страницу, K-й доступ к которой самый последний в прошлом. Например, LRU-1 - это просто LRU, тогда как LRU-2 удаляет страницы согласно времени их предпоследнего доступа. LRU-K значительно улучшает LRU в отношении местоположения во времени.
2. В ARC^[16] Алгоритм расширяет LRU, сохраняя историю недавно удаленных страниц и используя это, чтобы изменить предпочтение на недавний или частый доступ. Он особенно устойчив к последовательному сканированию.

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

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

Случайный

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

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

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

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

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

Старение

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

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

def simulate_aging(Рупий, k: int) -> Никто:    "" "Имитация старения" ""    Против = [0] * len(Рупий[0])    за т, р в перечислять(Рупий):        за я в классифицировать(len(Против)):            Против[я] = р[я] << k - 1 | Против[я] >> 1        Распечатать('% 02d  |  % s  |  [% s]' % (т, р, ', '.присоединиться([формат(V, '0% dб ' % k) за V в Против])))Рупий = [[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 = 8simulate_aging(Рупий, k)

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

 т | R-биты (0-5) | Счетчики страниц 0-500 | [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 замените страницу, которая находится на самом большом расстоянии от текущей страницы. Если две страницы находятся на одинаковом расстоянии, то страница, которая находится рядом с текущей страницей при повороте против часовой стрелки, будет заменена.^[20]

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

Методы аппаратной без ссылки бит

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

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

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

Другой пример используется Ядро Linux на РУКА. Отсутствие аппаратной функциональности компенсируется наличием двух таблиц страниц - таблиц страниц для процессора, без битов, на которые есть ссылки, и грязные биты, и таблицы страниц, поддерживаемые программным обеспечением, с необходимыми битами. Эмулируемые биты в таблице, поддерживаемой программным обеспечением, устанавливаются ошибками страниц. Чтобы получить ошибки страниц, очистка эмулированных битов во второй таблице отменяет некоторые права доступа к соответствующей странице, что реализуется путем изменения собственной таблицы.

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

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

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

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

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

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

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

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

Рекомендации

1. Белл, Джон. «Примечания к курсу операционных систем: виртуальная память». Университет Иллинойса в Чикагском инженерном колледже. В архиве из оригинала 23 сентября 2018 г.. Получено 21 июля 2017.
2. Джонс, Дуглас В. «22С: 116 Конспект лекций». Департамент компьютерных наук Университета Айовы. В архиве с оригинала 30 июня 2012 г.. Получено 18 марта 2008.
3. Торрес, Пол; и другие. "CS111 Лекция 11 примечания". UCLA Департамент компьютерных наук. Архивировано из оригинал 9 января 2009 г.
4. Bahn, Hyokyung; Но, Сэм Х. (12–14 февраля 2003 г.). Пересмотр характеристики поведения веб-ссылок: свидетельства дихотомического управления кешем. Международная конференция по информационным сетям 2003 г.. Чеджу, Южная Корея: Springer-Verlag. С. 1018–1027. Дои:10.1007/978-3-540-45235-5_100. ISBN  978-3-540-40827-7.
5. Зильбершац, Авраам; Гэлвин, Питер Баер; Ганье, Грег (14 декабря 2004 г.). Понятия операционной системы (7-е изд.). Хобокен, Нью-Джерси, США: John Wiley & Sons. п. 339. ISBN  0-47169-466-5. OCLC  56913661.
6. Справка VMS - Параметры системы, TBSKIPWSL
7. Таненбаум, Эндрю С. (2001). Современные операционные системы (2-е изд.). Река Аппер Сэдл, Нью-Джерси, США: Прентис-Холл. п.218 (4.4.5). ISBN  978-0-13-031358-4. LCCN  00051666. OCLC  45284637. ПР  24214243M.
8. Корбато, Фернандо Х. (1969). «Эксперимент по пейджингу с системой Multics» (PDF). Festschrift: В честь П. М. Морса. MIT Press. С. 217–228.
9. Смит, Алан Джей (сентябрь 1978 г.). «Последовательность и предварительная выборка в системах баз данных». Транзакции ACM в системах баз данных. Нью-Йорк, Нью-Йорк, США: ACM. 3 (3): 223–247. Дои:10.1145/320263.320276. S2CID  11611563.
10. Цзян, Сун; Чен, Фэн; Чжан, Сяодун (10–15 апреля 2005 г.). ЧАСЫ-Pro: эффективное улучшение замены ЧАСОВ (PDF). Ежегодная техническая конференция USENIX 2005 г.. Анахайм, Калифорния, США: Ассоциация USENIX. п. 35. В архиве (PDF) с оригинала 12 июня 2019 г.. Получено 24 марта 2009.
11. Карр, Ричард В .; Хеннесси, Джон Л. (14–16 декабря 1981 г.). WSCLOCK—a simple and effective algorithm for virtual memory management (gzipped PDF). Eighth ACM symposium on Operating systems principles. Pacific Grove, CA, USA: ACM. pp. 87–95. Дои:10.1145/800216.806596. ISBN  0-89791-062-1. В архиве from the original on 10 June 2007.
12. Gottlieb, Allan. "WSClock". New York University Computer Science Department. В архиве из оригинала 30 июля 2012 г.. Получено 12 июн 2019.
13. Tanenbaum, Andrew S. "Page Replacement Algorithms". InformIT. В архиве from the original on 10 September 2012. Получено 12 июн 2019.
14. Bansal, Sorav & Modha, Dharmendra S. (31 March – 2 April 2004). CAR: Clock with Adaptive Replacement (PDF). 3rd USENIX Conference on File and Storage Technologies (FAST '04). San Francisco, CA, USA: USENIX Association. pp. 187–200. CiteSeerX  10.1.1.105.6057. В архиве (PDF) from the original on 31 July 2004.
15. O'Neil, Elizabeth J.; и другие. (25–28 May 1993). The LRU-K page replacement algorithm for database disk buffering (PDF). 1993 ACM SIGMOD international conference on Management of data. Washington, D.C., USA: ACM. pp. 297–306. CiteSeerX  10.1.1.18.1434. Дои:10.1145/170035.170081. ISBN  0-89791-592-5. В архиве (PDF) из оригинала 6 сентября 2019 г.. Получено 29 августа 2019.
16. Megiddo, Nimrod & Modha, Dharmendra S. (31 March – 2 April 2003). ARC: A Self-Tuning, Low Overhead Replacement Cache (PDF). 2nd USENIX Conference on File and Storage Technologies (FAST '03). San Francisco, CA, USA: USENIX Association. pp. 115–130. В архиве (PDF) from the original on 8 February 2010.
17. Megiddo, Nimrod & Modha, Dharmendra S. (2004). "Outperforming LRU with an Adaptive Replacement Cache Algorithm" (PDF). Компьютер. IEEE Computer Society. 37 (4): 58. CiteSeerX  10.1.1.231.498. Дои:10.1109/MC.2004.1297303. S2CID  5507282. В архиве (PDF) from the original on 21 October 2012. Получено 20 сентября 2013.
18. Rhodehamel, Michael W. (2–4 October 1989). The Bus Interface and Paging Units of the i860 Microprocessor. 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors. Cambridge, MA, USA: IEEE. pp. 380–384. Дои:10.1109/ICCD.1989.63392. ISBN  0-8186-1971-6. INSPEC Accession Number 3719504.
19. Tanenbaum, Andrew S.; Bos, Herbert (2015). Modern Operating Systems (4-е изд.). Boston, MA, USA: Pearson. п. 215. ISBN  978-0-13-359162-0. ПР  25620855M.
20. Kumar, Gyanendra; Tomar, Parul (September 2017). "A Novel Longest Distance First Page Replacement Algorithm". Indian Journal of Science and Technology. 10 (30): 1–6. Дои:10.17485/ijst/2017/v10i30/115500. ISSN  0974-6846. В архиве from the original on 7 September 2017.
21. See explanation at the start of /mm/workingset.c in the Linux source
22. Corbet, Jonathan Corbet (2 May 2012). "Better active/inactive list balancing". LWN.net.

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

• Wong, Kin-Yeung (23 January 2006). "Web cache replacement policies: a pragmatic approach". IEEE Network. IEEE. 20 (1): 28–34. Дои:10.1109/MNET.2006.1580916. ISSN  0890-8044. S2CID  17969287. INSPEC Accession Number 8964134.
• Aho, Alfred V.; Denning, Peter J.; Ullman, Jeffrey D. (January 1971). "Principles of Optimal Page Replacement". Журнал ACM. Нью-Йорк, Нью-Йорк, США: ACM. 18 (1): 80–93. Дои:10.1145/321623.321632. S2CID  3154537.
• Tanenbaum, Andrew S. (1997). Operating Systems: Design and Implementation (2-е изд.). Upper Saddle River, NJ, USA: Prentice-Hall. ISBN  0-13-638677-6. LCCN  96037153. ПР  998396M.
• Tanenbaum, Andrew S. (2001). Modern Operating Systems (2-е изд.). Upper Saddle River, NJ, USA: Prentice-Hall. ISBN  978-0-13-031358-4. LCCN  00051666. OCLC  45284637. ПР  24214243M. Online excerpt on page replacement algorithms: Page Replacement Algorithms.
• Johnson, Theodore; Shasha, Dennis (12–15 September 1994). 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm (PDF). 20th International Conference on Very Large Data Bases. Santiago de Chile, Chile: Morgan Kaufmann. pp. 439–450. ISBN  1-55860-153-8. В архиве (PDF) from the original on 17 March 2020. Получено 31 июля 2005.
• Glass, Gideon; Cao, Pei (15–18 June 1997). Adaptive page replacement based on memory reference behavior. 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. Seattle, WA, USA: ACM. pp. 115–126. Дои:10.1145/258612.258681. ISBN  0-89791-909-2. Also available in extended form as "Technical Report 1338". Department of Computer Sciences, University of Winconsin-Madison.
• Kim, Jong Min; и другие. (17–21 October 2000). A Low-Overhead High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping References (PDF). 4th Usenix Symposium on Operating System Design and Implementation (OSDI'2000). 4. San Diego, CA, USA: USENIX Association. В архиве (PDF) from the original on 18 September 2004.
• Smaragdakis, Yannis; Kaplan, Scott; Wilson, Paul (1–4 May 1999). EELRU: simple and effective adaptive page replacement (PDF). 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. Atlanta, GA, USA: ACM. pp. 122–133. Дои:10.1145/301453.301486. ISBN  1-58113-083-X. В архиве (PDF) from the original on 4 March 2016. Получено 11 января 2015.
• Jiang, Song; Zhang, Xiaodong (15–19 June 2002). LIRS: a Low Inter Reference recency Set replacement (PDF). 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. Marina Del Rey, CA, USA: ACM. pp. 31–42. Дои:10.1145/511334.511340. ISBN  1-58113-531-9. В архиве (PDF) from the original on 12 June 2019. Получено 1 августа 2007.
• Lee, Donghee; и другие. (1–4 September 1997). Implementation and Performance Evaluation of the LRFU Replacement Policy. 23rd Euromicro Conference New Frontiers of Information Technology. Budapest, Hungary: IEEE Computer Society. pp. 106–111. Дои:10.1109/EMSCNT.1997.658446. ISBN  0-8186-8215-9. INSPEC Accession Number 5856800.
• Zhou, Yuanyuan; Philbin, James; Li, Kai (25–30 June 2001). The Multi-Queue Replacement Algorithm for Second-Level Buffer Caches (PDF). 2001 USENIX Annual Technical Conference. Boston, MA, USA: USENIX Association. pp. 91–104. ISBN  1-880446-09-X. В архиве (PDF) from the original on 24 November 2005.