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

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

Алгоритм В {Маркировка). Этот алгоритм позволяет получить те же результаты, что и алгоритм А, за счет использования ячеек STACK[1], STACK[2], ... в качестве вспомогательной памяти для хранения сведений обо всех путях, которые еще не были отслежены до конца.

81. [Инициализация.] Пусть Т - количество непосредственно доступных узлов. Маркировать их и разместить указатели на них в STACK [1], ..., STACK [Т].

82. [Стек пуст?] Если Т = О, выполнение алгоритма прекращается.

83. [Удаление верхнего элемента стека.] Установить К <- STACK [Т], Т Т - 1.

84. [Проверка связей.] Если NODE(K)-атом, вернуться к шагу В2. В противном случае, если NODE (ALINK (К))-непомеченный узел, его нужно маркировать и установить Т Т + 1, STACK[T] <г- ALINK(K); если NODE(BLINK(K))-немаркированный узел, то его нужно маркировать и установить Т Т -f-1, STACK [Т] +-BLINK (К). Вернуться к шагу В2.

Ясно, что время выполнения алгоритма В прямо пропорционально количеству маркируемых ячеек, причем это оценка наиболее благоприятного случая. На самом деле оказывается, что алгоритм не подходит для сборки .мусора, потому что в нем не предусмотрено достаточно места для поддержания стека! Вполне разумно было бы предположить, что стек в алгоритме В может возрасти, например, до размера, равного 5% всего объема памяти. Но дело в том, что в процессе сборки мусора все свободное пространство уже израсходовано и остается только фиксированное (очень небольшое) количество ячеек, которые можно использовать в качестве такого стека. Большая часть ранних программ сборки мусора основывалась на этом алгоритме, и при полном исчерпании специального используемого для стека пространства работа всей программы прекращалась.

Несколько лучший вариант основан на комбинации алгоритмов А и В с использованием стека фиксированного размера.

Алгоритм С (Маркировка). Этот алгоритм позволяет получить такой же результат, как и алгоритмы А и В, с по.мощью вспомогательной таблицы, состоящей из Н ячеек, STACK[0], STACK [1], ..., STACK[Н - 1].

В данном алгоритме действие "Вставить X в стек" означает следующее: "Установить Т (T-f-1) mod Н и STACK [Т] <-X. Если Т = В, то установить В <-(B-Hl) mod Н и К1 min(Kl,STACK[B])". (Обратите внимание на то, что Т указывает на текущий верхний элемент стека, а В - на одну позицию ниже текущего нижнего элемента стека. Таким образом, STACK функционирует, как дек с ограниченным входом.)

Cl. [Инициализация.] Установить Tf-H-l, Bf-H-l, Klf-M-f-l. Маркировать все непосредственно доступные узлы и последовательно внести их адреса в стек (как описано выше).

С2. [Стек пуст?] Если Т = В перейти к шагу С5.

СЗ. [Удаление верхнего элемента.] Установить К STACK [Т], Т (Т - 1) mod Н.

С4. [Проверка связей.] Если NODE(K)-атом, вернуться к шагу С2. В противном случае, если NODE(ALINK(K)) не маркирован, маркировать его и вставить ALINK(К) в стек. Аналогично, если NODE(BLINK(К)) не маркирован, маркировать его и вставить BLINK (К) в стек. Вернуться к шагу С2.

С5. [Выметание мусора.] Если К1 > М, прекратить выполнение алгоритма. (Переменная К1 представляет наименьший адрес, по которому можно снова выйти на узел, подлежащий маркировке.) В противном случае, если NODE(Kl) -атом или немаркированный узел, увеличить К1 на 1 и повторить этот шаг. Если NODE(Kl) маркирован, то установить К <- К1, увеличить К1 на 1 и перейти к шагу С4. I

Этот алгоритм и алгоритм В можно усовершенствовать, если не вносить X в стек, когда NODE(X)-атом. Более того, на шагах В4 и С4 не следует помещать в стек элементы, которые сразу же будут удалены. Такие модификации достаточно просто выполняются, но они не использовались здесь, чтобы избежать усложнения алгоритмов.

