В каких языках программирования используется сборщик мусора

Эта статья посвящена сборке мусора в управлении памятью. Сведения о сборке мусора на твердотельном диске см. в разделе Сборка мусора (SSD).

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

После этого содержимое рабочей памяти отбрасывается в пользу сжатой копии. А роли рабочей и свободной памяти обмениваются (изображаются).

В информатикесбор мусора (GC) — это форма автоматического управления памятью. Сборщик мусора пытается восстановить память. Которая была выделена программой. Но больше не упоминается—также называется мусором. Сбор мусора был изобретен американским компьютерным ученым Джоном Маккарти около 1959 года. Чтобы упростить ручное управление памятью в Lisp.]

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

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

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

Основные принципы сборки мусора состоят в том. Чтобы найти объекты данных в программе. Которые не могут быть доступны в будущем. И восстановить ресурсы. Используемые этими объектами.

Многие языки программирования требуют сборки мусора либо как часть спецификации языка (например, Java, C#, D,[3]Go и большинство скриптовых языков), либо эффективно для практической реализации (например. Формальные языки. Такие как лямбда-исчисление); они называются языками сбора мусора. Другие языки были разработаны для использования с ручным управлением памятью. Но имеют доступные реализации сборки мусора (например,

C и C++). Некоторые языки. Такие как Ada, Modula-3и C++/CLI, позволяют как сборку мусора . Так и ручное управление памятью сосуществовать в одном приложении. Используя отдельные кучи для собранных и управляемых вручную объектов; другие . Такие как D, собирают мусор. Но позволяют пользователю вручную удалять объекты. А также полностью отключать сборку мусора. Когда требуется скорость.

В то время как интеграция сборки мусора в компилятор языка

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

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

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

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

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

Недостатки

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

Штраф за удобство не аннотировать время жизни объекта вручную в исходном коде-это накладныерасходы . Которые могут привести к снижению или неравномерности производительности.[4] Рецензируемая статья 2005 года пришла к выводу. Что GC нуждается в пятикратном увеличении объема памяти. Чтобы компенсировать эти накладные расходы и выполнять столь же быстрое. Как и явное управление памятью.[5] Взаимодействие с эффектами иерархии памяти может сделать эти накладные расходы невыносимыми в условиях. Которые трудно предсказать или обнаружить при рутинном тестировании.

Влияние на производительность также было дано Apple в качестве причины для отказа от использования сборки мусора в iOS, несмотря на то. Что это была самая желаемая функция.]

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

Трассировка

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

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

Подсчет ссылок сборка мусора. Где каждый объект имеет подсчет количества ссылок на него.

Мусор идентифицируется по количеству ссылок. Равному нулю. Количество ссылок на объект увеличивается при создании ссылки на него и уменьшается при уничтожении ссылки. Когда количество достигает нуля. Память объекта восстанавливается.[7]

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

виртуальной памяти эксплуатацию.

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

Циклы
Если два или более объекта ссылаются друг на друга. Они могут создать цикл. В котором ни один из них не будет собран. Поскольку их взаимные ссылки никогда не позволяют их ссылочным счетам стать нулевыми. Некоторые системы сбора мусора, использующие подсчет ссылок (например, в CPython), используют специальные алгоритмы обнаружения циклов для решения этой проблемы.[8] Другая стратегия заключается в использовании

слабых ссылок для При подсчете ссылок слабая ссылка аналогична слабой ссылке при трассировке сборщика мусора. Это специальный ссылочный объект. Существование которого не увеличивает количество ссылок референтного объекта. Кроме того, слабая ссылка безопасна в том смысле, что . Когда референтный объект становится мусором. Любая слабая ссылка на него исчезает, вместо того чтобы оставаться висящей. А это означает. Что она превращается в предсказуемое значение. Такое как нулевая ссылка.

