Как сборка мусора Java работает с круговыми ссылками?

Question

Насколько я понимаю, сборка мусора в Java очищает некоторые объекты, если ничто другое не "указывает" на этот объект.

Мой вопрос: что произойдет, если у нас будет что-то вроде этого:

class Node {
    public object value;
    public Node next;
    public Node(object o, Node n) { value = 0; next = n;}
}

//...some code
{
    Node a = new Node("a", null), 
         b = new Node("b", a), 
         c = new Node("c", b);
    a.next = c;
} //end of scope
//...other code

a, b и c должны собираться мусором, но на них все ссылаются другие объекты.

Как Java-сборка мусора справляется с этим? (или это просто утечка памяти?)

Answer 1

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

См. Раздел о недоступных объектах в Приложении A: Правда о сборке мусора в Производительность платформы Java: стратегии и тактики для получения подробной информации.

Answer 2

да Java-сборщик мусора обрабатывает циклическую ссылку!

How?

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

Простое Java-приложение имеет следующие корни GC: * ​​1006 *

1. Локальные переменные в основном методе
2. Основная нить
3. Статические переменные основного класса

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

1. Алгоритм перебирает все ссылки на объекты, начиная с GC корни и помечает каждый найденный объект как живой.
2. Вся память кучи, которая не занята отмеченными объектами, утилизирован. Он просто помечен как свободный, по существу, освобожден от неиспользованные предметы.

Таким образом, если какой-либо объект недоступен из корней GC (даже если он самоссылочный или циклический), он будет подвергнут сборке мусора.

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

Источник: Управление памятью Java

Answer 3

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

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

Тем не менее, основная идея остается прежней: все это основано на том, чтобы начинать с некоторого корневого набора вещей, которые, как он принимает, можно использовать как должное, а затем преследовать все указатели, чтобы найти то, что еще можно использовать. *

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

Answer 4

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

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

И эта простая стратегия имеет именно ту проблему, которую вы описываете: если A ссылается на B и B ссылается на A, то оба их счетчика ссылок могут никогда не быть меньше 1, что означает, что они никогда не будут собраны.

Существует четыре способа решения этой проблемы:

1. Игнорировать это. Если у вас достаточно памяти, ваши циклы малы и нечасты, а время выполнения короткое, может, вам просто сойдет с рук просто не собирать циклы. Подумайте о интерпретаторе сценариев оболочки: сценарии оболочки обычно выполняются всего несколько секунд и не выделяют много памяти.
2. Объедините ваш сборщик мусора с подсчетом ссылок с другим сборщиком мусора, у которого нет проблем с циклами. Например, CPython делает это: основной сборщик мусора в CPython является сборщиком подсчета ссылок, но время от времени для сбора циклов запускается трассирующий сборщик мусора.
3. Обнаружение циклов. К сожалению, обнаружение циклов в графе является довольно дорогой операцией. В частности, для этого требуются те же накладные расходы, что и для сборщика трассировки, так что вы также можете использовать один из них.
4. Не реализуйте алгоритм наивно, как вы и я: с 1970-х годов было разработано несколько довольно интересных алгоритмов, которые объединяют обнаружение циклов и подсчет ссылок в одной операции умным способом, который значительно дешевле, чем либо выполняем их по отдельности, либо выполняем сборщик трассировки.

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

Поскольку цикл доступен только внутри самого себя, но не доступен из корневого набора, он будет собран.

Answer 5

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

• статические переменные
• локальные переменные (включая все применимые ссылки 'this') в настоящее время в стеке работающего потока

Итак, в вашем случае, когда локальные переменные a, b и c выйдут из области видимости в конце вашего метода, больше не будет корней GC, которые прямо или косвенно содержат ссылку на любую из ваших трех узлы, и они будут иметь право на сборку мусора.

Ссылка на TofuBeer содержит более подробную информацию, если вы этого хотите.

Answer 6

Эта статья (более недоступна) подробно описывает сборщик мусора (концептуально ... существует несколько реализаций) Соответствующая часть вашего сообщения "A.3.4 Недоступен":

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

Answer 7

Билл ответил на ваш вопрос напрямую. Как сказал Амнон, ваше определение сборки мусора - просто подсчет ссылок. Я просто хотел добавить, что даже очень простые алгоритмы, такие как разметка, сборка и копирование, легко обрабатывают циклические ссылки. Так что в этом нет ничего волшебного!

Answer 8

Сборка мусора обычно не означает «очистить какой-либо объект, если только ничто не« указывает »на этот объект» (это подсчет ссылок). Сборка мусора примерно означает поиск объектов, недоступных из программы.

Так что в вашем примере, после того, как a, b и c выйдут из области видимости, они могут быть собраны GC, поскольку вы больше не можете получить доступ к этим объектам.