Трассировка сборки мусора

редактировать

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

Содержание

  • 1 Достижимость объекта
  • 2 Сильные и слабые ссылки
  • 3 Слабые коллекции
  • 4 Базовый алгоритм
    • 4.1 Простая маркировка
    • 4.2 Трехцветная маркировка
  • 5 Стратегии реализации
    • 5.1 Перемещение по сравнению с неподвижным
    • 5.2 Копирование по сравнению с меткой и разверткой и меткой и без очистки
    • 5.3 Сборщик мусора поколений (эфемерный сборщик мусора)
    • 5.4 Остановить мир против инкрементальных и параллельных
    • 5.5 Точных против консервативных и внутренних указателей
  • 6 Производительность
  • 7 Детерминизм
  • 8 Сборка мусора в реальном времени
  • 9 См. Также
  • 10 ссылок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наивная метка и очистка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Перемещение и неподвижность

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

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

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

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

Копирование vs. mark-and-sweep vs.-mark-and-not-sweep

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

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

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

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

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

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

Стратегия и не развернуть, следовательно, может

Последняя правка сделана 2021-06-11 09:05:03
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте