4.4 Стратегия замещения страниц
Управлении памятью UNIX делится на аппаратно-зависимую и аппаратно-независимую части.
Аппаратная часть интерпретирует адрес памяти, вырабатываемый командой, аппаратурой не как реальный физический адрес, а как некоторая структура, разные поля которой обрабатываются разным образом.
Аппаратно-независимая часть описывается структурой as и связывается с конкретной аппаратной реализацией с помощью аппаратно-зависимой части.
Если нет свободных страничных фреймов, то для размещения новой страницы ядро должно удалить страницу, находящуюся в памяти в текущий момент времени. Стратегии замещения страниц служат для принятия решения о том, какую именно страницу следует удалить из памяти. Идеальным кандидатом является “мертвая” страница, которая больше не требуется (например, если она принадлежит завершенному процессу). Если таких страниц нет в памяти (или их мало), ядро может выбрать правило либо локального, либо глобального замещения страниц. Правило локального замещения выделяет определенное количество страниц каждому процессу или группе взаимосвязанных процессов и если процессу необходима новая страница, он должен заменить одну из своих собственных страниц. При глобальном замещении нужно замещать страницу любого процесса, используя глобальные критерии выбора.
Правила локального замещения применяются в том случае, если нужно гарантированно выделять ресурсы определенным процессам. Например, системный администратор может выделить больший объем страниц наиболее важным процессам. С другой стороны, ”глобальные правила” проще для реализации и подходят для систем разделения времени. В большинстве вариантов UNIX реализовано правило глобального замещения, но для каждого активного процесса резервируется некое минимальное количество резидентных страниц.
Для реализации глобального замещения необходимо выбрать правило, в соответствии с которым, будет приниматься решение о том, какие страницы хранить в памяти. В идеале нужно хранить только те страницы, которые будут использованы вскоре. Этот набор страниц получил название рабочего набора (working set) процесса.
Обычно для замещения страниц применяется правило наименее частого использования (LRU). При этом удаляются те страницы, к которым доступ давно не производился.
Стратегия выбора страницы для замещения зависит от типа операционной системы.
Страничное замещение в BSD
Вся ОП делится на три части. Первые две фиксированы в ОП (не выгружаются) – ядро и карта памяти. Остальная часть поделена на страничные блоки, каждый из которых может быть занят текстом, данными, стеком или быть свободным. Информация о содержимом блоков содержится в карте памяти.
При загрузке процесса ОС берет первый блок из списка свободных страниц, удаляет его из списка и считывает в него нужную страницу. Если свободных страниц нет, процесс приостанавливается до тех пор, пока страничный демон не освободит страничный блок.
В системе поддерживается количество страниц не меньшее некоторого заданного параметра lotsfree(как правило ¼ памяти). Если становится меньше, начинается откачка страниц из памяти на диск. Если >=, то страничный демон ничего не делает – спит.
Страничный демон использует модификацию алгоритма часов.
Изначально использовался основной алгоритм с одной стрелкой.
Основной алгоритм часов работает, сканируя в цикле страничные блоки (как если бы они лежали на окружности циферблата). При первом проходе, сбрасываются биты использования со страничных блоков. При втором обходе, те блоки, к которым не было доступа за это время, записываются на диск и помещаются в список свободных страниц. При этом эти блоки сохраняют свое содержимое, что позволяет восстановить его, если потребуется.
При больших объемах ОП основной алгоритм работает медленно. Поэтому его заменили на алгоритм часов с двумя стрелками.
Первый проход делает первая стрелка и очищает биты использования блоков страниц. Вторая стрелка проверяет этот бит (как было при втором проходе). Если стрелки находятся очень близко, то только очень активно используемые страницы имеют шанс остаться в памяти. Если стрелки далеко (~ 3590), то получится основной алгоритм. Выбирается оптимальный вариант.
При каждом запуске страничного демона, стрелки проходят не полный оборот, а столько, сколько необходимо, чтобы поддерживать нужное количество свободных страниц.
Страничное замещение в System V
Страничная подкачка в System V во многом похожа на BSD. Но есть некоторые отличия.
1. Используется оригинальный алгоритм с одной стрелкой. Страница помещается в список свободных, если не использовалась в течении нескольких проходов.
2. Вместо переменной lotsfree, используются две переменные min и мах. Страничный демон начинает освобождать страницы, когда их количество становится меньше min, пока число свободных страниц не не сравняется с мах. Такой подход позволяет страничному демону дольше находиться в состоянии сна.
Управление памятью в Linux
ВАП (Вирт. Адр простр) процесса делится на однородные непрерывные области, состоящие из соседних страниц с одинаковым режимом защиты и свойствами подкачки. Например, сегменты текса и отображенных файлов.
Каждый процесс имеет список областей, где каждая область представлена структурой vm_area_struct. Эта структура содержит следующую информацию:
Режим защиты (чтение, чт/запись)
Является ли данная область фиксированной или выгружаемой
Направление роста области
Является ли область приватной или совместно используемой
Есть ли у области место хранения на диске и где оно расположено (текстовые сегменты имеют в качестве места резервного копирования двоичные файлы, файлы, отображаемые на память – соответствующие им файлы, напр, библиотеки. Все остальные сегменты не имеют области резервного копирования пока не потребуется из выгрузка на диск, тогда создаются временные файлы.)
В Linux используется трехуровневая система страничной подкачки. Каждый виртуальный адрес разбит на четыре поля:
Каталог (используется как индекс в каталоге /proc, который содержит ссылку на среднюю таблицу страниц)
Середина (указывает на таблицу из средней таблицы страниц)
Страница (указывает на страницу из таблицы станиц)
Смещение (указывает на текущее слово)
Рисунок 4.8 - Трехуровневая система страничной подкачки Linux
Для управления памяти в Linux используются три алгоритма, взятые из System V.
Первый – «дружественный» - выделяет память с произвольным количеством страниц. При выделении памяти процессу общий размер памяти делится пополам до тех пор, пока не получим нужный размер.
Рисунок 4.9 – Дружественный алгоритм
При таком выделении памяти получается большая фрагментация. Для решения этой проблемы применяется второй алгоритм, нарезающий из блоков более мелкие фрагменты и управляющий ими отдельно.
Кроме того, есть еще третий алгоритм, который используется, когда выделяемая память должна быть непрерывна только в ВАП, но не в физической памяти.
В Linux реализована страничная подкачка по требованию без предварительной загрузки страниц и без концепции рабочего набора.
Алгоритм замещения страниц работает следующим образом. Страничный демон должен поддерживать достаточное количество свободных страниц. Для этого он просыпается каждую секунду.
Страничный демон состоит из цикла, который выполняется до шести раз с возрастающей скоростью. Тело цикла выполняет обращения к трем процедурам, каждая из которых пытается получить различные типы страниц. Процедурам передается параметр скорости. В результате сначала выбираются легко доступные страницы каждой категории, а потом переходит к труднодоступным. Первая процедура ищет страницы в страничном и буферном кэше по алгоритму часов. Вторая – ищет совместно используемые страницы. Третья – пытается получить страницы, используемые пользователями.
В управлении памятью используется еще один демон, bdflush. Он следит за тем, чтобы количество «грязных» страниц (бит обращения очищен, но страница хранит информацию) не превышало определенного уровня. Если превысило, демон начинает сохранять их на диск.