Накладные расходы на пространство (количество ссылок)
Подсчет ссылок требует. Чтобы для каждого объекта было выделено пространство для хранения его счетчика ссылок.

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

Часто архитектура фактически не позволяет программам получить доступ ко всему диапазону адресов памяти. Которые могут быть сохранены в ее собственном размере указателя; определенное количество старших битов в адресе либо игнорируется. Либо требуется равным нулю. Если объект надежно имеет указатель в определенном месте. То счетчик ссылок может быть сохранен в неиспользуемых битах указателя. Например, каждый объект в Objective-C имеет указатель на свой класс в начале своей памяти; в архитектуре ARM64 с использованием iOS 7, 19 неиспользуемых битов этого указателя класса используются для хранения количества ссылок объекта.

[9][10]

Накладные расходы на скорость (инкремент/декремент)
В наивных реализациях каждое назначение ссылки и каждая ссылка. Выпадающая из области действия. Часто требуют модификации одного или нескольких счетчиков ссылок. Однако в общем случае. Когда ссылка копируется из переменной внешней области в переменную внутренней области. Так что время жизни внутренней переменной ограничено временем жизни внешней. Приращение ссылки может быть исключено. Внешняя переменная В языке программирования C++ эта методика легко реализуется и демонстрируется с использованием

const Рекомендации. Подсчет ссылок в C++ обычно реализуется с помощью умных указателей[11] чьи конструкторы. Деструкторы и операторы присваивания управляют ссылками. Интеллектуальный указатель может быть передан по ссылке на функцию. Что позволяет избежать необходимости копирования-построения нового интеллектуального указателя (что увеличило бы количество ссылок при входе в функцию и уменьшило бы его при выходе). Вместо этого функция получает ссылку на интеллектуальный указатель. Который производится недорого. Метод подсчета ссылок Дойча-Боброва использует тот факт. Что большинство обновлений подсчета ссылок фактически генерируются ссылками. Хранящимися в локальных переменных.

Он игнорирует эти ссылки. Считая только ссылки в куче. Но прежде чем объект с нулевым количеством ссылок может быть удален. Система должна проверить с помощью сканирования стека и регистров. Что никакой другой ссылки на него все еще не существует. Дальнейшее существенное снижение накладных расходов на встречные обновления может быть достигнуто путем объединения обновлений введенных Леванони и Петранк.[12][13] Рассмотрим указатель. Который в заданном интервале выполнения обновляется несколько раз.

Сначала он указывает на объект O1, затем на объект O2и так далее . Пока в конце интервала он не указывает на какой-то объект On. Алгоритм подсчета ссылок обычно выполняет rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, …, rc(On)++. Но большинство этих обновлений являются избыточными. Для того чтобы правильно оценить количество ссылок в конце интервала. Достаточно выполнить rc(O1)--и rc(On)++. Леванони и Петранк измерили устранение более 99% обновлений счетчика в типичных тестах Java.

Требуется атомарность
При использовании в многопоточной среде эти модификации (инкремент и декремент) могут нуждаться в

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

Обновление coalescing by Levanoni and Petrank [12][13] может использоваться для устранения всех атомарных операций из барьера записи. Счетчики никогда не обновляются потоками программы в процессе выполнения программы. Они изменяются только коллектором. Который выполняется как один дополнительный поток без синхронизации.

Этот метод может быть использован в качестве механизма остановки параллельных программ. А также с параллельным сборщиком подсчета ссылок.

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

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

Escape — анализ-это метод времени компиляции . Который может преобразовать выделение кучи в выделение стека, тем самым уменьшая объем сборки мусора. Этот анализ определяет. Доступен ли объект. Выделенный внутри функции. За ее пределами. Если функция-локальное выделение оказывается доступным для другой функции или потока. Выделение называется “escape” и не может быть выполнено в стеке. В противном случае объект может быть выделен непосредственно в стеке и освобожден при возврате функции в обход кучи и связанных с ней затрат на управление памятью.[14]

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

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

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

