Алгоритмы замены страниц в виртуальной памяти

Введение

Алгоритм реализации виртуальной памяти, алгоритмы, специфичные для постраничной организации

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

История

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

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

Местная и глобальная замена

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

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

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

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

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

Проблема соединения (h,k)

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

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

Алгоритмы маркировки — это общий класс алгоритмов подкачки. Для каждой страницы мы связываем её с битом, называемым маркером. Изначально все страницы устанавливаются как немаркированные. В течение этапа (периода работы или последовательности запросов) запросов страниц мы маркируем страницу при её первом запросе в этом этапе. Алгоритм маркировки — это алгоритм, который никогда не выгружает маркированную страницу. Если ALG — это алгоритм маркировки с кэшем размером k, а OPT — оптимальный алгоритм с кэшем размером h, где , то ALG является конкурентоспособным. Следовательно, каждый алгоритм маркировки достигает конкурентоспособного коэффициента. LRU является алгоритмом маркировки, а FIFO — нет.

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

Алгоритм считается консервативным, если для любой последовательности запросов, содержащей не более k различных ссылок на страницы, алгоритм вызовет не более k промахов страниц. Если ALG – консервативный алгоритм с кэшем размера k, а OPT – оптимальный алгоритм с кэшем размера k, то ALG является конкурентоспособным. Следовательно, любой консервативный алгоритм достигает конкурентоспособного коэффициента. LRU, FIFO и CLOCK – консервативные алгоритмы.

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

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

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

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

3. обращённая, изменённая
2. обращённая, неизменённая
1. необращённая, изменённая
0. необращённая, неизменённая

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

Первый входит, первый выходит.

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

Второй шанс

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

Часы

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

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

GCLOCK: обобщенный алгоритм замещения страниц "Clock". Clock Pro поддерживает кольцевой список информации о недавно использованных страницах, включая все страницы M, находящиеся в памяти, а также M самых последних страниц, которые были выгружены. Эта дополнительная информация о выгруженных страницах, подобно информации, поддерживаемой ARC, позволяет ему работать лучше, чем LRU при больших циклах и однократных сканированиях. WSclock. Комбинируя алгоритм Clock с концепцией рабочего множества (то есть набора страниц, которые, как ожидается, будут использоваться процессом в течение определенного промежутка времени), можно повысить производительность алгоритма. На практике алгоритмы "aging" и "WSClock", вероятно, являются наиболее важными алгоритмами замещения страниц. Clock с адаптивным замещением (CAR) – это алгоритм замещения страниц, производительность которого сопоставима с ARC и значительно превосходит LRU и CLOCK. Алгоритм CAR самонастраиваемый и не требует от пользователя задания каких-либо специальных параметров. CLOCK – консервативный алгоритм, поэтому он конкурентоспособен.

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

Наименее недавно используемый алгоритм замены страниц (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 вытесняет страницу, K-я последняя запись о доступе к которой была сделана в самом отдалённом прошлом. Например, LRU 1 – это просто LRU, а LRU 2 вытесняет страницы, основываясь на времени их предпоследнего обращения. LRU K значительно превосходит LRU с точки зрения временной локальности. Алгоритм ARC расширяет LRU, поддерживая историю недавно вытесненных страниц и используя её для переключения предпочтения между недавними и частыми обращениями. Он особенно устойчив к последовательным сканированиям. Алгоритм 2Q улучшает алгоритмы LRU и LRU/2. Используя две очереди – одну для "горячих" элементов, а другую для "холодных" – элементы сначала помещаются в очередь "холодных", а после второго обращения перемещаются в очередь "горячих". Поскольку ссылки на добавленные элементы сохраняются дольше, чем в алгоритмах LRU и LRU/2, он имеет более эффективную очередь "горячих", что повышает коэффициент попаданий в кэш. Сравнение ARC с другими алгоритмами (LRU, MQ, 2Q, LRU 2, LRFU, LIRS) можно найти в работе Megiddo & Modha, 2004 год. LRU является алгоритмом маркировки, поэтому он конкурентоспособен.

Случайный

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

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

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

Алгоритм замены страниц по принципу "наиболее длинная дистанция в первую очередь" (LDF)

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

Техника для оборудования без референтного бита

Многие из техник, описанных выше, предполагают наличие бита обращения, связанного с каждой страницей. Некоторые аппаратные средства не имеют такого бита, поэтому для их эффективного использования требуются техники, хорошо работающие без него. Ярким примером является аппаратное обеспечение VAX, работающее под управлением OpenVMS. Эта система знает, была ли страница изменена, но не обязательно, была ли страница прочитана. Такой подход известен как вторичное кэширование страниц (Secondary Page Caching). Страницы, удаленные из рабочих множеств (частная память процесса, как правило), помещаются в специальные списки, оставаясь в физической памяти в течение некоторого времени. Удаление страницы из рабочего множества технически не является операцией замещения страницы, но фактически определяет эту страницу как кандидата. Страница, резервная копия которой все еще действительна (содержимое которой не является "грязным" или иным образом не требует сохранения), помещается в конец списка свободных страниц. Страница, требующая записи в резервное хранилище, будет помещена в список измененных страниц. Эти действия обычно запускаются, когда размер списка свободных страниц опускается ниже настраиваемого порога. Страницы могут выбираться для удаления из рабочего множества практически случайным образом, с ожиданием, что если будет сделан неудачный выбор, последующий доступ может извлечь эту страницу из списка свободных или измененных страниц до ее удаления из физической памяти. Страница, к которой обратились таким образом, будет удалена из списка свободных или измененных страниц и возвращена в рабочее множество процесса. Список измененных страниц также предоставляет возможность записи страниц в резервное хранилище группами, состоящими более чем из одной страницы, что повышает эффективность. Затем эти страницы могут быть помещены в список свободных страниц. Последовательность страниц, продвигающихся к началу списка свободных страниц, напоминает результаты работы механизма LRU или NRU, а общий эффект аналогичен алгоритму второго шанса, описанному ранее. Другой пример используется ядром Linux на архитектуре ARM. Отсутствие аппаратной функциональности компенсируется использованием двух таблиц страниц – таблиц страниц, специфичных для процессора, без битов обращения и "грязных" битов, и таблиц страниц, поддерживаемых программным обеспечением, с присутствующими необходимыми битами. Эмулированные биты в таблице, поддерживаемой программным обеспечением, устанавливаются при возникновении ошибок страниц. Чтобы вызвать ошибки страниц, очистка эмулированных битов во второй таблице отменяет некоторые права доступа к соответствующей странице, что реализуется путем изменения исходной таблицы.