Страничное распределение

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

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

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

Размер страницы выбирается равным степени двойки: 512, 1024, 4096 байт и т. д, Это позволяет упростить механизм преобразования адресов.

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

Запись таблицы, называемая дескриптором страницыивключает следующую информацию:

· номер физической страницы,в которую загружена данная виртуальная страница;

· признак присутствия,устанавливается в единицу, если виртуальная страница находится в оперативной памяти;

· признак модификациистраницы, который устанавливается в единицу всякий раз, когда производится запись по адресу, относящемуся к данной странице;

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

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

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

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

После определения виртуальной страницы, обнуляется ее бит присутствия и анализируется ее признак модификации. Если за время последнего пребывания в оперативной памяти была модифицирована, ее новая версия должна быть переписана на диск. Если нет, то никакой записи на диск не производится (она и так есть). Физическая страница объявляется свободной.

Виртуальный адрес при страничном распределении может быть представлен в виде пары (р, s_v), где p — порядковый номер виртуальной страницы процесса (нумерация страниц начинается с 0), a s_v — смещение в пределах виртуальной страницы.

Физический адрес также может быть представлен в виде пары (n, S_f), где n — номер физической страницы, a S_f — смещение в пределах физической страницы. Задача подсистемы виртуальной памяти состоит в преобразовании пары (р, s_v) в (n, S_f).

Рассмотрим два базисных свойства страничной организации.

Первое из них состоит в том, что объем страницы выбирается равным степени двойки — 2^k . Из этого следует, что смещение s может быть получено простым отделением k младших разрядов в двоичной записи адреса, а оставшиеся старшие разряды адреса представляют собой двоичную запись номера страницы.

Например:

Размер страницы 1 Кбайт (2¹⁰). Двоичной адрес 101 000 111 001₂. Он принадлежит странице 10₂ и смещен относительно ее начала на 1 000 111 001₂ байт.

Второе свойство заключается в том, что в пределах страницы непрерывная последовательность виртуальных адресов однозначно отображается в непрерывную последовательность физических адресов, т.е. s_v = S_f.

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

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

Если происходит обращение к памяти по некоторому виртуальному адресу. Аппаратными схемами процессора выполняются следующие действия:

· Из специального регистра процессора извлекается адрес AT таблицы страниц активного процесса. На основании начального адреса таблицы страниц, номе­ра виртуальной страницы p (старшие разряды виртуального адреса) и длины отдельной записи в таблице страниц L (системная константа) определяется адрес нужного дескриптора в таблице страниц: а =АТ+(рхL).

· Из этого дескриптора извлекается номер соответствующей физической страницы — n.

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

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

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

При выборе страницы на выгрузку смысл критерия сводится к одному: на диск выталкивается страница, к которой дольше всего не будет обращений

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

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

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

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

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

Важнейшая задача – выбор оптимального размера страницы.

Если страница велика, то велики потери из фиктивных областей (в среднем половина последней страницы). Выбор размера страницы – сложная оптимизационная задача. На практике размер страницы выбирают в несколько килобайт. Например, в процессорах Pentiumи ОС на них, поддерживают страницы размером 4096 байт (4 Кбайт).

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

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

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

Все страницы имеют одинаковый размер, а разделы содержат одинаковое количество страниц.

Если размер страницы и количество страниц в разделе выбрать равными степени двойки (2^k и 2ⁿ соответственно), то принадлежность виртуального адреса к разделу и странице, а также смещение внутри страницы определяется очень просто: младшие k двоичных разрядов дают смещение, следующие n разрядов – номер виртуальной страницы, а оставшиеся старшие разряды содержат номер раздела.

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

Например, в процессоре Pentium при размере страницы 4 Кбайт длина дескриптора составляет 4 байта и количество записей в таблице страниц, помещающейся на страницу, равно 1024. Каждая таблица страниц описывается дескриптором, структура которого полностью совпадает со структурой дескриптора обычной страницы. Эти дескрипторы сведены в таблицу разделов, называемую также каталогом страниц. Физический адрес таблицы разделов активного процесса содержится в специальном регистре процессора и поэтому всегда известен ОС. Страница, содержащая таблицу разделов, никогда не выгружается из памяти.

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

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

Проследим более подробно схему преобразования адресов для случая двухуровневой структуризации виртуального адресного пространства:

1. Путем отбрасывания k+n младших разрядов в виртуальном адресе определяется номер раздела, к которому принадлежит данный виртуальный адрес.

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

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

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

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