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

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

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

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

История [ править ]

Алгоритмы замены страниц были горячей темой исследований и дискуссий в 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 [ править ]

  1. LRU-K [15] удаляет страницу, K-й самый последний доступ к которой был самым дальним в прошлом. Например, LRU-1 - это просто LRU, тогда как LRU-2 удаляет страницы в соответствии со временем их предпоследнего доступа. LRU-K значительно улучшает LRU в отношении местоположения во времени.
  2. АРК [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 моделирует алгоритм старения. Счетчики инициализируются и обновляются, как описано выше , с использованием операторов арифметического сдвига .

def  simulate_aging ( Rs ,  k :  int )  ->  None :  "" "Имитация старения." ""  Vs  =  [ 0 ]  *  len ( Rs [ 0 ])  для  t ,  R  в  enumerate ( Rs ):  для  i  в  диапазоне ( len ( Vs )):  Vs [ i ]  =  R [ i ]  <<  k  -  1 |  Vs [ i ]  >>  1  print ( ' % 02d  | % s  | [ % s ]'  %  ( t ,  R ,  ',' . Join ([ format ( V ,  '0 % d b'  %  k )  для  V  в  Вс ])))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 )

В данном примере R-битов для 6 страниц за 5 тактов тактовой частоты функция выводит следующий вывод, в котором перечислены R-биты для каждого такта и отдельные значения счетчиков для каждой страницы в двоичном представлении. [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 на ARM . Отсутствие аппаратной функциональности компенсируется наличием двух таблиц страниц - собственных таблиц страниц процессора без битов ссылок и грязных битов и таблиц страниц, поддерживаемых программным обеспечением, с необходимыми битами. Эмулируемые биты в таблице, обслуживаемой программным обеспечением, устанавливаются ошибками страниц. Чтобы получить ошибки страницы, очистка эмулированных битов во второй таблице отменяет некоторые права доступа к соответствующей странице, что реализуется путем изменения собственной таблицы.

Кеш страницы в Linux [ править ]

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

  • brkи анонимные mmaped -регионы. Это включает в себя кучу и стек программ пользовательского пространства . Написано для подкачки при выгрузке.
  • Неанонимные (файловые) 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. ^ a b Джонс, Дуглас В. "22C: 116 Лекционные заметки" . Департамент компьютерных наук Университета Айовы . Архивировано 30 июня 2012 года . Проверено 18 марта 2008 года .
  3. ^ Торрес, Пол; и другие. «CS111 Лекция 11 примечания» . Департамент компьютерных наук Калифорнийского университета в Лос-Анджелесе . Архивировано из оригинала 9 января 2009 года.
  4. ^ Bahn, Хёкён; Но, Сэм Х. (12–14 февраля 2003 г.). Пересмотренная характеристика поведения веб-ссылок: доказательства дихотомического управления кешем . Международная конференция по информационным сетям 2003 . Чеджу, Южная Корея: Springer-Verlag. С. 1018–1027. DOI : 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 . ПР  24214243М .
  8. ^ Корбато, Фернандо Дж. (1969). «Эксперимент по пейджингу с системой Multics» (PDF) . Festschrift: В честь премьер-министра Морса . MIT Press . С. 217–228.
  9. ^ Смит, Алан Джей (сентябрь 1978 г.). «Последовательность и предварительная выборка в системах баз данных». ACM-транзакции в системах баз данных . Нью-Йорк, Нью-Йорк, США: ACM. 3 (3): 223–247. DOI : 10.1145 / 320263.320276 . S2CID 11611563 . 
  10. ^ Цзян, Сун; Чен, Фэн; Чжан, Сяодун (10–15 апреля 2005 г.). ЧАСЫ-Pro: эффективное улучшение замены ЧАСОВ (PDF) . 2005 USENIX Ежегодная техническая конференция . Анахайм, Калифорния, США: Ассоциация USENIX. п. 35. Архивировано (PDF) из оригинала 12 июня 2019 года . Проверено 24 марта 2009 года .
  11. ^ Карр, Ричард В .; Хеннесси, Джон Л. (14–16 декабря 1981 г.). WSCLOCK - простой и эффективный алгоритм управления виртуальной памятью (сжатый PDF-файл) . Восьмой симпозиум ACM по принципам операционных систем . Пасифик Гроув, Калифорния, США: ACM. С. 87–95. DOI : 10.1145 / 800216.806596 . ISBN  0-89791-062-1. Архивировано 10 июня 2007 года.
  12. ^ Готтлиб, Аллан. "WSClock" . Департамент компьютерных наук Нью-Йоркского университета . Архивировано 30 июля 2012 года . Проверено 12 июня 2019 .
  13. ^ Таненбаум, Эндрю С. «Алгоритмы замены страниц» . InformIT . Архивировано 10 сентября 2012 года . Проверено 12 июня 2019 .
  14. ^ Bansal, Sorav & Modha, Dharmendra S. (31 марта - 2 апреля 2004). АВТОМОБИЛЬ: часы с адаптивной заменой (PDF) . 3-я конференция USENIX по файловым технологиям и технологиям хранения (FAST '04) . Сан-Франциско, Калифорния, США: Ассоциация USENIX. С. 187–200. CiteSeerX 10.1.1.105.6057 . Архивировано 31 июля 2004 года (PDF) .  
  15. ^ О'Нил, Элизабет Дж .; и другие. (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) .
  16. ^ Мегиддо, Нимрод и Modha, Dharmendra С. (31 марта - 2 апреля 2003). ARC: самонастраивающийся кэш для замены с низкими накладными расходами (PDF) . 2-я конференция USENIX по файловым технологиям и технологиям хранения (FAST '03) . Сан-Франциско, Калифорния, США: Ассоциация USENIX. С. 115–130. Архивировано 8 февраля 2010 года (PDF) .
  17. ^ Мегиддо, Нимрод и Modha, Dharmendra S. (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 года .   
  18. ^ Rhodehamel, Michael W. (2-4 октября 1989). Шинный интерфейс и модули пейджинга микропроцессора i860 . 1989 Международная конференция IEEE по компьютерному дизайну: СБИС в компьютерах и процессорах . Кембридж, Массачусетс, США: IEEE. С. 380–384. DOI : 10.1109 / ICCD.1989.63392 . ISBN 0-8186-1971-6. Регистрационный номер INSPEC 3719504.
  19. ^ Таненбаум, Эндрю С .; Бос, Герберт (2015). Современные операционные системы (4-е изд.). Бостон, Массачусетс, США: Пирсон. п. 215. ISBN 978-0-13-359162-0. ПР  25620855М .
  20. ^ Кумар, Гьянендра; Томар, Парул (сентябрь 2017 г.). «Новый алгоритм замены первой страницы на наибольшее расстояние» . Индийский журнал науки и технологий . 10 (30): 1–6. DOI : 10.17485 / ijst / 2017 / v10i30 / 115500 . ISSN 0974-6846 . Архивировано 7 сентября 2017 года. 
  21. ^ См. Объяснение в начале/mm/workingset.cисходного текста Linux.
  22. ↑ Корбет, Джонатан Корбет (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 Июля 2 005 .
  • Гласс, Гидеон; Цао, Пей (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) .