Страничное преобразование адреса

В процессе страничного преобразования старшие 20 бит 32-битного линейного адреса (номер виртуальной страницы) заменяются другим 20-битным значением — номером физической страницы. Для этого привлекается находящаяся в памяти таблица страниц. Младшие 12 бит линейного адреса, определяющие положение байта внутри страницы (смещение в странице) остаются неизменными (см. рис.2. 14). Если производить такое преобразование за один этап, потребуется линейная таблица, содержащая 1М элементов. При размере элемента таблицы четыре байта (кроме 20-битного номера физической страницы элемент должен содержать дополнительную информацию о странице, т.е. служить своеобразным дескриптором страницы) для хранения таблицы страниц придется выделить блок памяти 4 Мбайт. В мультизадачной среде такая таблица может потребоваться для каждой задачи, что практически невозможно.

Физический адрес Рис.2.14. Одноэтапное преобразование линейного адреса в физический

Вместо этого в процессоре i486 реализовано более гибкое двухэтапное или двухуровневое преобразование, показанное на рис.2.15. Основой страничного преобразования выступает регистр управления CR3, который содержит 20-битный физический базовый адрес каталога страниц текущей задачи и называется регистром базового адреса каталога страниц — PDBR (Page Directory Base Register ). Отметим, что это единственный внутренний регистр процессора, который содержит физический адрес памяти. Младшие 12 бит адреса считаются нулевыми, т. е. каталог выравнен по границе страниц. Предполагается, что каталог страниц постоянно находится в памяти и не участвует в свопинге.

Корневая таблица, называемая таблицей страниц первого уровня или просто каталогом страниц, содержит 1024 32-битных дескриптора, называемых элементами каталога страниц — PDE (Page Directory Entry). Каждый из них адресует подчиненную таблицу страниц (таблицу страниц второго уровня), т.е. всего допускается до 1024 подчиненных таблиц страниц. Каждая из таблиц страниц содержит 1024 32-битных дескриптора, называемых элементами таблицы страниц — РТЕ (Page Table Entry ), и каждый из элементов РТЕ, в свою очередь, адресует страничный кадр в физической памяти. Отметим, что наличие в каталоге страниц и таблице страниц по 1024 32- битных элементов определяет их размер точно в одну страницу.

Собственно преобразование линейного адреса в физический состоит из следующих действий:

— старшие 10 бит 31—22 линейного адреса, дополненные двумя младшими нулями, служат индексом каталога страниц, выбирая один из 1024 элементов; выбранный элемент PDE определяет 20-битный адрес таблицы страниц,

— средние 10 бит 21 — 12 линейного адреса, дополненные двумя младшими нулями, индексируют таблицу страниц, выбирая из нее элемент РТЕ; он содержит 20-битный базовый адрес страничного кадра в физической памяти,

— базовый адрес из элемента РТЕ объединяется (сцепляется) с младшими двенадцатью битами 11—0 линейного адреса, в результате чего получается 32-битный физический адрес памяти, по которому производится обращение.

Таблицы страниц Физическая

память

Рис.2.15. Двухэтапное преобразование линейного адреса в физический

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

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

ФОРМАТ ЭЛЕМЕНТА ТАБЛИЦ СТРАНИЦ.Элементы таблиц страниц обоих уровней, т.е. элементы PDE и РТЕ, имеют одинаковый формат, представленный на рис. 2.16.

Рис.2.16. Формат элемента таблицы страниц

Адрес страничного кадра.Вэтом поле находится физический базовый адрес страницы. Так как в физической памяти страницы таблиц выравнены по границам страниц (по границам 4 Кбайт), младшие 12 бит базового адреса считаются нулевыми. В элементе PDE адрес страничного кадра является адресом таблицы страниц. В элементе РТЕ адрес страничного кадра является адресом страницы, содержащей данные или команды.

Биты системного программиста.Процессор никогда не использует и не изменяет биты 9, 10 и 11. Разработчики операционных систем могут привлечь эти биты для хранения информации о «старении» таблиц страниц, т.е. о том, как часто они используются.

Бит присутствия.Бит присутствия Р (Present) показывает, отображается ли адрес страничного кадра на страницу в физической памяти. Когда Р = 1, страница находится в памяти.

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

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

1. Операционная система копирует страницу с диска в физическую память.

2. Операционная система загружает адрес страничного кадра в элемент таблицы страниц и устанавливает бит Р. Могут быть установлены и другие биты, например бит R/W.

3. Так как в буфере TLB может оставаться копия старого элемента таблицы страниц, операционная система очищает его.

4. Осуществляется рестарт команды, вызвавшей особый случай.

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

31 0

Рис.2.17. Формат элемента таблицы страниц для неприсутствующей страницы

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

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

За исключением бита D в элементе каталога страниц эти биты устанавливаются в 1 аппаратно, т.е. автоматически; однако процессор самостоятельно не сбрасывает ни один из этих бит. Процессор устанавливает бит А в таблицах страниц обоих уровней до операции считывания или записи в таблицу. Процессор устанавливает в 1 бит D в в элементе РТЕ до производства операции записи по адресу, определяемому этим элементом. Бит D в элементах PDE каталога не определен.

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

Операционная система привлекает бит D при возвращении страницы на диск. Сбрасывая в 0 бит D при загрузке страницы в память, операционная система может узнать о производстве записи в страницу. Если на диске есть копия страницы и к странице в па­мяти не было обращений для записи, передавать страницу из памяти на диск не нужно.

Состояние D = 0 показывает, что содержимое страничного кадра не изменялось и при выборе его для передачи на диск в процессе свопинга физическую передачу производить не нужно. Когда же бит D = 1, при выборе страничного кадра на удаление из физической памяти его содержимое необходимо записывать на диск. (В этом смысле термин «бит мусора», который применяется в некоторых переводных книгах, оказывается не только неудачным, но и логически неверным.)

Биты считывание/запись и пользователь/супервизор.Биты R/W считывания/записи и U/S супервизор/пользователь применяются в механизме защиты применительно к страницам; контроль достоверности обращения осуществляется одновременно с преобразованием адреса. Подробнее о механизме защиты см. гл. 3.

Биты управления кэшированием.Биты PCD запрещения кэширования страницы и PWT сквозной записи применяются для управления кэшированием на уровне страниц. С их помощью программа может управлять кэшированием отдельных страниц.

Рассмотрение формата элемента таблицы страниц показывает, что он напоминает дескриптор сегмента, но гораздо проще. В нем нет полей типа и предела (размер всех страниц одинаков) и он явно разрешает только операции считывания и записи. С помощью бита U/S реализована простая двухуровневая система привилегий. Самое большое поле в рассматриваемом элементе, как и в дескрипторе сегмента, служит указателем памяти.

ОСОБЕННОСТИ СТРАНИЧНОГО ПРЕОБРАЗОВАНИЯ.В общем, механизм страничного преобразования действует примерно так же, как механизм сегментации, но оказывается более простым. Основные отличия дескрипторов страниц от дескрипторов сегментов заключаются в меньшем поле адреса (20-битный базовый адрес страницы вместо 32-битного базового адреса сегмента) и отсутствии поля предела. Оба этих отличия связаны с тем, что все страницы имеют одинаковый размер 4 Кбайт и выравнены по границам страниц; перекрытие страниц невозможно. В результате получается, что определяемая пользователем система сегментов накладывается на определяемую процессором систему страниц.

Таблицы страниц предназначены для преобразования (отображения) линейных адресов до их использования для обращения к физической памяти. При желании можно преобразовать любой адрес всего линейного адресного пространства 4 Гбайт. Но преобразование всегда осуществляется единицами (блоками) по 4 Кбайт. Другими словами, линейные адреса от 0 до 00000FFFH можно отобразить на другой диапазон адресов как блок; все адреса от 00001000Н до 00001FFFH можно отобразить на другие адреса и т.д. На рис. 2.18 показаны линейное адресное пространство (видимое пользователю) и физическое адресное пространство. На каждой границе 4 Кбайт адреса следующего блока 4 Кбайт линейного пространства можно отобразить на любой блок 4 Кбайт физической памяти. Все адреса в блоке преобразуются как группа.

Рис.2.18. Линейное и физическое пространства памяти

Можно считать элемент РТЕ источником 20 старших бит физического адреса. Они объединяются с младшими 12 битами линейного адреса, образуя полный 32-битный физический адрес. Поле адреса в элементе PDE непосредственно не отражается в физическом адресе; оно используется только для локализации таблицы страниц.

2.2.3. Построение таблиц

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

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

На рис.2.19 показано схематическое представление диапазона линейных адресов некоторой системы, имеющей несколько сегментов кода, данных и стека. Вверху линейного адресного пространства размещено загрузочное ПЗУ. Из рис. 2.19 видно, что сегменты образуют четыре блока с промежутками между ними. Некоторые промежутки невелики, но другие могут быть очень большими например промежуток от последнего сегмента данных до начала сегмента кода загрузочного ПЗУ. Можно гарантировать, что нельзя образовать линейные адреса вне этих диапазонов; а если нет линейных адресов, то не нужна и таблица преобразования.

