¿Cómo funciona Java Garbage Collection con referencias circulares?

161

Según tengo entendido, la recolección de basura en Java limpia algunos objetos si nada más está 'apuntando' a ese objeto.

Mi pregunta es, qué pasa si tenemos algo como esto:

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, bY cdebe ser recogido de basura, pero todos ellos están siendo referenciado por otros objetos.

¿Cómo trata la recolección de basura Java con esto? (¿o es simplemente una pérdida de memoria?)

AlexeyMK
fuente
1
Ver: stackoverflow.com/questions/407855/… , específicamente la segunda respuesta de @gnud.
Seth

Respuestas:

161

El GC de Java considera que los objetos son "basura" si no son accesibles a través de una cadena que comienza en una raíz de recolección de basura, por lo que estos objetos serán recolectados. Aunque los objetos pueden señalarse entre sí para formar un ciclo, siguen siendo basura si están separados de la raíz.

Consulte la sección sobre objetos inalcanzables en el Apéndice A: La verdad sobre la recolección de basura en el rendimiento de la plataforma Java: estrategias y tácticas para obtener detalles sangrientos.

Bill el lagarto
fuente
14
Tienes una referencia para eso? Es difícil probarlo.
tangens
55
Agregué una referencia. También puede anular el método finalize () de un objeto para averiguar cuándo se recopila (aunque eso es lo único que recomendaría usar finalize () para).
Bill the Lizard
1
Solo para aclarar ese último comentario ... coloque una declaración de impresión de depuración en el método de finalización que imprima una identificación única para el objeto. Podrá ver todos los objetos que hacen referencia entre sí se recopilan.
Bill the Lizard
44
"... lo suficientemente inteligente como para reconocer ..." suena confuso. GC no tiene que reconocer los ciclos: son simplemente inalcanzables, por lo tanto, basura
Alexander Malakhov
86
@tangens "¿Tienes una referencia para eso?" en una discusión sobre recolección de basura. Mejor. Retruécano. Nunca.
Michał Kosmulski
139

sí ¡El recolector de basura Java maneja la referencia circular!

How?

Hay objetos especiales llamados raíces de recolección de basura (raíces GC). Estos son siempre accesibles y también lo es cualquier objeto que los tenga en su propia raíz.

Una aplicación Java simple tiene las siguientes raíces GC:

  1. Variables locales en el método principal.
  2. El hilo principal
  3. Variables estáticas de la clase principal.

ingrese la descripción de la imagen aquí

Para determinar qué objetos ya no están en uso, la JVM ejecuta de manera intermitente lo que se llama muy bien un algoritmo de marcado y barrido . Funciona de la siguiente manera

  1. El algoritmo atraviesa todas las referencias de objetos, comenzando con las raíces del GC, y marca cada objeto encontrado como vivo.
  2. Se recupera toda la memoria de almacenamiento dinámico que no está ocupada por objetos marcados. Simplemente está marcado como libre, esencialmente libre de objetos no utilizados.

Por lo tanto, si no se puede acceder a ningún objeto desde las raíces del GC (incluso si es autorreferenciado o cíclico), estará sujeto a la recolección de basura.

Por supuesto, a veces esto puede conducir a una pérdida de memoria si el programador olvida desreferenciar un objeto.

ingrese la descripción de la imagen aquí

Fuente: Java Memory Management

Aniket Thakur
fuente
3
Explicación perfecta! ¡Gracias! :)
Jovan Perovic
Gracias por vincular ese libro. ¡Está lleno de gran información sobre este y otros temas de desarrollo de Java!
Droj
14
En la última imagen, hay un objeto no accesible pero está en la sección de objetos accesibles.
La VloZ Merrill
13

Un recolector de basura comienza desde algún conjunto "raíz" de lugares que siempre se consideran "accesibles", como los registros de la CPU, la pila y las variables globales. Funciona encontrando cualquier puntero en esas áreas, y encontrando recursivamente todo lo que señalan. Una vez que se encuentra todo eso, todo lo demás es basura.

Hay, por supuesto, bastantes variaciones, principalmente por el bien de la velocidad. Por ejemplo, la mayoría de los recolectores de basura modernos son "generacionales", lo que significa que dividen los objetos en generaciones, y a medida que un objeto envejece, el recolector de basura se alarga cada vez más entre las veces que intenta averiguar si ese objeto aún es válido o no. - Simplemente comienza a suponer que si ha vivido mucho tiempo, es muy probable que continúe viviendo aún más.

No obstante, la idea básica sigue siendo la misma: todo se basa en comenzar a partir de un conjunto raíz de cosas que da por sentado que aún se podrían usar, y luego perseguir todos los punteros para encontrar qué más podría estar en uso.

Interesante aparte: muchas personas pueden sorprenderse a menudo por el grado de similitud entre esta parte de un recolector de basura y el código para ordenar objetos para cosas como llamadas a procedimientos remotos. En cada caso, está comenzando desde algún conjunto raíz de objetos y persiguiendo punteros para encontrar todos los otros objetos a los que se refieren ...

Jerry Coffin
fuente
Lo que está describiendo es un colector de rastreo. Hay otros tipos de coleccionistas. De particular interés para esta discusión son los colectores de recuento de referencia, que no suelen tener problemas con ciclos.
Jörg W Mittag
@ Jörg W Mittag: Ciertamente cierto, aunque no conozco una JVM (razonablemente actual) que utilice el recuento de referencias, por lo que parece poco probable (al menos para mí) que haga mucha diferencia en la pregunta original.
Jerry Coffin
@ Jörg W Mittag: Al menos de manera predeterminada, creo que Jikes RVM actualmente utiliza el recopilador Immix, que es un recopilador de rastreo basado en regiones (aunque también utiliza el recuento de referencias). No estoy seguro de si te estás refiriendo a ese recuento de referencias u otro recopilador que usa el recuento de referencias sin rastrear (supongo que esto último, ya que nunca he oído hablar de Immix llamando "reciclador").
Jerry Coffin
Me confundí un poco: el Recycler está (¿estaba?) Implementado en Jalapeno, el algoritmo en el que estaba pensando, que está (¿estaba?) Implementado en Jikes es Ulterior Reference Counting . Aunque, por supuesto, decir que Jikes usa este o aquel recolector de basura es bastante inútil, dado que Jikes y especialmente MMtk están específicamente diseñados para desarrollar y probar rápidamente diferentes recolectores de basura dentro de la misma JVM.
Jörg W Mittag
2
Ulterior Reference Counting fue diseñado en 2003 por las mismas personas que diseñaron Immix en 2007, por lo que supongo que este último probablemente reemplazó al primero. URC fue diseñado específicamente para que pueda combinarse con otras estrategias, y de hecho el documento de URC menciona explícitamente que URC es solo un trampolín hacia un recolector que combina las ventajas del rastreo y el conteo de referencias. Supongo que Immix es ese coleccionista. De todos modos, el Recycler es un colector de recuento de referencia puro , que sin embargo puede detectar y recopilar ciclos: WWW.Research.IBM.Com/people/d/dfb/recycler.html
Jörg W Mittag
13

Estás en lo correcto. La forma específica de recolección de basura que describe se denomina " recuento de referencias ". La forma en que funciona (conceptualmente, al menos, las implementaciones más modernas de conteo de referencias se implementan de manera bastante diferente) en el caso más simple, se ve así:

  • cada vez que se agrega una referencia a un objeto (por ejemplo, se asigna a una variable o un campo, se pasa al método, etc.), su recuento de referencias aumenta en 1
  • cada vez que se elimina una referencia a un objeto (el método regresa, la variable queda fuera del alcance, el campo se reasigna a un objeto diferente o el objeto que contiene el campo se recolecta basura), el recuento de referencias se reduce en 1
  • tan pronto como el recuento de referencias llegue a 0, no habrá más referencias al objeto, lo que significa que ya nadie puede usarlo, por lo tanto, es basura y se puede recolectar

Y esta estrategia simple tiene exactamente el problema que usted describe: si A hace referencia a B y B hace referencia a A, entonces sus dos recuentos de referencia nunca pueden ser inferiores a 1, lo que significa que nunca se recopilarán.

Hay cuatro formas de lidiar con este problema:

  1. Ignoralo. Si tiene suficiente memoria, sus ciclos son pequeños e infrecuentes y su tiempo de ejecución es corto, tal vez pueda salirse con la suya simplemente no recolectando ciclos. Piense en un intérprete de script de shell: los scripts de shell normalmente solo se ejecutan durante unos segundos y no asignan mucha memoria.
  2. Combine su recolector de basura de conteo de referencia con otro recolector de basura que no tenga problemas con los ciclos. CPython hace esto, por ejemplo: el recolector de basura principal en CPython es un recolector de conteo de referencia, pero de vez en cuando se ejecuta un recolector de basura de rastreo para recolectar los ciclos.
  3. Detecta los ciclos. Desafortunadamente, detectar ciclos en un gráfico es una operación bastante costosa. En particular, requiere casi la misma sobrecarga que requeriría un recopilador de rastreo, por lo que podría usar uno de esos.
  4. No implemente el algoritmo de la manera ingenua que usted y yo haríamos: desde la década de 1970, se han desarrollado múltiples algoritmos bastante interesantes que combinan la detección del ciclo y el recuento de referencias en una sola operación de una manera inteligente que es significativamente más barata que cualquiera de ellos. tanto por separado como haciendo un colector de rastreo.

