Отслеживание сборки мусора - Tracing garbage collection

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

Досягаемость объекта

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

  1. Выделенный набор корней: объекты, которые считаются достижимыми. Обычно они включают все объекты, на которые есть ссылки из любого места в стек вызовов (это все локальные переменные и параметры в вызываемых функциях), и любые глобальные переменные.
  2. Все, на что ссылается достижимый объект, само доступно; более формально достижимость - это переходное закрытие.

Определение достижимости «мусора» не является оптимальным, поскольку последний раз программа использует объект задолго до того, как этот объект выпадет из области действия среды. Иногда проводится различие между синтаксический мусор, те объекты, которые программа не может достичь, и семантический мусор, эти объекты программа фактически никогда больше не будет использовать. Например:

Объект Икс = новый Фу();Объект у = новый Бар();Икс = новый Quux();/ * На этом этапе мы знаем, что объект Foo  * изначально присвоено x, никогда не будет * доступ: это синтаксический мусор. */если (Икс.check_something()) {    Икс.сделай что-нибудь(у);}Система.выход(0);/ * В приведенном выше блоке y * может быть семантическим мусором; * но мы не узнаем, пока x.check_something () не вернет * какое-то значение - если оно вообще вернется. */

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

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

Сильные и слабые ссылки

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

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

В некоторых реализациях слабые ссылки делятся на подкатегории. Например, Виртуальная машина Java предоставляет три формы слабых ссылок, а именно мягкие ссылки,[1] фантомные ссылки,[2] и регулярные слабые ссылки.[3] Объект с мягкими ссылками может быть восстановлен только в том случае, если сборщик мусора решит, что программе не хватает памяти. В отличие от мягкой ссылки или обычной слабой ссылки, фантомная ссылка не предоставляет доступа к объекту, на который она ссылается. Вместо этого фантомная ссылка - это механизм, который позволяет сборщику мусора уведомлять программу, когда объект, на который указывает ссылка, стал фантомная достижимость. Объект является фантомно достижимым, если он все еще находится в памяти и на него ссылается фантомная ссылка, но его финализатор уже выполнен. По аналогии, Microsoft.NET предоставляет две подкатегории слабых ссылок,[4] а именно длинные слабые ссылки (воскрешение треков) и короткие слабые ссылки.

Слабые коллекции

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

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

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

Базовый алгоритм

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

Наивная метка и размах

Наивная метка в действии на куча содержащий восемь объекты. Стрелки представляют ссылки на объекты. Круги представляют сами объекты. Объекты № 1, № 2, № 3, № 4 и № 6 строго связаны из корневого набора. С другой стороны, объекты # 5, # 7 и # 8 не имеют прямых или косвенных ссылок из корневого набора; следовательно, они мусор.

В наивном методе отметки и очистки каждый объект в памяти имеет флаг (обычно один бит), зарезервированный только для использования при сборке мусора. Этот флаг всегда очищен, кроме периода сбора.

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

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

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

Трехцветная маркировка

Пример трехцветной маркировки на куче с 8 объектами. Белые, серые и черные объекты представлены соответственно светло-серым, желтым и синим цветом.

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

Созданы три набора - белый, чернить и серый:

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

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

  1. Выберите объект из серого набора и переместите его в черный набор.
  2. Переместите каждый белый объект, на который он ссылается, в серый набор. Это гарантирует, что ни этот объект, ни какой-либо объект, на который он ссылается, не могут быть собраны в мусор.
  3. Повторяйте последние два шага, пока серый набор не станет пустым.

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

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

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

Стратегии реализации

Движение против неподвижного

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

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

  • Никаких дополнительных работ по освоению освобожденного от мертвых предметов пространства не требуется; всю область памяти, из которой были перемещены доступные объекты, можно считать свободным пространством. Напротив, неподвижный сборщик мусора должен посещать каждый недостижимый объект и записывать, что занимаемая им память доступна.
  • Точно так же можно очень быстро разместить новые объекты. Поскольку большие непрерывные области памяти обычно предоставляются движущимся сборщиком мусора, новые объекты могут быть выделены путем простого увеличения указателя «свободной памяти». Неподвижная стратегия может через некоторое время привести к сильному фрагментированный куча, требующая дорогостоящего обращения к «свободным спискам» небольших доступных блоков памяти для размещения новых объектов.
  • Если используется соответствующий порядок обхода (например, cdr-first для списка кончает ) объекты можно перемещать очень близко к объектам, на которые они ссылаются в памяти, увеличивая вероятность того, что они будут расположены в той же строка кеша или же виртуальная память страница. Это может значительно ускорить доступ к этим объектам через эти ссылки.

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

Копирование против маркировки и развертки против маркировки и не очистки

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

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

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