БАЗОВЫЙ

BASIC и Logoчасто использовали сборку мусора для типов данных переменной длины . Таких как строки и списки. Чтобы не обременять программистов деталями управления памятью. На ранних микрокомпьютерах ЭЛЕМЕНТАРНАЯ сборка мусора могла вызвать необъяснимые паузы во время работы программы.[требуется цитирование]

Некоторые БАЗОВЫЕ интерпретаторы. Такие как Applesoft BASIC в семействе Apple II, многократно сканируют дескрипторы строк на наличие строки с самым высоким адресом. Чтобы сжать ее до высокой памяти. Что приводит к

O(n2){\displaystyle O(n^{2})}

повышению производительности. замена сборщика мусора для Applesoft BASIC. Опубликованная в Call-A. P. P. L. E. (январь 1981, страницы 40-45, Рэнди Уиггинтон), определяет группу строк в каждом проходе над кучей. Что значительно сокращает время сбора. БАЗОВЫЕ МОДЕЛИ.Система, выпущенная вместе с ProDOS в 1983 году был создан оконный сборщик мусора для BASIC. Который сокращает большинство коллекций до доли секунды.[требуется цитирование]

Objective-С

В то время как Objective-С традиционно нет сборки мусора, с выходом ОС х 10.5 в 2007 году компания Apple представила вывоз мусора для объективно-C 2.0, используя разработанный выполнения коллекционер.[17] однако, с 2012 года выпуска ОС X 10.8, вывоз мусора был объявлен устаревшим в пользу кода LLVMс автоматический счетчик ссылок (Arc). Которая была введена с ОС Х 10.7.[18] Более того, с мая 2015 года компания Apple запрещает использование сборки мусора для новой OS X-приложения в магазине приложений.[19][20] для иос, сборка мусора никогда не была введена из-за проблем с отзывчивостью и производительностью приложений;[6][21] вместо этого iOS использует ARC.]

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

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

Java

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

Использование

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

Эта форма сбора мусора была изучена в языке программирования Mercury[26], и она увидела большее использование с введением автоматического счетчика ссылок LLVM (ARC) в экосистему Apple (iOS и OS X) в 2011.[22][23][19]

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

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

