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

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

Одинаковыми полагаются и единицы памяти, которые предоставляются для размещения фрагментов программы. Эти одинаковые части называют страницами и говорят, что ОП разбивается на физические страницы, а программа – на виртуальные страницы. Часть виртуальных страниц задачи размещается в ОП, а часть – во внешней памяти. Обычно место во внешней памяти, в качестве которой в абсолютном большинстве случаев выступают накопители на магнитных дисках (поскольку они относятся к быстродействующим устройствам с прямым доступом), называют файлом подкачки, или страничным файлом (англ. paging file). Иногда этот файл называют swap-файлом, тем самым подчеркивая, что записи этого файла – страницы – замещают друг друга в ОП. В некоторых ОС выгруженные страницы располагаются не в файле, а в специальном разделе дискового пространства.

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

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

Страничный метод распределения памяти имеет следующие недостатки:

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

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

 

 

18. Какие существуют варианты организации и использования таблиц страниц?

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

1. Многоуровневая таблица страниц

Для примера рассмотрим двухуровневую таблицу с размером страниц 4 Кбайт, реализованную в 32-разрядной архитектуре Intel. Таблица, состоящая из 2²⁰ строк, разбивается на 2¹⁰ таблиц второго уровня по 2¹⁰ строк. Эти таблицы второго уровня объединены в общую структуру при помощи одной таблицы первого уровня, состоящей из 2¹⁰ строк. 32-разрядный адрес делится на 10-разрядное поле p1, 10-разрядное поле p2 и 12-разрядное смещение d. Поле p1 указывает на нужную строку в таблице первого уровня, поле p2– второго, а поле d локализует нужный байт внутри указанного страничного кадра.

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

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

2. Ассоциативная память

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

Одна запись таблицы в ассоциативной памяти (один вход) содержит информацию об одной виртуальной странице: ее атрибутах и кадре, в котором она находится. Эти поля в точности соответствуют полям в таблице страниц.

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

3. Инвертированная таблица страниц

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

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