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

Насколько я понимаю, сборка мусора в 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-сборка мусора справляется с этим? (или это просто утечка памяти?)

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

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

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

How?

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

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

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

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

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

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

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

Источник: Java Memory Management

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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