Первые несколько элементов PDE в каталоге страниц приведены на рис. 2.20; выбор конкретного элемента определяется десятью старшими битами линейного адреса. Следовательно, первый элемент PDE 0 используется для линейных адресов от 0 до 003FFFFFH, второй элемент PDE 1 для линейных адресов от 00400000Н до 007FFFFFH и т.д. Последний элемент PDE 1023 привлекается для адресов от FFC00000H до FFFFFFFFH. Таким образом, каждый элемент PDE перекрывает адресный диапазон 4 Мбайт. Если известно, что линейный адрес никогда не попадет данный адресный диапазон 4 Мбайт, то не нужно определять cooтветствующую таблицу страниц. Поэтому каждый адресный диапазон 4 Мбайт, который будет обязательно отсутствовать, экономит одну таблицу страниц размером 4 Кбайт.

Рис.2.19. Карта линейных адресов

Казалось бы, что ненужный элемент PDE можно удалить, но это невозможно. Обычно любая таблица (каталог или таблица страниц) должны содержать точно 1024 дескриптора страниц независимо от того, используются некоторые из них или нет. При наличии промежутков в адресном пространстве (см. рис.2.19) неиспользуемые элементы PDE служат пассивными «держателями места» (placeholders). Элементы PDE не похожи на дескрипторы сегментов, которые в дескрипторной таблице размещаются в любом порядке. Нужный элемент PDE (и РТЕ) отыскивается в процессе преобразования адреса по его позиции в таблице, определяемой 10-битным индексом.

Конечно, когда общий диапазон линейных адресов невелик, можно сократить размер каталога страниц. Если, например, известно, что никогда не будет образован линейный адрес больше 00480000Н (4.5 Мбайт), то в каталоге страниц необходимо определить только два первых элемента PDE 0 и PDE 1, которые перекрывают диапазон 8 Мбайт. Остальные 1022 элемента PDE определять не нужно.

Аналогичным приемом можно воспользоваться, когда рабочие линейные адреса находятся в любом диапазоне. Если линейный адрес меньше какого-то значения никогда не образуется, то начальные элементы каталога страниц можно не определять, загружая в регистр CR3 адрес, который меньше фактического адреса первого элемента PDE. Например, на рис. 2.21 этот прием показан для линейного адресного пространства 16 Мбайт, находящегося по старшим адресам.

Рис.2.21. Сокращенный каталог страниц

Приведенные выше соображения относятся и к элементам PTI в таблицах страниц, каждый из которых перекрывает 4 Кбайт линейных адресов (а вся таблица страниц определяет 4 Мбайт). Если известно, что будет использоваться только часть диапазона 4 Мбайт, можно сократить число «рабочих» элементов РТЕ, но сохраняя размер таблицы страниц в 4 Кбайт.

Рис.2.22. Фрагментированное пространство физической памяти

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

Одно из наиболее частых применений страничного преобразования связано с превращением фрагментированного пространства физической памяти в непрерывное (сплошное или смежное). Обратимся к карте физической памяти, показанной на рис.2.22. Как видно из этого рисунка, память «разбита» на отдельные блоки и в ней нет блоков более 128 Кбайт. Что произойдет, если пользователь захочет загрузить и выполнить программу, размер которой составляет, например, 140 Кбайт? Ее придется распределить на несколько логических сегментов и с помощью команд FAR JMP и FAR CALL передавать управление между сегментами. Естественно, при этом эффективная производительность системы ухудшается, так как такие передачи управления являются вынужденными и не требуются с точки зрения логики программы. Когда же разрешено страничное преобразование, можно легко преодолеть возникшую трудность.

Рис.2.23. Образование непрерывных линейных адресов

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

Рис.2.24. Альтернативное именование на страничном уровне

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

Страничное преобразование адреса можно применить также для альтернативного именования страниц, т.е. образования псевдонимов на страничном уровне, которое аналогично альтернативному именованию сегментов. Если отобразить два или более блоков линейных адресов на один и тот же страничный кадр, у него будет несколько псевдонимов; Принцип альтернативного именования страниц показан на рис. 2.24. Когда два элемента РТЕ показывают на один и тот же страничный кадр (на рис, 2.24 это отмечено крестиком), каждый его байт будет иметь два линейных адреса. Дублируемые адреса полностью зависят от позиций элементов РТЕ в таблицах страниц и позиции таблицы страниц в каталоге. На рис. 2.24 видно также, что два элемента PDE (PDE 0 и PDE 1) показывают на одну и ту же таблицу страниц. Следовательно, каждый адрес внутри описываемых элементами пространств 4 Мбайт соответствует одному и тому же физическому адресу.

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