Wie funktioniert die Java Garbage Collection mit Rundschreiben?

161

Nach meinem Verständnis bereinigt die Garbage Collection in Java einige Objekte, wenn nichts anderes auf dieses Objekt zeigt.

Meine Frage ist, was passiert, wenn wir so etwas haben:

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, bUnd csoll Müll gesammelt werden, aber sie sind alle von anderen Objekten verwiesen werden.

Wie geht die Java-Garbage Collection damit um? (oder ist es einfach ein Speicherverlust?)

AlexeyMK
quelle
1
Siehe: stackoverflow.com/questions/407855/… , insbesondere die zweite Antwort von @gnud.
Seth

Antworten:

161

Javas GC betrachtet Objekte als "Müll", wenn sie nicht über eine Kette erreichbar sind, die an einem Garbage Collection-Stamm beginnt, sodass diese Objekte gesammelt werden. Auch wenn Objekte zueinander zeigen, um einen Zyklus zu bilden, sind sie immer noch Müll, wenn sie von der Wurzel abgeschnitten sind.

Weitere Informationen finden Sie im Abschnitt zu nicht erreichbaren Objekten in Anhang A: Die Wahrheit über die Garbage Collection in Java Platform Performance: Strategien und Taktiken .

Bill die Eidechse
quelle
14
Haben Sie eine Referenz dafür? Es ist schwer zu testen.
Tangens
5
Ich habe eine Referenz hinzugefügt. Sie können auch die finalize () -Methode eines Objekts überschreiben, um herauszufinden, wann es gesammelt wird (obwohl dies das einzige ist, für das ich die Verwendung von finalize () empfehlen würde).
Bill the Lizard
1
Nur um diesen letzten Kommentar zu verdeutlichen ... fügen Sie eine debug print-Anweisung in die finalize-Methode ein, die eine eindeutige ID für das Objekt ausgibt. Sie können sehen, dass alle Objekte, die aufeinander verweisen, gesammelt werden.
Bill the Lizard
4
"... klug genug zu erkennen ..." klingt verwirrend. GC muss keine Zyklen erkennen - sie sind einfach nicht erreichbar, daher Müll
Alexander Malakhov
86
@tangens "Hast du eine Referenz dafür?" in einer Diskussion über die Speicherbereinigung. Beste. Wortspiel. Je.
Michał Kosmulski
139

ja Java Garbage Collector verarbeitet Zirkelverweise!

How?

Es gibt spezielle Objekte, die als Garbage-Collection-Roots (GC-Roots) bezeichnet werden. Diese sind immer erreichbar, ebenso wie jedes Objekt, das sie an seiner eigenen Wurzel hat.

Eine einfache Java-Anwendung hat die folgenden GC-Wurzeln:

  1. Lokale Variablen in der Hauptmethode
  2. Der Hauptfaden
  3. Statische Variablen der Hauptklasse

Geben Sie hier die Bildbeschreibung ein

Um festzustellen, welche Objekte nicht mehr verwendet werden, führt die JVM zeitweise einen sehr treffend als Mark-and-Sweep-Algorithmus bezeichneten Algorithmus aus . Es funktioniert wie folgt

  1. Der Algorithmus durchläuft alle Objektreferenzen, beginnend mit den GC-Wurzeln, und markiert jedes gefundene Objekt als lebendig.
  2. Der gesamte Heapspeicher, der nicht von markierten Objekten belegt ist, wird zurückgefordert. Es wird einfach als frei markiert, im Wesentlichen frei von nicht verwendeten Objekten.

Wenn also ein Objekt von den GC-Wurzeln aus nicht erreichbar ist (selbst wenn es selbstreferenziert oder zyklisch referenziert ist), wird es einer Speicherbereinigung unterzogen.

Natürlich kann dies manchmal zu einem Speicherverlust führen, wenn der Programmierer vergisst, ein Objekt zu dereferenzieren.

Geben Sie hier die Bildbeschreibung ein

Quelle: Java Memory Management

Aniket Thakur
quelle
3
Perfekte Erklärung! Vielen Dank! :)
Jovan Perovic
Vielen Dank, dass Sie dieses Buch verlinkt haben. Es ist voller großartiger Informationen zu diesem und anderen Java-Entwicklungsthemen!
Droj
14
Im letzten Bild gibt es ein nicht erreichbares Objekt, aber es befindet sich im Bereich für erreichbare Objekte.
La VloZ Merrill
13

Ein Garbage Collector startet an einigen "Root" -Sätzen, die immer als "erreichbar" gelten, z. B. den CPU-Registern, dem Stapel und den globalen Variablen. Es funktioniert, indem Zeiger in diesen Bereichen gefunden werden und rekursiv alles gefunden wird, auf das sie zeigen. Sobald alles gefunden ist, ist alles andere Müll.

Natürlich gibt es einige Variationen, hauptsächlich aus Gründen der Geschwindigkeit. Beispielsweise sind die meisten modernen Garbage Collectors "Generationen", was bedeutet, dass sie Objekte in Generationen unterteilen. Wenn ein Objekt älter wird, dauert der Garbage Collector zwischen den Versuchen, herauszufinden, ob dieses Objekt noch gültig ist oder nicht, immer länger - Es beginnt nur anzunehmen, dass die Chancen, wenn es lange gelebt hat, ziemlich gut sind, dass es noch länger leben wird.

Trotzdem bleibt die Grundidee dieselbe: Alles basiert darauf, von einigen Grundsätzen auszugehen, die für selbstverständlich gehalten werden, und dann alle Zeiger zu verfolgen, um herauszufinden, was sonst noch verwendet werden könnte.

Interessant beiseite: Mögen Menschen oft überrascht sein, wie ähnlich dieser Teil eines Garbage Collectors und der Code für das Marshalling von Objekten für Dinge wie Remoteprozeduraufrufe sind. In jedem Fall gehen Sie von einem Stammsatz von Objekten aus und suchen nach Zeigern, um alle anderen Objekte zu finden, auf die ...

Jerry Sarg
quelle
Was Sie beschreiben, ist ein Tracing-Sammler. Es gibt andere Arten von Sammlern. Von besonderem Interesse für diese Diskussion sind Referenzzählungskollektoren, die dazu neigen, Probleme mit Zyklen zu haben.
Jörg W Mittag
@ Jörg W Mittag: Sicherlich wahr - obwohl ich keine (einigermaßen aktuelle) JVM kenne, die Referenzzählung verwendet, scheint es (zumindest für mich) unwahrscheinlich, dass sie einen großen Unterschied zur ursprünglichen Frage macht.
Jerry Coffin
@ Jörg W Mittag: Zumindest standardmäßig verwendet Jikes RVM derzeit den Immix-Kollektor, einen auf Regionen basierenden Tracing-Kollektor (obwohl er auch die Referenzzählung verwendet). Ich bin mir nicht sicher, ob Sie sich auf diese Referenzzählung beziehen oder auf einen anderen Sammler, der Referenzzählung ohne Rückverfolgung verwendet (letzteres würde ich vermuten, da ich noch nie davon gehört habe, dass Immix "Recycler" nennt).
Jerry Coffin
Ich war ein bisschen durcheinander: Der Recycler ist (war?) In Jalapeno implementiert, der Algorithmus, über den ich nachgedacht habe und der in Jikes implementiert wurde (war?), Ist Ulterior Reference Counting . Trotzdem ist es ziemlich sinnlos zu sagen, dass Jikes diesen oder jenen Garbage Collector verwendet, da Jikes und insbesondere MMtk speziell dafür entwickelt wurden, schnell verschiedene Garbage Collectors innerhalb derselben JVM zu entwickeln und zu testen.
Jörg W Mittag
2
Ulterior Reference Counting wurde 2003 von denselben Personen entwickelt, die Immix 2007 entworfen haben. Ich denke also, dass letzteres wahrscheinlich das erstere abgelöst hat. URC wurde speziell entwickelt, um mit anderen Strategien kombiniert zu werden. In dem URC-Papier wird ausdrücklich erwähnt, dass URC nur ein Sprungbrett für einen Sammler ist, der die Vorteile der Verfolgung und Referenzzählung kombiniert. Ich denke, Immix ist dieser Sammler. Auf jeden Fall ist der Recycler ein reiner Referenzzählungssammler, der dennoch Zyklen erkennen und sammeln kann: WWW.Research.IBM.Com/people/d/dfb/recycler.html
Jörg W Mittag
13

Du hast Recht. Die von Ihnen beschriebene spezifische Form der Speicherbereinigung wird als " Referenzzählung " bezeichnet. Die Funktionsweise (zumindest konzeptionell werden die meisten modernen Implementierungen der Referenzzählung tatsächlich ganz anders implementiert) sieht im einfachsten Fall folgendermaßen aus:

  • Wenn ein Verweis auf ein Objekt hinzugefügt wird (z. B. wenn er einer Variablen oder einem Feld zugewiesen, an die Methode übergeben usw.) wird, wird seine Referenzanzahl um 1 erhöht
  • Wenn ein Verweis auf ein Objekt entfernt wird (die Methode gibt zurück, die Variable verlässt den Gültigkeitsbereich, das Feld wird einem anderen Objekt neu zugewiesen oder das Objekt, das das Feld enthält, wird selbst Müll gesammelt), wird die Referenzanzahl um 1 verringert
  • Sobald der Referenzzähler 0 erreicht, gibt es keinen Verweis mehr auf das Objekt, was bedeutet, dass niemand es mehr verwenden kann, daher ist es Müll und kann gesammelt werden

Und diese einfache Strategie hat genau das Problem, das Sie beschreiben: Wenn A auf B verweist und B auf A verweist, können beide Referenzzählungen niemals kleiner als 1 sein, was bedeutet, dass sie niemals gesammelt werden.

Es gibt vier Möglichkeiten, um mit diesem Problem umzugehen:

  1. Ignoriere es. Wenn Sie über genügend Speicher verfügen, Ihre Zyklen klein und selten sind und Ihre Laufzeit kurz ist, können Sie möglicherweise davonkommen, einfach keine Zyklen zu sammeln. Stellen Sie sich einen Shell-Skript-Interpreter vor: Shell-Skripte werden normalerweise nur einige Sekunden lang ausgeführt und weisen nicht viel Speicher zu.
  2. Kombinieren Sie Ihren Referenzzählungs-Garbage-Collector mit einem anderen Garbage-Collector, der keine Probleme mit Zyklen hat. CPython tut dies zum Beispiel: Der Haupt-Garbage-Collector in CPython ist ein Referenzzählungs-Collector, aber von Zeit zu Zeit wird ein Tracing-Garbage-Collector ausgeführt, um die Zyklen zu erfassen.
  3. Erkennen Sie die Zyklen. Leider ist das Erkennen von Zyklen in einem Diagramm eine ziemlich teure Operation. Insbesondere erfordert es fast den gleichen Overhead wie ein Tracing-Kollektor, sodass Sie genauso gut einen davon verwenden können.
  4. Implementieren Sie den Algorithmus nicht so naiv wie Sie und ich: Seit den 1970er Jahren wurden mehrere interessante Algorithmen entwickelt, die Zykluserkennung und Referenzzählung in einer einzigen Operation auf clevere Weise kombinieren, was erheblich billiger ist als beide beide getrennt oder als Rückverfolgungssammler.

Übrigens ist die andere wichtige Möglichkeit, einen Garbage Collector zu implementieren (und darauf habe ich bereits einige Male oben hingewiesen), die Ablaufverfolgung . Ein Tracing Collector basiert auf dem Konzept der Erreichbarkeit . Sie beginnen mit einem Stammsatz, von dem Sie wissen , dass er immer erreichbar ist (z. B. globale Konstanten oder die ObjectKlasse, der aktuelle lexikalische Bereich, der aktuelle Stapelrahmen), und verfolgen von dort aus alle Objekte, die vom Stammsatz aus erreichbar sind Alle Objekte, die von den Objekten aus erreichbar sind, die vom Stammsatz aus erreichbar sind, usw., bis Sie den transitiven Abschluss haben. Alles, was nicht in dieser Schließung ist, ist Müll.

Da ein Zyklus nur in sich selbst erreichbar ist, aber nicht über den Stammsatz erreichbar ist, wird er gesammelt.

Jörg W Mittag
quelle
1
Da die Frage Java-spezifisch ist, sollte erwähnt werden, dass Java keine Ref-Zählung verwendet und daher kein Problem besteht. Auch ein Link zu Wikipedia wäre hilfreich als "weiterführende Literatur". Ansonsten tolle Übersicht!
Alexander Malakhov
Ich habe gerade Ihre Kommentare zu Jerry Coffins Beitrag gelesen, also bin ich mir jetzt nicht so sicher :)
Alexander Malakhov
8

Die Java-GCs verhalten sich nicht so, wie Sie es beschreiben. Es ist genauer zu sagen, dass sie von einer Basismenge von Objekten ausgehen, die häufig als "GC-Wurzeln" bezeichnet werden, und alle Objekte sammeln, die von einer Wurzel aus nicht erreichbar sind.
GC-Wurzeln umfassen Dinge wie:

  • statische Variablen
  • Lokale Variablen (einschließlich aller zutreffenden 'this'-Referenzen), die sich derzeit im Stapel eines laufenden Threads befinden

In Ihrem Fall gibt es also keine GC-Wurzeln mehr, die direkt oder indirekt einen Verweis auf einen Ihrer drei Knoten enthalten, sobald die lokalen Variablen a, b und c am Ende Ihrer Methode den Gültigkeitsbereich verlassen haben Sie sind für die Müllabfuhr berechtigt.

Der Link von TofuBeer enthält weitere Details, wenn Sie dies wünschen.

Sbodd
quelle
"... befindet sich derzeit im Stapel eines laufenden Threads ..." werden nicht Stapel aller Threads gescannt, um die Daten anderer Threads nicht zu beschädigen?
Alexander Malakhov
6

Dieser Artikel (nicht mehr verfügbar) befasst sich ausführlich mit dem Garbage Collector (konzeptionell ... gibt es mehrere Implementierungen). Der relevante Teil Ihres Beitrags ist "A.3.4 Nicht erreichbar":

A.3.4 Nicht erreichbar Ein Objekt wechselt in einen nicht erreichbaren Zustand, wenn keine starken Verweise mehr darauf vorhanden sind. Wenn ein Objekt nicht erreichbar ist, ist es ein Kandidat für die Sammlung. Beachten Sie den Wortlaut: Nur weil ein Objekt ein Kandidat für die Sammlung ist, heißt das nicht, dass es sofort gesammelt wird. Die JVM kann die Erfassung verzögern, bis der vom Objekt verbrauchte Speicher sofort benötigt wird.

TofuBeer
quelle
1
direkter Link zu diesem Abschnitt
Alexander Malakhov
1
Die Links sind nicht mehr verfügbar
Titus
1

Garbage Collection bedeutet normalerweise nicht "ein Objekt bereinigen, wenn nichts anderes auf dieses Objekt" zeigt "(das ist Referenzzählung). Garbage Collection bedeutet ungefähr, Objekte zu finden, die vom Programm aus nicht erreichbar sind.

In Ihrem Beispiel können sie nach dem Verlassen des Gültigkeitsbereichs von a, b und c vom GC erfasst werden, da Sie nicht mehr auf diese Objekte zugreifen können.

Amnon
quelle
"Garbage Collection bedeutet ungefähr, Objekte zu finden, die vom Programm aus nicht erreichbar sind". Bei den meisten GC-Algorithmen ist es tatsächlich umgekehrt. Sie beginnen mit den GC-Wurzeln und sehen, was Sie finden können. Der Rest wird als nicht referenzierter Müll betrachtet.
Fredrik
1
Die Referenzzählung ist eine der beiden Hauptimplementierungsstrategien für die Speicherbereinigung. (Der andere verfolgt.)
Jörg W Mittag
3
@ Jörg: Wenn die Leute heute die meiste Zeit über Müllsammler sprechen, beziehen sie sich auf Sammler, die auf einer Art Mark'n'sweep-Algorithmus basieren. Ref-Zählen ist normalerweise das, woran Sie festhalten, wenn Sie keinen Garbage Collector haben. Es ist wahr, dass das Ref-Zählen in gewisser Weise eine Garbage-Collection-Strategie ist, aber es gibt heute kaum noch ein gc, das darauf aufbaut. Wenn man sagt, dass es sich um eine gc-Strategie handelt, wird dies die Leute nur verwirren, weil es in der Praxis kein gc mehr ist Strategie, aber eine alternative Möglichkeit, Speicher zu verwalten.
Fredrik
1

Bill hat Ihre Frage direkt beantwortet. Wie Amnon sagte, ist Ihre Definition der Speicherbereinigung nur eine Referenzzählung. Ich wollte nur hinzufügen, dass selbst sehr einfache Algorithmen wie Markieren, Sweepen und Kopieren leicht zirkuläre Referenzen verarbeiten können. Also nichts Magisches daran!

Claudiu
quelle