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

В программировании сборка мусора (устоявшийся термин, с точки зрения русского языка правильнее «сбор мусора», англ. garbage collection, GC) — одна из форм автоматического управления памятью. Специальный код, называемый сборщиком мусора (garbage collector), периодически освобождает память, удаляя объекты, которые уже не будут востребованы приложением — то есть производит сборку мусора.

История

Сборка мусора была впервые применена Джоном Маккарти в 1959 году в среде программирования на разработанном им функциональном языке программирования Лисп. Впоследствии она применялась в других системах программирования и языках, преимущественно — в функциональных и логических. Необходимость сборки мусора в языках этих типов обусловлена тем, что структура таких языков делает крайне неудобным отслеживание времени жизни объектов в памяти и ручное управление ею. Широко используемые в этих языках списки и основанные на них сложные структуры данных во время работы программ постоянно создаются, надстраиваются, расширяются, копируются, и правильно определить момент удаления того или иного объекта затруднительно.

В промышленных процедурных и объектных языках сборка мусора долго не использовалась. Предпочтение отдавалось ручному управлению памятью, как более эффективному и предсказуемому. Но со второй половины 1980-х годов технология сборки мусора стала использоваться и в директивных, и в объектных языках программирования, а со второй половины 1990-х годов всё большее число создаваемых языков и сред, ориентированных на прикладное программирование, включают механизм сборки мусора либо как единственный, либо как один из доступных механизмов управления динамической памятью. В настоящее время она используется в Oberon, Java, Python, Ruby, C#, D и других языках.

Проблемы ручного управления памятью

Традиционным для директивных языков способом управления памятью является ручной. Его сущность в следующем:

• Для создания объекта в динамической памяти программист явно вызывает команду выделения памяти. Эта команда возвращает указатель на выделенную область памяти, который сохраняется и используется для доступа к ней.
• До тех пор, пока созданный объект нужен для работы программы, программа обращается к нему через ранее сохранённый указатель.
• Когда надобность в объекте проходит, программист явно вызывает команду освобождения памяти, передавая ей указатель на удаляемый объект.

В любом языке, допускающем создание объектов в динамической памяти, потенциально возможны две проблемы: висячие ссылки (англ. dangling pointer) и утечки памяти (англ. memory leak).

Висячие ссылки

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

Появление висячих ссылок обычно становится следствием неправильной оценки времени жизни объекта: программист вызывает команду удаления объекта до того, как его использование прекратится.

Утечки памяти

Создав объект в динамической памяти, программист может не удалить его после завершения использования. Если ссылающейся на объект переменной будет присвоено новое значение и на объект нет других ссылок, он становится программно-недоступным, но продолжает занимать память, поскольку команда его удаления не вызывалась. Такая ситуация и называется утечкой памяти. Если объекты, ссылки на которые теряются, создаются в программе постоянно, то утечка памяти проявляется в постепенном увеличении объёма используемой памяти; если программа работает долго, объём используемой ею памяти постоянно растёт и через какое-то время ощутимо замедляется работа системы (из-за необходимости при любом выделении памяти использовать своппинг), либо программа исчерпывает доступный объем адресного пространства и завершается с ошибкой.

Механизм сборки мусора

Основные принципы

Сборка мусора — технология, позволяющая, с одной стороны, упростить программирование, избавив программиста от необходимости вручную удалять объекты, созданные в динамической памяти, с другой — устранить вызванные неправильным ручным управлением памятью ошибки.

В системе со сборкой мусора обязанность освобождения памяти от объектов, которые больше не используются, возлагается на среду исполнения программы. Программист лишь создаёт динамические объекты и пользуется ими, он может не заботиться об удалении объектов, поскольку это делает за него среда. Для осуществления сборки мусора в состав среды исполнения включается специальный программный модуль, называемый «сборщиком мусора». Этот модуль периодически запускается, определяет, какие из созданных в динамической памяти объектов более не используются и освобождает занимаемую ими память.

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

