Если список AVAIL не упорядочен, нетрудно понять, что попытка слияния блоков списка "в лоб" приведет к просмотру всего списка AVAIL; алгоритм В в среднем уменьшает этот поиск д% примерно половины списка AVAIL (на шаге В2). В упр. 11 показано, каким образом можно модифицировать алгоритм В, чтобы в среднем потребовалось просмотреть около одной трети списка AVAIL. Но ясно, что, когда список AVAIL длинный, все эти методы работают существенно медленнее, чем хотелось бы. Нет ли еще какого-либо способа выделения и освобождения памяти, при котором не требовался бы столь пространный поиск в списке AVAIL?

Рассмотрим метод, который позволяет устранить любой поиск при освобождении памяти и может быть модифицирован (см. упр. 6) для резкого сокращения времени поиска при выделении памяти. В этой технологии используется поле TAG в начале и в конце блока, а также поле SIZE в первом слове каждого блока. Такие накладные расходы не столь значительны при использовании больших блоков памяти, хотя, возможно, цена окажется слишком большой при наличии множества блоков очень малого среднего размера. Другой метод, описанный в упр. 19, требует только одного бита в первом слове каждого блока. Ценой этой экономии является несколько большее время работы и усложнение программы*.

Как бы там ни было, положим, что нет возражений против добавления некоторого количества битов управляющей информации для сохранения высокой скорости работы по сравнению с алгоритмом В при длинном списке AVAIL. В описываемом методе предполагается, что каждый блок имеет следующий вид.

Выделенный блок (TAG = "-)-")

Свободный блок (TAG = "-")

Первое слово Второе слово

SIZE-2 слова

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

Двойное связывание достигается обычным путем: LINK в первом слове указывает на следующий доступный блок в списке, а LINK во втором слове указьшает на предыдущий доступный блок. Таким образо.м, если Р - адрес блока, то

LINK(LINK(P) + !)=? = LINK(LINK(P-)- 1)).

* Этот принцип положен, в частности, в основу управления памятью в MS DOS, где каждый блок памяти (МСВ - Memory Control Block) имеет поля размера, владельца и типа блока. Менеджер памяти, основанный на списке блоков, использовался, например, в Turbo Pascal.- Прим. перев.

Для корректности "граничных условий" заголовок списка устанавливается следующим образом.

LOC(AVAIL) : LOC (AVAIL)-f-l:

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

Алгоритм С {Освобождение с дескрипторами границ) Предположим, что блоки памяти выглядят так, как в (7), а список AVAIL имеет две связи, как описывалось выше. Данный алгоритм помещает блок памяти с начальным адресом РО в список AVAIL. Если пул доступной памяти располагается от адреса то до mi включительно, в алгоритме для удобства предполагается, что

TAG(mo - 1) = TAG(mi -)-1) = "-h".

Cl. [Проверка нижней границы.] Если TAG(PO - 1) = "4-", перейти к шагу СЗ.

С2. [Удаление нижней области.] Установить Р (- РО - SIZE(PO - 1), а затем установить Р1 LINK(P), Р2 +- LINK(P-l-l), LINK(Pl-l-l) +- Р2, LINK(P2) Ч- PI, SIZE(P) +- SIZE(P)+ SIZE(PO), РО +- P.

СЗ. [Проверка верхней границы.] Установить P<-PO+SIZE(PO). Если TAG(P) ="-)-", перейти к шагу С5.

С4. [Удаление верхней границы.] Установить Р1 (- LINK(P), Р2 LINK(P-)-l), LINK(PH-l) Р2, LINK(P2) PI, SIZE(PO) SIZE(PO) + SIZE(P), P <- P -I-SIZE(P).

C5. [Добавление в список AVAIL.] Установить SIZE(P - 1) SIZE(PO), LINK(PO) +-AVAIL, LINK (PO-HI) <- LOC(AVAIL), LINK (AVAIL+1) PO, AVAIL PO, TAG(PO) TAG(P-1) "-". I

Шаги алгоритма С определяются видом блоков памяти (7); немного более длинный, но одновременно более быстрый алгоритм можно найти в упр. 15. На шаге С5 AVAIL означает аббревиатуру для LINK(LOC(AVAIL)), как показано в (9).

С. "Система двойников". Изучим теперь другой подход к динамическому выделению памяти для использования на двоичных компьютерах. В этом методе применяется по одному дополнительному биту на каждый блок; кроме того, все блоки должны иметь длину 1, 2, 4, 8, 16 и т. д. Если длина блока не равна 2* слов для некоторого целого к, выбирается следующая более высокая степень 2 и часть выделенной памяти при этом не используется.

Суть этого .метода заключается в организации отдельных списков доступных блоков каждого размера 2*, О < к < т. Весь пул распределяемого пространства памяти состоит из 2™ слов, адреса которых, предположим, находятся в диапазоне от О до 2™ - 1. Изначально весь блок из 2™ слов свободен. Позже, при требовании блока из 2* слов и отсутствии свободного блока такого размера больший доступный блок разбивается {split) на две равные части; в конечном итоге появится блок

ДВОЙНИКц, (ж) =

необходимого размера 2*. Когда один блОк разделяется на два (каждый половинного размера по сравнению с исходным), эти блоки называются двойниками {buddies*). Позже, когда оба двойника вновь становятся свободны, они объединяются в один большой блок. Таким образом, процесс выделения и освобождения Может осуществляться бесконечно, если только в какой-то момент вся доступная память не окажется занятой.

Ключевой факт, лежащий в основе практической ценности этого метода, состоит в том, чтЬ если известен адрес блока (адрес первого слова в блоке) и его размер, то известен и адрес его двойника. Например, двойником блока размером 16 с двоичным адресом 101110010110000 является блок с двоичным адресом 101110010100000. Для того чтобы понять, почему это так, сначала заметим, что во время работы алгоритма адрес блока размером 2 кратен 2*. Другими словами, адрес в двоичной записи содержит справа как минимум к нулей. Данное наблюдение легко выводится по индукции: если это верно для всех блоков размером 2*+, то это, несомненно, справедливо и при делении блока пополам.

Значит, блок размером, скажем, 32 имеет адрес вида жлс... лсООООО (где иксы представляют собой О или 1); при разделении блока вновь образуемые блоки-двойники имеют адреса хх... а;00000 к хх... лсЮООО. В общем, пусть

двойниК((а;)

обозначает адрес двойника блока размером 2*, адрес которого равен х. Тогда находим, что

ж+ 2*, если а; mod 2*+ = 0; /,„-,

,х-2\ eaiHa;mod2+i =2

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

Система двойников использует однобитовое поле TAG в каждом блоке:

ТАО(Р) = О, если блок с адресом Р выделен;

TAG(P) = 1, если блок с адресом Р свободен.

Кроме поля TAG, имеющегося в каждом блоке, в свободных блоках есть два поля связи, LINKF и LINKB, которые представляют обычные связи вперед и назад в дву-связном списке; также имеется поле KVAL, определяющее к для блока размером 2*. В приведенном ниже алгоритме используются ячейки таблицы AVAIL [0], AVAIL [1], ..., AVAIL tm], которые служат соответственно в качестве заголовков списков свободной памяти размером 1, 2, 4, ..., 2™. Это списки с двойными связями, так что, как обычно, заголовок списка содержит два указателя (см. раздел 2,2.5):

AVAILF[fc] = LINKF (LOC (AVAIL [ifc])) = связь с окончанием списка AVAIL [fc]; , AVAILB Ш = LINKB (LOC (AVAIL [A;])) = связь с началом списка AVAIL [kl.

Изначально перед выделением памяти мы имеем

AVAILF[m] = AVAILB [m] = О, LINKF(O) = LINKB(O) = LOC (AVAIL [m]), (13)

TAG(O) = 1, KVAL(O) = m

* Дословный перевод слова buddy-дружище, приятель. Прим. перев.