AOP_Tom1 (1021736), страница 119
Текст из файла (страница 119)
С5. ]Выметание мусора.] Если К1 > М, прекратить выполнение алгоритма, (Переменная К1 представляет наименьший адрес, по которому можно снова выйти на узел, подлежащий маркировке.) В противном случае, если МОРЕ(К1) — атом или немаркированный узел, увеличить К1 на 1 и повторить этот шаг. Если МОРЕ(К1) маркирован, то установить К г- К1, увеличить К1 на 1 и перейти к шагу С4. $ Этот алгоритьч и алгоритм В можно усовершенствовать, если не вносить Х в стек, когда МОРЕ(Х) — атом.
Более того, на шагах В4 и С4 не гледует помещать в стек элементы, которые сразу же будут удалены. Такие модификации достаточно просто выполняются, но они не использовались здесь, чтобы избежать усложнения алгоритлгов. Алгорятлг С эквивалентен алгоритму А, когда Н = 1, а также алгоритму В, когда Н = Н.
Чем больше значение Н, тем выше его эффективность. К сожалению, алгоритм С не поддается точному анализу по той же причине, что и алгоритлг А. Поэтому не ясно, прн каком значении Н этот метод может быть оценен как достаточно быстрый. Можно считать значение Н = 50 довольно правдоподобным, но не очень надежным критерием применяемости алгоритма С для сборки мусора в большинстве приложений. В алгоритмах В и С стек располагается в последовательных ячейках памяти, но, как было показано выше в этой главе, методы связанного распределения памяти прекрасно подходят для организации стеков, которые располагаются в памяти непоследовательно.
Таким образом, подразумеваетсн, что стек в алгоритме В может располагаться в той оюе области памяти, в которой происходит сборка мусора. Это довольно легко можно сделать, если предоставить программе сборки мусора немного больше пространства в памяти. Предположим, например, что все Списки представлены в виде (9), но поля ВЕР в узлах-заголовках Списков используются как сборщики мусора, а не как счетчики ссылок. Тогда алгоритм В можно перестроить, чтобы стек был организован с помощью полей НЕР в узлах-заголовках. Алгоритм О (Маркировка).
Этот алгоритм приводит к тому же результату, что и алгоритмы А, В и С, но предполагается, что в узлах вместо полей А51МК и В51МК содержатся описанные выше поля Я, Т, ВЕР и Н51МК. Поле Я используется как маркировочный бит таким образом, что Я(Р) = 1 означает, что узел МОРЕ(Р) маркирован. А)1. (РХницналнзация.] Установить ТОР < — Л. Затем для каждого указателя Р на заголовок непосредственно доступного Списка (см. шаг А1 алгоритма А), егли Я(Р) = О, установить Я(Р) +- 1, НЕР(Р) +- ТОР, ТОР < — Р. 1)2.
[Стек пуст?] Если ТОР = Л, прекратить выполнение алгоритма. 1)З. (Удаление верхнего элемента.] Установить Р < — ТОР. ТОР г — НЕР(Р). 1)4, [Перемещение по Списку.] Установить Р +- ВЬ1МК(Р); затем, если Р = Л или Т(Р) = О, перейти к шагу 02. В противном случае установить В(Р) е — 1. Если Т(Р) ) 1, установить $(ВЕР(Р)) +- 1 (маркируя таким образом узел-атом), В противном случае (Т(Р) = 1); установить Ц + — ВЕР(Р); если Ц ф Л и В(Ц) = О, установить Я(Ц) е- 1., КЕР(Ц) +- ТОР, ТОР ~- Ц.
Повторить шаг 1)4. ! Алгоритм 0 можно сравнить с очень похожим на него алгоритмом В, время выполнения которого также прямо пропорционально количеству маркированных узлов. Однако алгоритм В не рекомендуется использовать без дополнительных оговорок, поскольку его, казалось бы, незначительные ограничения часто оказываются очень строгими для универсальных систем обработки, Списков.
В данном алгоритме требуется, чтобы все Списки были правильно организованы, например, как в (7), когда бы нс начинался процесс сборки мусора. Но алгоритмы обработки Списков на какое-то малое время всегда искажают структуру Списков, и в такие моменты сборка мусора согласно алгоритму П должна быть приостановлена. Более того, следует внимательно выполнять действия на шаге 1)1, особенно тогда, когда в программе содержатся указатели на середину Списка. Эти рассуждения приводят нас к алгоритму Е (рис. 38), который представляет собой элегантный метод маркировки, независимо открытый Л.
П. Дойчсм (Ь. Р. Г)епгвсЪ), Г. ЬПорром (НегЪегс ЯсЪогг) и В, М. Вэйтом (1Ъ'. М. майе) в 1965 году. Используемые в нем предположения немного отличаются от тех, которые приняты в алгоритмах А — 1). После вшик После АЫХХ Рис. 38. Схема алгоритма Е для маркировки без использования вспомогательного про- странства стека. Алгоритм Е (Маркировка).
Предположим, что дано множество узлов, содержащих следующие поля: ИАНК (однобитовое поле), АТОМ (однобитовос поле), А1.1МК (указательное поле), В1.1МК (указательное поле). Если АТОМ = О, то поля АЬ1МК и ВЬХМК могут содержать Л или указатель на другой узел в таком же формате; сели АТОМ = 1, то содержание полей АЬ1МК и ВЬ1МК не будет иметь никакого значения для этого алгоритма. Для заданного ненулевого указателя РО данный алгоритм устанавливает по- ле МАКК равным 1 в узле МОВЕ(РО) и во всех других узлах, до которых можно добраться от узла МОВЕ(РО) по цепочке указателей АЬ1МК и ВЬ1МК в узлах, где АТОМ = МАКК = О.
В этом алгоритме используются три указательные переменные: Т, Ц и Р. Он модифицирует связи и контрольные биты таким образом, что после завершения работы алгоритма во всех полях АТОМ, АЕ1МК и ВЕ1МК восстанавливаются их исходные значения, хотя во время выполнения алгоритма они могут временно принимать другие значения.
Е1. [Инициализация.] Установить Т < — Л, Р < — РО. (В остальмой части этою алюритма переменная Т имеет двойственное значение. Если Т Ф Л, она указывает на верхний элемент того, что, по сути, является стеком в алгоритме Р, иначе узел, на который указывает Т, ранее содержал связь, равную Р, вместо "искусственной" связи стека, и теперь находящуюся в МОВЕ(Т).) Е2.[Маркировка.] Установить ИАНК(Р) < — 1. ЕЗ. [Атому] Если АТОИ(Р) = 1, то перейти к шагу Еб. Е4.
[Вниз по связям А1.1МК.] Установить Ц, АЫМК(Р). Если Ц ф Л и МАНКОЦ) = О, установить АТОИ(Р) е — 1, АЕ1МК(Р) с — Т, Т < — Р, Р +- Ц и перейти к шагу Е2. (Здесь поле АТОИ и поля АЫМК временно изменяются таким образом, что структура Списка в некоторых маркированных узлах существенно меняется. Но иа шаге Еб все будет восстановлено.) Е5. [Вниз по связям ВЕ1МК.] Установить Ц ь — ВЕ1МК(Р). Если Ц ф Л и ИАНК(Ц) = О, то установить ВЕ1МК(Р) +- Т, Т +- Р, Р +- Ц и перейти к шагу Е2.
Еб. [Вверх.] (На этом шаге отменяются переключения связей, выполненных ма шаге Е4 или Е5; значение поля АТОИ(Т) указывает, какую из связей (АЕ1МК(Т) или ВЕТМК(Т)) следует восстановить.) Если Т = Л, выполмемие алгоритма прекращается. В противном случае необходимо установить Ц +- Т, Если АТОИ(Ц) = 1, то установить АТОМ(Ц) +- О, Т <†АЕ1МК(Ц), АЕ1МК(Ц) <- Р, Р +- Ц и вернуться к шагу Е5. Если АТОМ(Ц) = О, то установить Т ( — В1.1МК(Ц), ВЕ1МК(Ц) +- Р, Р ( — Ц и повторить шаг Еб. Пример использования этого алюритма приведен на рис.
39, на котором показаны последовательные шаги работы со структурой простого Списка. Читателю будет полезно тщательно изучить алгоритм Е. При этом следует обратить внимание ма то, как искусственно меняется структура связей ма шагах Е4 и Е5, чтобы организовать работу аналогично работе стека в алгоритме Р. При возвращении в предыдущее состоямие поле АТОМ используется для указания того, какая из связей (АЕ1МК или В1.1МК) содержит искусственную связь. "Вложения", показанные в нижней части рис.
39, демонстрируют, как каждый меатомный узел трижды посещается во время выполнения алгоритма Е. При этом одна и та же конфигурация (Т,Р) встречается в начале шагов Е2, Р5 и Еб. Доказательство корректности алгоритма Е можно сформулировать с помощью метода индукции по количеству узлов, которые необходимо маркировать. Попутно докажем, что в конце этого алгоритма переменной Р возвращается ее исходное значение — РО (см. упр. 3).
Алгоритм Е будет работать быстрее, если удалить шаг ЕЗ и проверить условие "АТОМ(Ц) = 1" с выполнемием соответствующих действий на шагах Е4 и Е5, а также проверить условие "АТОМ(РО) = 1" на шаге Е1. Этот алгоритм представлен именно в таком виде для упрощения изложения, а упомянутые выше модификации приведены в упр. 4. Использованную в алгоритме Е идею можно применить не только для решения проблем сборки мусора, но и для обхода деревьев, как в улр, 2.3.1-21. Читателю с[Ц .. е [1] .. [о] [1] Т вЂ” Л а а Л а а с М д д с с а Л Р вЂ” а 6 6 а с с й е е с д й с а Следующий шаг Е1 Е2 Е2 Еб Е5 Е2 Е5 Е2 Е2 Е5 Еб Е5 Еб Еб Еб Вложения Рис.
39. Структура, маркируемая алгоритмом Е. [В таблице показаны только те измене- ния, которые произошли после предыдущего шага.) будет полезно сравнить алгоритм Е с более простой задачей, решение которой приводится в упр. 2.2.3-7. Среди всех рассмотренных выше алгоритмов только алгоритм Р можно непосредственно применять для Списков наподобие [9). В других алгоритмах выполняется проверка, не является ли данный узел Р атомом, а условия [9) не совместимы с такой проверкой, потому что они допускают заполнение данными всего слова целиком, за исключением маркировочного бита, Однако другие алгоритмы можно модифицировать таким образом, что оии смогут нормально функционировать, если данные атома можно будет отличить от указателя в связанном с ним слове, а не просматривать само слово целиком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