Хотя, в общем случае, невозможно точно определить момент, когда объект был использован в последний раз и больше не нужен, сборщики мусора используют консервативные оценки, позволяющие определить, что в будущем объект гарантированно не будет использоваться.

Достижимость объекта

Обычно критерием того, что объект ещё используется, является наличие ссылок на него. Если в системе нет больше ссылок на данный объект, то он, очевидно, больше не может быть использован программой, а следовательно, может быть удалён. Этот критерий используется большинством современных сборщиков мусора и называется ещё достижимостью объекта.

Неформально можно задать следующее рекурсивное определение достижимого объекта:

• Определённое множество объектов считается достижимым изначально. Такие объекты называются корневыми. Обычно в их число включают все глобальные переменные и объекты, на которые есть ссылки в стеке вызовов.
• Любой объект, на который есть ссылка из достижимого объекта тоже считается достижимым. Исключение составляют слабые ссылки.

Такое определение не является теоретически наилучшим, так как в число достижимых, согласно ему, попадают и те объекты, которые никогда не будут использованы, но на которые пока ещё существуют ссылки. Оптимальным было бы считать недостижимым объект, к которому в процессе дальнейшей работы программы не будет ни одного обращения, однако выявление таких объектов невозможно, поскольку сводится к алгоритмически неразрешимой задаче об остановке (для этого достаточно предположить, что некоторый объект X будет использован в том и только в том случае, если успешно завершится программа P).

Простой алгоритм определения достижимых объектов, «алгоритм пометок» (Mark and Sweep), заключается в следующем:

• Для каждого объекта хранится бит, указывающий, достижим ли этот объект из программы или нет.
• Изначально все объекты, кроме корневых, помечаются как недостижимые.
• Рекурсивно просматриваются объекты, до которых можно добраться из корневых по ссылкам. Все такие объекты помечаются как достижимые. Объекты уже помеченные достижимыми при этом не рассматриваются.
• Те объекты, у которых бит достижимости не был установлен, считаются недостижимыми.

(Следует обратить внимание, что, согласно данному алгоритму, если два или более объектов ссылаются друг на друга, но ни на один из этих объектов нет других ссылок, то есть имеет место циклическая ссылка, то вся группа считается недостижимой. Эта особенность алгоритма позволяет гарантированно удалять группы объектов, использование которых прекратилось, но в которых имеются ссылки друг на друга. Такие группы часто называются «islands of isolation» (острова изоляции))

Другой вариант алгоритма определения достижимости — обычный подсчёт ссылок. Его использование замедляет операции присваивания ссылок, но зато определение достижимых объектов тривиально — это все объекты, значение счётчика ссылок которых превышает нуль. Без дополнительных уточнений этот алгоритм, в отличие от предыдущего, не удаляет циклически замкнутые цепочки вышедших из употребления объектов, сохранивших ссылки друг на друга.

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

Как только определено множество недостижимых объектов, сборщик мусора может освободить память, занимаемую ими, и оставить остальное как есть. Также можно после освобождения памяти переместить все или часть оставшихся объектов в другие области памяти, обновив вместе с этим все ссылки на них. Эти два варианта реализации называются, соответственно, неперемещающим и перемещающим.

Обе стратегии имеют как достоинства, так и недостатки:

Скорость выделения и освобождения памяти

• Неперемещающий сборщик мусора быстро освобождает память (поскольку эта операция сводится к пометке соответствующих блоков памяти как свободных), но тратит больше времени на её выделение (поскольку память фрагментируется и при выделении необходимо найти в карте памяти нужное количество блоков подходящего размера).
• Перемещающий сборщик требует сравнительно больше времени на этапе сборки мусора (тратится дополнительное время на дефрагментацию памяти и изменение всех ссылок на перемещаемые объекты), зато перемещение позволяет использовать чрезвычайно простой и быстрый (O(1)) алгоритм выделения памяти. При дефрагментации объекты передвигаются так, чтобы разделить всю память на две большие области — занятую и свободную, и сохраняется указатель на их границу. Для выделения новой памяти достаточно лишь переместить эту границу, вернув кусок из начала свободной памяти.

