Сборка мусораУстоявшийся термин, с точки зрения русского языка правильнее «сбор мусора» (выдержка из словарей ABBYY Lingvo , словарь Ушакова: сборка , сбор , собрать ; Gramota.ru: обсуждение ). По словарю, сборка — это «соединяя отдельные части, детали, сделать, создать что-нибудь, превратить во что-нибудь готовое» и к остальным значениям слова «собрать» применяется именно «сбор». () в программировании — одна из форм автоматического управления памятью. Специальный процесс, называемый сборщиком мусора (), периодически освобождает память, удаляя из неё ставшие ненужными объекты.
Автоматическая сборка мусора позволяет повысить безопасность доступа к памяти.
История Сборка мусора была впервые применена Джоном Маккарти в 1959 году в среде программирования на разработанном им функциональном языке программирования Лисп. Впоследствии она применялась в других системах программирования и языках, преимущественно — в функциональных и логических. Необходимость сборки мусора в языках этих типов обусловлена тем, что структура таких языков делает крайне неудобным отслеживание времени жизни объектов в памяти и ручное управление ею. Широко используемые в этих языках списки и основанные на них сложные структуры данных во время работы программ постоянно создаются, надстраиваются, расширяются, копируются, и правильно определить момент удаления того или иного объекта затруднительно.
В промышленных процедурных и объектных языках сборка мусора долго не использовалась. Предпочтение отдавалось ручному управлению памятью, как более эффективному и предсказуемому. Но со второй половины 1980-х годов технология сборки мусора стала использоваться и в директивных (императивных), и в объектных языках программирования, а со второй половины 1990-х годов всё большее число создаваемых языков и сред, ориентированных на прикладное программирование, включают механизм сборки мусора либо как единственный, либо как один из доступных механизмов управления динамической памятью. В настоящее время она используется в Оберон, Java, Python, Ruby, C#, D, F#, Go и других языках.
Ручное управление памятью Традиционным для директивных языков способом управления памятью является ручной. Его сущность в следующем: Новый объект в динамической памяти создаётся специальной командой выделения памяти. Эта команда возвращает указатель на выделенную область памяти, который сохраняется и используется для доступа к ней. Пока созданный объект нужен для работы, программа обращается к нему через ранее сохранённый указатель. Когда надобность в объекте проходит, программа сама должна его удалить, явно вызвав команду освобождения памяти и передав ей указатель на удаляемый объект.
В любом языке, допускающем создание объектов в динамической памяти, потенциально возможны две проблемы: висячие ссылки и утечки памяти.
Висячие ссылки
Висячая ссылка () — это ссылка на объект, который уже удалён из памяти. После удаления объекта все сохранившиеся в программе ссылки на него становятся «висячими». Память, занимаемая ранее объектом, может быть передана операционной системе и стать недоступной, или быть использована для размещения нового объекта в той же программе. В первом случае попытка обратиться по «повисшей» ссылке приведёт к срабатыванию механизма защиты памяти и аварийной остановке программы, а во втором — к непредсказуемым последствиям.
Появление висячих ссылок обычно становится следствием неправильной оценки времени жизни объекта: программист вызывает команду удаления объекта до того, как его использование прекратится.
Утечки памяти
Создав объект в динамической памяти, программист может не удалить его после завершения использования. Если ссылающейся на объект переменной будет присвоено новое значение и на объект нет других ссылок, он становится программно недоступным, но продолжает занимать память, поскольку команда его удаления не вызывалась. Такая ситуация и называется утечкой памяти ().
Если объекты, ссылки на которые теряются, создаются в программе постоянно, то утечка памяти проявляется в постепенном увеличении объёма используемой памяти; если программа работает долго, объём используемой ею памяти постоянно растёт, и через какое-то время ощутимо замедляется работа системы (из-за необходимости при любом выделении памяти использовать свопинг), либо программа исчерпывает доступный объём адресного пространства и завершается с ошибкой.
Механизм сборки мусора Если бы память компьютера была бесконечной, можно было бы просто оставлять ненужные объекты в памяти. Автоматическое управление памятью со сборкой мусора — эмуляция такого бесконечного компьютера на конечной памятиРеймонд Чен. Наверняка вы думаете о сборке мусора неправильно . Многие ограничения сборщиков мусора (нет гарантии, что финализатор выполнится; управляет только памятью, но не другими ресурсами) вытекают из этой метафоры.
Основные принципы В системе со сборкой мусора обязанность освобождения памяти возлагается на среду исполнения программы. Программист лишь создаёт динамические объекты и пользуется ими, он может не заботиться об удалении объектов, поскольку это делает за него среда. Для этого в состав среды исполнения включается специальный программный модуль, называемый «сборщиком мусора». Этот модуль периодически запускается, определяет, какие из созданных в динамической памяти объектов больше не используются, и освобождает занимаемую ими память.
Периодичность запуска сборщика мусора определяется особенностями системы. Сборщик может работать в фоновом режиме, запускаясь при неактивности программы (например, когда программа простаивает, ожидая ввода данных пользователем). Сборщик мусора запускается безусловно, останавливая выполнение программы (), когда очередную операцию выделения памяти оказывается невозможно выполнить из-за того, что вся доступная память исчерпана. После освобождения памяти прерванная операция выделения памяти возобновляется, и программа продолжает исполняться дальше. Если же оказывается, что освободить память невозможно, среда исполнения останавливает программу с сообщением об ошибке «Недостаточно памяти».
Достижимость объекта Оптимальным было бы удалять из памяти объекты, к которым в процессе дальнейшей работы программы не будет ни одного обращения. Однако выявление таких объектов невозможно, поскольку сводится к алгоритмически неразрешимой задаче об остановке (для этого достаточно предположить, что некоторый объект X будет использован в том и только в том случае, если успешно завершится программа P). Поэтому сборщики мусора используют консервативные оценки, позволяющие гарантировать, что в будущем объект не будет использоваться.
Обычно критерием того, что объект ещё используется, является наличие ссылок на него: если в системе нет больше ссылок на данный объект, то он, очевидно, больше не может быть использован программой, а следовательно, может быть удалён. Этот критерий используется большинством современных сборщиков мусора и называется ещё достижимостью объекта. Он не является теоретически наилучшим, так как в число достижимых, согласно ему, попадают и те объекты, которые уже никогда не будут использованы, но на которые пока ещё существуют ссылки, но гарантирует защиту от появления «висячих» ссылок и может быть реализован достаточно эффективно.
Неформально можно задать следующее рекурсивное определение достижимого объекта: определённое множество объектов считается достижимым изначально — корневые объекты, обычно в их число включают все глобальные переменные и объекты, на которые есть ссылки в стеке вызовов; любой объект, на который есть ссылка из достижимого объекта, тоже считается достижимым, за исключением ссылок, указанных программистом как слабая.
Алгоритм выставления флагов Простой алгоритм определения достижимых объектов, «алгоритм пометок» (Mark and Sweep), заключается в следующем: для каждого объекта хранится бит, указывающий, достижим ли этот объект из программы или нет; изначально все объекты, кроме корневых, помечаются как недостижимые; рекурсивно просматриваются и помечаются как достижимые объекты, ещё не помеченные, и до которых можно добраться из корневых объектов по ссылкам; те объекты, у которых бит достижимости не был установлен, считаются недостижимыми.
Если два или более объектов ссылаются друг на друга, но ни на один из этих объектов нет ссылок извне, то вся группа считается недостижимой. Данный алгоритм позволяет гарантированно удалять группы объектов, использование которых прекратилось, но в которых имеются ссылки друг на друга. Такие группы часто называются «islands of isolation» (острова изоляции).
Алгоритм подсчёта ссылок Другой вариант алгоритма определения достижимости — обычный подсчёт ссылок. Его использование замедляет операции присваивания ссылок, но зато определение достижимых объектов тривиально — это все объекты, значение счётчика ссылок которых превышает нуль. Без дополнительных уточнений этот алгоритм, в отличие от предыдущего, не удаляет циклически замкнутые цепочки вышедших из употребления объектов, имеющих ссылки друг на друга.
Стратегии сборки мусора Как только определено множество недостижимых объектов, сборщик мусора может освободить память, занимаемую ими, и оставить остальное как есть. Также можно после освобождения памяти переместить все или часть оставшихся объектов в другие области памяти, обновив вместе с этим все ссылки на них. Эти два варианта реализации называются, соответственно, неперемещающим и перемещающим.
Обе стратегии имеют как достоинства, так и недостатки. Скорость выделения и освобождения памяти Неперемещающий сборщик мусора быстрее освобождает память (поскольку эта операция сводится к пометке соответствующих блоков памяти как свободных), но тратит больше времени на её выделение (поскольку память фрагментируется, и при выделении необходимо найти в памяти нужное количество блоков подходящего размера). Перемещающий сборщик требует сравнительно больше времени при сборе мусора (тратится дополнительное время на дефрагментацию памяти и изменение всех ссылок на перемещаемые объекты), зато перемещение позволяет использовать чрезвычайно простой и быстрый (O(1)) алгоритм выделения памяти. При дефрагментации объекты передвигаются так, чтобы разделить всю память на две большие области — занятую и свободную, и сохраняется указатель на их границу. Для выделения новой памяти достаточно лишь переместить эту границу, вернув кусок из начала свободной памяти. Скорость доступа к объектам в динамической памяти Объекты, поля которых используются совместно, перемещающий сборщик позволяет размещать в памяти недалеко друг от друга. Тогда они вероятнее окажутся в кэше процессора одновременно, что уменьшит количество обращений к относительно медленному ОЗУ. Совместимость с инородным кодом Перемещающий сборщик мусора вызывает затруднения при использовании кода, который не управляется системой автоматического управления памятью (такой код называется инородным () в традиционной терминологии или неуправляемым () в терминологии Microsoft). Указатель на память, выделенную в системе с неперемещающим сборщиком, можно просто передать инородному коду для использования, удерживая хотя бы одну обычную ссылку на объект, чтобы сборщик его не удалил. Перемещающий сборщик меняет положение объектов в памяти, синхронно меняя все ссылки на них, но поменять ссылки в инородном коде он не может, в результате переданные инородному коду ссылки после перемещения объекта станут некорректными. Для работы с инородным кодом используются различные специальные приёмы, например, pinning — явная блокировка объекта, запрещающая его перемещение во время сборки мусора.
Поколения объектов