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

В качестве первого подхода рассмотрим использование многоуровневой таблицы страниц, простой пример которой показан на рис. 3.12. В его левой части (на фрагменте а) показан 32-разрядный виртуальный адрес, разбитый на 10-битное поле PT1, 10-битное поле PT2 и 12-битное поле смещения.
Поскольку под смещение отведено 12 бит, страницы имеют размер 4 Кбайт и их общее количество составляет 220.

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

На рис. 3.12, б показано, как работает двухуровневая таблица страниц. Слева показана таблица страниц верхнего уровня, содержащая 1024 записи, соотносящиеся с 10-битным полем PT1. Когда диспетчеру памяти предоставляется виртуальный адрес, то сначала он извлекает поле PT1 и использует его значение в качестве индекса для таблицы страниц верхнего уровня. Каждая из этих 1024 записей в таблице страниц верхнего уровня представляет 4 Мбайт, поскольку все 4-гигабайтное (то есть 32-разрядное) виртуальное адресное пространство было разбито на фрагменты по 4096 байт.


б

Рис. 3.12. Многоуровневая таблица страниц: а — 32-разрядный адрес с двумя полями таблиц страниц; б — двухуровневая таблица страниц

Из записи, место которой определяется путем индексирования таблицы страниц верхнего уровня, извлекается адрес или номер страничного блока таблицы страниц второго уровня. Запись 0 таблицы страниц верхнего уровня указывает на таблицу страниц для текста программы, запись 1 — на таблицу страниц для данных, а запись 1023 — на таблицу страниц для стека. Другие (закрашенные) записи не используются. Поле PT2 теперь используется в качестве индекса на выбранную таблицу страниц второго уровня, предназначенного для поиска номера страничного блока для самой страницы.

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

Этот адрес выставляется на шину и отправляется к блоку памяти.

В отношении изображения на рис. 3.12 следует отметить одну интересную деталь. Хотя адресное пространство содержит более миллиона страниц, фактически востребованы только четыре таблицы: таблица верхнего уровня и таблицы второго уровня для памяти от 0 до 4 Мбайт - 1 (для текста программы), от 4 Мбайт до 8 Мбайт - 1 (для данных) и для верхних 4 Мбайт (выделенных под стек). Биты присутствия-отсутствия в остальных 1021 записи таблицы страниц верхнего уровня установлены в нуль, что при любом обращении к ним вызовет ошибку отсутствия страницы. При возникновении этой ошибки операционная система поймет, что процесс пытается обратиться к той памяти, обращение к которой не предполагалось, и предпримет соответствующие меры, например пошлет ему сигнал или уничтожит этот процесс. В данном примере мы выбрали для различных размеров округленные значения и размер поля PT1, равный размеру поля PT2, но в реальных системах, конечно, возможны и другие значения.

Система, показанная на рис. 3.12, в которой используется двухуровневая таблица страниц, может быть расширена до трех, четырех и более уровней. Дополнительные уровни придают ей большую гибкость. Например, 32-разрядный процессор Intel 80386 (выпущенный в 1985 году) способен был адресовать до 4 Гбайт памяти, используя двухуровневую таблицу страниц, которая состоит из каталога страниц, чьи записи указывают на таблицы страниц, которые, в свою очередь, указывают на фактические страничные блоки размером 4 Кбайт. Как в каталоге, так и в таблицах страниц содержится по 1024 записи, что в целом, как и требуется, дает 210 • 210 • 212 = 232 адресуемых байтов.

Спустя 10 лет с выпуском процессора Pentium Pro был введен еще один уровень: таблица указателей на каталоги страниц. Кроме всего прочего, каждая запись в каждом уровне иерархии таблиц страниц была расширена с 32 до 64 разрядов, что позволяло адресовать память за пределами 4-гигабайтной границы. Поскольку имелось всего 4 записи в таблице указателей на каталоги страниц, 512 записей в каждом каталоге страниц и 512 записей в каждой таблице страниц, общий объем возможной адресуемой памяти был по-прежнему ограничен максимальным значением 4 Гбайт. Когда же к семейству x86 была добавлена должная 64-разрядная поддержка (изначально это было сделано компанией AMD), дополнительный уровень можно было бы назвать указателем таблицы указателей на каталоги страниц. Это вполне вписалось бы в манеру присваивания названий производителями микросхем. К счастью, этого не произошло. И ими был выбран альтернативный вариант «страничное отображение уровня 4» (page map level 4) — конечно, имя не самое броское, зато короткое и более понятное. В любом случае, теперь эти процессоры используют все 512 записей во всех таблицах, выдавая объем адресуемой памяти 29 • 29 • 29 • 29 • 212 = 248 байтов. Они могли бы добавить и еще один уровень, но, возможно, подумали, что 256 Тбайт пока будет достаточно.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Многоуровневые таблицы страниц:

  1. Многоуровневость сознания в ее корреляции с многоуровневостью нервной системы
  2. Первая страница
  3. Таблица 2 Таблица баллов лучей мандалы
  4. Часть первая МНОГОУРОВНЕВАЯ МОДЕЛЬ ОРГАНИЗМА ЧЕЛОВЕКА
  5. Многофункциональность, многосубъектность. многоуровневость социальной сферы.
  6. ТАБЛИЦА ИЗОХРОМАТИЧЕСКАЯ
  7. Таблица. Иерархия функций
  8. Таблица типов
  9. Таблица 5. Диапазоны излучений патогенных микрооганизмов
  10. таблица болезней и их причин
  11. Периодическая таблица переживаний