Wir haben in den vorangegangenen Beiträgen (/ GC1 / und / GC2 /) das Prinzip der Generational Garbage Collection diskutiert, bei der der Heap-Speicher in unterschiedliche Bereiche, Young Generation und Old Generation, aufgeteilt wird, die mit jeweils anderen Algorithmen verwaltet werden.  Die Allokation und Garbage Collection auf der Young Generation haben wir beim letzen Mal angesehen.  In diesem und dem nächsten Beitrag wollen wir erläutern, wie die Garbage Collection auf der Old Generation funktioniert.

Die JVMs von Sun teilen den Heap-Speicher in mehrere Bereiche, die Generationen, auf, um auf den unterschiedlichen Bereichen jeweils unterschiedliche Allokations- und Garbage-Collection-Algorithmen zu verwenden.  Die Young Generation ist der Bereich, in dem all diejenigen Objekte entstehen, die von der Applikation mit new angefordert werden; in der Old Generation hingegen befinden sich Objekte, die mehrere Garbage Collections auf der Young Generation überlebt haben und in diesem Sinne „gealtert“ sind.  In einer typischen Java-Anwendung werden viele der jungen Objekte sehr schnell unerreichbar, deshalb wird auf der Young Generation ein Mark-and-Copy-Algorithmus verwendet.  Dieser Algorithmus hat den Vorteil, dass er die Young Generation so organisiert, dass anschließend eine effiziente Allokation möglich ist. Diesen Mark-and-Copy-Algorithmus auf der Young Generation haben wir im letzten Beitrag erläutert.  Sehen wir uns dieses Mal an, welcher Algorithmus auf der Old Generation verwendet wird.
 

Wozu braucht man auf der Old Generation einen anderen Algorithmus?

Geringe Sterblichkeit. In der Old Generation ist die „Sterblichkeitsrate“ deutlich geringer als in der Young Generation.  Wie wir in / GC1 / bereits erwähnt hatten, gibt es in einer typischen Java-Anwendung viele Objekte, die rasch sterben, und wenige Objekte, die dafür umso länger leben.  Abbildung 1 zeigt die übliche Altersverteilung der Objekte in einer Java-Anwendung.  Die Objekte in der Young Generation sterben sehr schnell und in großer Zahl (hohe Sterblichkeitsrate), wohingegen in der Old Generation erst nach längerer Zeit einige wenige Objekte sterben (niedrige Sterblichkeitsrate).    Erheblich Größe. Die Old Generation ist deutlich größer als die Young Generation.  Weil in der Young Generation zügig aufgeräumt wird, kommt man mit relativ wenig Platz für die vielen kurzlebigen Objekte aus (kleine Young Generation).  In der Old Generation häufen sich die Objekte mit der Zeit an; man spricht von zunehmender Speicherresidenz.  Deshalb muss in einer Old Generation viel mehr Platz sein als in der Young Generation (große Old Generation).

Abbildung 1: Typische Objekt-Population in Java

• Wenig Allokation. In der Old Generation passiert weniger Allokation als in der Young Generation.  Das liegt daran, dass in der Old Generation nur dann neue Objekte entstehen, wenn der Garbage Collector im Rahmen einer Promotion überlebende Objekte aus der Young in die Old Generation verschiebt.  In der Young Generation hingegen entstehen alle Objekte, die die Anwendung mit new erzeugt, d.h. der überwiegende Teil der Allokationen passiert in der Young Generation.

• Wenige Referenzzuweisungen . In der Old Generation passieren üblicherweise weniger Referenzzuweisungen als in der Young Generation.  Das liegt unter anderem daran, dass ein beträchtlicher Teil der Referenzzuweisungen Initialisierungen sind, die unmittelbar nach der Allokation eines Objekts gemacht werden, um die Felder des neu angelegten Objekts zu initialisieren.  Deshalb sind in  einer typischen Java-Anwendung überwiegend junge Objekte an den Referenzzuweisungen beteiligt.  In der Old Generation hingegen gibt es hingegen vergleichsweise wenige Änderungen an den Referenzbeziehungen.

Unter Berücksichtigung dieser Unterschiede hat man für die Young Generation einen Algorithmus gewählt, der möglichst schnell mit der Garbage-Collection fertig ist, weil er wegen der hohen Sterblichkeitsrate [Punkt (1)] oft aufgerufen werden muss.  Außerdem muss der Algorithmus dafür sorgen, dass anschließend eine möglichst effiziente Speicherallokation [Punkt (3)] möglich ist, weil in der Young Generation viel alloziert wird.  Der Mark-and-Copy-Algorithmus auf der Young Generation hat diese Eigenschaften.