Por cierto, la otra forma importante de implementar un recolector de basura (y ya lo he insinuado un par de veces más arriba) es el rastreo . Un colector de rastreo se basa en el concepto de accesibilidad . Comienza con un conjunto raíz que sabe que siempre es accesible (constantes globales, por ejemplo, o la Objectclase, el alcance léxico actual, el marco de pila actual) y desde allí rastrea todos los objetos a los que se puede acceder desde el conjunto raíz, luego todos los objetos a los que se puede acceder desde los objetos accesibles desde el conjunto raíz y así sucesivamente, hasta que tenga el cierre transitivo. Todo lo que no está en ese cierre es basura.

Como un ciclo solo es accesible dentro de sí mismo, pero no es accesible desde el conjunto raíz, se recopilará.

Jörg W Mittag
fuente
1
Dado que la pregunta es específica de Java, creo que vale la pena mencionar que Java no utiliza el recuento de referencias y, por lo tanto, el problema no existe. También el enlace a wikipedia sería útil como "lectura adicional". De lo contrario, una gran descripción!
Alexander Malakhov el
Acabo de leer sus comentarios en la publicación de Jerry Coffin, así que ahora no estoy tan seguro :)
Alexander Malakhov
8

Los GC de Java en realidad no se comportan como usted describe. Es más exacto decir que comienzan a partir de un conjunto base de objetos, frecuentemente llamados "raíces GC", y recolectarán cualquier objeto que no pueda ser alcanzado desde una raíz.
Las raíces de GC incluyen cosas como:

  • variables estáticas
  • variables locales (incluidas todas las referencias 'this' aplicables) actualmente en la pila de un hilo en ejecución

Entonces, en su caso, una vez que las variables locales a, byc salen del alcance al final de su método, no hay más raíces de GC que contengan, directa o indirectamente, una referencia a cualquiera de sus tres nodos, y serán elegibles para la recolección de basura.

El enlace de TofuBeer tiene más detalles si lo desea.

Sbodd
fuente
"... actualmente en la pila de un hilo en ejecución ..." ¿no está escaneando pilas de todos los hilos para no corromper los datos de otros hilos?
Alexander Malakhov
6

Este artículo (ya no está disponible) profundiza sobre el recolector de basura (conceptualmente ... hay varias implementaciones). La parte relevante de su publicación es "A.3.4 inalcanzable":

A.3.4 Inaccesible Un objeto entra en un estado inalcanzable cuando no existen más referencias fuertes a él. Cuando un objeto es inalcanzable, es un candidato para la colección. Tenga en cuenta la redacción: el hecho de que un objeto sea candidato para la recolección no significa que se recolecte de inmediato. La JVM es libre de retrasar la recopilación hasta que haya una necesidad inmediata de que el objeto consuma la memoria.

TofuBeer
fuente
1
enlace directo a esa sección
Alexander Malakhov
1
los enlaces ya no están disponibles
titus
1

La recolección de basura generalmente no significa "limpiar algún objeto si nada más está 'apuntando' a ese objeto" (eso es contar las referencias). Recolección de basura significa aproximadamente encontrar objetos a los que no se puede llegar desde el programa.

Entonces, en su ejemplo, después de que a, byc salgan del alcance, el GC puede recopilarlos, ya que ya no puede acceder a estos objetos.

Amnón
fuente
"Recolección de basura significa aproximadamente encontrar objetos a los que no se puede llegar desde el programa". En la mayoría de los algoritmos de GC, en realidad es al revés. Empiezas con las raíces de GC y ves lo que puedes encontrar, el resto se considera basura sin referencia.
Fredrik
1
El recuento de referencias es una de las dos estrategias principales de implementación para la recolección de basura. (El otro es el rastreo.)
Jörg W Mittag
3
@ Jörg: Hoy, la mayoría de las veces, cuando las personas hablan sobre recolectores de basura, se refieren a recolectores basados ​​en algún tipo de algoritmo de marcado. El conteo de referencias es generalmente lo que está atrapado si no tiene un recolector de basura. Es cierto que el recuento de referencia es, en cierto sentido, una estrategia de recolección de basura, pero casi no existe ningún gc hoy en día que se construya sobre él, por lo que decir que es una estrategia de gc solo confundirá a las personas porque en la práctica ya no es un gc estrategia pero una forma alternativa de administrar la memoria.
Fredrik
1

Bill respondió tu pregunta directamente. Como dijo Amnon, su definición de recolección de basura es solo un recuento de referencias. Solo quería agregar que incluso los algoritmos muy simples como marcar y barrer y copiar colecciones manejan fácilmente referencias circulares. Por lo tanto, no hay nada mágico al respecto!

Claudiu
fuente