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

Допустим, что нужно создать универсальную систему обработки Списков, которая будет применяться сотнями программистов. Для обслуживания списка свободной памяти существует два основных метода: счетчиков ссылок {reference counters) и сборки мусора {garbage collection). В методе на основе счетчиков ссылок в каждом поле используется новое поле с числом стрелок, которые указывают на этот узел. Показания такого счетчика легко отслеживать во время выполнения программы; при его обнулении узел можно поместить в список свободной памяти. С другой стороны, для метода сборки мусора требуется дополнительное однобитовое поле на каждом узле под названием маркировочный бит {mark bit). Основная идея в этом случае заключается в следующем: необходимо определить почти все алгоритмы так, чтобы они не возвращали неиспользуемые узлы в список свободной памяти сразу же. Пусть программа спокойно выполняется до тех пор, пока не будет израсходовано все свободное пространство в памяти. После этого специальный алгоритм "регенерации памяти" использует маркировочные биты для определения неиспользуемых в данный момент узлов и их возврата в список свободной памяти, после чего программа сможет продолжить свою работу.

Ни один из этих двух методов не является удовлетворительным. Основным недостатком метода счетчиков ссылок заключается в том, что не всегда удается освободить все неиспользуемые узлы. Он прекрасно подходит для перекрывающихся Списков (Списки могут содержать подСписки общего типа), но рекурсивные Списки наподобие L и Л из (4) никогда не буд>т возвращены в список свободной памяти с помощью метода счетчика ссылок. Их счетчики будут всегда ненулевыми (поскольку они ссылаются на самих себя), даже если никакие другие Списки во время работы программы на них не указывают. Более того, для применения метода на основе счетчиков ссылок требуется использовать значительную часть памяти (хотя это пространство иногда все равно не используется из-за размера компьютерного слова).

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

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

нестандартные методы или хранит указатели в необычных местах, то очень велика вероятность того, что сборка мусора будет выполнена неверно. Некоторые самые загадочные происшествия при отладке программ были вызваны тем, что сборка мусора возникала неожиданно во время работы программ, которые раньше работали вполне благополучно. Для корректной сборки мусора часто требуется, чтобы программисты сохраняли во всех полях указателей только значащую информацию, хотя часто бывает удобно оставлять нетронутой бессмысленную информацию в полях, которые не используются программой (например, связь в последнем узле очереди; см. упр. 2.2.3-6).

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

Дж. Вейзенбаум (J. Weizenbaum) предложил интересную модификацию метода на основе счетчика ссылок. Используя дважды связанные Списки, он разместил счетчик только в заголовке каждого Списка. Таким образом, при перемещении по Списку указательные переменные не включаются в счетчики ссылок для отдельных узлов. Если известны правила, по которым поддерживаются счетчики ссылок для полных Списков, то теоретически известно, как избежать ссылок на любые Списки, счетчики ссылок которых равны нулю. Кроме того, можно явным образом сбросить счетчики циклов и возвратить отдельные Списки в область свободной памяти. При использовании этих идей следует соблюдать осторожность, поскольку в руках неопытных программистов они могут представлять опасность, а отладка программ заметно усложнится из-за наличия ссылок на уже удаленные узлы. Самой замечательной частью метода Вейзенбаума является способ работы со Списком, счетчик ссылок которого только что стал нулевым. Такой Список добавляется в конце текущего списка свободной памяти (например, для дважды связанного списка это можно очень просто сделать) и рассматривается как свободная память в последнюю очередь, только если использованы все предыдущие свободные ячейки памяти. В конечном счете, как только отдельные узлы Списка становятся свободными, значения счетчиков ссылок Списков, на которые они ссылаются, уменьшаются на один. Такое отложенное удаление Списков очень эффективно с точки зрения времени выполнения. Но при этом может возникнуть ситуация, когда некорректные программы какое-то время будут работать вполне корректно! Более подробное описание этого метода можно найти в САСМ 6 (1963), 524-544.

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

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

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

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

Приведенный ниже алгоритм маркировки, вероятно, является наиболее очевидным.

Алгоритм А (Маркировка). Пусть вся используемая для Списка область памяти содержится в узлах NODE(l), N0DE(2), NODE(M). Предположим, что эти слова памяти являются либо атомами, либо полями связи ALINK и BLINK. Допустим, что все узлы в исходном состоянии не маркированы. Цель этого алгоритма заключается в маркировке всех узлов, к которым можно добраться с помощью цепочки указателей ALINK и/или BLINK в не являющихся атомами узлах, начиная с множества "непосредственно доступных" узлов, т. е. узлов, указатели на которые находятся в фиксированных ячейках памяти в основной программе. Эти фиксированные указатели используются в качестве отправной точки для доступа ко всем остальным данным.

Al. [Инициализация.] Пометить все "непосредственно доступные" узлы. Установить К 1,

А2. [Следует ли за узлом NODE(K) другой узел?] Установить К1 <- К -f 1, Если NODE(K) - атом или немаркированный узел, перейти к шагу A3. В противном случае, если узел NODE(ALINK(К)) немаркированный, маркировать его и, если он не атом, установить К1 <- min(Kl,ALINK(K)). Аналогично, если NODE (BLINK (К)) не маркирован, маркировать его и, если он не атом, установить К1 min(Kl,BLINK(K)).

A3. [Готово?] Установить К <- К1. Если К < М, вернуться к шагу А2; в противном случае выполнение алгоритма прекращается.

В этом и других алгоритмах настоящего раздела для удобства предполагается, что несуществующий узел NODE(А) является маркированным. (Например, ALINK(K) и BLINK (К) .могут быть равны Л на шаге А2.)

В одном из вариантов алгоритма А можно было бы установить К1 <- М -f- 1 на шаге А1, удалить операцию "К1 <- К 4- 1" на шаге А2, а шаг A3 использовать в следующей формулировке.

A3. [Готово?] Установить К К-1-1. Если К < М, вернуться к шагу А2. В противном случае, если К1 < М, установить К<- К1иК1М-ь1и вернуться к шагу А2. Иначе - прекратить выполнение алгоритма.

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