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

Возможности, которые открывает нам механизм страничного отображения, очень богаты и разнообразны. По этой причине здесь не будет дана одна схема работы с памятью, как наиболее удобная; дело в том, что реализация виртуальной памяти, как естественного функционирования страничного преобразования, довольно-таки сложно - оно требует использования в комплексе работы с дисковой подсистемой (винчестером) либо сетевым оборудованием (для сетевого компьютера), если же операционная система подразумевается не как самостоятельная ОС, а надстройка над ОС режима реальных адресов (MS-DOS), то для работы с диском понадобится реализация режима виртуального 8086-процессора. Всё это выходит за рамки данного раздела, поэтому виртуальная память, к сожалению, здесь рассматриваться не будет.
Другой способ работы с механизмом страничного преобразования заключается в том, что программа определяет сегменты максимального размера, но отображает на физическую память минимальное необходимое число страниц и затем, по мере надобности, отображает их (этот способ, кстати, является частью системы виртуальной памяти, так что когда дело дойдёт до неё, у вас уже будет база для построения механизма свопинга).
В качестве примера можно привести следующее. Вы в программе определяете стек размером 4Мб. Для того, чтобы описать этот стек, понадобится 1024 страниц - целая таблица страниц, но вы определяете только первую страницу, все остальные - просто очищаете или сбрасываете и них бит P (0-й бит в PTE). В начала программа может нормально пользоваться стеком - в пределах первой страницы, пока не перейдёт в нём границу 4Кб. После того, как последует обращение за предел 4Кб, т.е. в следующую страницу, процессор обнаружит, что в её описании сброшен бит P - страница не присутствует. Процессор сгенерирует исключение страничного нарушения (#PF - прерывание 0Eh), обработчик исключения отобразит не присутствующую страницу на первую свободную физическую страницу и возобновит работу программы.
Таким образом, вы можете определять стек размером вплоть до 4Гб и не знать такой проблемы, как переполнение стека, хотя, на самом деле, это конечно же будет не корректным решением, но, как иллюстрация применения страничного преобразования - вполне подходит.
В защищённом режиме программа может использовать всё 32-разрядное адресное пространство, поэтому, создавая сегменты, не скупитесь на размеры - реально всё равно будет использоваться столько физической памяти, сколько нужно, не более того.
Например, максимальный размер GDT равен 64Кб - создавайте её с таким размером! Как правило, программа определяет GDT с небольшим числом дескрипторов - порядка десяти, редко, когда порядка ста, т.е. используется только первая страница из 16, описывающих адресное пространство GDT. Создавая GDT таким образом, вы закладываете в программу потенциал для её развития в будущем - вы, наверное, уже успели обнаружить, что программа, проектируемая до её написания всегда получается сложнее в конце. В данном случае, обращение к не присутствующей странице GDT, при правильно написанном обработчике страничного нарушения, всего лишь заставит процессор отобразить эту страницу на свободную физическую и ни вы, ни программа, даже не заметят этого. Если же произойдёт обращение за предел GDT, то процессор сгенерирует исключение общей защиты, выход из которого, как правило, один - аварийное прекращение работы программы.
Те же рекомендации относятся ко всем объектам, используемым в программе - код, стек, данные - всё это может увеличиваться и, значит, нуждается в страничном отображении, но не полностью, а лишь используемой в данный момент части. Разумеется, есть некоторые разумные исключения. Например, при выводе в текстовом режиме 80х25 вам потребуется ровно 4000 байт для описания видеопамяти (точнее - её первой страницы, - но больше, как правило, не используется). Поэтому достаточно для видеопамяти определить одну страницу в адресном пространстве - больше и не надо. То же самое касается ПЗУ или таблиц данных BIOS-а - они находятся в памяти по фиксированным адресам, их размеры не меняются, поэтому можно смело определять сегменты для них и сразу же целиком отображать их на физическую память.
Применяя страничное отображение, старайтесь размещать сегменты по адресам, кратным 4Кб и с размерами, также кратными 4Кб - это заметно упрощает управление страницами. Если же сегмент совмещён в одной странице с другим сегментом, то понятие присутствия страницы в памяти будет относиться уже к двум сегментам и управлять такой страницей гораздо сложнее. При этом, конечно же, будет наблюдаться некоторая экономия памяти, но расплачиваться за неё придётся более сложным кодом и потерей производительности.
При обработке страничного нарушения перед обработчиком встают две основные задачи: знать, сколько свободных страниц физической памяти осталось и где, собственно, они находятся. В связи с этим возникает необходимость вести специальные таблицы, в которых будут отображаться наличие и размещение свободных страниц физической памяти - эта задача целиком находится под ответственностью программы и процессор в этом явно никак не помогает. В результате - возникает множество вариантов таких таблиц и реализаций работы с ними и, как следствие, нельзя предусмотреть одного универсального способа. Здесь приводятся два примера решения такой задачи, возможно, они вам пригодятся как база для ваших собственных решений.

§ Пример 1

• Программа перед включением страничного отображения определяет количество доступной физической памяти в компьютере.
• Строится битовая карта, в которой каждой физической странице ставится в соответствие один бит, если этот бит равен 0, то страница свободна, если 1 - занята.
• Каждый раз, когда возникает необходимость в отображении новой страницы, обработчик страничного нарушения проходит всю битовую карту в поисках первой свободной физической страницы и как только находит её, устанавливает соответствующий бит в карте, вычисляет адрес этой страницы, строит элемент PTE (а если надо, то PDE и таблицу страниц), устанавливает бит P в PTE и производит рестарт команды, вызвавшей страничное нарушение.

В данном примере есть свои плюсы и минусы.
Плюсы:

• Маленький размер используемой таблицы свободных страниц. Один бит на страницу означает то, что один байт описывает 8 страниц, т.е. 32Кб памяти, следовательно, для каждого мегабайта физической памяти понадобится 1Мб / 4Кб / 8 = 32 байта таблицы. Т.е. если в вашем компьютере установлено 128Мб физической памяти, то для её описания понадобится битовая карта размером всего лишь 4Кб.
• Удобно просматривать такую таблицу - можно придумать множество алгоритмов, ускоряющих поиск бита, равного нулю.
• Для нахождения физического адреса свободной страницы не нужно хранить дополнительные данные - адрес вычисляется исходя из номера страницы в битовой карте - он просто умножается на 4096 и вы получаете нужный адрес.
• Получается битовая карта фиксированного размера, что упрощает к ней доступ.

Минусы:

• При работе с большим объемом памяти (например, 4Гб) получается большая битовая карта ( 128Кб ! ) и "прочёсывание" такой карты заметно притормозит любой, даже самый быстрый, процессор.

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

§ Пример 2

• Программа также в начале определяет количество доступной физической памяти.
• Создаётся таблица блоков свободных страниц в виде: число_блоков, [ число_страниц, номер_первой_страницы ] = число_блоков
• В процессе поиска свободной физической страницы сам поиск производится по блокам. При нахождении свободной страницы или группы страниц, описание блока меняется либо создаётся новый блок или несколько блоков.
• Для ускорения поиска можно ввести дополнительную битовую карту, в которой каждый бит будет определять, свободен ли блок или целиком занят.

В этом примере также есть плюсы и минусы.
Плюсы:

• Размер исследуемой структуры при поиске свободной страницы значительно меньше, чем в битовой карте.
• При отображении группы страниц можно подыскать целый блок, т.е. поиск производится по числу_страниц, что также ускоряет процесс.
• Можно использовать различные сортировки блоков по размеру, вводить указатели на группы блоков приблизительно одинакового размера и т.п.

Минусы:

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

отказ в отображении страницы из-за слишком большого списка блоков,

• Со временем поиск будет усложняться, следовательно, работа системы будет постепенно замедлятся (правда, похоже на Windows ?),
• Возможна неустойчивость в работе алгоритмов поиска просто потому, что они сами по себе получаются сложнее, чем в первом примере.

Как видите, оба примера достаточно сложны и имеют ряд недостатков. Можно попробовать объединить эти два метода в той или иной пропорции, но в любом случае получается сложная система. Вообще говоря, удачно построенная система управления памятью в вашей ОС является залогом её успешной работы (и чуть ли не самым сложным компонентом) и заодно - точкой приложения вашего таланта и фантазии. В следующей главе мы рассмотрим пример реализации обработчика исключения страничного нарушения, а когда изучим мультизадачность, программирование контроллеров дисковой подсистемы и режим виртуального 8086-процессора - построим систему виртуальной памяти и свопинга.