случае , когда все другие методы возврата неиспользуемых ячеек памяти уже не помогают. Хорошо продуманная система, в которой реализована эта идея и включен механизм отложенных Ъпераций со счетчиками ссылок для достижения повышенной эффективности, предложена Л. П. Дойчем (L. Р. Deutsch) и Д. Г. Бобровым (D. G. Bobrow) [см. САСМ 19 (1976), 522-526].

Кроме того, для Списков можно использовать последовательное представление, которое 1Позволяет сэкономить пространство, занимаемое многими полями связи, за счет более сложного управления памятью. [См. N. Е. Wiseman and J. О. Hiles, Сотр. J. 10 (1968), 338-343; W. J. Hansen, CACM 12 (1969), 499-506; C. J. Cheney, CACM 13 (1970), 677-678.]

Даниэль П. Фридман (Daniel P. Friedman) и Дэвид С. Вайс (David S. Wise) обнаружили, что метод счетчика ссылок можно успешно применять даже в тех случаях, когда Списки указывают на самих себя, если только не учитывать при подсчете ссылок некоторые поля связи [Inf. Proc. Letters 8 (1979), 41-45].

В настоящее время накоплено огромное количество усовершенствованных вариантов алгоритмов сборки мусора. Подробный анализ всей научной литературы на эту тему, опубликованной до 1981 года, вместе с комментариями о дополнительных затратах на операции доступа к памяти при перекачках страниц памяти между оперативной и дисковой памятью можно найти в обзоре Ж. Козна (Jacques Cohen) [Computing Surveys 13 (1981), 341-367].

Описанные здесь методы сборки мусора не совсем подходят для "интерактивных" приложений ("real time" applications), в которых все основные операции работы со Списками должны выполняться очень быстро. Даже если сборка мусора осуществляется не часто, все равно придется затратить довольно большую часть времени вычислений. В упр. 12 рассмотрены некоторые способы реализации метода сборки мусора в интерактивных приложениях.

Печально, что в наи/и дни осталось так мало бесполезной информации.

- ОСКАР УАЙЛЬД (OSCAR WILDE) (1894)

УПРАЖНЕНИЯ

► 1. [Af;8i] В разделе 2.3.4 было показано, что "дерево"-это особый случай "классического" математического понятия "ориентированный граф". Можно ли описать Списки иа основе терминологии теории графов?

2. [20] В разделе 2.3.1 показано, что обход дерева можно упростить, используя прошитое представление дешных внутри компьютера. Можно ли аналогичным образом прошить структуру Списка?

3. [М2б] Докажите корректность алгоритма Е. [Указание. См. доказательство алгоритма 2.3.1Т.]

4. [28] Создайте программу для компьютера MIX, которая реализует алгоритм Е при условии, что узлы представлены одним словом компьютера MIX, причем маркировочный бит HARK находится в поле (0:0) ["+" = О, "-" = 1], узел-атом АТОМ -в поле (1:1), ALINK - в поле (2:3), BLINK - в поле (4:5), а Л = 0. Определите также время выполнения этой программы на основе соответствующих параметров. (При работе с компьютером MIX не так уж просто определить, что содержится в ячейке памяти: -О или -t-O. Поэто.му данная особенность может существенным образом повлиять на вашу программу.)

5. [25] (Задача Шорра и, Вэйта.) Предложите алгоритм маркировки, который представляет собой комбинацию алгоритмов В и Е со следующими свойствами. Остаются в силе допущения алгоритма Е в сгношении полей внутри узлов и т. д. Но вспомогательный стек STACK[1], STACK[2], STACK[N] используется так же, как в алгоритме В, и механизм алгоритма Е применяется только при полном заполнении стека.

6. [00] При осуществлении количественной оценки в конце дсшного раздела сказано, что время выполнения программы сборки мусора приблизительно равно ciN + сгН единицам. На каком основании в эту оценку включен член "сгН"?

7. [24] (Задача Р. В. Флойда (R. W. Floyd).) Создайте алгоритм маркировки, в котором так же, как и в алгоритме Е, не используется вспомогательный стек, за исключением того, что (i) он имеет гораздо более сложное управление, поскольку в каждом узле содержатся поля HARK, ALINK и BLINK, а поля АТОМ, которые помогают упростить управление, в нем отсутствуют; (ii) он имеет более простое управление, так как маркирует только бинарное дерево, а не Список общего типа. В этом случае связи ALINK и BLINK являются обычными связями LLINK и RLINK бинарного дерева.

► 8. [27] (Задача Л. П. Дойча (L. Р. Deutsch).) Создайте алгоритм маркировки, в котором так же, как в алгоритмах D и Е, не используется вспомогательная память для стека. Однако измените этот метод так, чтобы его можно было применять для узлов переменного размера и для переменного количества указателей в следающем формате. В первом слове узла находятся два поля: HARK и SIZE; поле HARK имеет тот же смысл, что и в алгоритме Е, а поле SIZE содержит число п > 0. Это значит, что вслед за первым словом последовательно располагается п слов, каждое из которых содержит поле HARK (которое равно нулю и должно оставаться таким) и поле LINK (которое равно Л или указывает на первое слово другого узла). Например, узел с тремя указателями будет содержать четыре последовательно расположенных слова.

Первое слово HARK = О (будет установлено равным 1) SIZE = 3

Второе слово HARK =: О LINK = первый указатель

Третье слово HARK = О LINK = второй указатель

Четвертое слово HARK = О LINK = третий указатель

Созданный вами алгоритм должен маркировать все узлы, к которым можно добраться из заданного узла РО.

► 9. [28] (Задача Д. Эдвардса (D. Edwards).) Создайте алгоритм для второй фазы сборки мусора, который "упаковывает память" в указанном ниже смысле. Пусть NODE(l), NODE(H) -однословные узлы с полями HARK, АТОН, ALINK и BLINK, как описано в алгоритме Е. Предположим, что MARK = 1 во всех узлах, которые не относятся к мусору. Искомый алгоритм должен таким образом переместить маркированные узлы (в случае необходимости), чтобы они расположились в последовательных ячейках памяти NODE(l), ..., NODE (К). Причем в то же время поля ALINK и BLINK узлов, которые не являются атомами, необходимо изменить так (в случае необходимости), чтобы сохранилась структура Списка.

► 10. [28] Создайте алгоритм для копирования структуры Списка, предполагая, что она имеет внутреннее представление наподобие (7). (Таким образом, при копировании с помощью этого алгоритма Списка, заголовок которого содержится в верхнем левом углу схемы (7), должно получиться новое множество Списков с 14 узлами со структурой и данными, которые идентичны показанным на схеме (7).)

Предположим, что структура Списка хранится в памяти и организована на основе полей S, Т, REF, RLINK так, как на схеме (9), и что NODE(PO) - это заголовок копируемого Списка. Также допустим, что поле REF в заголовке каждого Списка равно А. Чтобы избежать дополнительных расходов памяти, в созданной вами программе копирования

должны использоваться поля REF (после завершения работы программы следует вернуть их исходные значения Л).

11. [МЗО] Любая структура Списка может быть "полностью расширена" до древовидной структуры за счет повторения всех перекрывающихся элементов до тех пор, пока не останется ни одного такого элемента. Например, при расширении рекурсивного Списка таким образом можно получить бесконечное дерево: при расширении Списка (5) получится бесконечное дерево со следующими первыми четырьмя уровнями:

/ \ J

/* д* а* а* о с*

/\ /\ /\ ! ,

h* j* f* д* f* д* d* а* Ь

/А\/\ /\ /\/\/\

Создайте алгоритм для проверки эквивалентности двух структур Списка в том смысле, что древовидные структуры их полного расширения имеют одну и ту же форму. Например, Списки А и В в этом смысле эквивалентны, если

Л = (а: С, 6, а: (6: D));

В = {а: {Ь. С = {Ь: {а D = (а: (6:

D),b,a:E); С));

E=(b: {а: О).

12. [30] (Задача М. Л. Мински (М. L. Minsky).) Покажите, что метод сборки мусора может вполне надежно использоваться в "оперативных" приложениях, например, когда компьютер управляет работой некоторого физического устройства, даже если на максимальное время выполнения каждой операции со Списками накладываются очень строгие ограничения. [Указание. Соблюдая все необходимые в таких случаях предосторожности, можно организовать сборку мусора и операции со Списками в параллельном режиме.]