А отметить и подметать Сборщик мусора хранит бит или два с каждым объектом для записи, является ли он белым или черным. Серый набор хранится в виде отдельного списка или с использованием другого бита. Поскольку дерево ссылок просматривается во время цикла сбора (фаза «метки»), эти биты обрабатываются сборщиком. Последний "проход" по областям памяти освобождает белые объекты. Стратегия отметки и зачистки имеет то преимущество, что после определения запрещенного набора можно использовать либо подвижную, либо неподвижную стратегию сбора. Этот выбор стратегии может быть сделан во время выполнения, если позволяет доступная память. Его недостатком является «раздувание» объектов на небольшое количество, например, каждый объект имеет небольшую стоимость скрытой памяти из-за списка / дополнительного бита. Это может быть несколько смягчено, если сборщик также обрабатывает выделение, поскольку тогда он потенциально может использовать неиспользуемые биты в структурах данных выделения. Или эту «скрытую память» можно устранить с помощью Указатель с тегами, меняя стоимость памяти на процессорное время. Тем не менее отметить и подметать - это единственная стратегия, которая в первую очередь охотно взаимодействует с внешними распределителями.

А отмечать и не подметать Сборщик мусора, как и mark-and-sweep, сохраняет бит с каждым объектом, чтобы записать, белый он или черный; серый набор хранится как отдельный список или с использованием другого бита. Здесь есть два ключевых отличия. Во-первых, черное и белое означают разные вещи, чем в сборщике отметок и подметаний. В коллекторе «пометить и не подметать» все доступные объекты всегда черные. В момент размещения объект помечается черным, и он останется черным, даже если станет недоступным. Белый объект - это неиспользуемая память и может быть выделена. Во-вторых, может измениться интерпретация битов черного / белого. Первоначально бит черного / белого может иметь значение (0 = белый, 1 = черный). Если при операции выделения памяти не удается найти доступную (белую) память, это означает, что все объекты помечаются как использованные (черным). Затем значение бит черного / белого инвертируется (например, 0 = черный, 1 = белый). Все становится белым. Это на мгновение нарушает инвариант, согласно которому достижимые объекты являются черными, но сразу же следует полная фаза маркировки, чтобы снова пометить их черным. Как только это будет сделано, вся недостижимая память станет белой. Никакой фазы "развертки" не требуется.

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

В отмечать и не подметать поэтому стратегию можно рассматривать как компромисс между достоинствами и недостатками отметить и подметать и остановить и скопировать стратегии.

GC поколения (эфемерный GC)

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

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

Унгар Классическое поколение мусорщиков насчитывает два поколения. Он разделяет самое молодое поколение, называемое «новым пространством», на большой «рай», в котором создаются новые объекты, и два меньших «пространства выживших», пространство прошлого и пространство будущих выживших. Объекты в старом поколении, которые могут ссылаться на объекты в новом пространстве, хранятся в «запоминаемом наборе». При каждой уборке объекты в новом пространстве отслеживаются от корней в запомненном наборе и копируются в пространство будущего выжившего. Если пространство будущего выжившего заполняется, объекты, которые не подходят, перемещаются в старое пространство, процесс, называемый «владение». В конце уборки некоторые объекты находятся в пространстве будущего выжившего, а пространство Эдема и прошлого выжившего пусто. Затем пространство будущего выжившего и пространство прошлого выжившего меняются местами, и программа продолжается, выделяя объекты в eden. В оригинальной системе Ангара Эдем в 5 раз больше, чем место каждого выжившего.

Сборка мусора поколений - это эвристический подход, и некоторые недостижимые объекты не могут быть восстановлены в каждом цикле. Поэтому иногда может потребоваться выполнить полную отметку и очистку или копирование сборки мусора, чтобы освободить все доступное пространство. Фактически, исполняющие системы для современных языков программирования (таких как Ява и .NET Framework ) обычно используют некий гибрид различных стратегий, которые были описаны до сих пор; например, в большинстве циклов сбора данных может рассматриваться только несколько поколений, в то время как иногда выполняется метка и очистка, а еще реже выполняется полное копирование для борьбы с фрагментацией. Термины «малый цикл» и «большой цикл» иногда используются для описания этих различных уровней агрессии коллекционера.

Stop-the-world против инкрементального против одновременного

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

Это имеет очевидный недостаток, заключающийся в том, что программа не может выполнять полезную работу во время выполнения цикла сбора (иногда называемого «неловкой паузой»).[6]). Поэтому сборка мусора Stop-the-world в основном подходит для неинтерактивных программ. Его преимущество в том, что его проще реализовать и быстрее, чем инкрементная сборка мусора.

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

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

Точные против консервативных и внутренних указателей