Auf der Old Generation hingegen ist dieser Algorithmus nicht sinnvoll.  Die Verhältnisse sind anders: der Garbage Collector muss sich in der Old Generation um sehr viele Objekte kümmern [Punkt (2)] und der überwiegende Teil davon lebt noch; nur ein kleiner Teil ist unerreichbar geworden und kann frei gegeben werden [Punkt (1)]. Wenn der Garbage Collector alle überlebenden Objekte bei jeder Garbage Collection kopieren würde, so wie er es beim Mark-and-Copy macht, dann würde er sehr viel Zeit mit Kopieren verbringen, ohne dabei viel zu gewinnen.

Deshalb wird auf der Old Generation der schon in / GC1 / erwähnte Mark-and-Sweep-Algorithmus gemacht, bei dem nichts kopiert wird, sondern einfach nur die unerreichbaren Objekte frei gegeben werden.  Da dieser Algorithmus zur Fragmentierung des Heaps führt, hat man sich zusätzlich eine Variation des Mark-and-Sweep-Algorithmus überlegt, bei der im Anschluss an die Sweep-Phase eine Kompaktierung gemacht wird, durch die die Fragmentierung reduziert wird. Dieser Algorithmus wird als Mark-and-Compact-Algorithmus bezeichnet.

Serial Mark-and-Compact

Der Mark-and-Compact-Algorithmus hat jedoch den Nachteil, dass er aufwändig ist; für jedes „Loch“ muss erst einmal ein Objekt gefunden werden, das hineinpasst und das Loch schließt (siehe Abbildung 2).

Wie aufwändig der Mark-and-Compact-Algorithmus auf der Old Generation ist, erkennt man schon daran, dass er mehreren Phasen abläuft:

• Marking.
• Calculation of new locations.
• Reference adjustments.
• Moving.

Calculation of new locations. In der nächsten Phase wird ermittelt, wohin die überlebenden Objekte während der Kompaktierung kopiert werden sollen.  Der Garbage Collector fängt am Anfang der Old Generation an und sucht sich die erste freie Stelle und das erste überlebende Objekt, das von der Größe her in das Loch hineinpasst.  Diese neue Adresse für das überlebende Objekt merkt er sich für später.  Dann bestimmt er die nächste freie Stelle und das nächste überlebende Objekt und wiederholt den Vorgang, bis alle zu verschiebenden Objekte neue Zieladressen haben.

Reference adjustments. Danach werden die Referenzen auf die zu verschiebenden Objekte angepasst, da diese nach dem Umkopieren eine neue Adresse haben werden.  Dazu besucht der Garbage Collector vom Root Set ausgehend alle erreichbaren Objekte in allen Generationen und passt die Verweise an, die diese Objekte auf andere (zu verschiebende) Objekte haben.

Moving. In der letzten Phase werden dann endlich die Objekte an ihre Zieladressen verschoben.  Dazu fängt der Garbage Collector am Anfang der Old Generation an, sucht sich das jeweils nächste überlebende Objekt und kopiert es an die bereits berechnete Zieladresse.  Am Ende ist der eine Teil der Old Generation fast dicht gepackt und der Rest leer.

Unterm Strich ist der Mark-and-Compact-Algorithmus also ein relativ aufwändiger Algorithmus, der die Fragmentierung durch Kompaktierung reduziert; er ist vom Algorithmus her teuer und dauert lange.  Da er alle lebenden Objekte mehrmals besucht, wie man der Beschreibung der verschiedenen Phasen entnehmen kann, dauert der Algorithmus umso länger, je mehr überlebende Objekte es gibt und je größer der Bereich ist, der aufgeräumt werden muss. Da die Old Generation typischerweise groß ist und viele Objekte darin überleben, ist es naheliegend, dass sie nicht so häufig aufgeräumt wird wie die Young Generation.  Der teure Mark-and-Compact-Algorithmus läuft nur selten, dafür dann aber lange.

Man hat also einen Algorithmus gewählt, der die Eigenschaften der Old Generation angemessen berücksichtigt:

• Wegen der geringen Sterblichkeitsrate und der Größe der Old Generation läuft er selten und darf dann auch etwas länger dauern.  Wo nicht viel Müll entsteht, muss man auch nicht so oft aufräumen.
• Ebenfalls wegen der großen Zahl von überlebenden Objekten reorganisiert er den zur Verfügung stehenden Bereich (per Kompaktierung), statt alle lebendigen Objekte in einen freien Bereich zu kopieren oder die Fragmentierung des Speichers zu riskieren.
• Die anschließende Allokation funktioniert gut, weil wegen der Kompaktierung ein zusammenhängender freier Bereich zur Verfügung steht.

Alternative Algorithmen für die Old Generation

• einen parallelen Mark-and-Compact-Algorithmus , der zwar immer noch alle Applikation-Threads anhält, aber dann mit mehreren Garbage-Collector-Threads die Markierung und anschließende Kompaktierung erledigt.  Das ist zwar immer noch eine Stop-the-World-Vorgehensweise, aber die entstehende Pause ist auf einer Multi-Core- oder Multi-Prozessor-Maschine kürzer als beim seriellen Mark-and-Compact-Algorithmus.  Dieser parallele Algorithmus auf der Old Generation („ParallelOld“ genannt) ist seit Java 5 Update 6 verfügbar und wird mit der Option –XX:+UseParallelOldGC ausgewählt.

• einen konkurrierenden Mark-and-Sweep-Algorithmus , der zumindest teilweise konkurrierend zur Applikation läuft, ohne deren Threads anzuhalten, und nur gelegentlich kurze Stop-the-World-Phasen braucht.  Diesen Concurrent-Mark-and-Sweep-Algorithmus („CMS“ genannt) gibt es seit Java 1.4.1; er wird mit der Option –XX:+UseConcMarkSweepGC eingeschaltet. Wichtig dabei ist, dass dies nur ein Mark-and-Sweep-Algorithmus ist; eine Kompaktierung findet nicht statt, was zu dem schon diskutierten Problem der Fragmentierung führt.

Der ursprüngliche serielle Mark-and-Compact-Algorithmus wird übrigens zur Unterscheidung von den Alternativen „SerialOld“ genannt und kann mit der Option –XX:+UseSerialGC ausgewählt werden.

Wenn keine der drei Optionen explizit angegeben ist, bestimmt die JVM das Default-Verhalten.  Die Defaults ändern sich von Release zu Release.  Die nachfolgenden Angaben zu den Defaults sind daher als Momentaufnahme zu betrachten.

Seit Java 5 macht die virtuelle Maschine eine sogenannte Server-Class Machine Detection.  Dabei gilt eine Plattform mit mindestens zwei Prozessoren oder Kernen und mindestens 2 GB physikalischen Speicher als Server-Maschine (es sei denn, es handelt sich um eine i586 Microsoft Windows Plattform; sie wird per Default als Client-Maschine eingestuft).  Details zur Server-Class Machine Detection finden sich in / SUN1 /.

