Алгоритмы освобождения памяти

Алгоритм выставления флагов

Простой алгоритм определения достижимых объектов, «алгоритм пометок» (Mark and Sweep), заключается в следующем:

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

(Следует обратить внимание, что, согласно данному алгоритму, если два или более объектов ссылаются друг на друга, но ни на один из этих объектов нет других ссылок, то имеет место циклическая ссылка, и вся группа считается недостижимой. Эта особенность алгоритма позволяет гарантированно удалять группы объектов, использование которых прекратилось, но в которых имеются ссылки друг на друга. Такие группы часто называются «islands of isolation» (острова изоляции))

Алгоритм подсчёта ссылок

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