Т, Q и p. Он модифицирует связи и контрольные биты таким образом, что после завершения работы алгоритма во всех полях АТОМ, ALINK и BLINK восстанавливаются их исходные значения,, хотя во время вьшолнения алгоритма они могут временно принимать другие значения.

Е1. [Инициализация.] Установить Т <- Л, Р <- РО. (В остальной части этого алгоритма переменная Т имеет двойственное значение. Если 1 ф к, она ука-зьшает на верхний элемент того, что, по сути, является стеком в алгоритме D, иначе узел, на который указьшает Т, ранее содержал связь, равную Р, вместо "искусственной" связи стека, и теперь находяшуюся в NODE(T).)

Е2. [Маркировка.] Установить MARK(P) <- 1.

ЕЗ. [Атом?] Если АТОМ(Р) = 1, то перейти к шагу Е6.

Е4. [Вниз по связям ALINK.] Установить Q ALINK(Р). Если ф к ш MARK(Q) = О, установить АТОМ(Р) -« 1, ALINK (Р) -е-Т, Т-е-Р, P-e-Qn перейти к шагу Е2. (Здесь поле АТОМ и поля ALINK временно изменяются таким образом, что структура Списка в некоторых маркированных узлах существенно меняется. Но на шаге Е6 все будет восстановлено.)

Е5. [Вниз по связям BLINK.] Установить Q <- BLINK (Р). Если ф ки MARK(Q) = О, то установить BLINK (Р) -е-Т, Т-е-Р, P-e-Qn перейти к шагу Е2.

Е6. [Вверх.] (На этом шаге отменяются переключения связей, выполненных на шаге Е4 или Е5; значение поля АТОМ(Т) указьшает, какую из связей (ALINK(Т) или BLINK(Т)) следует восстановить.) Если Т = А, выполнение алгоритма прекращается. В противном случае необходимо установить Q <- Т. Если ATOM(Q) = 1, то установить ATOM(Q) О, Т ALINK(Q), ALINK(Q) Р, Р Q и вернуться к шагу Е5. Если ATOM(Q) = О, то установить Т BLINK(Q), BLINK(Q) Р, Р Q и повторить шаг Е6.

Пример использования этого алгоритма приведен на рис. 39, на котором показаны последовательные шаги работы со структурой простого Списка. Читателю будет полезно тщательно изучить алгоритм Е. При этом следует обратить внимание на то, как искусственно меняется структура связей на шагах Е4 и Е5, чтобы организовать работу аналогично работе стека в алгоритме D. При возвращении в предыдущее состояние поле АТОМ используется для указания того, какая из связей (ALINK или BLINK) содержит искусственную связь. "Вложения", показанные в нижней части рис. 39, демонстрируют, как каждый неатомный узел трижды посещается во время выполнения алгоритма Е. При этом одна и та же конфигурация (Т,Р) встречается в начале шагов Е2, Е5 и Е6.

Доказательство корректности алгоритма Е можно сформулировать с помощью метода индукции по количеству узлов, которые необходимо маркировать. Попутно докажем, что в конце этого алгоритма переменной Р возвращается ее исходное значение - РО (см. упр. 3). Алгоритм Е будет работать быстрее, если удалить шаг ЕЗ и проверить условие "ATOM(Q) = 1" с выполнением соответствующих действий на шагах Е4 и Е5, а также проверить условие "АТОМ(РО) = 1" на шаге Е1. Этот алгоритм представлен именно в таком виде для упрощения изложения, а упомянутые выше модификации приведены в упр. 4.

Использованную в алгоритме Е идею можно применить не только для решения проблем сборки мусора, но и для обхода деревьев, как в упр. 2.3.1-21. Читателю

ALINK BLINK ALINK BLINK ALINK BLINK ALINK BLINK ALINK BLINK

[MARK] 6[0]

[ATOM] c[0]

[MARK] -[0]

[ATOM] -[1]

[MARK] 6[0]

[ATOM] d[0]

[MARK] e[0]

[ATOM] d[0]

[MARK] Л[0]

[ATOM] c[0]

T - Л P - a

Л[1] [1]

