AOP_Tom1 (1021736), страница 118
Текст из файла (страница 118)
Другая проблема заключается в трудности определения Списков, которые в текущий момент не являются "мусором'. Если программист игоо.н гот какие-то нестандартные методы или хранит указатели в необычных местах, то очень велика вероятность того, что'сборка мусора будет выполнена неверно. Некоторые самые загадочные происшесзрия при отладке программ были вызваны тем, что сборка мусора возникала неожиданно во время работы программ, которые раньше работали вполне благополучно. Для корректной сборки мусора часто требуется, чтобы программисты сохраняли во всех полях указателей только значащую информацию, хотя часто бывает удобно оставлять нетронутой бессмысленную информацию в полях, которые не используются программой (например, связь в последнем узле очереди; см.
упр. 2.2.3-6). Хотя для сборки мусора необходимо выделять по одному маркировочному биту для каждого узла, на самом деле можно было бы для этой же цели использовать отдельную таблицу собранных в другой области памяти маркировочных битов с заданным соответствием между расположением узла и его маркировочным битом. В некоторых компьютерах зта идея сводится к управлению мусорной кучей, что более привлекательно, чем управление отдельными битами в каждом узле.
Дж. Вейзевбаум (Л. %еиепЬапш) предложил интересную модификацию метода на основе счетчика ссылок, Используя дважды связанные Списки, он разместил счетчик только в заголовке каждого Списка. Таким образом, при перемещении по Списку указательные переменные не включаются в счетчики ссылок для отдельных узлов. Если известны правила, по которым поддерживаются счетчики ссылок для полных Списков, то теоретически известно, как избежать ссылок на любые Списки, счетчики ссылок которых равны нулю. Кроме того, можно явным образом сбросить счетчики циклов и возвратить отдельные Списки в область свободной памяти.
При использовании этих идей следует соблюдать осторожность, поскольку в руках неопытных программистов они могут представлять опасность, а отладка программ заметно усложнится из-за наличия ссылок на уже удаленные узлы. Самой замечательной частью метода Вейзенбаума является способ работы со Списком, счетчик ссылок которого только что стал нулевым. Такой Список добавляется в конце текущего списка свободной памяти (например, для дважды связанного списка это можно очень просто сделать) и рассматривается как свободная память в последнюю очередь, только если использованы все предыдущие свободные ячейки памяти. В конечном счете, как только отдельные узлы Списка становятся свободными, значения счетчиков ссылок Списков, на которые оии ссылаются, уменьшаются на один.
Такое отложенное удаление Списков очень эффективно с точки зрения времени выполнения. Но при этом может возникнуть ситуация, когда некорректные программы какое-то время будут работать вполне корректно! Более подробное описание этого метода можно найти в САСМ 6 (1963), 524-544.
Алгоритмы сборки мусора интересны сразу по нескольким причинам. Во-первых, они полезны в некоторых ситуациях, когда требуется пометить все узлы, прямо или косвенно ссылающиеся на данный узел. (Например, можно найти все подпрограммы, которые прямо или косвенно вызываются другой подпрограммой, как в упр. 2.2.3-26.) Сборка мусора обычно состоит из двух фаз. Предположим, что маркировочнме биты всех узлов в исходном состоянии равнь. нулю (или все они инициализируются нулями). Тогда во время первой фазы отметим все узлы, которые не относятся к мусору, начиная с тех, которые непосредственно доступны из основной программы. На второй фазе выполняется последовательный проход всей области пула в памяти компьютера и все непомеченные узлы помещаются в список свободного пространства.
Наиболее интересной является фаза маркировки„поэтому основное внимание будет уделено именно ей. Некоторые варианты второй фазы могут, однако, выглядеть весьма нетривиально (см. упр. 9). При работе алгоритма сборки мусора для управления процессом маркировки доступна только очень ограниченная область памяти. Суть такой интригующей проблемы прояснится при дальнейшем изложении, но именно эту трудность многие не осознают при первом знакомстве с идеей сборки мусора. Причем в течение многих лет так и не было предложено достаточно хорошего решения этой проблемы.
Приведенный ниже алгоритм маркировки, вероятно, является наиболее очевидным. Алгоритм А (Маркировка). Пусть вся используемая для Списка область памяти содержится в узлах МОРЕ(1), МОРЕ(2), ..., МОРЕ(М). Предположим, что эти слова памяти являются либо атомами, либо полями связи АЕ1МК и ВЕ1МК. Допустим, что все узлы в исходном состоянии ие маркировании Цель этою алгоритма заключается в маркировке всех узлов, к которым можно добраться с помощью цепочки указателей АЕ1МК и/или ВЫМК в не являющихся атомами узлах, начиная с множества "непосредственно доступных" узлов, т.
е. узлов, указатели на которые находятся в фиксированных ячейках памяти в основной программе. Эти фиксированные указатели используются в качестве отправной точки для доступа ко всем остальным данным. А1.[Инициализация.] Пометить все "непосредственно доступные" узлы. Установить К ь- 1.
А2. [Следует лн за узлом МОРЕ(К) другой узел?] Установить К1 ь — К+ 1. Если МОРЕ(К) — атом или немаркированный узел, перейти к шагу АЗ, В противном случае, если узел МОРЕ(АЕ1МК(К)) немаркированный, маркировать его и, если он не атом, установить К1 ь- ппп(К1,А1.1МК(К)). Аналогично, если МОРЕ(ВЕХМК(К)) не маркирован, маркировать его и, егли он не атом, установить К1 е — ппп(К1,В1.1МК(К)).
АЗ. [Готово?] Установить К +- К1. Если К < М, вернуться к шагу А2; в противном случае выполнение алгоритма прекращается. Э В этом и других алгоритмах настоящего раздела для удобства предполагается, что несуществуюпшй узел МРОЕ СА) является маркнрованньмс (Например, А1.1МК (К) и ВЕ1МК(К) могут быть равны Л на шаге А2.) В одном из вариантов алгоритма А можно было бы установить К1 э — М+ 1 на шаге А1, удалить операцию "К1 е- К + 1" на шаге А2, а шаг АЗ использовать в следующей формулировке. АЗ'.
[Готово?] Установить К < — к+1. Егли К < М, вернуться к шагу А2. В противном случае, если К1 < М, установить К э — К1 и К1 с — М+ 1 и вернуться к шагу А2. Иначе — прекратить выполнение алгоритма. Довольно трудно выполнить точный анализ алгоритма А или определить, лучше он или хуже только что описанного варианта, поскольку нет обоснованного способа описания распределения вероятностей самих исходных данных.
Можно сказать, что в худшем случае для выролнения этого алгоритма потребуется время, пропорциональное пй, где п — количество маркируемых ячеек. В общем, можно считать, что алгоритм работает очень медленно при больших значениях и. Для сборки мусора алгоритм А работает очень медленно, поэтому он не пригоден в качестве практичного метода решения этой задачи. Другой очевидный алгоритм маркировки заключается в отслеживании всех путей и записи в стек сведений о точках разветвления этих путей. Алгоритм В (Маркировка). Этот алгоритм позволяет получить те же результаты, что и алгоритм А, за счет использования ячеек ЯТАСК[1], ЯТАСК[2], ...
в качестве вспомогательной памяти для хранения сведений обо всех путях, которые еще не были отслежены до конца. В1. [Инициализация.] Пусть Т вЂ” количество непосредственно доступных узлов. Маркировать их и разместить указатели на них в БТАСК[Ц, ..., БТАСК[Т]. В2. [Стек пуст?) Если Т = О, выполнение алгоритма прекращается. ВЗ.
[Удаление верхнего элемента стека.] Установить К ЯТАСК[Т], Т < — Т вЂ” 1. В4. [Проверка связей.! Если ИОВЕ(К) — атом, вернуться к шагу В2. В противном случае, если ИОВЕ(АЕ1ИК(К)) — непомеченный узел, его нужно маркировать и установить Т +- Т+ 1, ЯТАСК[Т] +- АЕ1ИК(К); если НОРЕ(ВЕ1ИК(К) ) — немаркированный узел, то его нужно маркировать и установить Т < — Т + 1, ЯТАСК[Т] <— ВЕ1ИК(К). Вернуться к шагу В2. $ Ясно, что время выполнения алгоритма В прямо пропорционально количеству маркируемых ячеек, причем это оценка наиболее благоприятного случая. На самом деле оказывается, что алгоритм не подходит для сборки мусора, потому что в нем не предусмотрено достаточно места для поддержания стека! Вполне разумно было бы предположить, что стек в алгоритме В может возрасти, например, до размера, равного 5% всего объема памяти. Но дело в том, что в процессе сборки мусора все свободное пространство уже израсходовано и остается только фиксированное (очень небольшое) количество ячеек, которые можно использовать в качестве такого стека.
Вбльшая часть ранних программ сборки мусора основывалась на этом алгоритме, и при полном исчерпании специального используемого для стека пространства работа всей программы прекращалась. Несколько лучший вариант основан на комбинации алгоритмов А и В с использованием стека фиксированного размера. Алгоритм С (Маркировка). Этот алгоритм позволяет получить такой же результат, как и алгоритмы А и В, с помощью вспомогательной таблицы, состоящей из Н ячеек, БТАСК[О], БТАСКШ, ..., ЯТАСК[Н вЂ” 1]. В данном алгоритме действие 'Вставить Х в стек" означает следующее: "Установить Т е — (Т+1) глоб Н и БТАСК [Т] +- Х. Если Т = В, то установить В < — (В+1) шос) Н и К1 е — гшп(К1, БТАСК [В])". (Обратите внимание на то, что Т указывает на текущий верхний элемент стека, а  — на одну позицию ниже текущего нижнего элемента стека. Таким образом, БТАСК функционирует, как дек с ограниченным входом.) С1.
[Инициализация.] Установить Т < — Н вЂ” 1, В < — Н вЂ” 1, К1 < — Н + 1. Маркировать все непосредственно доступные узлы и последовательно внести их адреса в стек (как описано выше). С2. (Стек пуст?] Если Т = В перейти к шагу С5. СЗ. (Удаление верхнего элемента.] Установить К+- ЯТАСК(Т], Т (Т вЂ” 1) шоб Н. С4. ]Проверка связей.] Если МОРЕ(К) — атом, вернуться к шагу С2. В противном случае, если МОРЕ(А11МК(К)) не маркирован, маркировать его и вставить АЕ1МК(К) в стек. Аналогично, если МОРЕ(ВЕ1МК(К)) не маркирован, маркировать его и вставить ВР1МК(К) в стек. Вернуться к шагу С2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
