Сборка мусора
Материал из Википедии — свободной энциклопедии
В программировании, сборка мусора (англ. garbage collection, GC) — одна из форм автоматического управления памятью. Специальный код, называемый сборщиком мусора (garbage collector), пытается освободить память, использованную объектами, которые уже не будут востребованы приложением — то есть производит сборку мусора. Сборка мусора была изобретена Джоном Маккарти (John McCarthy) примерно в 1959 при разработке языка программирования Лисп, для решения проблем, которые порождало ручное управление памятью.
Сборка мусора часто противопоставляется ручному управлению памятью, при котором программист явно указывает, когда и какие области памяти надо освободить. Однако есть языки, в которых используется комбинация двух методов управления памятью, равно как есть и другие технологии решения той же фундаментальной проблемы (например, en:region inference).
По сравнению с ручным управлением памятью, сборка мусора безопаснее, поскольку она предотвращает утечки памяти, а также упрощает сам процесс программирования. Недостатком сборки мусора является меньшая эффективность, как по скорости, так и по объёму используемой памяти. Кроме освобождения памяти, сборщик мусора также дефрагментирует (уплотняет) объекты в памяти системы, перемещая их так, что бы они занимали сплошную область памяти, что благоприятно отражается на производительности системы.
Некоторые языки программирования требуют использования механизма сборки мусора в соответствии со своей спецификацией (Java, C#), другие — по причинам эффективности реализации (например, формальные языки для лямбда-исчисления) — эти языки называются языками со сборкой мусора.
Некоторые языки (например, Modula-3) позволяют использовать как ручное управление памятью так и сборку мусора в одном приложении — используя две отдельные кучи.
Базовые принципы работы сборщика мусора:
- определение объектов программы, которые в будущем не будут использоваться;
- освобождение памяти, занимаемой этими объектами.
Хотя в общем случае невозможно точно определить момент, когда объект был использован в последний раз и больше не нужен, сборщики мусора используют консервативные оценки, позволяющие определить, что в будущем объект уже не будет использоваться. Например, если в системе нет больше ссылок на данный объект — то он больше не может быть использован программой. Этот критерий используется большинством современных сборщиков мусора.
Содержание |
[править] Отслеживающие сборщики мусора
Сборщики мусора этого типа отслеживают, какие объекты являются достижимыми (или потенциально достижимыми) и затем удаляют из памяти все остальные.
[править] Достижимость объекта
Неформально можно задать следующее рекурсивное определение достижимого объекта:
- Определённое множество объектов считается достижимым изначально. Такие объекты называются корневыми. Обычно в их число включают все глобальные переменные и объекты, на которые есть ссылки в стеке вызовов.
- Любой объект, на который есть ссылка из достижимого объекта тоже считается достижимым. Исключение составляют слабые ссылки.
Такое определение не является наилучшим. Оптимальнее было бы считать недостижимым объект, к которому в процессе дальнейшей работы программы не будет ни одного обращения. Однако определение таких объектов можно свести к неразрешимой задаче об останове. Для этого достаточно предположить, что некоторый объект X будет использован в том и только в том слуачае, если успешно завершится программа P.
[править] Простой алгоритм определения достижимых объектов
Рассмотрим работу сборщика мусора на примере алгоритма пометок.
- Для каждого объекта хранится бит, указывающий, достижим ли этот объект из программы или нет.
- Изначально все объекты, кроме корневых помечаются как недостижимые.
- Рекурсивно просматриваются объекты, до которых можно добраться из корневых по ссылкам. Все такие объекты помечаются как достижимые. Объекты уже помеченные достижимыми при этом не рассматриваются.
[править] Стратегии реализации
[править] Перемещающий или неперемещающий
Как только определено множество недостижимых объектов, сборщик мусора может освободить память, занимаемую ими, и оставить остальное как есть. Также можно переместить все или часть оставшихся объектов в другие области памяти, обновив вместе с этим все ссылки на них. Эти два варианта реализации называются, соответственно, перемещающим и неперемещающим.
Обе стратегии имеют как достоинства, так и недостатки. Недостатком перемещающего сборщика является то, что при каждом выполнении цикла сборки мусора может потребоваться переместить достаточно большие объёмы данных. Тем не менее, этот недостаток может быть скомпенсирован тем, что
- На этапе сборки мусора можно выполнить дефрагментацию памяти.
- Перемещение позволяет использовать чрезвычайно простой и быстрый (O(1)) алгоритм выделения памяти. Для этого достаточно подвинуть объекты так, чтобы разделить всю память на две большие области - занятую и свободную, и хранить указатель на их границу. Тогда для выделения новой памяти достаточно будет лишь переместить эту границу, вернув кусок из начала свободной памяти.
- Объекты, поля которых используются совместно, можно разместить в памяти недалеко друг от друга. Тогда они вероятнее окажутся в кэше процессора одновременно, что уменьшит количество обращений к относительно медленной ОЗУ.
Ещё один недостаток перемещающего сборщика заключается в том, что он должен уследить за всеми ссылками на объект, чтобы иметь возможность изменить их при перемещении. Для работы с кодом, который не позволяет этого делать (такой код называется неуправляемым в терминологии Microsoft), используются различные приёмы. Например, pinning - блокировка объекта, запрещающая его перемещение во время сборки мусора.
[править] Использование поколений
Как показывает практика, только что созданные объекты чаще становятся недостижимыми, чем объекты, существующие довольно долгий срок.
Согласно этому, многие современные сборщики мусора подразделяют все объекты на несколько поколений. Как только память, выделенная одному из поколений, заканчивается, в этом поколении производится поиск недостижимых объектов. Все они удаляются, а оставшиеся переводятся в более "старое" поколение. В этом случае не требуется просматривать все объекты в цикле сборки мусора, что увеличивает производительность. Однако этот метод требует от среды исполнения отслеживания ссылок между разными поколениями.
