В программировании сборка мусора (устоявшийся термин[1], с точки зрения русского языка правильнее «сбор мусора»[2], англ. garbage collection, GC) — одна из форм автоматического управления памятью. Специальный процесс, называемый сборщиком мусора (англ. garbage collector), периодически освобождает память, удаляя объекты, которые уже не будут востребованы приложениями — то есть производит «сбор мусора».
Содержание |
Сборка мусора была впервые применена Джоном Маккарти в 1959 году в среде программирования на разработанном им функциональном языке программирования Лисп. Впоследствии она применялась в других системах программирования и языках, преимущественно — в функциональных и логических. Необходимость сборки мусора в языках этих типов обусловлена тем, что структура таких языков делает крайне неудобным отслеживание времени жизни объектов в памяти и ручное управление ею. Широко используемые в этих языках списки и основанные на них сложные структуры данных во время работы программ постоянно создаются, надстраиваются, расширяются, копируются, и правильно определить момент удаления того или иного объекта затруднительно.
В промышленных процедурных и объектных языках сборка мусора долго не использовалась. Предпочтение отдавалось ручному управлению памятью, как более эффективному и предсказуемому. Но со второй половины 1980-х годов технология сборки мусора стала использоваться и в директивных (императивных), и в объектных языках программирования, а со второй половины 1990-х годов всё большее число создаваемых языков и сред, ориентированных на прикладное программирование, включают механизм сборки мусора либо как единственный, либо как один из доступных механизмов управления динамической памятью. В настоящее время она используется в Oberon, Java, Python, Ruby, Perl, C#, D и других языках.
Традиционным для директивных языков способом управления памятью является ручной. Его сущность в следующем:
В любом языке, допускающем создание объектов в динамической памяти, потенциально возможны две проблемы: висячие ссылки и утечки памяти.
Сборка мусора — технология, позволяющая, с одной стороны, упростить программирование, избавив программиста от необходимости вручную удалять объекты, созданные в динамической памяти, с другой — устранить вызванные неправильным ручным управлением памятью ошибки.
В системе со сборкой мусора обязанность освобождения памяти от объектов, которые больше не используются, возлагается на среду исполнения программы. Программист лишь создаёт динамические объекты и пользуется ими, он может не заботиться об удалении объектов, поскольку это делает за него среда. Для осуществления сборки мусора в состав среды исполнения включается специальный программный модуль, называемый «сборщиком мусора». Этот модуль периодически запускается, определяет, какие из созданных в динамической памяти объектов более не используются, и освобождает занимаемую ими память.
Периодичность запуска сборщика мусора определяется особенностями системы. Сборщик может работать в фоновом режиме, запускаясь при неактивности программы (например, когда программа простаивает, ожидая ввода данных пользователем). Сборщик мусора запускается безусловно, прерывая на время своей работы выполнение программы, когда очередную операцию выделения памяти оказывается невозможно выполнить из-за того, что вся доступная память исчерпана. После освобождения памяти прерванная операция выделения памяти возобновляется и программа продолжает исполняться дальше. Если же оказывается, что освободить память невозможно, среда исполнения останавливает программу с сообщением об ошибке «Недостаточно памяти».
Хотя, в общем случае, невозможно точно определить момент, когда объект был использован в последний раз и больше не нужен, сборщики мусора используют консервативные оценки, позволяющие определить, что в будущем объект гарантированно не будет использоваться.
Обычно критерием того, что объект ещё используется, является наличие ссылок на него. Если в системе нет больше ссылок на данный объект, то он, очевидно, больше не может быть использован программой, а следовательно, может быть удалён. Этот критерий используется большинством современных сборщиков мусора и называется ещё достижимостью объекта.
Неформально можно задать следующее рекурсивное определение достижимого объекта:
Такое определение не является теоретически наилучшим, так как в число достижимых, согласно ему, попадают и те объекты, которые уже никогда не будут использованы, но на которые пока ещё существуют ссылки. Оптимальным было бы считать недостижимым объект, к которому в процессе дальнейшей работы программы не будет ни одного обращения, однако выявление таких объектов невозможно, поскольку сводится к алгоритмически неразрешимой задаче об остановке (для этого достаточно предположить, что некоторый объект X будет использован в том и только в том случае, если успешно завершится программа P).
Простой алгоритм определения достижимых объектов, «алгоритм пометок» (Mark and Sweep), заключается в следующем:
(Следует обратить внимание, что, согласно данному алгоритму, если два или более объектов ссылаются друг на друга, но ни на один из этих объектов нет других ссылок, то имеет место циклическая ссылка, и вся группа считается недостижимой. Эта особенность алгоритма позволяет гарантированно удалять группы объектов, использование которых прекратилось, но в которых имеются ссылки друг на друга. Такие группы часто называются «islands of isolation» (острова изоляции))
Другой вариант алгоритма определения достижимости — обычный подсчёт ссылок. Его использование замедляет операции присваивания ссылок, но зато определение достижимых объектов тривиально — это все объекты, значение счётчика ссылок которых превышает нуль. Без дополнительных уточнений этот алгоритм, в отличие от предыдущего, не удаляет циклически замкнутые цепочки вышедших из употребления объектов, сохранивших ссылки друг на друга.
Как только определено множество недостижимых объектов, сборщик мусора может освободить память, занимаемую ими, и оставить остальное как есть. Также можно после освобождения памяти переместить все или часть оставшихся объектов в другие области памяти, обновив вместе с этим все ссылки на них. Эти два варианта реализации называются, соответственно, неперемещающим и перемещающим.
Обе стратегии имеют как достоинства, так и недостатки
Как показывает практика, недавно созданные объекты чаще становятся недостижимыми, чем объекты, существующие длительное время. В соответствии с этой закономерностью многие современные сборщики мусора подразделяют все объекты на несколько поколений — серий объектов с близким временем существования. Как только память, выделенная одному из поколений, заканчивается, в этом поколении и во всех более «молодых» производится поиск недостижимых объектов. Все они удаляются, а оставшиеся переводятся в более «старое» поколение.
Использование поколений сокращает время цикла сборки мусора, поскольку уменьшается число просматриваемых в ходе сборки объектов, однако этот метод требует от среды исполнения отслеживания ссылок между разными поколениями.
Чтобы программа могла использовать сборку мусора, необходимо выполнение ряда условий, относящихся к языку, среде исполнения и самой решаемой задаче.
Вопреки часто встречающимся утверждениям, наличие сборки мусора вовсе не освобождает программиста от всех проблем управления памятью.
IDisposable
.По сравнению с ручным управлением памятью сборка мусора безопаснее, поскольку она предотвращает утечки памяти и возникновение висячих ссылок из-за несвоевременного удаления объектов. Другой положительный момент — упрощение самого процесса программирования. С другой стороны, наличие сборки мусора может вызывать у неопытного разработчика чувство ложной безопасности, базирующееся на представлении, что вопросам выделения и освобождения памяти вообще не надо уделять внимания, поскольку они решаются сборщиком мусора. На практике, как уже говорилось выше, программист не может полностью игнорировать вопрос управления памятью и при наличии сборщика мусора, хотя затраты ручного труда на управление памятью в этом случае всё-таки существенно меньше.
Во многих случаях системы со сборкой мусора демонстрируют меньшую эффективность, как по скорости, так и по объёму используемой памяти (что неизбежно, так как сборщик мусора сам потребляет ресурсы и нуждается в некотором избытке свободной памяти для нормальной работы). Кроме того, в системах со сборкой мусора сложнее реализуются низкоуровневые алгоритмы, требующие прямого доступа к оперативной памяти компьютера, поскольку свободное использование указателей невозможно и прямой доступ к памяти требует наличия специальных интерфейсов, написанных на низкоуровневых языках.
Поддержка в некоторых императивных языках автоматического вызова деструктора, а также более простая, чем сборка мусора, технология использования «умных ссылок» (отслеживания количества ссылок на объект непосредственно в нём и автоматическое удаление при удалении последней ссылки, как это сделано в технологии COM) значительно снижает вероятность утечек, позволяя концентрировать опасные места внутри реализации класса, при этом не требуя лишних ресурсов, хотя и требует при этом более высокой квалификации программиста. Конечно, писать код освобождения ресурсов всё равно придётся, но автоматические деструкторы дадут уверенность, что этот код обязательно вызовется.
Существенное удобство от сборки мусора возникает тогда, когда динамически созданные объекты живут длительное время, многократно дублируются, а ссылки на них передаются между различными участками программы. В таких программах в общем случае достаточно сложно безошибочно определить место, где объект перестал использоваться и его можно удалять. Поскольку именно такая ситуация складывается при широком использовании динамически изменяемых структур данных (списки, деревья, графы), сборка мусора является необходимой в широко использующих такие структуры функциональных и логических языках, типа Хаскелла, Лиспа или Пролога. Использование сборки мусора в традиционных императивных языках (основанных на структурной парадигме, возможно, дополненной объектными средствами) определяется желаемым соотношением между простотой и скоростью разработки программ и эффективностью её выполнения.
Сборка мусора часто противопоставляется ручному управлению памятью, при котором программист явно указывает, когда и какие области памяти надо освободить. Однако есть языки, в которых используется комбинация двух методов управления памятью, равно как есть и другие технологии решения той же фундаментальной проблемы (например, en:region inference).
Некоторые языки программирования требуют использования механизма сборки мусора в соответствии со своей спецификацией (Java, C#, Eiffel), другие — по причинам эффективности реализации (например, формальные языки для лямбда-исчисления) — эти языки называются языками со сборкой мусора. Многие языки со сборкой мусора не имеют возможностей для явного ручного удаления объектов (например, оператора delete), благодаря чему возникновение висячих ссылок исключается в принципе, а сборщик мусора лишь занимается удалением объектов, на которые нет ссылок из программы.
Некоторые языки (например, Modula-3) позволяют использовать как ручное управление памятью, так и сборку мусора в одном приложении — используя две отдельные кучи.
Сборка мусора.