Инвертированные таблицы страниц

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

Алгоритмы очистки

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

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

· Алгоритм NRU - не использовавшаяся в последнее время страница. Используются биты Изменения и Обращения. Все страницы делятся на классы и удаляются страницы из непустого подмножества наименьшего класса.

o Класс 0: не было обращений и изменений.

o Класс 1: не было обращений, страница изменена.

o Класс 2: было обращение, страница не изменена.

o Класс 3: произошло и обращение, и изменение.

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

· Алгоритм FIFO — первым прибыл — первым обслужен. Все страницы хранятся в очереди относительно времени появления в памяти. Удаляется элемент в начале очереди. Операционная система поддерживает список всех страниц, находящихся в данный момент в памяти, в котором первая страница является старейшей, а страницы в хвосте списка попали в него совсем недавно. Когда происходит страничное прерывание, выгружается из памяти страница в хвосте списка, а новая страница добавляется в его конец.

· Вторая попытка. Модификация алгоритма FIFO, только если у элемента бит обращения стоит 1, он обнуляется и перемещается в конец очереди и алгоритм повторяется.

· Часы. Вторая попытка, только очереди нет, а вместо нее есть цикличный список элементов и стрелка, указывающая на самый старейший элемент. Также используется бит обращения.

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

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

· Алгоритм «Рабочий набор» – большинство программ случайным образом обращается к небольшому числу страниц, но это множество медленно изменяется во времени. Множество страниц, которое процесс использует в данный момент, называется рабочим набором.

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

· Алгоритм «WSclock». Часы + рабочий набор.

Когда загружается первая страница, она добавляется в список. По мере прихода страниц они поступают в список, формируя кольцо. Каждая запись, кроме бита R и бита М, содержит поле «время последнего использования» из базового алгоритма «рабочий набор».

Вывод:

Оптимальный - неосуществим; NRU - очень грубый; FIFO - может выгрузить важные страницы; Вторая попытка - значительно усовершенствованный FIFO; Часы - реалистичный; LRU - отличный алгоритм, но труден в осуществлении; NFU - грубое приближение LRU; Старение - эффективный; Рабочий набор - дорогостоящая реализация; WSClock - хороший, рациональный алгоритм.

Размер страницы:

· средний размер процесса равен s байт

· страницы — р байт

· запись для каждой страницы требует е байт

· р/2 - потеря памяти в последней странице

· s/p – число страниц процесса

· se/p – объем таблицы страниц

· расход памяти = se/p + р/2