Структура таблицы страниц

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

В большинстве систем для каждого процесса имеется одна таблица страниц. Однако каждый процесс может использовать большой объем виртуальной памяти — так, например, в архитектуре VAX каждый процесс может иметь до 2³¹ = 2 Гбайт виртуальной памяти. При использовании страниц размером 2⁹ = 512 байт оказывается, что нам требуется до 2²² записей в таблице страниц для каждого процесса. Понятно, что количество памяти, отводимое таблицам страниц, не может быть так велико. Для преодоления этой проблемы большинство схем виртуальной памяти хранят таблицы страниц не в реальной, а в виртуальной памяти. Это означает, что сами таблицы страниц становятся объектами страничной организации, как и любые другие страницы. При работе процесса как минимум часть его таблицы страниц должна располагаться в основной памяти, в том числе запись о странице, выполняющейся в настоящий момент. Некоторые процессоры используют двухуровневую схему для больших таблиц страниц. При такой схеме имеется каталог таблиц страниц, в котором каждая запись указывает на таблицу страниц. Таким образом, если размер каталога — X, а максимальный размер таблицы страниц — У, то процесс может состоять максимум из Х У страниц. Обычно максимальный размер таблицы страниц определяется условием ее размещения в одной странице (такой подход используется, например, в процессоре Pentium).

На рис, 8.4 приведен пример двухуровневой схемы, типичной для32х-битовой адресации. Принимая условие адресации байтов и 4-Кбайтовые (2¹²) страницы, мы получим 4-Гбайтовое (2³²) виртуальное адресное пространство, составленное из 2²⁰ страниц. Если каждая из этих страниц отображается посредством одной 4-байтовой записи в таблице страниц, то мы можем создать пользова­тельскую таблицу страниц, состоящую из 2²⁰ записей, общим объемом 4 Мбайт (2²² байт). Такая огромная таблица может быть размещена в 2¹⁰ страницах вир­туальной памяти, которые отображаются корневой таблицей страниц, состоящей из 2¹⁰ записей, которые занимают 4 Кбайт (2¹² байт) основной памяти. На рис. 8.5 показаны действия, выполняемые при трансляции адреса в двухуровневой системе. Корневая страница всегда остается в основной памяти. Первые 10 бит виртуального адреса используются для индексации в корневой таблице для поиска записи о странице пользовательской таблицы. Если нужная страница отсутствует в основной памяти, генерируется ошибка доступа к странице. Если же необходимая страница находится в основной памяти, то следующие 10 бит виртуального адреса используются как индекс для поиска записи о странице, на которую ссылается исходный виртуальный адрес.

Еще одним подходом к использованию одно- или двухуровневых таблиц страниц является применениеинвертированной таблицы страниц (invertedpage table), представленной на рис. 8.6, Этот подход применяется на машинах Power PC и IBM AS/400. Этот же подход использован и в операционной системе Mach на RT-PC.

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