Сборка мусора (информатика) - Garbage collection (computer science)

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

В информатике , сбор мусора ( GC ) является одной из форм автоматического управления памятью . В сборщик мусора пытается вернуть себе память , которая была выделенные программой, но уже не упоминаться-также называют мусором . Сборка мусора была изобретена американским ученым-компьютерщиком Джоном Маккарти примерно в 1959 году для упрощения ручного управления памятью в Лиспе .

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

Другие ресурсы, кроме памяти, такие как сетевые сокеты , дескрипторы базы данных , окна взаимодействия с пользователем , дескрипторы файлов и устройств, обычно не обрабатываются сборкой мусора. Методы управления такими ресурсами, особенно деструкторами , также могут быть достаточными для управления памятью, не оставляя необходимости в сборке мусора. Некоторые системы GC позволяют ассоциировать такие другие ресурсы с областью памяти, которая при сборе вызывает работу по возврату этих ресурсов.

Принципы

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

Многие языки программирования требуют сборки мусора либо как часть спецификации языка (например, Java , C # , D , Go и большинство языков сценариев ), либо эффективно для практической реализации (например, формальные языки, такие как лямбда-исчисление ); говорят, что это языки со сборкой мусора . Другие языки были разработаны для использования с ручным управлением памятью, но для них доступны реализации со сборкой мусора (например, C и C ++ ). Некоторые языки, такие как Ada , Modula-3 и C ++ / CLI , позволяют сосуществовать как сборке мусора, так и ручному управлению памятью в одном приложении, используя отдельные кучи для собранных и управляемых вручную объектов; другие, такие как D , собирают мусор, но позволяют пользователю вручную удалять объекты, а также полностью отключать сборку мусора, когда требуется скорость.

В то время как интеграция сборки мусора в компилятор языка и систему времени выполнения обеспечивает гораздо более широкий выбор методов, существуют системы post-hoc GC, такие как автоматический подсчет ссылок (ARC), в том числе те, которые не требуют перекомпиляции. ( Post-Hoc GC иногда отличается в коллекции мусора .) Сборщик мусора почти всегда будет тесно интегрирован с распределителем памяти .

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

Сборка мусора освобождает программиста от ручного освобождения памяти. Это устраняет или уменьшает некоторые категории ошибок :

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

Недостатки

Сборка мусора потребляет вычислительные ресурсы при принятии решения, какую память освободить, даже если программист, возможно, уже знал эту информацию. Наказанием за удобство отсутствия ручного аннотирования времени существования объекта в исходном коде являются накладные расходы , которые могут привести к снижению или неравномерной производительности. В рецензируемой статье 2005 года был сделан вывод, что сборщику мусора требуется в пять раз больше памяти, чтобы компенсировать эти накладные расходы и работать так же быстро, как та же программа с использованием идеализированного явного управления памятью, путем вставки аннотаций с помощью оракула, реализованного путем сбора трассировок из программ. запустить под профилировщиком. Однако программисты, такие как Джон Харроп, утверждают, что такая базовая линия нереальна, поскольку программисты редко пишут оптимальный явный код управления памятью. Взаимодействие с эффектами иерархии памяти может сделать эти накладные расходы невыносимыми в обстоятельствах, которые трудно предсказать или обнаружить при рутинном тестировании. Влияние на производительность также было названо Apple причиной отказа от внедрения сборки мусора в iOS, несмотря на то, что это самая желанная функция.

Момент, когда мусор действительно собирается, может быть непредсказуемым, что приводит к остановкам (паузам для сдвига / освобождения памяти), разбросанным по всему сеансу. Непредсказуемые задержки могут быть неприемлемыми в средах реального времени , при обработке транзакций или в интерактивных программах. Инкрементные, параллельные сборщики мусора и сборщики мусора в реальном времени решают эти проблемы с различными компромиссами.

Стратегии

Отслеживание

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

Подсчет ссылок

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

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

Подсчет ссылок имеет ряд недостатков; обычно это можно решить или смягчить с помощью более сложных алгоритмов:

Циклы
Если два или более объекта ссылаются друг на друга, они могут создать цикл, в котором ни один из них не будет собран, поскольку их взаимные ссылки никогда не позволяют их счетчикам ссылок становиться равными нулю. Некоторые системы сбора мусора, использующие подсчет ссылок (например, в CPython ), используют определенные алгоритмы обнаружения цикла для решения этой проблемы. Другая стратегия - использовать слабые ссылки для «обратных указателей», которые создают циклы. При подсчете ссылок слабая ссылка аналогична слабой ссылке при отслеживании сборщика мусора. Это специальный объект ссылки, существование которого не увеличивает счетчик ссылок объекта ссылки. Более того, слабая ссылка безопасна в том смысле, что, когда объект-референт становится мусором, любая слабая ссылка на него теряет силу , вместо того, чтобы оставаться висящей, что означает, что она превращается в предсказуемое значение, такое как пустая ссылка.
Накладные расходы на пространство (количество ссылок)
Подсчет ссылок требует, чтобы для каждого объекта было выделено пространство для хранения его счетчика ссылок. Счетчик может храниться рядом с памятью объекта или в дополнительной таблице где-то еще, но в любом случае каждый отдельный объект со счетчиком ссылок требует дополнительного хранилища для своего счетчика ссылок. Для этой задачи обычно используется пространство памяти с размером беззнакового указателя, что означает, что для каждого объекта должно быть выделено 32 или 64 бита хранилища счетчика ссылок. В некоторых системах можно уменьшить эти накладные расходы, используя тегированный указатель для хранения счетчика ссылок в неиспользуемых областях памяти объекта. Часто архитектура фактически не позволяет программам получить доступ ко всему диапазону адресов памяти, которые могут быть сохранены в ее собственном указателе размера; определенное количество старших битов в адресе либо игнорируется, либо должно быть равно нулю. Если объект надежно имеет указатель в определенном месте, счетчик ссылок может храниться в неиспользуемых битах указателя. Например, каждый объект в Objective-C имеет указатель на свой класс в начале своей памяти; в архитектуре ARM64 с iOS 7 19 неиспользуемых бит указателя этого класса используются для хранения счетчика ссылок на объект.
Накладные расходы по скорости (увеличение / уменьшение)
В наивных реализациях каждое присвоение ссылки и каждая ссылка, выходящая за пределы области действия, часто требует модификации одного или нескольких счетчиков ссылок. Однако в общем случае, когда ссылка копируется из переменной внешней области видимости во внутреннюю переменную области видимости, так что время жизни внутренней переменной ограничено временем жизни внешней, увеличение ссылки может быть исключено. Внешняя переменная «владеет» ссылкой. В языке программирования C ++ этот прием легко реализуется и демонстрируется с помощью constссылок. Подсчет ссылок в C ++ обычно реализуется с помощью « умных указателей », конструкторы, деструкторы и операторы присваивания которых управляют ссылками. Интеллектуальный указатель может быть передан по ссылке на функцию, что позволяет избежать необходимости копировать-конструировать новый интеллектуальный указатель (который увеличит счетчик ссылок при входе в функцию и уменьшит его при выходе). Вместо этого функция получает ссылку на интеллектуальный указатель, который производится недорого. Метод подсчета ссылок Дойча-Боброу основан на том факте, что большинство обновлений счетчика ссылок фактически генерируются ссылками, хранящимися в локальных переменных. Он игнорирует эти ссылки, только подсчитывая ссылки в куче, но перед тем, как объект с нулевым счетчиком ссылок может быть удален, система должна проверить с помощью сканирования стека и регистрации, что никакой другой ссылки на него еще не существует. Дальнейшее существенное снижение накладных расходов на обновления счетчиков может быть получено за счет объединения обновлений, введенного Леванони и Петранком . Рассмотрим указатель, который в заданном интервале выполнения обновляется несколько раз. Сначала он указывает на объект O1, затем на объект O2и так далее, пока в конце интервала не указывает на какой-либо объект On. Алгоритм подсчета ссылок, как правило , выполнять rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Но большинство этих обновлений избыточны. Для правильной оценки счетчика ссылок в конце интервала достаточно выполнить rc(O1)--и rc(On)++. Леванони и Петранк измерили устранение более 99% обновлений счетчиков в типичных тестах Java.
Требуется атомарность
При использовании в многопоточной среде эти модификации (увеличение и уменьшение) могут потребовать выполнения атомарных операций, таких как сравнение и замена , по крайней мере, для любых объектов, которые являются общими или потенциально совместно используемыми несколькими потоками. Атомарные операции дороги для мультипроцессора и даже дороже, если их нужно эмулировать с помощью программных алгоритмов. Эту проблему можно избежать, добавив счетчики ссылок для каждого потока или процессора и обращаясь к глобальному счетчику ссылок только тогда, когда локальные счетчики ссылок становятся или больше не равны нулю (или, в качестве альтернативы, используя двоичное дерево счетчиков ссылок, или даже отказ от детерминированного уничтожения в обмен на полное отсутствие глобального счетчика ссылок), но это добавляет значительные накладные расходы на память и, таким образом, имеет тенденцию быть полезным только в особых случаях (например, при подсчете ссылок модулей ядра Linux ). Объединение обновлений с помощью Levanoni и Petrank можно использовать для устранения всех атомарных операций с барьера записи. Счетчики никогда не обновляются потоками программы в процессе выполнения программы. Они изменяются только сборщиком, который выполняется как один дополнительный поток без синхронизации. Этот метод можно использовать в качестве механизма остановки для параллельных программ, а также с параллельным сборщиком подсчета ссылок.
Не в реальном времени
Наивные реализации подсчета ссылок обычно не обеспечивают поведение в реальном времени, потому что любое присвоение указателя потенциально может вызвать рекурсивное освобождение ряда объектов, ограниченных только общим размером выделенной памяти, в то время как поток не может выполнять другую работу. Этой проблемы можно избежать, делегировав освобождение объектов, на которые нет ссылок, другим потокам за счет дополнительных накладных расходов.

Анализ побега

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

Доступность

Вообще говоря, языки программирования более высокого уровня , скорее всего, будут иметь сборку мусора как стандартную функцию. В некоторых языках, в которых нет встроенной сборки мусора, ее можно добавить через библиотеку, как, например, сборщик мусора Boehm для C и C ++.

Большинство языков функционального программирования , таких как ML , Haskell и APL , имеют встроенную сборку мусора. Lisp особенно примечателен как первый язык функционального программирования, так и первый язык, в котором реализована сборка мусора.

Другие динамические языки, такие как Ruby и Julia (но не Perl  5 или PHP до версии 5.3, в которых используется подсчет ссылок), JavaScript и ECMAScript, также имеют тенденцию использовать GC. Объектно-ориентированные языки программирования, такие как Smalltalk и Java, обычно предоставляют интегрированную сборку мусора. Заметными исключениями являются C ++ и Delphi , у которых есть деструкторы .

БАЗОВЫЙ

BASIC и Logo часто используют сборку мусора для типов данных переменной длины, таких как строки и списки, чтобы не обременять программистов подробностями управления памятью. На Altair 8800 программы с большим количеством строковых переменных и небольшим строковым пространством могут вызывать длительные паузы из-за сборки мусора. Точно так же алгоритм сборки мусора интерпретатора Applesoft BASIC многократно сканирует строковые дескрипторы для строки с наивысшим адресом, чтобы сжать ее в сторону верхней памяти, что приводит к повышению производительности и делает паузы от нескольких секунд до нескольких минут. Заменяющий сборщик мусора для Applesoft BASIC от Randy Wigginton идентифицирует группу строк при каждом проходе по куче, значительно сокращая время сборки. BASIC.System, выпущенная вместе с ProDOS в 1983 году, предоставляет оконный сборщик мусора для BASIC, который работает во много раз быстрее.

Цель-C

В то время как Objective-C традиционно не имел сборки мусора, с выпуском OS X 10.5 в 2007 году Apple представила сборку мусора для Objective-C  2.0, используя собственный сборщик времени выполнения. Тем не менее, с выпуском 2012 OS X 10.8 , сбор мусора был устаревшим в пользу LLVM «ы автоматического счетчика ссылок (ARC) , которая была введена с OS X 10.7 . Более того, с мая 2015 года Apple даже запрещает использование сборки мусора для новых приложений OS X в App Store . Для iOS сборка мусора никогда не применялась из-за проблем с реактивностью и производительностью приложений; вместо этого iOS использует ARC.

Ограниченная среда

Сборка мусора редко используется во встроенных системах или системах реального времени из-за обычной необходимости очень жесткого контроля над использованием ограниченных ресурсов. Однако были разработаны сборщики мусора, совместимые со многими ограниченными средами. Microsoft .NET Micro Framework , .NET nanoFramework и Java Platform, Micro Edition - это встраиваемые программные платформы, которые, как и их более крупные собратья, включают сборку мусора.

Джава

Сборщики мусора, доступные в Java JDK, включают:

Использование во время компиляции

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

Эта форма сбора мусора была изучена в языке программирования Mercury , и он видел более широкое использование с введением LLVM «s автоматических счетчика ссылок (ARC) в экосистему Apple (IOS и OS X) в 2011 году.

Системы реального времени

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

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

Схемы сборки мусора , созданные поколениями , основаны на эмпирическом наблюдении, что большинство объектов умирают молодыми. При сборке мусора по поколениям сохраняются две или более области распределения (поколения), которые хранятся отдельно в зависимости от возраста объекта. Новые объекты создаются в «молодом» поколении, которое регулярно собирается, и когда поколение заполнено, объекты, на которые все еще ссылаются из более старых регионов, копируются в следующее старшее поколение. Иногда выполняется полное сканирование.

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

Большинство реализаций сборщиков мусора в реальном времени используют трассировку . Такие сборщики мусора в реальном времени сталкиваются с жесткими ограничениями реального времени при использовании с операционной системой реального времени.

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки