kailot2 1) Когда я делал свой аллокатор я обрёл знания. Эти знания я не встречал нигде.
2) Списки является прямым следствие после битовой карты. Более того битовая карта не применима для аллокатора. Так что не тратьте на неё время.
3) Я советую вам взять кукую либо открытую ОС или Компилятор и скопировать от туда алгоритм кучи.
Почему я не публикую свой? Да по простой причине руки не доходят нормально оттестировать.
А алгоритм достаточно сложный.
4) Но могу дать словесное описание.
Куча представляет из семя массив блоков свободных и занятых
Каждый блок имеет вначале и конце свой размер.
В переменных с размером также имеется битовый флаг,
который сигнализирует свободный или занятый блок
Свободные блоки организованы в список, при помощи указателей
на предыдущей и следующий свободные блоки.
Список не кольцевой и начинается и заканчивается с nil. В некоторых алгоритмах предлагается использовать кольцевой список.
Код:
PBlockFree = ^TBlockFree; // Элемент для списка свободных блоков
TBlockFree = packed record
LeftSize: DWord;
Prev: PBlockFree;
Next: PBlockFree;
FreeBytes:array [0..X] of Byte; //пустое место имеет переменное число байт
RightSize: DWord; // из-за этого структуру нельзя описать формально
end;
Поэтому формально каждый блок описывается двумя структурами.
Код:
PBlockFree_Start = ^TBlockFree_Start; // Начало блока
TBlockFree_Start = packed record
LeftSize: DWord;
Prev: PBlockFree_Start;
Next: PBlockFree_Start;
end;
PBlockFree_Stop = ^TBlockFree_Stop; // Конец блока
TBlockFree_Stop = packed record
RightSize: DWord;
end;
В элементах структур LeftSize и RightSize помимо размера хранится ещё и битовый флаг отвечающий свободный блок или занятый. Если флаг равен 0, то блок свободен 1 используется.
Для совмещения в одной DWord флага и размера. Любой блок выравнивается на границе в 4 байта. Поэтому у размера нижние 2 бита всегда 0. И можно при помощи маски совместить или отличить. Флаг от размера.
Код:
{Формула для выравнивания на границе}
function Allign(Addr:DWord; Chank:DWord):DWord;
begin
Allign:=(Addr+(Chank-1)) and not (Chank-1);
end;
Если блок свободный, то чтобы изменить его тип на занятый надо сделать
Код:
Block_Start^.LeftSize:=Size or 1; // Изменяем флаг на занято
Block_Stop:=PDWord(Addr(Block_Start^)+Size-SizeOf(Block_Stop^)); // вычисляем адрес конец блока
Block_Stop^.RighteSize:=Block_Start^.LeftSize; // Изменяем флаг на занято
Суть алгоритма выделения и освобождения памяти.
Если размер выделяемой памяти меньше чем описатель свободного блока, то надо его увеличить. Это решает проблему с тем что при освобождении надо выделять память. Теперь не нужно.
Надо перебрать все свободные блоки. Если нашли подходящий по размеру то помечаем блок как занятый. Или блок разрезается на два. Первый помечается как занятый, а второй(остаток) помечается как свободный.
Если размер
остатка меньше чем описатель свободного блока, то надо его увеличить. Это решает проблему с тем что при освобождении надо выделять память. Теперь не нужно.
Если не нашли нужный блок в списке свободных. То просим у ОС увеличить размер кучи. Т.е. сами увеличиваем.
Если и это не помогает генерируем ошибку системы.
Для освобождение блока нам надо проверить левый и правый блоки. Если они свободные то нам надо слить(объединить) наш блок с левым или правым или одновременно слить 3 блока(левый и наш и правый).
Ускоряем код. Для ускорения выделения надо начинать проверять с того блока который только что освободили. Для этого достаточно поместить освобожденный блок на верхушку списка.
В кольцевом варианте алгоритма просто запоминают позицию и начинают с неё.
Вход
Регистрация
FAQ
Поиск