Auf einer Server-Maschine ist seit Java 6 der parallele Mark-and-Compact-Algorithmus der Default für die Old Generation; in Java 5 und auf Client-Maschinen muss man ihn explizit mit –XX:+UseParallelOldGC auswählen (siehe / SUN3 /).  Der Default-Algorithmus für die Young Generation ist seit Java 5 der parallele Mark-and-Copy-Algorithmus; in Java 1.4 und auf Client-Maschinen muss man ihn explizit mit -XX:+UseParallelGC auswählen (siehe ( GC2 / und / SUN2 /).

Der konkurrierenden Mark-and-Sweep-Algorithmus wird automatisch als Default ausgewählt, wenn man auf einer Server-Maschine mit der Option -XX:MaxGCPauseMillis=<nnn> ein Pausenziel vorgibt und dieses Ziel kleiner oder gleich 1.000 Millisekunden ist. Ansonsten muss man den Algorithmus explizit mit der Option –XX:+UseConcMarkSweepGC einschalten.
 
 

	-XX: Option	verfügbar seit	per Default verwendet für	Beschreibung
SerialOld	+UseSerialGC			serieller Mark-and-Compact
ParallelOld	+UseParallelOldGC	Java 5 Update 6	Server-Maschine  seit Java 6	paralleler Mark-and-Compact
CMS	+UseConcMarkSweepGC	Java 1.4.1	Server-Maschine  MaxGCPauseMillis <= 1000 seit Java 6	konkurrierender Mark-and-Sweep

Tabelle 1: JVM-Optionen zur Auswahl des Garbage-Collection-Algorithmus auf der Old Generation
 

Parallel Mark-and-Compact

• Marking.
• Summary.
• Compacting.

Summary . In der anschließenden Summary-Phase werden die einzelnen Segmente untersucht, um ein sogenanntes Dense Prefix für die anschließende Kompaktierungsphase zu bestimmen.  Die Idee dabei ist, dass ein Teil des Segments bereits relativ dicht gepackt sein könnte, weil dort die Objekte liegen, die bei der vorherigen Kompaktierung zusammen geschoben worden sind.  Wenn in diesem dichten Bereich nur wenige Objekte gestorben sind, dann lohnt es sich nicht, dort erneut eine Kompaktierung zu versuchen.  In der Summary Phase wird deshalb nach einem Punkt in der Region gesucht, jenseits dessen sich eine Reorganisation lohnt.  Der bereits dichte Bereich, das „Dense Prefix“, braucht nicht kompaktiert werden; die Objekte im Rest der Region sollen verschoben werden.  Diese Phase ist nicht parallel, weil sie sowieso recht schnell abläuft.

Compacting .  Die Kompaktierungsphase läuft dann wieder parallel ab und benutzt die Summary-Information aus der vorangegangenen Phase, um den locker gefüllten Teil der verschiedenen Segmente zu reorganisieren.  Das geht jetzt nicht so wie bei dem seriellen Mark-and-Compact-Algorithmus, den wir oben beschrieben haben, indem der Garbage Collector durch die ganze Old Generation oder durch ein ganzes Segment läuft und sukzessive die Löcher füllt.  Stattdessen sucht sich jeder Garbage-Collection-Thread einen freien Bereich am Ende eines Segments und kopiert dorthin dicht hintereinander weg die zu verschiebenden, überlebenden Objekte aus einem anderen Segment.  (Dieses Vorgehen hat eine gewisse Ähnlichkeit mit der Copy-Phase des Mark-and-Copy-Algorithmus, den wir von der Young Generation kennen.)  Dabei dient der Punkt nach dem in der Summary-Phase ermittelten Dense Prefix als Zieladresse für das Kopieren der Objekte aus einem anderen Segment.
Jeder Garbage-Collector-Thread arbeitet also auf zwei Segmenten, einem Quell- und einem Zielsegment.  In beiden Segmenten beginnt er bei dem Punkt nach dem Dense Prefix.  Im Quellsegment schaut alle nacheinander alle Objekte an, überspring die „toten“ Objekte und kopiert die lebenden Quell-Objekte hintereinander weg in den Bereich nach dem Dense-Prefix des Zielsegments. Selbstverständlich gibt es auch dabei wieder eine Referenzanpassung: alle Referenzen, die auf die verschobenen Objekte zeigen, werden auf den neuen Stand gebracht.
Nach diesem Kompaktieren ist das „lockere“ Ende nach dem Dense-Prefix des Quellsegments leer, weil die Objekte, die dort waren, mittlerweile alle ins Zielsegment wegkopiert worden sind.  Dann geht der Zyklus erneut los: das ehemalige Quellsegment wird Zielsegment und der Garbage-Collector-Thread kopiert an die nun freie Stelle dicht hintereinander die zu verschiebenden, überlebenden Objekte aus einem anderen Segment.

Abbildung 3 zeigt den Ablauf (vereinfacht, am Beispiel von nur drei Segmenten; tatsächlich gibt es natürlich viel mehr Segmente in der Old Generation): zuerst werden die Dense Prefixes für die Segemente bestimmt, dann wird in den ersten freien Bereich kopiert, dann in den nächsten freien Bereich und am Ende ist jedes Segment auf der einen Seite fast dicht gepackt und auf der anderen Seite zusammenhängend leer. Wie man sieht, ist der Algorithmus eine Mischung aus Kompaktierungs- und Kopiertechniken.

Da nicht in allen Phasen parallel gearbeitet wird, ist die parallele Old-Generation-Garbage-Collection nicht wirklich parallel, sondern nur quasi-parallel.  Trotzdem wird dies auf einer Multi-Core- oder Multi-Prozessor-Maschine zu kürzeren Stop-the-World-Pausen führen.

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)