Скорость доступа к объектам в динамической памяти.

Объекты, поля которых используются совместно, перемещающий сборщик позволяет размещать в памяти недалеко друг от друга. Тогда они вероятнее окажутся в кэше процессора одновременно, что уменьшит количество обращений к относительно медленной ОЗУ.

Совместимость с инородным кодом.

Перемещающий сборщик мусора вызывает затруднения при использовании кода, который не контролируется системой автоматического управления памятью (такой код называется инородным (foreign) в традиционной терминологии или неуправляемым в терминологии Microsoft). Указатель на память, выделенную в системе с неперемещающим сборщиком, можно просто передать инородному коду для использования, удерживая хотя бы одну обычную ссылку на объект, чтобы сборщик его не удалил. Перемещающий сборщик меняет положение объектов в памяти, синхронно меняя все ссылки на них, но поменять ссылки в инородном коде он не может, в результате переданные инородному коду ссылки после перемещения объекта станут некорректными. Для работы с инородным кодом используются различные специальные приёмы, например, pinning — явная блокировка объекта, запрещающая его перемещение во время сборки мусора.

Поколения объектов

Как показывает практика, недавно созданные объекты чаще становятся недостижимыми, чем объекты, существующие длительное время. В соответствии с этой закономерностью многие современные сборщики мусора подразделяют все объекты на несколько поколений — серий объектов с близким временем существования. Как только память, выделенная одному из поколений, заканчивается, в этом поколении и во всех более «молодых» производится поиск недостижимых объектов. Все они удаляются, а оставшиеся переводятся в более «старое» поколение.

Использование поколений сокращает время цикла сборки мусора, поскольку уменьшается число просматриваемых в ходе сборки объектов, однако этот метод требует от среды исполнения отслеживания ссылок между разными поколениями.

Требования к языку и системе

Чтобы программа могла использовать сборку мусора, необходимо выполнение ряда условий, относящихся к языку, среде исполнения и самой решаемой задаче.

Необходимость среды исполнения со сборщиком мусора.

Естественно, для сборки мусора необходима динамическая среда, поддерживающая исполнение программы, и наличие в этой среде сборщика мусора.

Поддержка со стороны языка программирования.

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

Техническая допустимость кратковременных замедлений в работе программ.

Сборка мусора выполняется периодически, как правило, в заранее неизвестные моменты времени. Если приостановка работы программы на время, сравнимое со временем сборки мусора, может привести к критическим ошибкам, использовать в подобной ситуации сборку мусора, очевидно, нельзя.

Наличие некоторого резерва свободной памяти.

Чем больше памяти доступно среде исполнения, тем реже запускается сборщик мусора и тем эффективнее его работа. Работа сборщика мусора в системе, где количество доступной сборщику памяти приближается к пиковой потребности программы, может оказаться неэффективной и непроизводительной. Чем меньше избыток памяти, тем чаще происходит запуск сборщика и тем больше времени тратится на его выполнение. Падение производительности программы в таком режиме может оказаться слишком существенным.

Проблемы использования

Вопреки часто встречающимся утверждениям, наличие сборки мусора вовсе не освобождает программиста от всех проблем управления памятью.

Освобождение других ресурсов, занятых объектом.

Помимо динамической памяти, объект может владеть и другими ресурсами — подчас более ценными, чем память. Если объект при создании открывает файл, по завершении использования он должен его закрыть, если подключается к СУБД — должен отключиться. В системах с ручным управлением памятью это делается непосредственно перед удалением объекта из памяти, чаще всего — в деструкторах соответствующих объектов. В системах со сборкой мусора обычно есть возможность выполнить некоторый код непосредственно перед удалением объекта, так называемые финализаторы, но для освобождения ресурсов они не годятся, так как момент удаления заранее неизвестен и может оказаться, что ресурс освобождается намного позже, чем перестаёт использоваться объект. В подобных случаях программисту всё равно приходится отслеживать использование объекта вручную и вручную выполнять операции по освобождению занятых объектом ресурсов.

