Лекция 6: Аппаратно-независимое управление виртуальной памятью

памятью

осуществляется при помощи таблицы страниц.
Для каждой виртуальной страницы запись в

таблице страниц содержит номер соответствующего страничного кадра в оперативной памяти, а также атрибуты страницы для контроля обращений к памяти.
Что же происходит, когда нужной страницы в памяти нет или операция обращения к памяти недопустима?

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

(exceptions).
При попытке выполнить подобное обращение к виртуальной странице возникает исключительная ситуация «страничное нарушение» (page fault), приводящая к вызову специальной последовательности команд для обработки конкретного вида страничного нарушения.

оперативной памяти,
при попытке записи в страницу с атрибутом «только чтение»

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

ситуации (page fault);
чтения (подкачки) страницы из вторичной памяти (иногда, при

недостатке места в основной памяти, необходимо вытолкнуть одну из страниц из основной памяти во вторичную, то есть осуществить замещение страницы);
возобновления выполнения процесса, вызвавшего данный page fault.

за счет уменьшения частоты страничных нарушений, а также за счет

увеличения скорости их обработки.
Таким образом, уменьшение частоты page faults является одной из ключевых задач системы управления памятью. Ее решение обычно связано с правильным выбором алгоритма замещения страниц.

из вторичной памяти в первичную?
Существует два основных варианта выборки —

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

чтение — кроме страницы, вызвавшей исключительную ситуацию, в память также

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

поступающую страницу?
В системах со страничной организацией все просто — в

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

память, чтобы освободить место в оперативной памяти?
Разумная стратегия замещения, реализованная

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

страницу основной памяти;
Переместить в случае надобности ее содержимое во внешнюю

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

основной и вторичной памятью. Процесс замещения может быть оптимизирован за

счет использования бита модификации. Бит модификации устанавливается, если хотя бы один байт был записан на страницу.
Если бит не установлен, нет необходимости переписывать данную страницу на диск. Метод применяется и к read-only-страницам, они никогда не модифицируются. Эта схема уменьшает время обработки page fault.

аппаратные средства, позволяющие собирать статистику обращений к памяти. Эти средства

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

для которой подсчитывается число возникающих page faults.
Эта последовательность называется строкой

обращений (reference string).
Мы можем генерировать строку обращений искусственным образом при помощи датчика случайных чисел или трассируя конкретную систему.

FIFO.

просто созданием очереди страниц, в конец которой страницы попадают, когда

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

чем больше в памяти страничных кадров, тем реже будут иметь

место page faults.
Удивительно, но это не всегда так. Как установил Билэди с коллегами, определенные последовательности обращений к страницам в действительности приводят к увеличению числа страничных нарушений при увеличении кадров, выделенных процессу. Это явление носит название «аномалии Билэди» или «аномалии FIFO».

поиск оптимального алгоритма, который при заданной строке обращений имел бы

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

которые будут выполнены, прежде чем на эту страницу будет сделана

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

того, чтобы алгоритм замещения был максимально близок к идеальному алгоритму,

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

страницы. Алгоритм LRU

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

течение самого долгого времени. Такой подход называется least recently used алгоритм (LRU).

8 pf

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

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

NFU

не предоставляют соответствующей аппаратной поддержки для реализации алгоритма LRU, хотелось

бы иметь алгоритм, достаточно близкий к LRU, но не требующий специальной поддержки.
Программная реализация алгоритма, близкого к LRU, — алгоритм NFU (Not Frequently Used).

на каждую страницу, которые сначала равны нулю.
При каждом прерывании по

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

что он ничего не забывает. Страница, к которой очень часто

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

«забывать». Достаточно, чтобы при каждом прерывании по времени содержимое счетчика

сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения.

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

часто используемых страниц с помощью анализа флага обращений для самой

старой страницы. Если флаг установлен, то страница, в отличие от алгоритма FIFO, не выталкивается, а ее флаг сбрасывается, и страница переносится в конец очереди. Если первоначально флаги обращений были установлены для всех страниц, алгоритм Second-Chance превращается в алгоритм FIFO. Использовался в Multics и BSD Unix.

Recently-Used), где страница-«жертва» выбирается на основе анализа битов модификации и

ссылки.
Интересные стратегии, основанные на буферизации страниц, реализованы в VAX/VMS и Mach.

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

для учета свободных и занятых страничных блоков
структура, организованная для контроля доступа к страницам процесса

страниц LRU?
стратегию размещения страницы в памяти при наличии списка свободных

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