Некоторые сборщики могут правильно идентифицировать все указатели (ссылки) в объекте; они называются точный (также точный или же точный) коллекционеры, напротив консервативный или же частично консервативный коллектор. Консервативные сборщики предполагают, что любой битовый шаблон в памяти может быть указателем, если, интерпретируемый как указатель, он будет указывать на выделенный объект. Консервативные сборщики могут давать ложные срабатывания, когда неиспользуемая память не освобождается из-за неправильной идентификации указателя. На практике это не всегда проблема, если программа не обрабатывает большое количество данных, которые легко могут быть ошибочно идентифицированы как указатель. Ложные срабатывания обычно менее проблематичны 64-битный системы, чем на 32-битный систем, потому что диапазон допустимых адресов памяти, как правило, составляет крошечную часть диапазона 64-битных значений. Таким образом, произвольный 64-битный шаблон вряд ли имитирует действительный указатель. Ложноотрицательный результат может также произойти, если указатели «скрыты», например, при использовании Связанный список XOR. Практичность точного сборщика обычно зависит от свойств безопасности типа рассматриваемого языка программирования. Примером, для которого может потребоваться консервативный сборщик мусора, является Язык C, который позволяет преобразовывать типизированные (непустые) указатели в нетипизированные (недействительные) указатели и наоборот.

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

Спектакль

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

Что касается пропускной способности, трассировка по своей природе требует некоторой неявной среды выполнения. накладные расходы, хотя в некоторых случаях амортизированная стоимость может быть чрезвычайно низкой, а в некоторых случаях даже ниже, чем одна инструкция на выделение или сбор данных, превосходя выделение стека.[7] Ручное управление памятью требует накладных расходов из-за явного освобождения памяти, а подсчет ссылок имеет накладные расходы из-за увеличения и уменьшения счетчиков ссылок и проверки того, не переполнился ли счетчик или упал до нуля.[нужна цитата ]

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

Выделение кучи вручную
  • поиск наиболее подходящего / подходящего блока достаточного размера
  • бесплатное ведение списка
Вывоз мусора
  • находить доступные объекты
  • копировать доступные объекты для движущихся коллекторов
  • барьеры чтения / записи для инкрементных сборщиков
  • поиск наиболее подходящего / подходящего блока и бесплатное ведение списков неподвижных коллекторов

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

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

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

Детерминизм

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

Сборка мусора в реальном времени

Хотя сборка мусора обычно недетерминирована, ее можно использовать в жестких в реальном времени системы. Сборщик мусора в реальном времени должен гарантировать, что даже в худшем случае он выделит определенное количество вычислительных ресурсов для потоков-мутаторов. Ограничения, накладываемые на сборщик мусора в реальном времени, обычно основаны либо на работе, либо на времени. Ограничение на основе времени будет выглядеть так: в каждом временном окне продолжительности Т, потокам мутатора должно быть разрешено работать хотя бы в течение Тм время. Для анализа работы, MMU (минимальное использование мутатора)[9] обычно используется в качестве ограничения в реальном времени для алгоритма сборки мусора.

Одна из первых реализаций жесткий режим реального времени сборщик мусора для JVM был основан на Алгоритм метронома,[10] чья коммерческая реализация доступна как часть IBM WebSphere в реальном времени.[11] Еще один алгоритм сборки мусора в реальном времени - Staccato, доступный в IBM с J9 JVM, который также обеспечивает масштабируемость для больших многопроцессорных архитектур, обеспечивая при этом различные преимущества перед Metronome и другими алгоритмами, которые, наоборот, требуют специализированного оборудования.[12]

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

Рекомендации

  1. ^ "Класс SoftReference ". Стандарт платформы Java ™ Под ред. 7. Oracle. Получено 25 мая 2013.
  2. ^ "Класс PhantomReference ". Стандарт платформы Java ™ Под ред. 7. Oracle. Получено 25 мая 2013.
  3. ^ "Класс WeakReference ". Стандарт платформы Java ™ Под ред. 7. Oracle. Получено 25 мая 2013.
  4. ^ "Слабые ссылки". .NET Framework 4.5. Microsoft. Получено 25 мая 2013.
  5. ^ «Копирование и закрепление». Msdn2.microsoft.com. Получено 9 июля 2010.
  6. ^ Стил, Гай Л. (сентябрь 1975 г.). «Многопроцессорная компактификация сборки мусора». Коммуникации ACM. 18 (9): 496.
  7. ^ Аппель, Эндрю В. (17 июня 1987 г.). «Сборка мусора может быть быстрее, чем выделение стека». Письма об обработке информации. 25 (4): 275–279. CiteSeerX  10.1.1.49.2537. Дои:10.1016 / 0020-0190 (87) 90175-Х.CS1 maint: ref = harv (связь)
  8. ^ «Распределение памяти во встроенных системах». Eros-os.org. Получено 29 марта 2009.
  9. ^ Ченг, Перри; Блеллох, Гай Э. (22 июня 2001 г.). «Параллельный сборщик мусора в реальном времени» (PDF). Уведомления ACM SIGPLAN. 36 (5): 125–136. Дои:10.1145/381694.378823.
  10. ^ «Метроном: более простой подход к сборке мусора в системах реального времени» (PDF).
  11. ^ «Java в реальном времени. Часть 4: Сборка мусора в реальном времени».
  12. ^ Макклоски, Билл; Бэкон, Дэвид Ф .; Ченг, Перри; Гроув, Дэвид (22 февраля 2008 г.). "Staccato: параллельный и параллельный сборщик мусора в реальном времени для мультипроцессоров" (PDF). Получено 11 марта 2014.