Сборка мусора¶

Сборка мусора — это процесс автоматического обнаружения и освобождения памяти, занятой объектами, которые больше не используются программой. Является одной из форм автоматического управления памятью, противопоставляемой ручному управлению, где программист явно выделяет и освобождает память. Сборка мусора применяется во многих языках программирования высокого уровня, включая Java, C#, Python, Go, JavaScript, Ruby и другие, а также в средах выполнения, таких как .NET Framework и виртуальная машина Java (JVM).

¶История

Концепция сборки мусора впервые была предложена Джоном Маккарти в 1959 году для языка Lisp, предназначенного для исследований в области искусственного интеллекта. Ранние реализации сборщиков мусора были простыми и неэффективными, что приводило к значительным задержкам в работе программ. В 1960-х годах были разработаны первые алгоритмы, такие как «подсчёт ссылок» (reference counting) и «маркировка-очистка» (mark-and-sweep). В 1970-х годах появились более совершенные алгоритмы, включая «копирующий сборщик» (copying collector) и «поколенческий сборщик» (generational collector), которые позволили существенно повысить производительность.

В 1980-х и 1990-х годах сборка мусора стала стандартной функцией в языках Smalltalk, Java и C#. В 2000-х годах развитие получили параллельные и конкурентные сборщики, способные работать одновременно с основным потоком программы, минимизируя паузы. В 2010-х годах были разработаны низкопаузные сборщики, такие как G1 (Garbage-First) в Java и ZGC (Z Garbage Collector), которые позволяют обрабатывать большие объёмы данных с минимальными задержками.

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

Сборка мусора основывается на понятии «достижимости» объектов. Объект считается достижимым, если на него существует прямая или косвенная ссылка из корневого набора (root set), который включает в себя глобальные переменные, локальные переменные в стеке вызовов и регистры процессора. Все остальные объекты считаются недостижимыми и подлежат удалению.

Основные этапы работы сборщика мусора:

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

¶Алгоритмы сборки мусора

Существует несколько основных алгоритмов, используемых в сборщиках мусора.

¶Подсчёт ссылок

В этом алгоритме каждый объект содержит счётчик, который увеличивается при создании новой ссылки на объект и уменьшается при её удалении. Когда счётчик достигает нуля, объект немедленно удаляется. Преимущество — простота и низкая задержка. Недостаток — неспособность обрабатывать циклические ссылки (когда два или более объектов ссылаются друг на друга, но не достижимы из корневого набора). Примеры языков: Swift, Objective-C, Python (использует подсчёт ссылок как дополнение к основному сборщику).

¶Маркировка-очистка

Алгоритм состоит из двух фаз:

• Маркировка — обход графа объектов, начиная с корневого набора, и пометка всех достижимых объектов.
• Очистка — проход по всей памяти и освобождение блоков, не помеченных как достижимые.

Недостаток — фрагментация памяти, так как освобождённые блоки могут быть разного размера. Примеры: ранние версии Java, некоторые реализации Lisp.

¶Копирующий сборщик

Память делится на две равные части: «активное» и «резервное» пространство. В активном пространстве живут объекты. При сборке мусора все достижимые объекты копируются в резервное пространство, после чего активное пространство полностью очищается, и роли пространств меняются. Преимущество — отсутствие фрагментации. Недостаток — удвоение требуемой памяти. Примеры: виртуальная машина Dalvik в Android, некоторые реализации Smalltalk.

¶Поколенческий сборщик

Основан на наблюдении, что большинство объектов умирают молодыми (гипотеза поколений). Память делится на поколения: молодое (young generation) и старое (old generation). Молодые объекты собираются часто и быстро, а старые — реже. Это позволяет сократить время пауз. Примеры: Java HotSpot VM, .NET CLR.

¶Параллельные и конкурентные сборщики

Параллельные сборщики используют несколько потоков для ускорения сборки, но приостанавливают выполнение программы. Конкурентные сборщики работают одновременно с программой, минимизируя паузы. Примеры: G1, ZGC, Shenandoah в Java.

¶Преимущества и недостатки

¶Преимущества

• Уменьшение ошибок — автоматическое управление памятью исключает утечки памяти и двойное освобождение.
• Упрощение разработки — программисту не нужно явно управлять памятью.
• Повышение безопасности — предотвращает доступ к уже освобождённой памяти.

¶Недостатки

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

¶Применение

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

• Языках программирования — Java, C#, Python, Ruby, JavaScript, Go, Swift, Kotlin.
• Средах выполнения — JVM, .NET CLR, V8 (JavaScript), CPython.
• Базах данных — некоторые системы управления базами данных (СУБД) используют сборку мусора для управления памятью.
• Веб-браузерах — сборка мусора применяется для управления памятью JavaScript и DOM-объектами.

¶Критика

Сборка мусора критикуется за:

• Непредсказуемость пауз — в системах реального времени и высоконагруженных приложениях паузы могут быть неприемлемы.
• Потребление ресурсов — сборка мусора может потреблять до 10-20% процессорного времени.
• Сложность настройки — для достижения оптимальной производительности требуется тонкая настройка параметров сборщика.

Альтернативой сборке мусора является ручное управление памятью (например, в C и C++) или использование методов, таких как «умные указатели» (smart pointers) в C++.

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

• Первый сборщик мусора был реализован в 1960 году для языка Lisp.
• В Java существует несколько реализаций сборщиков мусора, включая Serial, Parallel, CMS, G1, ZGC и Shenandoah.
• В языке Go используется конкурентный сборщик мусора, который минимизирует паузы.
• В 2019 году компания Microsoft представила сборщик мусора для .NET, способный обрабатывать до 10 гигабайт в секунду.

¶Источники

• Jones, R., & Lins, R. (1996). Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons.
• McCarthy, J. (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM.
• Oracle Corporation. (2023). Java Platform, Standard Edition HotSpot Virtual Machine Garbage Collection Tuning Guide.
• Microsoft Corporation. (2023). .NET Garbage Collection Documentation.