#common

Сборщики мусора 2/2.

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

Одним из самых эффективных алгоритмов сборки мусора является сборщик мусора с поколениями. Он основан на простом утверждении: большинство объектов умирают молодыми.
Новые объекты считаются объектами первого поколения. Если эти объекты переживают n сборок мусора, их поколение становится вторым. Объекты более высокого поколения проверяются реже, т.к. подразумевается, что раз они уже долго прожили, то и далее проживут дольше молодых объектов. В случае, если они опять переживают несколько сборок мусора своего поколения, то они перемещаются в третье поколение. Количество поколений обычно ограничено каким-то небольшим числом (т.е. не растут бесконечно). Правило при обходе графа объектов простое — если нам повстречался объект из более старшего поколения, чем проверяемое в данный момент, дальше в этом направлении не идем. Однако здесь есть тонкий момент. Поскольку объекты в общем случае могут изменяться, они также могут содержать ссылки на объекты более молодого поколения. Поэтому во время выполнения программы необходимо отслеживать ситуации, когда более старый объект начинает ссылаться на более молодой и добавлять в этом случае молодой объект в «корневое множество» объектов соответствующего поколения. Иначе сборщик мусора ошибочно удалит его, как недостижимый.
Иногда полезно знать, как устроен сборщик мусора, которым пользуется разработчик, чтобы не бояться создавать этот самый мусор. Например объекты можно переиспользовать, однако для сборщика мусора с поколениями это будет означать, что объект долгоживущий, из-за чего его поколение вырастет и он будет проверяться реже. Это искуственное продлевание жизни объекта в итоге может сделать операции сборщика мусора менее эффективными.

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