В алгоритме Бейкера распределение выполняется в любой половине одной области памяти. Когда он заполняется наполовину. Выполняется сборка мусора. Которая перемещает живые объекты в другую половину. А остальные объекты неявно освобождаются. Запущенная программа ([30]

Поколенческие схемы сбора мусора основаны на эмпирическом наблюдении. Что большинство объектов умирают молодыми. В поколенческой сборке мусора сохраняются две или более областей выделения (поколений). Которые хранятся отдельно в зависимости от возраста объекта. Новые объекты создаются в Иногда выполняется полное сканирование.

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

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

  1. ^
  2. ^ Маккарти, Джон (1960). . Коммуникации АСМ. 3 (4): 184–195. doi:10.1145/367177.367199. S2CID 1489409. Проверено 2009-05-29.
  3. ^ . dlang.org. Цифровой Марс. 2014-07-29.
  4. ^ Zorn, Benjamin (1993-01-22). Практика и опыт работы с программнымобеспечением . Факультет компьютерных наук, Университет Колорадо в Боулдере. 23 (7): 733–756. CiteSeerX 10.1.1.14.1816. doi:10.1002/spe.4380230704. S2CID 16182444.
  5. ^ Мэтью Герц; Эмери Д. Бергер (2005). Явное управление памятью (PDF). Материалы 20-й ежегодной конференции ACM SIGPLAN по объектно — ориентированному программированию, системам. Языкам и приложениям-OOPSLA ’05. p. 313. doi:10.1145/1094811.1094836. ISBN 1595930310. S2CID 6570650. Проверено 2015-03-15.
  6. ^ b (PDF). WWDC 2011. Apple, inc. 2011-06-24. Проверено 2015-03-27.
  7. ^ Сборка Мусора Подсчета Ссылок
  8. ^ . Расширение и встраивание интерпретатора Python. 2008-02-21. Проверено 2014-05-22.
  9. ^ Майк Эш. . mikeash.com. Проверено 2014-04-27.
  10. ^ . Sealiesoftware.com 2013-09-24 . Проверено 2014-04-27.
  11. ^ RAII, Динамические объекты и фабрики в C++, Roland Pibinger, 3 мая 2005 г.
  12. ^ b Йоси Леванони, Эрез Петранк (2001). . Материалы 16-й конференции ACM SIGPLAN по объектно-ориентированному программированию, системам. Языкам и приложениям. OOPSLA 2001. Стр. 367-380. doi:10.1145/504282.504309.
  13. ^ b Йосси Леванони, Эрез Петранк (2006). . ACM Trans. Программа. Lang. Сист. 28: 31-69. CiteSeerX 10.1.1.15.9106. doi:10.1145/1111596.1111597. S2CID 14777709.
  14. ^ Salagnac, G; et al. (2005-05-24). . Электронные заметки по теоретической информатике. 131: 99–110. doi:10.1016/j.entcs.2005.01.026.
  15. ^ Чизнолл, Дэвид (2011-01-12). Влиятельные языки программирования, Часть 4: Лисп.
  16. ^ . php.net. Проверено 2015-01-14.
  17. ^ Обзор Objective-C 2.0
  18. ^ Mac OS X 10.7 Lion: обзор Ars Technica John Siracusa (20 июля 2011)
  19. ^ b Apple говорит. Что создатели приложений Mac должны перейти на управление памятью ARC к маю от AppleInsider (20 февраля 2015 г.)
  20. ^ Cichon, Waldemar (2015-02-21). . Heise.de. Проверено 2015-03-30.
  21. ^ Сильва, Прешес (2014-11-18). . Международные деловые времена. Проверено 2015-04-07.
  22. ^ b Роб Нейпир. Мугунт Кумар (2012-11-20). Программирование iOS 6 Толкает предел. Джон Уайли и сыновья. ISBN 9781118449974. 2015-03-30 .
  23. ^ b Cruz, José R.C. (2012-05-22). . Доктор Доббс. Проверено 2015-03-30.
  24. ^ Fu, Wei; Hauser, Carl (2005). Материалы семинара 2005 года по программному обеспечению и компиляторам для встраиваемых систем — SCOPES ’05. pp. 20-26. doi:10.1145/1140389.1140392. ISBN 1595932070. S2CID 8635481.
  25. ^ Tene, Gil; Iyengar, Balaji; Wolf, Michael (2011). (PDF). ISMM ’11: Материалы международного симпозиума по управлению памятью. doi:10.1145/1993478. ISBN 9781450302630.
  26. ^ Мазур, Нанси (май 2004). Сборка мусора во время компиляции для декларативного языка Mercury (PDF) (Тезис). Katholieke Universiteit Leuven.
  27. ^ Huelsbergen, Lorenz; Winterbottom. Phil (1998). (PDF). Труды Первого Международного симпозиума по управлению памятью — ISMM ’98. стр. 166-175. doi:10.1145/286860.286878. ISBN 1581131143. S2CID 14399427.
  28. ^ .
  29. ^ Либерман, Генри; Хьюитт, Карл (1983). . Коммуникации АСМ. 26 (6): 419–429. doi:10.1145/358141.358147. лпвп:1721,1/6335. S2CID 14161480.
  30. ^ Бейкер, Генри Г. (1978). Коммуникации АСМ. 21 (4): 280–294. doi:10.1145/359460.359470. лпвп:1721,1/41976. S2CID 17661259. см. Также описание
  31. McCloskey, Bacon, Cheng. Grove., 2008.

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

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