Сборщик мусора

Сборщик мусора (англ. garbage collector, GC) — это компонент системы управления памятью, который автоматически освобождает участки оперативной памяти, занятые объектами, более не используемыми программой. Сборка мусора является одной из форм автоматического управления памятью, противопоставляемой ручному управлению (например, через вызовы malloc/free в C или new/delete в C++). Основная цель сборщика мусора — предотвратить утечки памяти и ошибки, связанные с обращением к уже освобождённой памяти (висячие указатели), повышая надёжность и безопасность программ.

История

Ранние концепции

Идея автоматического управления памятью возникла в 1950-х годах. Первые реализации сборщиков мусора появились в языке Lisp, разработанном Джоном Маккарти в 1958 году. В Lisp память для списков и атомов выделялась динамически, и ручное освобождение было бы крайне неудобным. Маккарти предложил алгоритм «mark-and-sweep» (пометить и очистить), который стал основой для многих последующих реализаций.

Развитие в 1960–1980-х годах

В 1960-х годах сборщики мусора были реализованы в языках APL и Snobol. В 1970-х годах появились более эффективные алгоритмы, такие как сборка мусора с поколениями (generational GC) и алгоритм «stop-the-world» (остановка мира), при котором выполнение программы приостанавливалось для проведения сборки. В 1980-х годах сборка мусора стала стандартной функцией в языках Smalltalk и Java (последний сделал GC неотъемлемой частью своей виртуальной машины).

Современный этап

С 1990-х годов сборка мусора активно применяется в языках Java, C#, Python, Ruby, JavaScript, Go и многих других. Современные сборщики мусора, такие как G1 (Garbage-First) в Java, .NET GC и Go GC, используют сложные эвристики, параллельные и конкурентные алгоритмы, чтобы минимизировать задержки и повысить производительность. В 2010-х годах появились сборщики мусора с низкой задержкой (low-latency GC), например, ZGC и Shenandoah в Java, способные работать с паузами менее 10 миллисекунд.

Принципы работы

Основные этапы

Сборщик мусора обычно работает в несколько этапов:

1. Обнаружение мусора — определение объектов, которые больше не доступны программе.
2. Освобождение памяти — возврат памяти, занятой мусором, в пул свободной памяти.
3. Уплотнение (опционально) — перемещение живых объектов в памяти для устранения фрагментации.

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

Существует два основных подхода к обнаружению мусора:

• Подсчёт ссылок (reference counting) — каждый объект хранит счётчик количества ссылок на него. Когда счётчик становится равным нулю, объект считается мусором и немедленно освобождается. Этот метод прост, но не может обрабатывать циклические ссылки (например, объекты A и B ссылаются друг на друга, но недоступны извне). Применяется в Python, PHP, Objective-C, Swift (в комбинации с другими методами).
• Трассировка (tracing) — сборщик мусора начинает с корневых объектов (глобальные переменные, стек, регистры) и обходит граф объектов, помечая все достижимые. Недостижимые объекты считаются мусором. Этот метод обрабатывает циклические ссылки, но требует более сложной реализации. Применяется в Java, C#, Go, Ruby, JavaScript.

Стратегии сборки

• Stop-the-world — выполнение программы приостанавливается на время сборки. Простая реализация, но может вызывать заметные паузы.
• Конкурентная (concurrent) сборка — сборщик мусора работает параллельно с программой, минимизируя паузы.
• Параллельная (parallel) сборка — сборка выполняется несколькими потоками одновременно, ускоряя процесс.
• Инкрементальная (incremental) сборка — сборка разбивается на небольшие шаги, выполняемые между операциями программы.

Классификация сборщиков мусора

По поколениям

• Однопоколенческие (single-generational) — все объекты обрабатываются одинаково.
• Многопоколенческие (generational) — объекты делятся на поколения (например, молодое и старое). Молодые объекты проверяются чаще, так как они с большей вероятностью становятся мусором. Это повышает эффективность, поскольку большинство объектов умирают молодыми. Применяется в Java HotSpot, .NET, Go.

По типу кучи

• Копирующие (copying GC) — объекты перемещаются из одной области памяти в другую. Живые объекты копируются, а исходная область полностью очищается. Пример: алгоритм «Cheney’s algorithm» в Lisp.
• Не копирующие (non-copying GC) — объекты не перемещаются. Пример: mark-and-sweep.
• С уплотнением (compacting GC) — живые объекты перемещаются, чтобы устранить фрагментацию. Пример: mark-compact.

По способу обнаружения

• Трассирующие (tracing GC) — на основе обхода графа объектов.
• На основе подсчёта ссылок (reference counting GC) — на основе счётчиков ссылок.

Применение

Языки программирования

Сборка мусора используется в большинстве современных высокоуровневых языков:

• Java — стандартный сборщик мусора (G1, ZGC, Shenandoah) является частью виртуальной машины Java (JVM).
• C# — сборщик мусора .NET Framework и .NET Core.
• Python — использует подсчёт ссылок и дополнительный сборщик мусора для циклических ссылок.
• JavaScript — сборщик мусора в браузерах (например, V8 в Chrome) и Node.js.
• Go — конкурентный сборщик мусора с низкой задержкой.
• Ruby — сборщик мусора с поколениями.
• Swift — использует подсчёт ссылок (Automatic Reference Counting, ARC) с дополнительным сборщиком мусора для циклических ссылок.

Операционные системы

Некоторые операционные системы, такие как Microsoft Windows и Linux, используют сборщики мусора для управления памятью в некоторых своих компонентах. Например, в Windows сборка мусора применяется в среде .NET, а в Linux — в некоторых реализациях виртуальных машин.

Встраиваемые системы

В встраиваемых системах с ограниченными ресурсами сборка мусора применяется реже из-за накладных расходов. Однако существуют специализированные сборщики мусора для таких систем, например, в языке MicroPython.

Критика и ограничения

Производительность

Сборка мусора может приводить к непредсказуемым паузам в работе программы, что критично для систем реального времени. Даже современные низкозадержечные сборщики не гарантируют абсолютной детерминированности. В высоконагруженных системах (например, в финансовых или игровых) часто предпочитают ручное управление памятью или использование пулов объектов.

Фрагментация

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

Накладные расходы

Сборка мусора требует дополнительных вычислительных ресурсов (процессорное время, память для метаданных). В системах с ограниченными ресурсами это может быть неприемлемо.

Циклические ссылки

Подсчёт ссылок не может обрабатывать циклические ссылки, что требует дополнительных механизмов (например, сборщик мусора для циклических ссылок в Python или Swift).

Интересные факты

• Первый сборщик мусора был реализован в 1958 году для языка Lisp.
• В языке Java сборка мусора является обязательной и не может быть отключена.
• В языке C++ сборка мусора не является стандартной, но существуют сторонние библиотеки, такие как Boehm GC.
• В языке Go сборщик мусора был значительно переработан в версии 1.5 (2015 год), что позволило снизить паузы до 10–100 микросекунд.
• В языке Rust сборка мусора отсутствует — управление памятью осуществляется через систему владения и заимствования, что гарантирует безопасность без сборщика мусора.

Источники

• Jones, R., & Lins, R. (1996). Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley.
• McCarthy, J. (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine.
• Документация Oracle Java Virtual Machine (Garbage Collection Tuning Guide).
• Документация .NET Framework (Garbage Collection).
• Документация Go (Garbage Collection Guide).