Глава 7. Использование страничного преобразования.

        Возможности, которые открывает нам механизм страничного отображения, очень богаты и разнообразны. По этой причине здесь не будет дана одна схема работы с памятью, как наиболее удобная; дело в том, что реализация виртуальной памяти, как естественного функционирования страничного преобразования, довольно-таки сложно - оно требует использования в комплексе работы с дисковой подсистемой (винчестером) либо сетевым оборудованием (для сетевого компьютера), если же операционная система подразумевается не как самостоятельная ОС, а надстройка над ОС режима реальных адресов (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.

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

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

Плюсы:

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

Минусы:

1.

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

Пример 2.

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

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

Плюсы:

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

Минусы:

1.

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

2.

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

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

Следующая глава

Оглавление

Вопросы? Замечания? Пишите: sasm@narod.ru

Copyright © Александр Семенко.