Данный алгоритм, определенно, несколько прямолинеен. Однако всего лишь небольшое изменение стратегии может существенно повысить скорость его работы. Это весьма важное улучшение алгоритма, и читатель получит удовольствие, выполнив его поиск самостоятельно (см. упр. 6).

Алгоритм А может использоваться как для больших, так и для малых значений N. Временно предположим, однако, что нас интересуют, в первую очередь, большие значения N. Рассмотрим, что случится, если в алгоритме SIZE(P) равно N -f-1: перейдем к шагу А4 и уменьшим SIZE(P) до 1. Другими словами, будет создан блок доступной памяти размером 1. Он настолько мал, что практически бесполезен и только засоряет систему. Было бы лучше выделить весь блок размером N -f- 1 слов вместо экономии одного слова; зачастую стоит заплатить несколькими словами памяти за избавление от несущественных деталей. Подобные примечания относятся и к блокам памяти размером N -f- К слов при очень малом К.

Если допустить выделение блоков немного большего размера, чем N слов, придется помнить размер выделенного блока, чтобы при его освобождении корректно вернуть в пул свободной памяти все N-f-K слов. Это увеличивает накладные расходы, ведь придется использовать пространство в каждом блоке для того, чтобы сделать систему более эффективной в тех случаях, когда имеется почти подходящий блок. Так что подобная модифицированная стратегия не кажется очень привлекательной. Однако зачастую использование в начале рсаждого блока переменного размера специального управляющего слова представляется желательным по множеству других причин, так что предположение о том, что в перво.м слове каждого блока, как выделенного, так и свободного, присутствует поле SIZE, вполне разумно.

В соответствии с этими соглашениями можно изменить шаг А4 приведенного выше алгоритма следующим образом.

А4. [Выделение > N.] Установить К SIZE(P) - N. Если К < с (где с - малая положительная константа, зависящая от того, каким количеством памяти мы готовы пожертвовать для ускорения работы), установить LINK(Q) LINK(P) и L P. В противном случае установить SIZE(P) К, L Р-НК, SIZE(L) <- N. Алгоритм успешно завершается, выделив область длиной N илн больше, которая начинается с адреса L.

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

В. Освобождение. Теперь рассмотрим обратную задачу. Каким образом вернуть блоки в список свободного пространства, когда необходимость в них отпадает?

Пожалуй, заманчиво было бы избежать решения данной задачи, используя сборку мусора* (см. раздел 2.3.5). Следуя этой политике, мы просто ничего не делаем до тех пор, пока пространство не окажется заполненным, а затем ищем все используемые в текущий момент области памяти и строим новый список AVAIL.

* Именно этот метод работы с освобождаемой памятью используется, например, в языке Java. - Прим. перев.

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

Есть и еще одна, более важная (хотя и не встречавшаяся до сих пор при обсуждении атого метода) причина, по которой сборка мусора нас не устраивает, Предположим, что имеются две соседние свободные области памяти, но из-за испольэо* вания технологии сборки мусора одна из них (заштрихов?1нная) пока не попала в список AVAIL,

На этой диаграмме черные области памяти слева и справа зарезервированы и недоступны, По запросу можно зарезервировать часть области памяти, о которой известно, что она свободна;

HBZZIZHIEiBiiiiiiiHi

Если в этот момент пройЗбйдет сборка муеора, niMyMatCM две раздельные свободные области памяти:

Границы между свободной и выделенной памятью имеют тенденцию к самовоС производству, и со временем ситуация становится все хуже и хуже. Но если бы использовалась политика немедленного возврата освобожденных блоков памяти в список AVAIL и слиянил смежных свободных блоков, то (2) тут же превратилась бы в

и при выделении памяти получилось бы такое распределение блоков памяти

Kofopoe гораздо лучше, чем (4), Как видите, рассмотренное явление вызывает большее дробление памяти при использовании метода сборки мусора, чем должно быть.

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

* Здесь сяедв! otMSTHtb, что «кой метод применим далеко не ио seex яяыкак программи-poiftMHH. При нерймещений блока памяти должны быть корректно обновлены нсо указатели на

Поскольку многие приложения не соответствуют этим требованиям, выдвигаемым методом сборки мусора, изучим методы возврата блоков памяти в список свободного пространства, Единственная сложность в этих методах заключается в объединении соседних свободных блоков памяти. Так, когда освобождается блок, находящийся между двумя свободными блоками, все три области памяти должны быть слиты в одну. Таким образом достигается хорошее равновесие памяти даже при длительном непрерывном процессе выделения и освобождения областей памяти. (Для доказательства этого факта обратитесь к правилу "50%", приведенному Ниже.)

В данном случае задача заключается в определении, йВЛйётся ли соседняя (с той или другой стороны) область памяти свободной, и если она свободна, то необходимо корректно обновить список AVAIL. Последняя операция несколько сггажнее, чем кажется из ее названия.

Первое решение этой проблемы состоит в содержании списка AVAIL в порядке возрастания адресов памяти.

Алгоритм В {Освобождение в рассортированном списке). В предположениях алгоритма А с дополнительным предположением об упорядоченности списка AVAIL по адресам памяти (т. е. если Р указывает на свободный блок и LINK(P) ф А, то LINK(P) > Р) этот алгоритм добавляет блок из N последовательных ячеек. Начинающийся с адреса РО, в список AVAIL. Естественно, предполагается, что эти N ячеек уже свободны.

81. [Инициализация.] Установить Q <- LOC(AVAIL). (См. примечание к шагу А1.)

82. [Продвижение Р.] Установить Р LINK(Q). Если Р = Л или если Р > РО, перейти к шагу ВЗ; в противном случае установить Q Р и повторить шаг В2.

ЁЗ. [Проверка верхней границы.] Если РО -i- N = Р и Р Л, установить N <-N + SIZE(P) и установить LINK<PO) f- LINK(P). В противном случае установить LINK(PO) <-Р.

В4. [Проверка нижней границы.] Если Q + SIZE(Q) = РО (предполагается, что

SIZE<LOC(AVAIL)) =0,

так что условие всегда не выполняется при Q = LOC(AVAIL)), установить SIZE(q) SIZE(Q) + N и LINK(CI) <- LINK(PO). В противном случае установить LINK(Q) +- РО, SIZE(PO) +- N,

На шагах ВЗ и В4 выполняется требуемое слияние; учитывается тот факт, что указатели Q < РО < Р являются начальными адресами трех последовательных свобод1П>1х блоков.

Этот блок (и внутрь него). Например, в случае Java такой метод может применяться, поскольку в языке отсутствует понятие указателя и реальная адресация блоков памяти переменными может быть отслежена внутренними средствами языка. В то же время в языках наподобие С и Pascal, в которых используются указатели, отследить создание указателя на ту или иную область памяти невозможно, а значит, применение метода ограничено его использованием только в менеджерах памяти Программ, созданных специальным образом с учетом требований такого менеджера (с дополнительными средствами регистрации всех указателей на выделяемые блоки памяти). (Вопросы косвенной адресации и защищенного режима процессоров не упоминаем, так как они не связаны с тематикой книги.) - Прим. персе.