Утечка памяти.

В системах со сборкой мусора, так же, как и при отсутствии таковой, могут возникать утечки памяти, правда, имеющие несколько другую природу. Ссылка на неиспользуемый объект может сохраниться в другом объекте, который используется и становится своеобразным «якорем», удерживающим ненужный объект в памяти. Например созданный объект добавляется в коллекцию, используемую для вспомогательных операций, потом перестаёт использоваться, но не удаляется из коллекции. Коллекция удерживает ссылку, объект остаётся достижимым и не подвергается сборке мусора. Результатом становится всё та же утечка памяти.
Чтобы устранить подобные проблемы, среда исполнения может поддерживать специальное средство — так называемые слабые ссылки.

Приёмы программирования.

Использование сборки мусора оказывает влияние и на то, какие приёмы программирования, конструкции, шаблоны алгоритмов допустимы для использования программистом. Сколь бы качественным ни был сборщик мусора, он всегда будет ощутимо замедлять работу программ при возникновении некоторых, особо неудачных для быстрой сборки мусора, ситуаций. Одной из таких ситуаций является создание программой в процессе работы слишком большого количества короткоживущих объектов. Рассмотрим условный фрагмент программы на языке Java:

        String buffer = new String("");
        while (!source.eof()) {
          buffer = buffer + source.getNextString();
        }

На первый взгляд, код выглядит вполне невинно, он всего лишь превращает возвращаемый источником source набор текстовых строк в одну строку, на каждом проходе цикла добавляя к объекту buffer очередную строку. В действительности же всё гораздо хуже: в первой строке создаётся объект класса String, который содержит пустую строку. После этого при каждом исполнении тела цикла создаётся новый (!) объект класса String, содержимое которого формируется из объединения содержимого объекта buffer и строки, возвращённой из source. Ссылка на этот новый объект и записывается в переменную buffer. Таким образом, если цикл будет выполнен 1000 раз, будет создан 1001 объект String, первый из которых останется пуст, а каждый следующий будет содержать ту же строку, что и предыдущий, плюс некоторый «хвост». Реально в программе будет использован только последний из созданных объектов, все остальные окажутся «брошены» прямо по ходу исполнения цикла, до следующего запуска сборщика мусора будут занимать память, а после его запуска — отнимать время на удаление.
Чтобы избежать негативных последствий, программист в данном случае должен избрать другой способ объединения строк (например, использовать класс StringBuilder).

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

Достоинства и недостатки

По сравнению с ручным управлением памятью сборка мусора безопаснее, поскольку она предотвращает утечки памяти и возникновение висячих ссылок из-за несвоевременного удаления объектов. Другой положительный момент — упрощение самого процесса программирования. Как говорилось выше, программист не может полностью игнорировать вопрос управления памятью и при наличии сборщика мусора, но затраты на управление памятью в этом случае всё-таки существенно меньше.

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

Управление памятью в конкретных языках и системах

Сборка мусора часто противопоставляется ручному управлению памятью, при котором программист явно указывает, когда и какие области памяти надо освободить. Однако есть языки, в которых используется комбинация двух методов управления памятью, равно как есть и другие технологии решения той же фундаментальной проблемы (например, en:region inference).

Некоторые языки программирования требуют использования механизма сборки мусора в соответствии со своей спецификацией (Java, C#, Eiffel), другие — по причинам эффективности реализации (например, формальные языки для лямбда-исчисления) — эти языки называются языками со сборкой мусора. Многие языки со сборкой мусора не имеют возможностей для явного ручного удаления объектов (например, оператора delete), благодаря чему возникновение висячих ссылок исключается в принципе, а сборщик мусора лишь занимается удалением объектов, на которые нет ссылок из программы.

Некоторые языки (например, Modula-3) позволяют использовать как ручное управление памятью так и сборку мусора в одном приложении — используя две отдельные кучи.