Garbage Collection en Java et références circulaires

Question

D'après ce que j'ai compris, le ramassage des déchets en Java nettoie un objet si rien d'autre ne pointe vers cet objet. Ma question est la suivante : que se passe-t-il si nous avons quelque chose comme.. :

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 et c devraient être collectés, mais ils sont tous référencés par d'autres objets. Comment le ramassage des ordures de Java gère-t-il cette situation ? (ou s'agit-il simplement d'une perte de mémoire ?)

Answer 1

La GC de Java considère que les objets sont "poubelles" s'ils ne sont pas accessibles par une chaîne partant d'une racine de collecte des ordures, et ces objets seront donc collectés. Même si les objets peuvent pointer les uns vers les autres pour former un cycle, ils sont toujours considérés comme 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 la collecte d'ordures dans le manuel de l'utilisateur. Performances de la plate-forme Java : Stratégies et tactiques (livre électronique gratuit, également disponible sur Safari ) pour les détails sanglants.

Answer 2

oui le collecteur d'ordures de Java gère les références circulaires !

How?

Il existe des objets spéciaux appelés racines de ramassage des ordures (racines GC). Ceux-ci sont toujours accessibles, de même que tout objet qui les possède à sa propre racine.

Une application Java simple possède 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 JVM exécute par intermittence ce qu'on appelle fort justement un algorithme de marquage et de balayage . Il fonctionne comme suit

1. L'algorithme parcourt toutes les références d'objets, 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 des objets marqués est récupérée. Elle est simplement marquée comme libre, essentiellement débarrassée des objets inutilisés.

Ainsi, si un objet n'est pas accessible à partir des racines GC (même s'il est autoréférencé ou cyclique), il sera soumis à la collecte des déchets.

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

Answer 3

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

• chaque fois qu'une référence à un objet est ajoutée (par exemple, si elle est assignée à une variable ou à un champ, passée à une méthode, etc.), son nombre de références est augmenté de 1.
• chaque fois qu'une référence à un objet est supprimée (retour de la méthode, sortie de la variable, réaffectation du champ à un autre objet ou ramassage de l'objet contenant le champ), 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, il est donc une poubelle et peut être collecté.

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

Il existe quatre façons de traiter ce problème :

1. Ignorez-le. Si vous avez suffisamment de mémoire, que vos cycles sont petits et peu fréquents et que votre temps d'exécution est court, vous pouvez peut-être vous en sortir en ne collectant pas les cycles. Pensez à un interpréteur de shell script : 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 collecteur de déchets de comptage de références avec un autre un collecteur d'ordures qui n'a pas de problèmes de cycles. C'est ce que fait CPython, par exemple : le principal garbage collector de CPython est un collecteur de comptage de références, mais de temps en temps, un garbage collector de traçage est lancé pour collecter les cycles.
3. Détecter les cycles. Malheureusement, la détection des cycles dans un graphe est une opération assez coûteuse. En particulier, elle nécessite à peu près la même surcharge qu'un collecteur de traçage, donc vous pourriez tout aussi bien utiliser l'un de ces collecteurs.
4. N'implémentez pas l'algorithme de la manière naïve dont vous et moi le ferions : depuis les années 1970, de nombreux algorithmes très intéressants ont été développés pour combiner la détection des cycles et le comptage des références en une seule opération, d'une manière intelligente et nettement moins coûteuse que de les faire séparément ou de faire un collecteur de traçage.

D'ailleurs, le autre La principale façon d'implémenter un ramasseur d'ordures (et j'y ai déjà fait allusion à plusieurs reprises ci-dessus) est de traçage . Un collecteur de traçage est basé sur le concept de accessibilité . Vous commencez avec quelques Ensemble des racines que vous savez être toujours atteignable (les constantes globales, par exemple, ou les Object la classe, la portée lexicale actuelle, le cadre de pile actuel) et à partir de là, vous trace tous les objets qui sont atteignables à partir de l'ensemble racine, puis tous les objets qui sont atteignables à partir des objets atteignables à partir de l'ensemble racine et ainsi de suite, jusqu'à obtenir la fermeture transitive. Tout ce qui est pas dans cette fermeture est un déchet.

Comme un cycle n'est atteignable qu'à l'intérieur de lui-même, mais pas à partir de l'ensemble des racines, il sera collecté.

Answer 4

Un ramasseur de déchets commence à partir d'un ensemble "racine" d'endroits qui sont toujours considérés comme "accessibles", tels que les registres du CPU, la pile et les variables globales. Il travaille en trouvant tous les pointeurs dans ces zones, et en trouvant récursivement tout ce vers quoi ils pointent. Une fois qu'il a trouvé tout ça, tout le reste est de la merde.

Il existe, bien sûr, de nombreuses variantes, principalement pour des raisons de rapidité. Par exemple, la plupart des ramasseurs de déchets modernes sont "générationnels", ce qui signifie qu'ils divisent les objets en générations, et qu'au fur et à mesure qu'un objet vieillit, le ramasseur de déchets passe de plus en plus de temps entre les moments où il essaie de déterminer si cet objet est toujours valide ou non -- il commence simplement à 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 : il s'agit de partir d'un ensemble d'éléments de base dont on suppose qu'ils peuvent encore être utilisés, puis de rechercher tous les pointeurs pour trouver ce qui pourrait être utilisé.

Aparté intéressant : les gens sont souvent surpris par le degré de similitude entre cette partie d'un garbage collector et le code pour le marshaling d'objets pour des choses comme les appels de procédure à distance. Dans chaque cas, on part d'un ensemble d'objets racine, et on recherche les pointeurs pour trouver tous les autres objets auxquels ils font référence...

Answer 5

Les GC de 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, fréquemment appelés "racines GC", et qu'ils collecteront tout objet qui ne peut être atteint à partir d'une racine.
Les racines du GC comprennent des choses comme :

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

Ainsi, dans votre cas, une fois que les variables locales a, b et c sont hors de portée à 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 elles seront éligibles pour la collecte des déchets.

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