Страничная организация памяти. Многоуровневая организация виртуального адресного пространства. Пример схемы двухуровневой страничной организации

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

Вся оперативная память машины также делится на части такого же размера, называемые физическими страницами (или блоками, или кадрами). Размер страницы выбирается равным степени двойки: 512, 1024, 4096 байт и т. д. Это позволяет упростить механизм преобразования адресов.

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

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

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

Другим важным резервом повышения производительности системы является правильный выбор размера страницы. С одной стороны, чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. С другой стороны, если страница велика, то велика и фиктивная область в последней виртуальной странице каждого процесса. Если учесть, что в среднем в каждом процессе фиктивная область составляет половину страницы, то в сумме при большом объеме страницы потери могут составить существенную величину. Типичный размер страницы составляет несколько килобайт, например, наиболее распространенные процессоры х86 и Pentium компании Intel, а также операционные системы, устанавливаемые на этих процессорах, поддерживают страницы размером 4096 байт (4 Кбайт).

Размер страницы влияет также на количество записей в таблицах страниц. Чем меньше страница, тем более объемными являются таблицы страниц процессов и тем больше места они занимают в памяти. Учитывая, что в современных процессорах максимальный объем виртуального адресного пространства процесса, как правило, не меньше 4 Гбайт (2³²), то при размере страницы 4 Кбайт (2¹²) и длине записи 4 байта для хранения таблицы страниц может потребоваться 4 Мбайт памяти! Выходом в такой ситуации является хранение в памяти только той части таблицы страниц, которая активно используется в данный период времени — так как сама таблица страниц хранится в таких же страницах физической памяти, что и описываемые ею страницы, то принципиально возможно временно вытеснять часть таблицы страниц из оперативной памяти.

Двухуровневая таблица страниц

Таблица страниц хранится в памяти. Если она имеет большой размер(для адресного пространства в 4 Гб и размера страницы в 4Кб - таблица 4 Мб), то необходимо как-то выгрузит часть ее из памяти. Для этого она разбивается на части (разделы). Причем кол-во страниц подбирается таким образом, чтобы объем раздела был равен объему страницы (чтобы раздел можно было выгрузить на жесткий диск, как обычную страницу). И создается таблица разделов, выглядещая как таблица страниц. При вычислении физического адреса по логическому сначала вычисляется адрес таблицы разделов (по старшим битам в адресе), потом уже по остальным битам в этой таблице разделов ищется адрес необходимой страницы (для этого необходимо, чтобы число страниц в разделе было кратно 2). То есть мы будем иметь логический адрес вида: РРРРФФФФФФФФФССССС,

Где РРР – номер раздела, ФФФФ –страницы в разделе, СССС – смещение в странице. (все это нули или единицы, то есть 1110111100111101111 и всего их 32 штуки!)

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

Недостатки страничной организации памяти: Сложен совместный доступ пользователей к процедурам, наличие внешней фрагментации.

Задача

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

1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3.

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