- Mark-sweep
- Mark-compact
- Copying
- Reference counting
Каждому из этих алгоритмов посвящена отдельная глава в основополагающем учебнике The Garbage Collection Handbook. Рекомендуем обратиться к этому учебнику для полного погружения в тему.
Каждое анимированное изображение - это пространство памяти, выделенное процессу. Чёрным цветом изображена неиспользуемая память, по мере использования память начинает подсвечиваться жёлтым (операции записи) и зелёным (операции чтения) цветами. Цвет фрагментов памяти, которые используются дольше, начинает тускнеть, чтобы визуализировать развитие процесса во времени. По ходу выполнения программа перестаёт использовать отдельные участки памяти. Они и считаются "мусором".
Первая анимация демонстирует отсутствие всякой сборки мусора -
NO_GC, в этом случае память освобождается только при завершении процесса. Механизм NO_GC прост в реализации, он удобен, когда есть способ разбить задачу на отдельные подпроцессы. Так, например, работает веб-сервер Apache.Вторая анимация демонстрирует работу сборщика мусора с использованием техники подсчёта ссылок. Суть алгоритма заключается в подсчёте количества ссылок на объекты в памяти, если количество ссылок становится равным нулю, то объект удаляется. Подсчёт ссылок - единственный алгоритм, хорошо совместимый с разными менеджерами ресурсов. По сравнению с первой анимацией появились красные пиксели, они соответствуют операциям подсчёта ссылок. Можно оценить и эффективность сборщика, если сразу после красной вспышки область памяти освобождается.
Третья анимация демонстрирует работу алгоритма "mark-and-sweep". Все объекты делятся на достижимые и недостижимые. Определённое множество объектов считается достижимым изначально - так называемые корневые объекты. Объект, на который есть ссылка из достижимого объекта, тоже считается достижимым. При запуске сборщик мусора выполняет следующие шаги:
- Фаза Mark: отмечает все достижимые объекты
- Фаза Sweep: проходит рекурсивно по объектам в куче, удаляет недостижимые объекты и возвращает их в пул свободной памяти.
Визуализации остальных алгоритмов приведены в репозитории. Помимо описанных визуализаций алгоритмов сборки мусора есть и другие, например интерактивная визуализация алгоритма tricolor mark-sweep, используемого в реализации языка Go.