Алгоритм С эквивалентен алгоритму А, когда Н = 1, а также алгоритму В, когда Н = М. Чем больше значение Н, тем выше его эффективность. К сожалению, алгоритм С не поддается точному анализу по той же причине, что и алгоритм А. Поэтому не ясно, при каком значении Н этот .метод может быть оценен как достаточно быстрый. Можно считать значение Н = 50 довольно правдоподобным, но не очень надежным критерием применяемости алгоритма С для сборки мусора в большинстве приложений.

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

Алгоритм D {Маркировка). Этот алгоритм приводит к тому же результату, что и алгоритмы А, В и С, но предполагается, что в узлах вместо полей ALINK и BLINK содержатся описанные выше поля S, Т, REF и RLINK. Поле S используется как маркировочный бит таким образом, что S(P) = 1 означает, что узел NODE(P) маркирован.

D1. [Инициализация.] Установить ТОР <г- Л. Затем для каждого указателя Р на заголовок непосредственно доступного Списка (см. шаг А1 алгоритма А), если S(P) = О, установить S(P) <г- 1, REF(P) <- ТОР, ТОР <- Р.

D2. [Стек пуст?] Если ТОР = Л, прекратить выполнение алгорит.ма.

D3. [Удаление верхнего элемента.] Установить Р <г- ТОР, ТОР REF(P).

D4. [Перемещение по Списку.] Установить Р <- RLINK(P); затем, если Р = Л или Т(Р) = О, перейти к шагу D2. В противном случае установить S(P) <г- 1. Если Т(Р) > 1, установить S(REF(P)) <- 1 (маркируя таким образом узел-атом). В противном случае (Т(Р) = 1); установить Q <г- REF(P); если Q 7 Л и 5(0) = О, установить 5(0) <г- 1, REF(Q) <г- ТОР, ТОР <г- Q. Повторить шаг D4.

Алгоритм D можно сравнить с очень похожим на него алгоритмом В, время вьтолнения которого также прямо пропорционально количеству маркированных узлов. Однако алгоритм D не рекомендуется использовать без дополнительных оговорок, поскольку его, казалось бы, незначительные ограничения часто оказываются очень строгими для универсальных систем обработки.Списков. В данном алгоритме требуется, чтобы все Списки были правильно организованы, например, как в (7), когда бы не начинался процесс сборки мусора. Но алгоритмы обработки Списков на какое-то малое время всегда искажают структуру Списков, и в такие моменты сборка мусора согласно алгоритму D должна быть приостановлена. Более того, следует внимательно выполнять действия на шаге D1, особенно тогда, когда в программе содержатся указатели на середину Списка.

Эти рассуждения приводят нас к алгоритму Е (рис. 38), который представляет собой элегантный метод маркировки, независимо открытый Л. П. Дойчем (L. Р. Deutsch), Г. Шорром (Herbert Schorr) и В. М. Вэйтом (W. М. Waite) в 1965 году. Используемые в нем предположения немного отличаются от тех, которые приняты в алгоритмах A-D.

После ALINK

После BLINK

Рис. 38. Схема алгоритма Е для маркировки без использования вспомогательного пространства стека.

Алгоритм Е (Маркировка). Предположим, что дано множество узлов, содержащих следующие поля;

MARK (однобитовое поле), АТОМ (однобитовое поле), ALINK (указательное поле), BLINK (указательное поле).

Если АТОМ = О, то поля ALINK и BLINK могут содержать А или указатель на другой узел в таком же формате; если АТОМ = 1, то содержание полей ALINK и BLINK не будет иметь никакого значения для этого алгоритма.

Для заданного ненулевого указателя РО данный алгоритм устанавливает поле MARK равным 1 в узле NODE(PO) и во всех других узлах, до которых можно добраться от узла NODE(PO) по цепочке указателей ALINK и BLINK в узлах, где АТОМ = MARK = 0. В этом алгоритме используются три указательные переменные: