к ячейке памяти. Типичная команда процессора часто включает в себя, помимо слова-опкода, также операнд(ы) памяти. В результате необходимо сделать 1, 2 или иногда больше обращений к таблице страниц в рамках отработки одной команды. Если выполнение команды занимает, скажем, 4 не, то поиск в таблице страниц должен завершиться до истечения 1 не, чтобы преобразование виртуальных адресов не стало главным узким местом системы.

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

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

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

Многоуровневые таблицы страниц

Чтобы обойти проблему необходимости постоянного хранения в памяти офом-ных таблиц страниц, во многих компьютерах применяются многоуровневые таблицы страниц. Простой пример представлен на рис. 4.10. На рис. 4.10, а изображен 32-разрядный виртуальный адрес, разделенный на 10-разрядное поле РТ1, 10-разрядное поле РТ2 и 12-разрядное поле Offset (смещение). Так как под смещение отведено 12 бит, страницы имеют размер 4 Кбайт, и их всего 2°.

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

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

Таблица страниц второго уровня

Табпица страниц верхнепэ уровня

1023

Биты 10

10 12

Смещение

Таблица страниц

для старших 4 Мбайт памяти

1023

К страницам

Рис. 4.10. а - разрядные адреса с полями двух таблиц страниц; б - двухуровневая таблица страниц

На рис. 4.10, 5 мы видим, как в данном примере работает двухуровневая таблица страниц. Слева находится таблица страниц верхнего уровня с 1024 записями, соответствующими 10-разрядному полю РТ1. Когда виртуальный адрес предстает перед диспетчером памяти, тот сначала выделяет поле РТ1 и использует его значение как индекс таблицы верхнего уровня. Каждая из этих 1024 записей

представляет 4 Мбайт, поскольку целое 4-гигабайтное (то есть 32-разрядное) виртуальное адресное пространство было нарезано на куски по 1024 байта.

Запись, место которой определяется по индексу в таблице страниц верхнего уровня, выдает адрес или номер страничного блока таблицы страниц второго уровня. Запись О в таблице страниц первого уровня указывает на таблицу страниц для текста программы, запись 1 указывает на таблицу страниц для данных, запись 1023 указывает на таблицу страниц для стека. Другие (заштрихованные) записи не задействованы. Поле РТ2 теперь используется как индекс в выбранной таблице второго уровня для поиска номера страничного блока самой страницы.

В качестве примера рассмотрим 32-разрядный адрес 0x00403004 (4 206 596 в десятичном виде), который соответствует байту 12292 в данных. У этого виртуального адреса РТ1 = 1, РТ2 = 2 и Offset = 4. Менеджер памяти сначала по полю РТ1, то есть по индексу в таблице страниц верхнего уровня, получает запись 1, которая соответствует адресам от 4 М до 8 М. Затем из поля РТ2, по индексу из только что найденной таблицы второго уровня, извлекает запись 3, которая соответствует адресам от 12 288 до 16 383 внутри своего участка размером 4 М (то есть абсолютным адресам от 4 206 592 до 4 210 687). Эта запись содержит номер физического блока страницы, содержащей виртуальный адрес 0x00403004. Если данная страница не находится в памяти, бит присутствия/от-сутствия в записи таблицы страниц будет равен нулю, что приведет к страничному прерыванию. Если страница в памяти, номер страничного блока, взятый из таблицы страниц второго уровня, присоединяется к смещению (4), образуя физический адрес. Этот адрес выставляется на шину и передается памяти.

Следует отметить одну интересную деталь на рис. 4.10. Хотя адресное пространство содержит больше миллиона страниц, фактически нужны только четыре таблицы: таблица верхнего уровня и таблицы нижнего уровня для памяти от О до 4 М, от 4 М до 8 М и для верхних 4 М. Битам присутствия/отсутствия для 1021 записи таблицы страниц верхнего уровня присвоено значение О, что вызовет страничное прерывание при любом обращении к ним. Если это произойдет, операционная система заметит, что процесс пытается обратиться к области памяти, не предполагающей ссылок на нее, и предпримет соответствующее действие, например пошлет ему сигнал или уничтожит его. В описанном выше примере мы выбрали круглые значения для различных величин и размер поля РТ1, равный размеру поля РТ2, но в реальной практике, конечно, возможны другие цифры.

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

Теперь от структуры таблиц страниц в целом мы перейдем к описанию отдельного элемента записи таблицы. Точная структура элемента в значительной мере зависит от машины, но виды представленной информации примерно одни и те же. На рис. 4.11 мы привели образец записи в таблице страниц. Ее длина варьируется от компьютера к компьютеру, но 32 бита - это наиболее распространенный размер. Самым важным полем является номер страничного блока.