Антисортировка
Рисунок 4.6. Антисортировка
Разработчик программы динамического распределения памяти обязан решить еще одну важную проблему, а именно — объединение свободных блоков. Действительно, обидно, если мы имеем сто свободных блоков по одному килобайту и не можем сделать из них один блок в 100 килобайт. Но если все эти блоки расположены в памяти один за другим, а мы не можем их при этом объединить — это просто унизительно.
Кроме того, если мы умеем объединять блоки и видим, что объединенный блок ограничен сверху значением brkievel, то мы можем, вместо помещения этого блока в список, просто уменьшить значение brkievel и, таким образом, вернуть ненужную память системе.
Представим себе для начала, что все, что мы знаем о блоке, — это его начальный адрес и размер. Легко понять, что это очень плохая ситуация. Действительно, для объединения блока с соседями мы должны найти их в списке свободных, или же убедиться, что там их нет. Для этого мы должны просмотреть весь список. Как одну из идей мозгового штурма можно выдвинуть предложение сортировать список свободных блоков по адресу.
Гораздо проще запоминать в дескрипторе блока указатели на дескрипторы соседних блоков. Немного развив эту идею, мы приходим к методу, который называется алгоритмом парных меток и состоит в том, что мы добавляем к каждому блоку по два слова памяти. Именно слова, а не байта. Дело в том, что требуется добавить достаточно места, чтобы хранить в нем размер блока в байтах или словах. Обычно такое число занимает столько же места, сколько и адрес, а размер слова обычно равен размеру адреса. На х86 в реальном режиме это не так, но это вообще довольно странный процессор.
Итак, мы добавляем к блоку два слова — одно перед ним, другое после него. В оба слова мы записываем размер блока. Получается своеобразный дескриптор, который окружает блок. При этом мы устанавливаем, что значения длин будут положительными, если блок свободен, и отрицательными, если блок занят. Можно сказать и наоборот, важно только потом соблюдать это соглашение (Рисунок 4.7).
Представим, что мы освобождаем блок с адресом addr. Считаем, что addr имеет тип word *, и при добавлении к нему целых чисел результирующий адрес будет отсчитываться в словах, как в языке С. Для того чтобы проверить, свободен ли сосед перед ним, мы должны посмотреть слово с адресом addr 2. Если оно отрицательно, то сосед занят, и мы должны оставить его в покое (Рисунок 4.8). Если же оно положительно, то мы можем легко определить адрес начала этого блока как addr - addr[-2].
Определив адрес начала блока, мы можем легко объединить этот блок с блоком addr, нам нужно только сложить значения меток-дескрипторов и записать их в дескрипторы нового большого блока. Нам даже не нужно будет добавлять освобождаемый блок в список и извлекать оттуда его соседа!
