Wir haben uns im letzten Beitrag (siehe / GC1 /) das Prinzip der Generational Garbage Collection angesehen, bei der der Heap-Speicher in unterschiedliche Bereiche, Young Generation und Old Generation, aufgeteilt wird, die mit jeweils anderen Allokations- und Garbage-Collection-Algorithmen verwaltet werden.  In diesem Beitrag wollen wir uns ansehen, wie die Allokation und Garbage Collection auf der Young Generation genau funktionieren.

Ehe wir auf den Garbage-Collection-Algorithmus kommen, der in der Sun-JVM für die Young Generation verwendet wird, wollen wir uns erst die typischen Garbage Collection Techniken in einem kurzen Überblick ansehen.  Das Ziel jeder Garbage Collection ist es, „tote“, d.h. von dem Anwendungsprogramm nicht mehr benötigte, Objekte zu identifizieren und ihren Speicher für zukünftige Allokation frei zu geben.

Mark-and-Sweep

Der Root Set spielt eine wesentliche Rolle.  Zum Root Set gehören die Referenzen auf den Call-Stacks der verschiedenen Threads, also der Einstieg, über den die lokalen Referenzvariablen und die Parameter von Methoden auf dem Call-Stack erreicht werden.  Zum Root Set gehören auch „globale“ Referenzen, d.h. die static-Referenzen in den Klassen. Alle Root-Referenzen zusammen liefern den Einstieg in einen Referenzgraphen, der alle lebendigen Objekte enthält.

Der Markierungsphase folgt eine Aufräumphase, in der der Speicher der nicht erreichbaren Objekte freigegeben und für zukünftige Allokationen bereitgestellt wird.  Im einfachsten Fall wird der Speicher einfach nur als „frei“ gekennzeichnet und in eine Free-List eingetragen.  Das ergibt den Mark-and-Sweep-Algorithmus.  Der Allokator verwendet die Free-List, um Speicher für neu anzulegende Objekte zu finden.  Die Abbildungen 1 und 2 zeigen einen Objektgraphen nach der Markierung und nach der Sweep-Phase.
 
 

Abbildung 1: Referenzgraph nach der Mark-Phase	Abbildung 2: Referenzgraph nach der Sweep-Phase

Der Mark-and-Sweep-Algorithmus hat einen gravierenden Nachteil. Wenn der Garbage Collector in der Sweep-Phase einfach nur den Speicher aller „toten“ Objekte als „frei“ kennzeichnet, dann besteht der Heap nach einer Weile aus lauter Löchern unterschiedlicher Größe, in denen neue Objekte abgelegt werden könnten.  Diesen Zustand bezeichnet man als Fragmentierung (siehe Abbildung 3).

Ein fragmentierter Speicher ist ungünstig für den Allokator, weil es zunehmend aufwändiger wird, die Löcher zu füllen, die die „toten“ Objekte hinterlassen haben, und gleichzeitig wird es immer schwieriger, genügend große Löcher für die neuen Objekte zu finden.  Wenn die Löcher nicht gefüllt werden, dann liegt freier Speicher ungenutzt herum.  Es könnte im ungünstigsten Falle passieren, dass eine Speicher-Allokation z.B. für ein größeres Array scheitert, obwohl es in Summe noch deutlich mehr Speicher gibt als benötigt. Aber der Speicher ist nicht zusammenhängend, sondern nur in kleinen Fragmenten vorhanden. Das heißt, bei hoher Speicherfragmentierung geht der Anwendung eher als wirklich nötig der Speicher aus.  Ein Garbage-Collection-Algorithmus wird also stets bemüht sein, die Speicherfragmentierung gering zu halten.

Mark-and-Copy

Diese Copy-Technik benötigt zwei Bereiche, FromSpace und ToSpace genannt, die nach jeder Garbage Collection die Rollen tauschen.  Einer der Bereiche, der ToSpace, ist passiv, d.h. er ist leer und unbenutzt und wird auch nicht für die Allokation verwendet.  Im anderen aktiven Bereich, dem FromSpace, legt die Applikation mithilfe des Allokators neue Objekte an, solange bis er voll ist.  Bei der Garbage Collection werden dann alle überlebenden Objekte vom aktiven FromSpace in den leeren, passiven ToSpace kopiert.  Die Abbildungen 4 und 5 zeigen einen Objekt-Graphen vor und nach dem Kopieren. Nach dem Kopieren wird der vormals aktive Bereich als Ganzes freigegeben; er ist dann leer.  Die beiden Bereiche tauschen anschließend die Rollen.  Neue Objekte entstehen dann wieder im aktiven Bereich, bis dieser voll ist und der Zyklus von vorne beginnt.
 

Abbildung 4: Referenzgraph nach der Mark-Phase	Abbildung 5: Referenzgraph nach der Copy-Phase

Bei diesem Algorithmus gibt es überhaupt keine Fragmentierung.  Die überlebenden Objekte liegen nach der Garbage Collection dicht nebeneinander; dahinter gibt es einen zusammenhängenden, freien Speicherbereich.

Das vereinfacht die Allokation ungemein.  Nun muss der Allokator keine Free-Listen mehr führen, in denen er nach hinreichend großen Speicherplätzen für die neuen Objekte sucht, sondern er kann die Objekte hintereinanderweg im freien Bereich angelegen.  Dazu verwendet er eine Bump-the-Pointer-Technik: er merkt sich das Ende des zuletzt allozierten Objekts und schiebt den Zeiger weiter, wenn er ein neues Objekt dahinter angelegt hat.  Für die Befriedigung einer Speicheranfrage muss er nur schauen, ob noch genug Platz da ist für das neue Objekt und den Zeiger verschieben.

Mark-and-Copy Garbage Collection hat zusätzlich zur schnellen Allokation, die sie erlaubt, den Vorteil, dass die Vermeidung der Fragmentierung relativ einfach ist.   Die lebenden Objekte in einen leeren Speicherbereich zu kopieren, ist unkompliziert und schnell.  Man spricht bei diesen Algorithmen auch von Scavenging (dt. wörtlich: Unrat beseitigen, Mülleimer plündern).  Der Scavenger pickt sich einfach die überlebenden Objekte raus und kopiert es in einen frischen Bereich.  Der Nachteil der Copy-Technik ist der Speicherverbrauch.  Es wird mehr Speicher vorrätig gehalten (nämlich der gesamte leere ToSpace), als tatsächlich gebraucht wird.  Das ist für Anwendungen mit engen Speicherbedingungen ein Problem.  Dafür bekommen wir einen hocheffizienten Speicher-Allokator.

Die Mark-and-Copy-Variante in der Sun-JVM

Abbildung 6: Heap-Aufteilung in einer Sun JVM

Die beiden Survivor-Bereiche wechseln ständig ihre Rollen, wie oben beschrieben, und einer davon ist immer leer als To-Space für die nächste Copy-Phase.  Neue Objekte entstehen nicht im aktiven Survivor-Bereich, sondern in Eden. Ansonsten ist das Prinzip aber ähnlich wie im klassischen Mark-and-Copy-Algorithmus.  Wenn Eden so voll ist, dass dort keine neuen Objekte mehr angelegt werden können, wandern die überlebenden Objekte von Eden und dem From-Space in den To-Space. Die überlebenden Objekte des Survivor-Spaces werden auf diese Weise zwischen den beiden Survivor-Bereichen hin- und herkopiert, bis sie eine Altersschwelle erreichen, nach der sie dann in die Old Generation kopiert werden.  Dieses Kopieren in die Old Generation bezeichnet man als Promotion. Die Garbage Collection auf Eden und den Survivor-Bereichen ist eine sogenannte Minor Collection im Unterschied zur Major oder Full Collection auf der Old Generation.

In Abbildung 7 kann man gut sehen, wie die beiden Survivor-Bereiche die Rollen wechseln.  Die Abbildung zeigt den Output, den die JVM ausgibt, wenn man die Option -XX:+PrintHeapAtGC setzt.  Man bekommt dann Informationen über den Heap vor und nach jeder Garbage Collection.

Zusammenfassung

Abbildung 7: Heap vor und nach einer Minor Garbage Collection.

Man kann sehen, dass immer einer der Survivor-Bereiche leer ist.  Wenn man die Addressangaben anschaut, kann man auch sehen, dass sie nach der Garbage Collection die Rolle gewechselt haben.  Man stellt fest, dass ein Teil der Objekte von der Young Generation in die Old (Tenured) Generation gewandert ist; sie ist von 67% auf 74% angewachsen. Die Größenverhältnisse sind auch interessant und durchaus typisch: die Old Generation ist mit ~60MB sehr viel größer als die Young Generation mit ~5MB.

Vor- und Nachteile von Mark-and-Copy auf der Young Generation

Die Garbage Collection selbst ist wegen dem Kopieren der überlebenden Objekte ein bisschen teurer, als wenn man die Objekte dort liegen ließe, wo sie waren.  Nach dem Kopieren haben die Objekte eine andere Adresse als zuvor und sämtliche Referenzen auf die kopierten Objekte müssen entsprechend angepasst werden.  Da der Mark-and-Sweep-Algorithmus ein Stop-the-World-Algorithmus ist, d.h. während der Garbage Collection sind alle Threads der Applikation gestoppt, hat der Collector exklusiven Zugriff auf den gesamten Objekt-Graphen und kann die notwendigen Referenzanpassungen ungestört machen.

Wie lange das Anpassen der Referenzen dauert, hängt davon ab, wie viele Referenzen es von Objekten der Old Generation auf Objekte in der Young Generation gibt.  Die Old Generation ist nämlich vergleichsweise groß, und wenn jedes alte Objekt eine Referenz auf ein überlebendes junges Objekt hätte, dann hätte der Garbage Collector ziemlich viel Arbeit mit dem Anpassen der Referenzen.  Eine solche Situation ist aber unwahrscheinlich, oder – sagen wir mal so – es wäre eine für Java-Programm untypische Situation.

Referenzen von der Old Generation in die Young Generation sind aber nicht nur in der Copy-Phase ungünstig; sie sind auch für die Markierungsphase von besonderer Bedeutung.

Intergenerational References

Aus diesem Grunde verfolgt eine Minor Garbage Collection auf der Young Generation keine Root-Referenzen in die Old Generation.  Wie schafft sie es dann, alle lebendigen Objekte in der Young Generation zu erkennen?  Es könnte ja sein, dass die einzige Referenz, die ein junges Objekt am Leben erhält, ausgerechnet aus der Old Generation kommt.  Abbildung 8 zeigt eine Situation, in der es zwei solche Referenzen aus der Old in die Young Generation gibt; sie sind blau eingezeichnet.

Eine solche Situation kann durch Promotion während der Garbage Collection entstehen, wenn ursprünglich das referenzierte und das referenzierende Objekt beide in der Young Generation waren und dann das referenzierende Objekt in die Old Generation abgeschoben wird.  Es kann aber auch durch Referenzzuweisungen seitens der Applikation entstehen, indem einem Referenz-Feld in einem alten Objekt die Adresse eines jungen Objekts zugewiesen wird.  Egal ob die Alt-nach-Jung-Referenz durch Promotion oder Zuweisung entstanden ist, der Garbage Collection muss für eine Minor Garbage Collection alle Referenzen in die Young Generation hinein kennen. In Abbildung 8 kann man sehen, dass die Ausgangspunkte für die Markierung sowohl Referenzen aus dem Root Set als auch Alt-nach-Jung-Referenzen sind; sie sind in der Abbildung fett eingezeichnet.

Die Markierungsphase einer Collection auf der Young Generation verfolgt also alle Referenzen aus dem Root Set, die in die Young Generation verweisen, und alle Alt-nach-Jung-Referenzen. Wie beschafft sich der Collector die Alt-nach-Jung-Referenzen?  Er sammelt sie in einem sogenannten Remembered Set.

Die Alt-nach-Jung-Referenzen, die durch Promotion entstehen, kann sich der Garbage Collector einfach fürs nächste Mal merken; diese Referenzen legt er ja selber durch die Promotion an.
Schwieriger als sich selbsterzeugte Intergenerationen-Referenzen zu merken, ist es für den Garbage Collector, diejenigen Alt-nach-Jung-Referenzen zu identifizieren, die durch Referenzzuweisungen in der Applikation im Zeitraum zwischen zwei Garbage Collections entstanden sind.  Wie könnte der Garbage Collector es in den Griff bekommen?  Eigentlich muss er nur die Objekte in der Old Generation mit Referenzfeldern anschauen, an denen sich seit der letzten Garbage Collection etwas geändert hat.  Um die Suche auf eben jene veränderten Objekte zu beschränken, merkt sich die JVM bei jeder Referenzzuweisung, die die Applikation macht, welches Objekt geändert wurde, damit der Garbage Collector später gezielt nur die geänderten Objekte auf Alt-nach-Jung-Referenzen untersuchen muss.  Diese veränderten Objekte sind in Abbildung 8 mit einem * gekennzeichnet.

Die Information über die geänderten Objekte wird in so genannten Card Tables abgelegt. Dazu wird der Speicher in Bereiche, die Cards, aufgeteilt und jedem Bereich wird ein Bit in der Card Table zugeordnet.  Wenn in dem Bereich eine Referenz modifiziert wurde, wird der Bereich as „dirty“ markiert, indem das zugehörige Bit in der Card Table gesetzt wird. Später sucht der Garbage Collector in den „dirty“ Bereichen nach Intergenerationen-Referenzen.  Dieser Card-Table-Mechanismus kostet natürlich:

• Speicher für die Card Tables,
• Zusatzaufwand bei jeder Referenzzuweisung für das Setzen der „dirty“-Markierung; dazu wird eine sogenannte Write Barrier benötigt, und
• zusätzlicher Aufwand bei der Garbage Collection für die Suche nach den Inter-Generationen-Referenzen in den „dirty cards“.

Insgesamt kann man sagen, dass von der Generational Garbage Collection in erster Linie solche Applikationen profitieren,

• in der viele Objekte früh sterben; sonst lohnt sich Aufteilung in Generationen und die unterschiedliche Behandlung der Generationen nicht; das haben wir in unserem letzten Artikel ausführlich diskutiert / GC1 /; und
• es wenige Referenzen von alten auf junge Objekte gibt; sonst wird die Behandlung der Intergenerationen-Referenzen zu teuer.

Parallele Garbage Collection

Traditionell wurde die Garbage Collection von nur einem Thread, dem sogenannten Reaper-Thread, gemacht.  Da aber mit zunehmender Verfügbarkeit von Multiprozessor- und Multicore-Architekturen die Applikationen mit vielen Threads parallel neue Objekte erzeugen, ist es nicht besonders effizient, wenn ein einzelner Reaper-Thread in der Stop-the-World-Pause die Garbage Collection durchführt.  Es führt zu unnötig langen Pausen und nutzt die verfügbaren Prozessorkapazitäten nur ungenügend aus.  Also hat man eine Parallel Garbage Collection auf der Young Generation entwickelt; sie war in Java 1.4.1 noch experimentell und ist seit Java 1.4.2 offiziell verfügbar.

Unter paralleler Garbage Collection versteht man Techniken, bei denen die Speicherbereinigung von mehreren Thread gleichzeitig abgewickelt wird.  Dabei wird sowohl die Markierungs- als auch die Kopierphase in Teilaufgaben aufgeteilt, die auf die verschiedene Garbage-Collector-Threads verteilt werden.

Die Arbeit wird in der Markierungsphase so aufgeteilt, dass die Root-Referenzen auf verschiedene Threads verteilt werden, die dann die von dieser Referenz aus erreichbaren Objekte markieren.  Da jede Root-Referenz nur von je einem Garbage-Collector-Thread verwendet wird, müssen die Threads die Zugriffe auf die Referenz nicht synchronisieren.  In den wenigen Fällen, in denen eine Koordination der Threads erforderlich ist, wird dies mit atomaren CAS-Operationen (Compare-And-Set) gemacht, um lock-basierte Synchronisation zwischen zu vermeiden.

In der Copy-Phase geht es so ähnlich.  Jedem Garbage-Collection-Thread wird ein Teil des Survivor-Bereichs (ein PLAB = Parallel Local Allocation Buffer) zugeteilt, in den er die lebendigen Objekte kopieren darf.  Da jeder Thread exklusiven Zugriff auf seinen Teilbereich hat, braucht er sich nicht mit den anderen Threads synchronisieren.  Bei dieser Technik lässt sich ein gewisses Maß an Fragmentierung nicht vermeiden, weil jeder Garbage-Collection-Thread nur seinen Teil des Survivor-Bereichs auffüllt; zwischen den Teilen bleiben Lücken.  Aber die Zerstückelung lässt sich tolerieren angesichts des Performancevorteils durch das parallele Kopieren.

Parallele Garbage Collection ist immer noch eine „Stop-the-World“-Aktion, bei der die Anwendung angehalten wird.  Allerdings sind die Pausen auf einer Multiprozessor-Maschine bei paralleler Garbage Collection kürzer.  Auf einer Single-Prozessor-Architektur mit einem Single-Core-Prozessor dürfte parallele Garbage Collection hingegen kontraproduktiv ausfallen, weil ein gewisses Maß an Overhead für Koordination und Synchronisation zwischen den Garbage-Collection-Threads unvermeidlich ist. Der zusätzliche Aufwand zahlt sich also ohne die Nutzung mehrerer Prozessoren oder Prozessorkerne nicht aus.

Seit Java 5 ist die parallele Garbage Collection schon per Default eingeschaltet, wenn es sich um eine Maschine mit mehreren Prozessoren oder -kernen handelt.  Die JVM macht eine sogenannte Server Machine Detection, d.h. sie schaut sich die Ausstattung der Maschine an und wenn sie mehr als zwei Prozessoren und mehr als 2 Gigabyte Speicher, dann handelt es sich um einer Server-Maschine.  In älteren Versionen von Java oder auf Client-Maschinen muss man die parallele Garbage Collection mit der Kommandozeilen-Option -XX:+UseParallelGC einschalten.  Per Default werden so viele Garbage Collection Threads verwendet, wie es Prozessoren oder Prozessorkerne auf der Hardware gibt.  Bei mehr als 8 Prozessoren werden nur noch 5/8 so viele Threads verwendet, wie es Prozessoren gibt.  Man kann die Zahl der verwendeten Garbage Collection Threads auch explizit steuern über die Option -XX:ParallelGCThreads=<n>.

Parallele Allokation und TLABs

Wir haben oben besprochen, dass die Allokation mit Bump-the-Pointer-Technik aus dem leeren Eden-Bereich erfolgt.  Wenn mehrere Threads gleichzeitig Speicher aus Eden haben wollen, dann müssen sie sich koordinieren. Prinzipiell könnte jeder Thread ein Lock anfordern, den Speicher holen, den Pointer, der den Anfang von freien Bereich markiert, weiterschalten und dann das Lock wieder freigeben, damit der nächste Thread Speicher holen kann.  Damit wäre die Allokation ein heftiger Engpass.

In der Sun JVM wird die Speicherallokation ohne Locks gemacht. Es gibt stattdessen sogenannte Thread-Local Allocation Buffers (TLABs).  Ein TLAB ist ein Teil von Eden, der einem Thread exklusiv zur Verfügung steht. Dort kann er effizient mit Bump-the-Pointer-Technik und ohne Synchronisation Speicher beschaffen.  Nur wenn ein solcher thread-lokaler Puffer voll ist und der Thread einen neuen braucht, muss er sich mit den anderen Threads synchronisieren; aber diese Aktion ist selten und stellt kein relevantes Performance-Problem dar.

Wer sich für Details zu den TLABs interessiert, beispielsweise für deren Größe und wie man sie steuern kann, dem sei Jon Masamitsu's Weblog empfohlen (siehe / TLAB /).  An dieser Stelle sei auch erwähnt, dass die Verwendung lokaler Allocation Buffer auf NUMA-Architekturen noch weiter optimiert ist.  Wenn man keine SMP- sondern eine NUMA-Prozessorarchitektur verwendet, dann werden die Speicheranforderungen bevorzugt aus dem node-lokalen Bereich („node-lokal“ im Sinne von NUMA) befriedigt, wenn die JVM-Option –XX:+UseNUMA gesetzt ist.  Informationen dazu finden sich in / NUMA /.

Zusammenfassung

Literaturverweise

Die gesamte Serie über Garbage Collection:

If you are interested to hear more about this and related topics you might want to check out the following seminar:

Seminar   High-Performance Java - programming, monitoring, profiling, and tuning techniques 4 day seminar ( open enrollment and on-site) Garbage Collection Tuning - profiling and tuning of memory related performance issues 1 day seminar ( open enrollment and on-site)