33. Gl. [Очистка полей связей.] Установить Р <- 1 и повторять операции LINK(P) 4- Л и Р 4- Р + SIZE(P) до тех пор, пока не будет выполнено условие Р = AVAIL. (Таким образом поля LINK в первых словах каждого узла устанавливаются равными Л. В большинстве случаев можно считать, что этот шаг не является необходимым, поскольку поле LINK(P) устанавливается равным Л на шаге G9 ниже, а также может быть сброшено распределителем памяти.)

G2. [Инициализация фазы маркировки.] Установить ТОР <- USE, LINK (ТОР) <- AVAIL, LINK (AVAIL) <- Л. (TOP указывает на вершину стека, как в алгоритме 2.3.5D.)

G3. [Поднятие стека.] Установить Р 4- ТОР, ТОР <- LINK(TOP). Если ТОР = Л, перейти к шагу G5.

G4. [Поместить новые связи в стек.] Для 1 < fc < Т(Р) выполнить следующие операции: установить Q <- LINK(P-l-fc); затем, если Q Л и LINK(Q) = Л, установить LINK(Q) 4- ТОР, ТОР <- Q, после чего вернуться к шагу G3.

G5. [Инициализация следующей фазы.] (Теперь Р = AVAIL и фаза маркировки завершена, так что первое слово каждого доступного узла имеет ненулевую связь LINK. Цель наших последующих действий - объединение смежных недоступных узлов для ускорения последующих шагов и назначение новых адресов доступным узлам.) Установить Q <- 1, LINK(AVAIL) <- Q, SIZE(AVAIL) О, Р <- 1. (Ячейка AVAIL используется в качестве ограничителя для указания конца цикла в последующих фазах.)

G6. [Присвоение новых адресов.] Если LINK(P) = Л, перейти к шагу G7. Если условие не соблюдено, то при SIZE(P) = О перейти к шагу G8, иначе - установить LINK(P) <- Q, Q <- Q -t- SIZE(P), Р <- Р -t- SIZE(P) и повторить этот шаг.

G7. [Слияние свободных областей.] Если LINK(Р-t-SIZE(Р)) = Л, увеличить SIZE(P) на SIZE(P + SIZE(P)) и повторить этот шаг. Иначе - установить Р 4- Р -Н SIZE(P) и вернуться к шагу G6.

G8. [Преобразование всех связей,] (Теперь в поле LINK первого слова каждого доступного узла содержится адрес, куда будет перемещен узел.) Установить USE <-LINK (USE) и AVAIL 4- Q. Затем установить Р 4- 1 и повторять следующие операции до тех пор, пока не будет выполнено условие SIZE(P) = 0: если LINK(P) ф Л, установить LINK(Q) <- LINK (LINK (Q)) для всех Q, таких, что Р < Q < Р -t- Т(Р) и LINK(Q) ф Л; затем независимо от значения LINK(P) установить Р 4- Р -t- SIZE(P).

G9. [Перемещение.] Установить Р 1 и повторять следующие операции до тех пор, пока не будет выполнено условие SIZE(P) = 0: установить Q 4- LINK(P) и, если Q Л, установить LINK(P) <- А и NODE(Q) NODE(P); затем независимо от того, справедливо ли условие Q = Л, установить Р <- P--SIZE(P). (Операция NODE(Q) 4- NODE(P) приводит к перемещению SIZE(P) слов; всегда Q < Р, так что перемещение этих слов из меньших адресов в большие безопасно.)

[Этот метод называется "сборщик мусора в LISP 2". Другой интересный метод, не требующий наличия поля LINK в начале узла, может основываться на идее связывания всех указателей на каждый узел. См. Lars-Erik Tliorelli, BIT 16 (1976), 426-441; R. В. К. Dewar and A. P. McCann, Software Practice & Exp. 7 (1977), 95-113; F. Lockwood Morris, CACM 21 (1978), 662-665, 22 (1979), 571; H. B. M. Jonkers, Inf. Proc. Letters 9 (1979), 26-30; J. J. Martin, CACM 25 (1982), 571-581; F. Lockwood Morris, Jnf. Proc. Letters 15 (1982), 139-142, 16 (1983), 215. Другие методы можно найти в работах В К. Haddon and W. М. Waite, Сотр. J. 10 (1967), 162-165; В. Wegbreit, Сотр. J. 15 (1972), 204-208; D. A. Zave, fnf Proc. Letters 3 (1975), 167-169. Коэн (Cohen) и Николау (Nicolau) проанализировали четыре из этих подходов в АСМ Trans. Prog. Languages and Systems 5 (1983), 532-553.]

34. Пусть TOP = гП, Q упрощения щага G4, что

S г12, Р = г13, к = г14, SIZE(P) = rI5. Л = О и LINK(O) ф 0. Шаг 01 опущен.

Положим также для

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

Общее время работы данной программы составляет (44а + 17Ь + 2u) + 25с + 8d + 47) и, где а - количество доступных узлов, b - количество полей связи в них, с - ксхличество недоступных узлов, которым не предшествует недоступный узел, d-количество недоступных узлов, которым предшествует недоступный узел, и w - общее количество слов в доступных узлах. Если в памяти содержится п узлов, и рп из них недоступно, то можно оценить а = (1 - р)п, с = (1 - р)рп, d = рп, например узлы, состоящие в среднем из пяти слов, в среднем с двумя полями связей на узел и памятью на 1000 узлов. Тогда при Р-\ программа требует 374и времени на восстановление одного свободного узла; при р = j время работы составляет 104и, а при Р = f - всего ЗЗи.

36. Посетитель, который пришел один, может сесть на одно из 16 мест - 1, 3, 4, 6, ..., 23. Если приходит пара, для нее должно оставаться свободное место, так как иначе минимум два посетителя будут находиться на местах (1, 2, 3), минимум два - на местах (4,5, 6), ..., минимум два-на местах (19, 20, 21) и минимум один-на месте 22 или 23, так что в этот момент в закусочной будет находиться как минимум 15 человек.

37. Хозяйка усадила первых 16 одиноких мужчин. В результате между занятыми местами есть 17 промежутков, включая промежутки на концах ряда мест (предполагается, что между соседними занятыми местами имеется промежуток нулевой длины). Общее количество пустых мест, т. е. сумма всех семнадцати промежутков, равна 6. Предположим, что имеется X промежутков нечетной длины; тогда к услугам вновь вошедшей пары - 6 - х свободных мест. (Заметьте, что 6-ж четно и > 0.) Теперь каждый посетитель номер 1, 3, 5, 7, 9, 11, 13, 15 слева направо, у которого четны промежутки с обеих сторон, встает и уходит. Каждый нечетный промежуток препятствует уходу не более одного из посетителей, следовательно, уйдут по меньшей мере 8 - ж человек. Остается все еще только 6 - ж мест для того, чтобы посадить вошедшие пары, которых вдруг оказывается (8 - ж)/2.