Сбор мусора

Каждый алгоритм сбора мусора выполняется в две стадии:

Маркировка активных элементов (т.е. элементов, являющихся частью доступных, используемых в данный момент структур данных).

Сбор элементов, помеченных как мусор и возврат их в список свободных блоков кучи.

Для реализации алгоритмов сбора мусора необходимо выполнение определенных условий:

¨ Система должна иметь возможность выявить все указатели на элементы кучи, находящиеся вне ее.

Начиная с этих элементов можно организовать процесс маркировки активных элементов, просматривая цепочки ссылок между активными элементами кучи.

¨ Для каждого активного элемента кучи система должна иметь возможность определить все поля внутри него, содержащие указатели на элементы кучи.

Это не всегда просто, так как накладывает дополнительные ограничения на формат элементов, размещаемых в куче (все элементы должны быть либо одного формата, либо иметь фиксированные форматы для представления данных различных типов), чтобы при просмотре кучи система могла выявить поля. содержащие ссылки. Кроме того, указатели нельзя “вычислять” в программе (например, путем добавления смещения к базовому адресу), значения ссылок могут только присваиваться или сравниваться.

¨ На каждый активный элемент кучи должна быть ссылка извне кучи или из другого ее активного элемента.

Наличие какого-либо указателя на элемент кучи не является признаком его доступности для использования (это было показано в примере предыдущего пункта, рис.3.5), то есть не означает, что этот элемент активен. Следовательно признаком активности элемента кучи может быть только его достижимость по цепочке ссылок, начинающейся вне кучи.

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

Маркировка активных элементов кучи выполняется путем обхода всех активных элементов кучи по цепочкам указателей, начинающимся вне кучи.

Сбор элементов, помеченных как мусор, осуществляется через последовательный просмотр всех элементов кучи. При этом все биты сбора мусора активных элементов снова устанавливаются в 1 (в состояние “включен”) для следующего сбора:

if Установлен бит сбора мусора

then Добавить элемент к свободному списку

else Установить бит сбора мусора

Наиболее сложным этапом является маркировка активных элементов, так как этот шаг требует выбора и просмотра доступных элементов по имеющимся ссылкам на них. Перед началом маркировки все биты сбора мусора элементов кучи установлены (предполагается, что все элементы являются мусором и могут быть освобождены).

Существует несколько алгоритмов маркировки, отличающихся объемом накладных расходов на их реализацию.

Один из наиболее простых алгоритмов маркировки основан на использовании временного стека.

Этот алгоритм включает следующие шаги:

¨ Инициализация: поместить в стек все внешние указатели на элементы кучи.

¨ Повторять, пока стек не пуст, следующие действия:

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

Данный алгоритм прост для реализации, но требует выделения памяти для размещения временного стека. Причем, чем больше активных элементов (т.е. чем острее проблема выделения памяти), тем больше места требуется для создания стека.

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

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

Для реализации этого алгоритма требуется использовать всего две фиксированные ячейки памяти (или регистра) для хранения ссылки на текущий выбранный элемент и указателя последнего промаркированного перед ним элемента.

Для описания алгоритма введем следующие обозначения:

· Current - ссылка на текущий элемент;

· Last - ссылка на последний элемент.

Кроме того, в каждый элемент включается дополнительное поле для хранения информации о том, какое поле ссылки в данном элементе использовано для выбора указателя следующего активного элемента кучи. Предположим, что каждый элемент содержит массив ссылочных полей (например, две ссылки на левого и правого потомков в бинарном дереве), тогда для идентификации используемого поля можно запоминать его номер в массиве полей, содержащих указатели. Обозначим Pointers массив указателей в элементе кучи, а Number - номер используемого поля указателя. В это поле при проходе через данный элемент в процессе маркировки заносится вместо выбранной из него ссылки на следующий элемент указатель предшествующего элемента, на который будет выполняться возврат. При возврате из данного элемента на предшествующий в это поле заносится значение 0 (для подготовки к последующим просмотрам).

Поле, в которое записывается маркер (бит сбора мусора), назовем Sign. Через Pointers_Counter обозначим количество полей, содержащих указателина элементы кучи, в каждом ее элементе.

Таким образом, перед началом работы алгоритма в поле Sign бита сбора мусора каждого элемента записано значение 1 (элемент помечен как мусор), а в поле номера выбранного указателя Number - значение 0 (указатели не выбирались, данный элемент еще не просматривался).

Алгоритм может быть описан следующим образом:

{ Выбираем внешние ссылки на структуры данных, размещенных в куче: }

while Есть непустые внешние указатели на немаркированные элементы кучи do

begin { Переход к следующей маркируемой структуре данных в куче: }

Current Внешний непустой указатель на немаркированный элемент;

Last nil; { Предшествующего элемента нет }

{ Маркировка текущего элемента: }

while Current.Sign = 1 { Данный элемент отмечен пока как мусор. }

{ Следовательно, нужно его промаркировать как активный и }

{ просмотреть все его ссылки на другие элементы кучи }

begin { Выбрать новый элемент по ссылке из данного элемента: }

Current.Number Current.Number +1;

while ( Current.Number < Pointers_Counter ) and

( Current.Pointers [ Number ] = nil) do

{ Ищем непустую ссылку на элемент кучи: }

Current.Number Current.Number +1;

if ( Current.Number £ Pointers_Counter )

and ( Current.Pointers [ Current. Number ] ¹ nil)

then { Нашли непустую ссылку - переходим на выбранный }

{ по ней элемент, выполняя циклическую перестановку }

Current ® Last ® Current.Pointers [ Current. Number ]

{ если элемент еще не выбирался при обходе списка: }

begin

P Current.Pointers [ Current. Number ];

if ( P.Sign =1) and ( P.Number = 0) then

{ элемент еще не маркирован и ссылка не циклическая }

begin Current.Pointers [ Current. Number ] Last;

Last Current; Current P;

end;

end

else { Непройденных ссылок больше нет - маркируем элемент: }

begin Current.Sign 0; Current.Number 0;

if Last ¹ nil then

{ Возврат по цепочке к предшествующему элементу и }

{ восстановление ссылок обратной перестановкой: }

Current Last Current.Pointers [ Current. Number ]

begin P Current; Current Last;

Last Current.Pointers [ Current. Number ];

Current.Pointers [ Current. Number ] P;

End

End

end;

End.

После маркировки элементов система выполняет последовательный просмотр элементов кучи, включая блоки, помеченные как мусор в список свободных пространств, а в элементах, являющихся активными устанавливает биты сбора мусора для последующих попыток сбора мусора.

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