Создание операционной системы на ассемблере
Проститутки Красное село

Динамическое распределение памяти.


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

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

В ДОСе вся память на равных правах принадлежит всем запущенным программам. Но чтобы операционная система могла как-то контролировать использование памяти, в ДОСе применяются MCB (Memory Control Block). Формат этого блока таков:

struct { char Signature; unsigned short OwnerId; unsigned short SizeParas; char Reserved[3]; char OwnerName[8]; };

Размер структуры 16 байт (1 параграф памяти) и эта структура непосредственно предшествует описываемому блоку памяти.
Размер блока указывается в параграфах в поле SizeParas. Такая структура вполне подходит для ограниченной по размерам памяти DOS, но для приложений она не очень то применима. Разница состоит в том, что в случае ДОС, чтобы найти блок свободной памяти (Такие блоки помечаются нулевым OwnerId), необходимо пройти по всем блокам от начала цепочки, до тех пор, пока не встретится свободный блок соответствующего размера. В ДОСе имеется функция, с помощью которой можно получить адрес первого блока (Base MCB) (int 21h, fn 52h).
Столь медленный поиск не страшен для DOS, у которого количество блоков редко превышает несколько десятков, но в приложениях поиск по цепочке блоков может быть достаточно долгой процедурой.
Поэтому в приложениях обычно применяется другой алгоритм, который заключается в следующем. (Я рассмотрю наиболее быстрый алгоритм, вариантов, конечно, может быть множество):

У каждого блока, как я уже говорил, есть два основных параметра: размер и флаг занятости. Оба эти параметра размещаются в одном двойном слове памяти. Поскольку как начало блока, так и его размер обычно выравниваются на четное число байт, младшие биты размера остаются неиспользуемыми (всегда равны нулю) и флаг занятости размещается в одном из них.




Этот параметр блока размещается перед началом и по окончанию блока. Начальный параметр следующего блока соответственно будет размещен непосредственно после конечного параметра предыдущего, что позволит анализировать цепочку блоков с одинаковым успехом в обоих направлениях.

Свободные блоки памяти размещаются в списках в соответствии со своим размером. Размер блоков в списках увеличивается в геометрической прогрессии. К примеру, в первом списке хранятся блоки до 16 байт длиной, во втором до 32-х байт длиной и так далее. Такая система позволяет, зная размер необходимого блока, сразу же выбирать из соответствующего списка подходящий блок и не требует поиска по всем блокам. Для организации списков к блоку добавляются несколько параметров (поскольку блок свободен, и его внутреннее пространство может быть использовано для любых целей, эти параметры размещаются в самом блоке). К этим параметрам относятся ссылка на следующий свободный блок в списке, и номер списка в котором находится блок. (Это позволяет ускорить удаление блока из списка).

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

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

При освобождении блока, если предыдущий или последующий блоки пусты, он объединяется с ними в один блок и добавляется в список соответствующего размера. Использованные окружающие блоки удаляются из тех списков, в которых они были записаны ранее.

Для того, чтобы предотвратить попытку объединения первого блока памяти (при его освобождении) с предшествующим ему, перед первым блоком ставится параметр с флагом занятости. То же самое делается и для последнего блока памяти, но только после него.

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

Отправлено 2002-02-15 для 6542 подписчиков.
ведущий рассылки Dron
Сайт проекта
Архив Рассылки

При поддержке Kalashnikoff.ru



Содержание раздела