Следующий шаг El E2 E2 E6 E5 E2 E5 E2 E2 E5 E6 E5 E6 E6 E6 Вложения

Рис. 39. Структура, маркируемая алгоритмом Е. (В таблице показаны только те изменения, которые произошли после предыдущего шага.)

будет полезно сравнить алгоритм Е с более простой задачей, решение которой приводится в упр. 2.2.3-7.

Среди всех рассмотренных выше алгоритмов только алгоритм D можно непосредственно применять для Списков наподобие (9). В других алгорит.мах выполняется проверка, не является ли данный узел Р атомом, а условия (9) не совместимы с такой проверкой, потому что они допускают заполнение данными всего слова целиком, за исключением маркировочного бита. Однако другие алгоритмы можно модифицировать таким образом, что они смогут нормально функционировать, если данные атома .можно будет отличить от указателя в связанном с ним слове, а не просматривать само слово целиком. В алгоритмах А и С можно довольно просто избежать маркировки слов-атомов, пока все слова-не атомы правильно маркированы. Тогда одного прохода по всем данным будет достаточно для маркировки всех слов-атомов. Алгоритм В можно еще проще модифицировать, так как для этого придется всего лишь сохранить слова-атомы вне стека. Почти так же просто можно адаптировать алгоритм Е, хотя, если ALINK и BLINK указывают на данные атомы, потребуется в словах-не атомах ввести другое 1-битовое поле. Обычно это не так

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

Хотя время вьшолнения алгоритма Е прямо пропорционально количеству маркируемых узлов, константа пропорциональности не так мала, как для алгоритма В. Наиболее быстрый метод сборки мусора основан на сочетании алгоритмов В и Е (подробности приводятся в упр. 5).

Попробуем теперь дать количественную оценку эффективности сборки мусора по сравнению с подходом на основе команды "AVAIL <= X", которая использовалась в большинстве предыдущих примеров настоящей главы. В каждом из этих случаев можно было бы опустить все особые упоминания о возврате узлов в свободную область памяти и использовать вместо них сборку мусора. (В специализированных приложениях по сравнению с множеством универсальных программ обработки Списков программирование и отладка программ сборки мусора выполняются гораздо сложнее, чем описанных до сих пор методов, и, конечно, для сборки мусора в каждом узле необходимо выделить дополнительный бит. Но в данном случае нас интересует сравнительная скорость выполнения уже готовых и отлаженных программ.)

Время вьшолнения наилучших программ сборки мусора можно представить в виде CiN + C2M, где Ci и сг-константы, N - количество маркированных узлов, а М - общее количество узлов в памяти. Таким образом, М - N - это количество найденных свободных узлов, а среднее время, необходимое для возврата одного узла в свободную область памяти, равно (ciN + С2М)/(М - N). Пусть N = рК; тогда это выражение принимает вид {cip + С2)/{1 - р). Поэтому, если р = , т. е. если память заполнена на три четверти, для возврата в свободную память одного узла потребуется Зсх + 4с2 единиц времени. А при заполнении р - \ соответствующие затраты времени составят всего ci + с2 единиц времени. Если не использовать метод сборки мусора, то количество времени для возврата одного узла в свободную память будет равно некоторой константе сз, а отношение сз /ci вряд ли будет очень большим. Следовательно, нетрудно сделать вывод о том, насколько неэффективен метод сборки мусора при высокой степени заполнения памяти и соответственно насколько он эффективен при незначительном ее заполнении.

Для многих программ характерно то, что отношение количества маркированных узлов к общему объему памяти р = N/M достаточно мало. Если в таких случаях пул полностью заполняется, то лучше всего, наверное, переместить все активные Списки в другой пул такого же размера, используя упомянутый в упр. 10 метод копирования, но не беспокоясь о сохранении содержимого копируемых узлов. Тогда при заполнении второго пула можно снова переместить данные в первый пул. Благодаря такому методу в оперативной памяти можно одновременно хранить гораздо больше данных, поскольку поля связи указывали бы на соседние узлы. Более того, не потребовалось бы применять фазу маркировки, а распределение памяти было бы просто последовательным.

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