Как сборщики мусора отслеживают все живые объекты?

Question

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

1. Как поддерживается этот список?Хранит ли среда выполнения для языков GC гигантский список всех объектов?

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

Answer 1

1. Система управления памятью отслеживает размер каждого выделенного объекта, как это происходит в C или C ++. Один из способов, как это обычно делается, состоит в том, чтобы система управления памятью выделяла дополнительные size_t перед каждым выделением, что отслеживает размер каждого объекта. Менеджер памяти также должен отслеживать размер каждого свободного блока, чтобы он мог повторно использовать блоки для их распределения.

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

   В фазе очистки сборщик мусора проходит кучу снизу вверх, переходя от распределения к распределению на основе этих size_t с, и освобождает все, что не отмечено.

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

---

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

Answer 2

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

Не совсем. GC делятся на отслеживание и подсчет ссылок (см. Единая теория сбора мусора ). Трассирующие GC начинаются с набора глобальных корней и отслеживают все доступные им объекты. GC подсчета ссылок подсчитывает количество ссылок на каждый объект и восстанавливает его, когда счет достигает нуля. Также не требуется список, включающий недоступные объекты.

Как поддерживается этот список? Хранит ли время выполнения для языков GC гигантский список всех объектов?

Педагогические решения, такие как HLVM , могут вести список всех объектов, потому что это просто, но это редко.

Кроме того, насколько я понимаю, GC включает в себя обход стека вызовов для поиска ссылок на объекты - как алгоритм различает GC-совместимые указатели и примитивные данные?

Опять же, есть много разных стратегий. Консервативные GC не могут различить указатели и не указатели, поэтому они консервативно считают, что указатели могут быть не указателями. Педагогические GC, такие как HLVM , могут использовать такие алгоритмы, как Henderson Accurate GC в непригодной среде . Производственные GC хранят достаточно информации в стеке потоков ОС, чтобы точно определить, какие слова являются указателями (и какие кадры стека пропустить, поскольку они не связаны с управляемым кодом), а затем использовать средство поиска стека для их поиска.

Обратите внимание, что вы также должны найти локальные ссылки, хранящиеся как в регистрах, так и в стеке.

Answer 3

Этот сайт ( Как работает сборщик мусора в Java? ) содержит хорошее, краткое объяснение того, как работают сборщики мусора, а не только Java по умолчанию.