Comment Java Garbage Collection fonctionne-t-il avec les références circulaires?

D'après ce que je comprends, le garbage collection en Java nettoie certains objets si rien d'autre ne «pointe» vers cet objet.

Ma question est, que se passe-t-il si nous avons quelque chose comme ça:

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, bet cdoivent être récupérés, mais ils sont tous référencés par d'autres objets.

Comment le garbage collection Java gère-t-il cela? (ou est-ce simplement un drain de mémoire?)

Le GC de Java considère les objets comme "garbage" s'ils ne sont pas accessibles via une chaîne commençant à une racine de garbage collection, donc ces objets seront collectés. Même si les objets peuvent se pointer les uns vers les autres pour former un cycle, ils sont toujours des déchets s'ils sont coupés de la racine.

Voir la section sur les objets inaccessibles dans l'annexe A: La vérité sur le nettoyage de la mémoire dans les performances de la plate-forme Java: stratégies et tactiques pour les détails sanglants.

oui Java Garbage collector gère la référence circulaire!

How?

Il existe des objets spéciaux appelés racines de garbage collection (racines GC). Ceux-ci sont toujours accessibles, tout comme tout objet qui les a à sa propre racine.

Une application Java simple a les racines GC suivantes:

1. Variables locales dans la méthode principale
2. Le fil conducteur
3. Variables statiques de la classe principale

Pour déterminer quels objets ne sont plus utilisés, la machine virtuelle Java exécute par intermittence ce qu'on appelle très justement un algorithme de marquage et de balayage . Cela fonctionne comme suit

1. L'algorithme parcourt toutes les références d'objet, en commençant par les racines GC, et marque chaque objet trouvé comme vivant.
2. Toute la mémoire du tas qui n'est pas occupée par les objets marqués est récupérée. Il est simplement marqué comme libre, essentiellement exempt d'objets inutilisés.

Donc, si un objet n'est pas accessible à partir des racines GC (même s'il est auto-référencé ou cyclique), il sera soumis à un garbage collection.

Bien sûr, cela peut parfois conduire à une fuite de mémoire si le programmeur oublie de déréférencer un objet.

Source: Gestion de la mémoire Java

Un garbage collector démarre à partir d'un ensemble "racine" d'endroits qui sont toujours considérés comme "accessibles", tels que les registres du processeur, la pile et les variables globales. Cela fonctionne en trouvant tous les pointeurs dans ces domaines et en trouvant récursivement tout ce qu'ils pointent. Une fois tout cela trouvé, tout le reste est des ordures.

Il existe bien sûr de nombreuses variantes, principalement pour des raisons de vitesse. Par exemple, la plupart des garbage collector modernes sont "générationnels", ce qui signifie qu'ils divisent les objets en générations, et à mesure qu'un objet vieillit, le garbage collector va de plus en plus longtemps entre les moments où il essaie de déterminer si cet objet est toujours valide ou non - il commence juste à supposer que s'il a vécu longtemps, il y a de bonnes chances qu'il continue à vivre encore plus longtemps.

Néanmoins, l'idée de base reste la même: tout est basé sur le fait de partir d'un ensemble racine de choses qui pourraient encore être utilisées, puis de rechercher tous les pointeurs pour trouver ce qui pourrait être utilisé.

A part intéressant: les gens sont souvent surpris par le degré de similitude entre cette partie d'un ramasse-miettes et le code de marshaling d'objets pour des choses comme les appels de procédure distante. Dans chaque cas, vous partez d'un ensemble d'objets racine et poursuivez des pointeurs pour trouver tous les autres objets auxquels ils font référence ...

Vous avez raison. La forme spécifique de garbage collection que vous décrivez est appelée « comptage de références ». La façon dont cela fonctionne (conceptuellement, au moins, la plupart des implémentations modernes du comptage de références sont en fait implémentées de manière très différente) dans le cas le plus simple, ressemble à ceci:

• chaque fois qu'une référence à un objet est ajoutée (par exemple, elle est affectée à une variable ou à un champ, transmise à la méthode, etc.), son compteur de références est augmenté de 1
• chaque fois qu'une référence à un objet est supprimée (la méthode retourne, la variable sort de la portée, le champ est réaffecté à un objet différent ou l'objet qui contient le champ se récupère lui-même), le nombre de références est diminué de 1
• dès que le nombre de références atteint 0, il n'y a plus de référence à l'objet, ce qui signifie que personne ne peut plus l'utiliser, donc c'est des ordures et peut être collecté

