В компьютерной операционной системе, которая использует разбиение на страницы для управления виртуальной памятью , алгоритмы замены страниц решают, какие страницы памяти следует выгружать, что иногда называется подкачкой, или записывать на диск, когда необходимо выделить страницу памяти. Замена страницы происходит, когда запрошенная страница отсутствует в памяти ( ошибка страницы ), и свободная страница не может использоваться для удовлетворения выделения, либо потому, что их нет, либо потому, что количество свободных страниц ниже некоторого порогового значения.
При повторном обращении к странице, которая была выбрана для замены и выгружена, она должна быть выгружена (считана с диска), что предполагает ожидание завершения ввода-вывода. Это определяет качество алгоритма замены страниц: чем меньше время ожидания загрузки страниц, тем лучше алгоритм. Алгоритм замены страниц смотрит на ограниченную информацию о доступах к страницам, предоставляемую оборудованием, и пытается угадать, какие страницы следует заменить, чтобы минимизировать общее количество пропусков страниц, при этом уравновешивая это затратами (основное хранилище и время процессора) сам алгоритм.
Проблема замены страниц - это типичная онлайн-проблема с точки зрения конкурентного анализа в том смысле, что известен оптимальный детерминированный алгоритм.
История
Алгоритмы замены страниц были горячей темой исследований и дискуссий в 1960-х и 1970-х годах. Это в основном закончилось разработкой сложных LRU (реже используемых) приближений и алгоритмов рабочего набора . С тех пор некоторые базовые предположения, сделанные традиционными алгоритмами замены страниц, были признаны недействительными, что привело к возрождению исследований. В частности, следующие тенденции в поведении базового оборудования и программного обеспечения пользовательского уровня повлияли на производительность алгоритмов замены страниц:
- Размер первичного хранилища увеличился на несколько порядков. При наличии нескольких гигабайт первичной памяти алгоритмы, требующие периодической проверки каждого кадра памяти, становятся все менее практичными.
- Иерархии памяти стали выше. Стоимость промаха кэша ЦП намного дороже. Это усугубляет предыдущую проблему.
- Ослаблена локальность обращения к пользовательскому ПО. В основном это связано с распространением методов объектно-ориентированного программирования , которые отдают предпочтение большому количеству небольших функций, использованием сложных структур данных, таких как деревья и хеш-таблицы, которые, как правило, приводят к хаотическим шаблонам обращения к памяти, и появлению сборки мусора, которая радикально изменилась. поведение приложений при доступе к памяти.
Требования к алгоритмам замены страниц изменились из-за различий в архитектурах ядра операционной системы . В частности, большинство современных ядер ОС имеют унифицированную виртуальную память и кеши файловой системы, что требует от алгоритма замены страниц выбора страницы из страниц как виртуальных адресных пространств пользовательских программ, так и кэшированных файлов. Последние страницы обладают определенными свойствами. Например, они могут быть заблокированы или могут иметь требования к порядку записи, налагаемые журналированием . Более того, поскольку цель замены страницы - минимизировать общее время ожидания памяти, она должна учитывать требования к памяти, налагаемые другими подсистемами ядра, которые выделяют память. В результате замена страниц в современных ядрах ( Linux , FreeBSD и Solaris ) имеет тенденцию работать на уровне распределителя памяти ядра общего назначения, а не на более высоком уровне подсистемы виртуальной памяти.
Локальная или глобальная замена
Алгоритмы замены могут быть локальными или глобальными.
Когда процесс вызывает сбой страницы, алгоритм замены локальной страницы выбирает для замены некоторую страницу, которая принадлежит тому же процессу (или группе процессов, совместно использующих раздел памяти ). Алгоритм глобальной замены позволяет выбрать любую страницу в памяти.
Замена локальной страницы предполагает некоторую форму разделения памяти, которая определяет, сколько страниц должно быть назначено данному процессу или группе процессов. Наиболее популярные формы разбиения - это алгоритмы фиксированного разбиения и сбалансированного набора , основанные на модели рабочего набора . Преимущество замены локальной страницы заключается в ее масштабируемости: каждый процесс может обрабатывать свои сбои страниц независимо, что приводит к более стабильной производительности этого процесса. Однако глобальная замена страниц более эффективна для всей системы. [1]
Определение страниц, на которые есть ссылки и которые изменяются
Современные компьютеры общего назначения и некоторые встроенные процессоры поддерживают виртуальную память . У каждого процесса есть собственное виртуальное адресное пространство. Таблицы страниц отображает подмножество процесса виртуальных адресов в физические адреса. Кроме того, в большинстве архитектур таблица страниц содержит бит «доступа» и бит «грязный» для каждой страницы в таблице страниц. ЦП устанавливает бит доступа, когда процесс читает или записывает память на этой странице. ЦП устанавливает грязный бит, когда процесс записывает память на этой странице. Операционная система может изменять биты доступа и грязные биты. Операционная система может обнаруживать доступ к памяти и файлам следующими способами:
- Сбросив бит доступа на страницах, присутствующих в таблице страниц процесса. Через некоторое время ОС просматривает таблицу страниц в поисках страниц, для которых ЦП установлен бит доступа. Это быстро, потому что бит доступа устанавливается автоматически ЦП, и неточно, потому что ОС не сразу получает уведомление о доступе и не имеет информации о порядке, в котором процесс обращался к этим страницам.
- Удаляя страницы из таблицы страниц процесса, не обязательно удаляя их из физической памяти. Следующий доступ к этой странице обнаруживается немедленно, потому что он вызывает ошибку страницы . Это медленно, потому что сбой страницы включает переключение контекста в ОС, программный поиск соответствующего физического адреса, изменение таблицы страниц и переключение контекста обратно в процесс, и является точным, поскольку доступ обнаруживается сразу после его возникновения.
- Непосредственно, когда процесс выполняет системные вызовы, которые потенциально могут получить доступ к кешу страниц, как
read
иwrite
в POSIX.
Предварительная очистка
Большинство алгоритмов замены просто возвращают в качестве результата целевую страницу. Это означает, что если целевая страница загрязнена (то есть содержит данные, которые должны быть записаны в стабильное хранилище, прежде чем страница может быть восстановлена), должен быть инициирован ввод-вывод для отправки этой страницы в стабильное хранилище (для очистки страницы ). На заре виртуальной памяти время, затрачиваемое на очистку, не представляло особого беспокойства, поскольку виртуальная память впервые была реализована в системах с полнодуплексными каналами для стабильного хранилища, а очистка обычно перекрывалась с разбиением по страницам. С другой стороны, современное массовое оборудование не поддерживает полнодуплексную передачу, и очистка целевых страниц становится проблемой.
Чтобы справиться с этой ситуацией, применяются различные политики предварительной очистки . Предварительная очистка - это механизм, который запускает ввод-вывод на грязных страницах, которые (вероятно) скоро будут заменены. Идея состоит в том, что к тому времени, когда предварительно очищенная страница будет фактически выбрана для замены, ввод-вывод завершится и страница будет чистой. Предварительная очистка предполагает, что можно определить страницы, которые будут заменены в следующий раз . Слишком активная предварительная очистка может тратить впустую пропускную способность ввода-вывода из-за написания страниц, которые удается повторно загрязнить перед выбором для замены.
Предварительный пейджинг
Некоторые системы используют подкачку по запросу - ожидание фактического запроса страницы перед ее загрузкой в ОЗУ.
Другие системы пытаются уменьшить задержку, угадывая, какие страницы не в ОЗУ, скорее всего, понадобятся в ближайшее время, и предварительно загружая такие страницы в ОЗУ до того, как эта страница будет запрошена. (Это часто происходит в сочетании с предварительной очисткой, которая определяет, какие страницы в настоящее время в ОЗУ вряд ли понадобятся в ближайшее время, и предварительно записывает их в хранилище).
Когда происходит сбой страницы, системы «упреждающего пейджинга» вводят не только страницу, на которую указывает ссылка, но и следующие несколько последовательных страниц (аналогично входной очереди предварительной выборки в ЦП).
Механизм предварительной выборки подкачки идет еще дальше в загрузке страниц (даже если они не являются последовательными), которые, вероятно, вскоре понадобятся.
Проблема (h, k) -пейджинга
Задача (h, k) -пейджинга является обобщением модели проблемы пейджинга: пусть h, k - положительные целые числа такие, что . Мы измеряем производительность алгоритма с размером кэшаотносительно теоретически оптимального алгоритма замены страниц . Если, мы обеспечиваем оптимальный алгоритм замены страниц при значительно меньших ресурсах.
Задача (h, k) -пейджинга - это способ измерить, как работает онлайн-алгоритм, сравнивая его с производительностью оптимального алгоритма, в частности, отдельно параметрируя размер кэша онлайн-алгоритма и оптимального алгоритма.
Алгоритмы маркировки
Алгоритмы маркировки - это общий класс алгоритмов разбиения на страницы. Для каждой страницы мы связываем ее с меткой. Изначально мы устанавливаем все страницы как неотмеченные. На этапе запросов страниц мы отмечаем страницу при первом запросе на этом этапе. Алгоритм маркировки - это такой алгоритм, который никогда не выгружает отмеченную страницу.
Если ALG - алгоритм маркировки с размером кэша k, а OPT - оптимальный алгоритм с кешем размера h, где , то ALG -конкурентоспособный. Таким образом, каждый алгоритм маркировки достигает-конкурентоспособность.
LRU - это алгоритм маркировки, а FIFO - не алгоритм маркировки.
Консервативные алгоритмы
Алгоритм является консервативным, если в любой последовательной последовательности запросов, содержащей k или меньше различных ссылок на страницы, алгоритм вызовет k или меньше ошибок страниц.
Если ALG - консервативный алгоритм с размером кэша k, а OPT - оптимальный алгоритм с размером кэша , то ALG -конкурентоспособный. Таким образом, каждый консервативный алгоритм достигает-конкурентоспособность.
LRU, FIFO и CLOCK - консервативные алгоритмы.
Алгоритмы замены страниц
Существует множество алгоритмов замены страниц: [2]
Теоретически оптимальный алгоритм замены страницы
Теоретически оптимальный алгоритм замены страницы (также известный как OPT, алгоритм замены ясновидящего или оптимальная политика замены страницы Белади ) [3] [4] [2] - это алгоритм, который работает следующим образом: когда страницу необходимо заменить, операционная система выгружает страницу, следующее использование которой произойдет дальше всего в будущем. Например, страница, которая не будет использоваться в течение следующих 6 секунд, будет заменена страницей, которая будет использоваться в течение следующих 0,4 секунды.
Этот алгоритм не может быть реализован в операционной системе общего назначения, потому что невозможно надежно вычислить, сколько времени пройдет до того, как страница будет использоваться, за исключением случаев, когда все программное обеспечение, которое будет запускаться в системе, либо известно заранее и поддается статический анализ его шаблонов ссылок на память или только класс приложений, позволяющих анализировать во время выполнения. Несмотря на это ограничение, существуют алгоритмы [ необходима цитата ], которые могут обеспечивать почти оптимальную производительность - операционная система отслеживает все страницы, на которые ссылается программа, и использует эти данные, чтобы решить, какие страницы нужно менять, а какие при последующих запусках. Этот алгоритм может предложить почти оптимальную производительность, но не при первом запуске программы и только в том случае, если шаблон обращения к памяти программы относительно постоянен при каждом запуске.
Анализ проблемы пейджинга также проводился в области онлайн-алгоритмов . Эффективность рандомизированных онлайн-алгоритмов для задачи разбиения на страницы измеряется с помощью амортизированного анализа .
Не использовался в последнее время
Алгоритм замены неиспользованных недавно страниц (NRU) - это алгоритм, который способствует сохранению в памяти недавно использованных страниц. Этот алгоритм работает по следующему принципу: когда на страницу ссылаются, для этой страницы устанавливается бит ссылки, помечающий ее как указанную. Точно так же, когда страница модифицируется (записывается), устанавливается модифицированный бит. Установка битов обычно выполняется аппаратно, хотя это возможно и на программном уровне.
Через определенный фиксированный интервал времени срабатывает прерывание таймера и очищает указанный бит на всех страницах, поэтому только страницы, на которые есть ссылки в текущем интервале таймера, помечаются указанным битом. Когда страницу необходимо заменить, операционная система делит страницы на четыре класса:
- 3. упомянутые, измененные
- 2. упомянутые, не измененные
- 1. не упоминается, изменено
- 0. не упоминается, не изменяется
Хотя не представляется возможным изменить страницу, но при этом на нее не будет ссылаться, это происходит, когда ссылочный бит страницы класса 3 сброшен прерыванием таймера. Алгоритм NRU выбирает случайную страницу из самой низкой категории для удаления. Таким образом, из четырех вышеперечисленных категорий страниц алгоритм NRU заменит страницу без ссылок и без изменений, если такая страница существует. Обратите внимание, что этот алгоритм подразумевает, что измененная, но не упоминаемая (в пределах последнего интервала таймера) страница менее важна, чем не измененная страница, на которую часто ссылаются.
NRU - это алгоритм маркировки, поэтому он -конкурентоспособный.
Первым прибыл, первым обслужен
Самый простой алгоритм замены страниц - это алгоритм FIFO. Алгоритм замены страниц «первым пришел - первым обслужен» (FIFO) - это алгоритм с низкими накладными расходами, который требует небольшого учета со стороны операционной системы . Идея очевидна из названия - операционная система отслеживает все страницы в памяти в очереди, причем самые свежие поступления находятся сзади, а самые старые - впереди. Когда страницу необходимо заменить, выбирается страница в начале очереди (самая старая страница). Хотя FIFO дешев и интуитивно понятен, он плохо работает на практике. Таким образом, он редко используется в неизмененном виде. Этот алгоритм обнаруживает аномалию Белади . Проще говоря, при отказе страницы заменяется фрейм, который дольше всех находился в памяти.
Алгоритм замены страницы FIFO используется операционной системой VAX / VMS с некоторыми изменениями. [5] Частичный второй шанс предоставляется за счет пропуска ограниченного числа записей с действительными ссылками на таблицу преобразования, [6] и, кроме того, страницы перемещаются из рабочего набора процессов в общесистемный пул, из которого они могут быть восстановлены, если они еще не использовались повторно. .
FIFO - консервативный алгоритм, поэтому он -конкурентоспособный.
Второй шанс
Модифицированная форма алгоритма замены страницы 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 самонастраивается и не требует никаких магических параметров, задаваемых пользователем.
ЧАСЫ - консервативный алгоритм, поэтому он -конкурентоспособный.
Наименее недавно использованный
Алгоритм замены страниц, который использовался не так давно (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 [15] удаляет страницу, K-й самый последний доступ к которой был самым дальним в прошлом. Например, LRU-1 - это просто LRU, тогда как LRU-2 удаляет страницы в соответствии со временем их предпоследнего доступа. LRU-K значительно улучшает LRU в отношении местоположения во времени.
- АРК [16] алгоритм LRU распространяется путем сохранения истории недавно выселенных страниц и использует это , чтобы предпочтение изменения недавнего или частый доступ. Он особенно устойчив к последовательному сканированию.
Сравнение ARC с другими алгоритмами (LRU, MQ, 2Q, LRU-2, LRFU, LIRS ) можно найти в Megiddo & Modha 2004. [17]
LRU - это алгоритм маркировки, поэтому он -конкурентоспособный.
Случайный
Алгоритм случайной замены заменяет случайную страницу в памяти. Это исключает накладные расходы на отслеживание ссылок на страницы. Обычно он работает лучше, чем 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 моделирует алгоритм старения. Счетчики инициализируются 0 и обновляется, как описано выше, через, используя операторы арифметического сдвига .
из collection.abc Импорт Последовательностьdef simulate_aging ( Rs : Sequence , k : int ) -> None : "" "Имитировать старение." "" print ( 't | R-bits (0- {length} ) | Счетчики для страниц 0- {length} ' . format ( length = len ( Rs ))) Vs = [ 0 ] * len ( Rs [ 0 ]) для t , R в перечислении ( Rs ): Vs [:] = [ R [ i ] << k - 1 | V >> 1 для i , V в перечислении ( Vs )] print ( ' {: 02d} | {} | [ {} ]' . Format ( t , R , ',' . Join ([ '{: 0 {} b} ' . format ( V , k ) для V в Vs ])))
В данном примере R-битов для 6 страниц за 5 тактов тактовой частоты функция выводит следующий вывод, в котором перечислены R-биты для каждого такта t и отдельные значения счетчиков.для каждой страницы в двоичном представлении. [19]
>>> 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-биты (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 замените страницу, которая находится на наибольшем расстоянии от текущей страницы. Если две страницы находятся на одинаковом расстоянии, то страница, которая находится рядом с текущей страницей при повороте против часовой стрелки, будет заменена. [20]
Детали реализации
Методы работы с оборудованием без опорного бита
Многие из описанных выше методов предполагают наличие справочного бита, связанного с каждой страницей. Некоторое оборудование не имеет такого бита, поэтому для его эффективного использования требуются методы, которые хорошо работают без него.
Одним из ярких примеров является оборудование VAX, на котором работает OpenVMS . Эта система знает, была ли страница изменена, но не обязательно, если страница была прочитана. Его подход известен как кэширование вторичной страницы. Страницы, удаленные из рабочих наборов (как правило, частной памяти процесса), помещаются в специальные списки, оставаясь в физической памяти в течение некоторого времени. Удаление страницы из рабочего набора технически не является операцией замены страницы, но эффективно идентифицирует эту страницу как кандидата. Страница, резервное хранилище которой все еще действует (чье содержимое не загрязнено или его не нужно сохранять по другим причинам), помещается в конец списка бесплатных страниц. Страница, требующая записи в резервное хранилище, будет помещена в список измененных страниц. Эти действия обычно запускаются, когда размер списка бесплатных страниц становится ниже регулируемого порогового значения.
Страницы могут быть выбраны для удаления рабочего набора по существу случайным образом, с ожиданием, что, если будет сделан неправильный выбор, будущая ссылка может извлечь эту страницу из списка Free или Modified до того, как она будет удалена из физической памяти. Страница, на которую ссылаются таким образом, будет удалена из списка Free или Modified и помещена обратно в рабочий набор процесса. Список измененных страниц дополнительно предоставляет возможность записывать страницы в резервное хранилище группами по несколько страниц, повышая эффективность. Эти страницы могут быть затем помещены в список бесплатных страниц. Последовательность страниц, которая продвигается к началу списка бесплатных страниц, напоминает результаты механизма LRU или NRU, и общий эффект имеет сходство с алгоритмом второго шанса, описанным ранее.
Другой пример используется ядром Linux на ARM . Отсутствие аппаратной функциональности компенсируется наличием двух таблиц страниц - собственных таблиц страниц процессора без битов ссылок и грязных битов и таблиц страниц, поддерживаемых программным обеспечением, с необходимыми битами. Эмулируемые биты в таблице, обслуживаемой программным обеспечением, устанавливаются ошибками страниц. Чтобы получить ошибки страницы, очистка эмулированных битов во второй таблице отменяет некоторые права доступа к соответствующей странице, что реализуется путем изменения собственной таблицы.
Кеш страницы в Linux
Linux использует единый кеш страниц для
- brkи анонимные mmaped -регионы. Это включает в себя кучу и стек программ пользовательского пространства . Написано для подкачки при выгрузке.
- Неанонимные (файловые)
mmap
редакционные регионы. Если физическая страница присутствует в памяти и не изменена частным образом, она используется совместно с файловым кешем или буфером. - Общая память приобретена через shm_open.
- В TMPFS в памяти файловой системы; написано для обмена при выгрузке.
- Файловый кеш, в том числе; записывается в базовое блочное хранилище (возможно, проходит через буфер, см. ниже) при подкачке.
- Кэш блочных устройств , называемый Linux «буфером» (не путать с другими структурами, также называемыми буферами, подобными тем, которые используются для каналов и буферов, используемых внутри Linux); записывается в базовое хранилище при выгрузке.
Единый страничный кеш работает с блоками наименьшего размера страницы, поддерживаемыми ЦП (4 КиБ в ARMv8 , x86 и x86-64 ), с некоторыми страницами следующего большего размера (2 МиБ в x86-64 ), которые называются «огромными страницами». Linux. Страницы в кэше страниц делятся на «активный» набор и «неактивный» набор. Оба набора содержат список страниц LRU. В основном случае, когда к странице обращается программа пользовательского пространства, она помещается в начало неактивного набора. При повторном обращении к нему он перемещается в активный список. Linux перемещает страницы из активного набора в неактивный по мере необходимости, так что активный набор меньше неактивного набора. Когда страница перемещается в неактивный набор, она удаляется из таблицы страниц любого адресного пространства процесса без подкачки из физической памяти. [21] [22] Когда страница удаляется из неактивного набора, она выгружается из физической памяти. Размер «активного» и «неактивного» списка можно запросить /proc/meminfo
в полях «Активный», «Неактивный», «Активный (анонс)», «Неактивный (анон)», «Активный (файл)» и «Неактивный». (аноним) ".
Рабочий набор
Рабочий набор процесса - это набор страниц, которые, как ожидается, будут использоваться этим процессом в течение некоторого промежутка времени.
«Модель рабочего набора» не является алгоритмом замены страниц в строгом смысле слова (на самом деле это своего рода среднесрочный планировщик ) [ требуется пояснение ]
Рекомендации
- ^ Белл, Джон. «Примечания к курсу операционных систем: виртуальная память» . Иллинойский университет в Чикагском инженерном колледже . Архивировано 23 сентября 2018 года . Проверено 21 июля 2017 года .
- ^ а б Джонс, Дуглас В. "22C: 116 Лекционные заметки" . Департамент компьютерных наук Университета Айовы . Архивировано 30 июня 2012 года . Проверено 18 марта 2008 года .
- ^ Торрес, Пол; и другие. «CS111 Лекция 11 примечания» . Департамент компьютерных наук Калифорнийского университета в Лос-Анджелесе . Архивировано из оригинала 9 января 2009 года.
- ^ Bahn, Hyokyung; Но, Сэм Х. (12–14 февраля 2003 г.). Пересмотренная характеристика поведения веб-ссылок: доказательства дихотомического управления кешем . Международная конференция по информационным сетям 2003 . Чеджу, Южная Корея: Springer-Verlag. С. 1018–1027. DOI : 10.1007 / 978-3-540-45235-5_100 . ISBN 978-3-540-40827-7.
- ^ Зильбершац, Авраам; Гэлвин, Питер Баер; Ганье, Грег (14 декабря 2004 г.). Понятия операционной системы (7-е изд.). Хобокен, Нью-Джерси, США: John Wiley & Sons. п. 339. ISBN. 0-47169-466-5. OCLC 56913661 .
- ^ Справка VMS - Параметры системы, TBSKIPWSL
- ^ Таненбаум, Эндрю С. (2001). Современные операционные системы (2-е изд.). Река Аппер Сэдл, Нью-Джерси, США: Прентис-Холл. п. 218 (4.4.5) . ISBN 978-0-13-031358-4. LCCN 00051666 . OCLC 45284637 . ПР 24214243М .
- ^ Корбато, Фернандо Х. (1969). «Эксперимент по пейджингу с системой Multics» (PDF) . Festschrift: В честь премьер-министра Морса . MIT Press . С. 217–228.
- ^ Смит, Алан Джей (сентябрь 1978 г.). «Последовательность и предварительная выборка в системах баз данных». ACM-транзакции в системах баз данных . Нью-Йорк, Нью-Йорк, США: ACM. 3 (3): 223–247. DOI : 10.1145 / 320263.320276 . S2CID 11611563 .
- ^ Цзян, Сун; Чен, Фэн; Чжан, Сяодун (10–15 апреля 2005 г.). ЧАСЫ-Pro: эффективное улучшение замены ЧАСОВ (PDF) . 2005 USENIX Ежегодная техническая конференция . Анахайм, Калифорния, США: Ассоциация 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" . Департамент компьютерных наук Нью-Йоркского университета . Архивировано 30 июля 2012 года . Проверено 12 июня 2019 .
- ^ Таненбаум, Эндрю С. «Алгоритмы замены страниц» . InformIT . Архивировано 10 сентября 2012 года . Проверено 12 июня 2019 .
- ^ Бансал, Сорав и Модха, Дхармендра С. (31 марта - 2 апреля 2004 г.). АВТОМОБИЛЬ: часы с адаптивной заменой (PDF) . 3-я конференция USENIX по файловым технологиям и технологиям хранения (FAST '04) . Сан-Франциско, Калифорния, США: Ассоциация USENIX. С. 187–200. CiteSeerX 10.1.1.105.6057 . Архивировано 31 июля 2004 года (PDF) .
- ^ О'Нил, Элизабет Дж .; и другие. (25–28 мая 1993 г.). Алгоритм замены страниц LRU-K для буферизации диска базы данных (PDF) . 1993 Международная конференция ACM SIGMOD по управлению данными . Вашингтон, округ Колумбия, США: ACM. С. 297–306. CiteSeerX 10.1.1.18.1434 . DOI : 10.1145 / 170035.170081 . ISBN 0-89791-592-5. Архивировано 6 сентября 2019 года (PDF) .
- ^ Мегиддо, Нимрод и Модха, Дхармендра С. (31 марта - 2 апреля 2003 г.). ARC: самонастраивающийся кэш для замены с низкими накладными расходами (PDF) . 2-я конференция USENIX по файловым технологиям и технологиям хранения (FAST '03) . Сан-Франциско, Калифорния, США: Ассоциация USENIX. С. 115–130. Архивировано 8 февраля 2010 года (PDF) .
- ^ Мегиддо, Нимрод и Модха, Дхармендра С. (2004). «Превосходство LRU с помощью алгоритма адаптивного кэширования замены» (PDF) . Компьютер . Компьютерное общество IEEE. 37 (4): 58. CiteSeerX 10.1.1.231.498 . DOI : 10,1109 / MC.2004.1297303 . S2CID 5507282 . Архивировано 21 октября 2012 года (PDF) из оригинала . Проверено 20 сентября 2013 года .
- ^ Родхамел, Майкл В. (2–4 октября 1989 г.). Шинный интерфейс и модули пейджинга микропроцессора i860 . 1989 Международная конференция IEEE по компьютерному дизайну: СБИС в компьютерах и процессорах . Кембридж, Массачусетс, США: IEEE. С. 380–384. DOI : 10.1109 / ICCD.1989.63392 . ISBN 0-8186-1971-6. Регистрационный номер INSPEC 3719504.
- ^ Таненбаум, Эндрю С .; Бос, Герберт (2015). Современные операционные системы (4-е изд.). Бостон, Массачусетс, США: Пирсон. п. 215. ISBN 978-0-13-359162-0. ПР 25620855М .
- ^ Кумар, Гьянендра; Томар, Парул (сентябрь 2017 г.). «Новый алгоритм замены первой страницы на наибольшее расстояние» . Индийский журнал науки и технологий . 10 (30): 1–6. DOI : 10.17485 / ijst / 2017 / v10i30 / 115500 . ISSN 0974-6846 . Архивировано 7 сентября 2017 года.
- ^ См. Объяснение в начале/mm/workingset.cисходного текста Linux.
- ^ Корбет, Джонатан Корбет (2 мая 2012 г.). «Лучшая балансировка активного / неактивного списка» . LWN.net .
дальнейшее чтение
- Вонг, Кин-Юнг (23 января 2006 г.). «Политики замены веб-кеша: прагматический подход». Сеть IEEE . IEEE. 20 (1): 28–34. DOI : 10.1109 / MNET.2006.1580916 . ISSN 0890-8044 . S2CID 17969287 . Регистрационный номер INSPEC 8964134.
- Ахо, Альфред V .; Деннинг, Питер Дж .; Ульман, Джеффри Д. (январь 1971 г.). «Принципы оптимальной замены страниц». Журнал ACM . Нью-Йорк, Нью-Йорк, США: ACM. 18 (1): 80–93. DOI : 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М .Отрывок из Интернета об алгоритмах замены страниц: Алгоритмы замены страниц .
- Джонсон, Теодор; Шаша, Деннис (12–15 сентября 1994 г.). 2Q: Высокопроизводительный алгоритм замены управления буфером с низкими накладными расходами (PDF) . 20-я Международная конференция по очень большим базам данных . Сантьяго-де-Чили, Чили: Морган Кауфманн. С. 439–450. ISBN 1-55860-153-8. Архивировано 17 марта 2020 года (PDF) . Проверено 31 Июль +2005 .
- Гласс, Гидеон; Цао, Пей (15–18 июня 1997 г.). Адаптивная замена страниц на основе поведения обращения к памяти . 1997 Международная конференция ACM SIGMETRICS по измерению и моделированию компьютерных систем . Сиэтл, Вашингтон, США: ACM. С. 115–126. DOI : 10.1145 / 258612.258681 . ISBN 0-89791-909-2. Также доступен в расширенном виде как «Технический отчет 1338» . Департамент компьютерных наук, Университет Винконсин-Мэдисон .
- Ким, Чон Мин; и другие. (17–21 октября 2000 г.). Унифицированная схема управления буфером с низкими накладными расходами и высокой производительностью, использующая последовательные и циклические ссылки (PDF) . 4-й симпозиум Usenix по разработке и внедрению операционных систем (OSDI'2000) . 4 . Сан-Диего, Калифорния, США: Ассоциация USENIX. Архивировано 18 сентября 2004 года (PDF) .
- Смарагдакис, Яннис; Каплан, Скотт; Уилсон, Пол (1–4 мая 1999 г.). EELRU: простая и эффективная адаптивная замена страниц (PDF) . 1999 Международная конференция ACM SIGMETRICS по измерению и моделированию компьютерных систем . Атланта, Джорджия, США: ACM. С. 122–133. DOI : 10.1145 / 301453.301486 . ISBN 1-58113-083-X. Архивировано 4 марта 2016 года (PDF) из оригинала.
- Цзян, Сун; Чжан, Сяодун (15–19 июня 2002 г.). LIRS: замена набора с низкой межссылочной свежестью (PDF) . 2002 Международная конференция ACM SIGMETRICS по измерению и моделированию компьютерных систем . Марина Дель Рей, Калифорния, США: ACM. С. 31–42. DOI : 10.1145 / 511334.511340 . ISBN 1-58113-531-9. Архивировано 12 июня 2019 года (PDF) .
- Ли, Донхи; и другие. (1–4 сентября 1997 г.). Внедрение и оценка эффективности политики замены LRFU . 23-я конференция Euromicro Новые рубежи информационных технологий . Будапешт, Венгрия: Компьютерное общество IEEE. С. 106–111. DOI : 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-X. Архивировано 24 ноября 2005 года (PDF) .