Et cette stratégie simple a exactement le problème que vous décrivez: si A référence B et B référence A, alors leurs deux nombres de références ne peuvent jamais être inférieurs à 1, ce qui signifie qu'ils ne seront jamais collectés.

Il existe quatre façons de résoudre ce problème:

1. Ignorez-le. Si vous avez assez de mémoire, vos cycles sont petits et peu fréquents et votre temps d'exécution est court, peut-être que vous pouvez vous en tirer simplement en ne collectant pas les cycles. Pensez à un interpréteur de script shell: les scripts shell ne s'exécutent généralement que pendant quelques secondes et n'allouent pas beaucoup de mémoire.
2. Combinez votre ramasse-miettes de comptage de références avec un autre garbage collector qui n'a pas de problèmes avec les cycles. CPython le fait, par exemple: le garbage collector principal de CPython est un collecteur de comptage de références, mais de temps en temps un garbage collector de traçage est exécuté pour collecter les cycles.
3. Détectez les cycles. Malheureusement, la détection de cycles dans un graphique est une opération assez coûteuse. En particulier, il nécessite à peu près les mêmes frais généraux qu'un collecteur de traçages, vous pouvez donc tout aussi bien utiliser l'un d'entre eux.
4. N'implémentez pas l'algorithme de la manière naïve que vous et moi le ferions: depuis les années 1970, de nombreux algorithmes assez intéressants ont été développés qui combinent la détection de cycle et le comptage de références en une seule opération d'une manière intelligente qui est nettement moins chère que les deux. les deux séparément ou faisant un collecteur de traçage.

À propos, l' autre moyen majeur d'implémenter un garbage collector (et j'ai déjà fait allusion à cela quelques fois ci-dessus), est le traçage . Un collecteur de traçage est basé sur le concept d' accessibilité . Vous commencez avec un ensemble de racines dont vous savez qu'il est toujours accessible (les constantes globales, par exemple, ou la Objectclasse, la portée lexicale actuelle, le cadre de pile actuel) et à partir de là, vous tracez tous les objets qui sont accessibles à partir de l'ensemble de racines, puis tous les objets qui sont accessibles à partir des objets accessibles à partir de l'ensemble racine et ainsi de suite, jusqu'à ce que vous ayez la fermeture transitive. Tout ce qui n'est pas dans cette fermeture est des ordures.

Puisqu'un cycle n'est accessible qu'en lui-même, mais pas accessible à partir de l'ensemble racine, il sera collecté.

Les GC Java ne se comportent pas réellement comme vous le décrivez. Il est plus exact de dire qu'ils partent d'un ensemble d'objets de base, souvent appelés "racines GC", et collecteront tout objet qui ne peut être atteint à partir d'une racine.
Les racines GC incluent des choses comme:

• variables statiques
• variables locales (y compris toutes les références 'this' applicables) actuellement dans la pile d'un thread en cours d'exécution

Donc, dans votre cas, une fois que les variables locales a, b et c sortent du champ d'application à la fin de votre méthode, il n'y a plus de racines GC qui contiennent, directement ou indirectement, une référence à l'un de vos trois nœuds, et ils seront éligibles à la collecte des ordures.

Le lien de TofuBeer a plus de détails si vous le souhaitez.

Cet article (plus disponible) approfondit le ramasse-miettes (conceptuellement ... il existe plusieurs implémentations). La partie pertinente de votre message est "A.3.4 Inaccessible":

A.3.4 Inaccessible Un objet entre dans un état inaccessible lorsqu'il n'y a plus de références fortes à lui. Lorsqu'un objet est inaccessible, il est candidat à la collecte. Notez le libellé: ce n'est pas parce qu'un objet est candidat à la collecte qu'il sera immédiatement collecté. La JVM est libre de retarder la collecte jusqu'à ce qu'il y ait un besoin immédiat de mémoire consommée par l'objet.

La récupération de place ne signifie généralement pas "nettoyer un objet ssi rien d'autre ne" pointe "vers cet objet" (c'est le comptage de références). Le garbage collection signifie à peu près trouver des objets qui ne peuvent pas être atteints à partir du programme.

Ainsi, dans votre exemple, une fois que a, b et c sont hors de portée, ils peuvent être collectés par le GC, car vous ne pouvez plus accéder à ces objets.

Bill a répondu directement à votre question. Comme l'a dit Amnon, votre définition du garbage collection n'est que le comptage de références. Je voulais juste ajouter que même des algorithmes très simples comme le marquage et le balayage et la collecte de copies gèrent facilement les références circulaires. Donc, rien de magique à ce sujet!