Im letzten Artikel (siehe / GC7 /) haben wir uns bereits in einem Überblick den neuen Garbage-First Garbage Collector (oder kurz: G1) auf Suns  JVM angesehen.   In diesem Artikel wollen wir uns die Details ansehen.  Diese Detailinformation helfen, die interne Funktionalität des Garbage Collectors und damit seine Trace-Ausgaben zu verstehen.  Dieses Verständnis ist wiederum notwendig für ein erfolgreiches Tuning.
 

Wiederholung

Eine Region enthält entweder nur junge Objekte ( Young Region ) oder nur alte Objekte ( Old Region ).  Natürlich kann eine Region auch aktuell gar nicht genutzt werden und leer sein. Durch die Aufteilung in Young und Old Regions ergibt sich wieder eine Generational Garbage Collection , die ähnlich, aber im Detail doch deutlich anders ist, als bei den bisherigen Garbage Collectoren.  Abbildung 1 zeigt beispielhaft einen G1 User-Heap.

Bei der Garbage Collection werden die überlebenden Objekte aus einer vollen Region in eine freie Old Region kopiert (Evakuierung). Die vormals volle Region wird danach freigegeben und ihr Speicher steht wieder für die Allokation zur Verfügung.  Ob eine Region als Young oder Old Region verwendet wird, ist im G1 immer nur temporär.  So kann eine Old Region nach der Evakuierung für die Allokation neuer Objekte (also als Young Region) oder auch erst mal gar nicht genutzt werden.

Die Young Regions teilen sich ihrerseits noch mal in zwei Typen von Regionen auf. Da sind zum einen die Regionen, in denen aktuell Objekte angelegt werden ( Allocation Regions ), und zum anderen die Survivor Regions .  Die Survivor Regions haben eine ähnliche Aufgabe wie die Survivor Spaces (siehe / GC1 /) bei den bisherigen Garbage Collectoren:  Sie nehmen Objekte auf, die bei der Evakuierung aus einer Young Region herauskopiert wurden, aber noch nicht direkt in eine Old Region kopiert werden sollten.

Die Regionen, die bei einer Garbage Collection evakuiert werden sollen, nennt man beim G1 Collection Set.  Der G1 kennt zwei Modi bei der Garbage Collection, die auch den Collection Set betreffen: Fully Young Mode und Partially Young Mode .  Im Fully Young Mode gehören alle Young Regions zum Collections Set.  Beim Partially Young Mode besteht der Collection Set auch wieder aus allen Young Regions; zusätzlich kommen die Old Regions dazu, die keine oder relativ wenig lebende Objekte enthalten.  Dieses letzte Charakteristikum hat dem G1 (Garbage-First) Garbage Collector seinen Namen gegeben:  Die Old Regions mit keinen oder relativ wenig lebenden Objekte, oder anders ausgedrückt: die mit besonders viel „Garbage“, werden zuerst berücksichtigt, und das heißt dann sehr verkürzt ausgedrückt: garbage first .
 

Details der G1 Verwaltung

Remembered Sets

Beim G1 ist es so ähnlich, nur nicht auf Basis von Generationen, sondern bezogen auf Regionen.  Pro Region gibt es einen Remembered Set, der alle externen Referenzen von anderen in diese Region kennt.

Abbildung 2 zeigt an einem Beispiel die Beziehungen zwischen Remembered Set und Regionen.  Zu jeder der drei Regionen (unten im Bild) gehört jeweils ein Remembered Set (oben im Bild).  Die vier Objekte referenzieren sich so wie dargestellt (dünne, abgewinkelte Pfeile).  Daraus ergibt sich, dass die Remembered Sets zu den beiden äußeren Regionen leer sind, weil es keine Verweise aus anderen Regionen in diese Regionen gibt.  Der Remembered Set zu der mittleren Region enthält zwei Einträge, die auf die zwei Objekte in der linken bzw. rechten Region verweisen (dicke, grade Pfeile); es sind die beiden einzigen Verweise aus anderen Regionen in die mittlere Region hinein.

Es stellt sich nun die Frage, warum der G1 für jede Region einen separaten Remembered Set braucht statt eine globale Verwaltungsstruktur für alle Querverweise zwischen den Regionen zu verwenden.  Das lässt sich leicht erklären.  Zum Zeitpunkt der Garbage Collection muss man alle Objekte im Collection Set kennen, die von außerhalb des Collection Sets referenziert und damit am Leben gehalten werden.  Das geht aber nur, wenn man weiß, welche Regionen zum Collection Set gehören.  Beim G1 wird (im Partially Young Mode) der Collection Set aber erst im Augenblick der Garbage Collection festgelegt. Erst zu diesem Zeitpunkt entscheidet sich für die Old Regions, welche davon im Collection Set sind und welche nicht.  Das ist das „garbage first“-Prinzip.  Wegen dieser dynamischen Vorgehensweise wird die Verwaltung der externen Referenzen in Form des Remembered Sets direkt mit den einzelnen Regionen assoziiert.  Die Vereinigungsmenge aller Remembered Sets, die zu den Regionen des Collection Sets gehören, liefert dann die Information, die bei der Garbage Collection gebraucht wird, nämlich welche Objekte im Collection Set von außerhalb des Collection Sets referenziert werden.  In der Vereinigungsmenge sind dann überflüssigerweise auch noch Referenzen innerhalb des Collection Sets enthalten. Diese lassen sich aber leicht identifizieren und ignorieren.

Wie die Information aus den Remembered Sets bei der Garbage Collection genau benutzt wird, schauen wir uns weiter unten an.  Hier wollen wir uns erst einmal überlegen, wie die Information in die Remembered Sets gelangt.

Immer wenn von der JVM (Java Virtual Machine) eine Codezeile wie diese:

this.myField = theOtherObject;

Um das Anwendungsprogramm durch diese Verwaltungsaufgaben nicht zu verlangsamen, wird der möglicherweise nötige Update des Remembered Set als eigene Task ausgeführt.  Das heißt, sollte die neue Referenz über Regionsgrenzen gehen, so wird eine spezielle Update Task erzeugt, um this im Remembered Set einzutragen.  Für die Abarbeitung der Update Tasks steht ein spezieller Thread zur Verfügung.  Dieser Thread hat eine besonders niedrige Priorität und läuft nur dann, wenn die CPU nicht von einem Anwendungsthread benötigt wird.

Die Konsequenz dieses Ansatzes ist, dass die Information in den Remembered Sets zumeist nicht up-to-date ist.  Das wird natürlich zum Problem, wenn der G1 die Remembered Sets in der Garbage Collection Pause benötigt.  Deshalb werden als erste Tätigkeit in der Garbage Collection Pause die noch nicht verarbeiteten Remember Set Updates für die Regionen im Collection Set durchgeführt.

Bis jetzt klingt es so, als würde die Remembered Set Verwaltung einen erheblichen Overhead verursachen.  Das ist aber nicht so.  Es gibt im Detail noch einige Optimierungen.  Diese zu diskutieren sprengt aber den Rahmen des Artikels.

Concurrent Marking

Wie beim CMS (/ GC4 /) läuft auch beim G1 das Marking im Wesentlichen konkurrierend zur Anwendung ab.  Das ist positiv, denn damit kommt es während des Markings nicht zu Pausen in der Anwendung.  Es gibt nur sehr kurze Unterbrechungen der Anwendung bei Start und Ende des Markings. Das ist auch wieder wie beim CMS.

Damit hören die Gemeinsamkeiten des G1 mit den bisherigen Garbage Collectoren schon auf.  Das Marking beim G1 hat einige Besonderheiten, die wir uns im Folgenden genauer ansehen.

Beim G1 wird ein Snapshot-At-The-Beginning (SATB) erzeugt.  Das bedeutet: der aus dem Marking resultierende Graph enthält alle lebenden Objekte zu Beginn des Markings .  Beim CMS (siehe / GC4 /) ist das anders.  Der CMS erzeugt einen Snapshot-At-The-End (SATE).  Deshalb muss beim CMS relativ viel Aufwand betrieben werden, damit das Marking die Änderungen berücksichtigt, die durch die Applikation während des Markings entstehen.  Der CMS läuft der Anwendung sozusagen hinterher, um das Marking up-to-date zu halten.  Das ist auch der Grund, warum der G1 keine einen Snapshot-At-The-End sondern einen Snapshot-At-The-Beginning erzeugt: das SATB-Marking ist weniger aufwändig, benötigt weniger Zeit und ist vorhersehbarer.

Der Nachteil des SATB ist, dass das Ergebnis nicht aktuell ist.  Der G1 kann damit leben, weil er anders als andere Garbage Collectoren die Marking Information nicht dazu hernimmt, um von jedem einzelnen Objekt zu bestimmen, ob es noch lebt oder nicht.  Beim G1 wird die Marking Information nur dazu verwandt, um zu bestimmen, ob die Objekte in den Remembered Sets noch leben.

Das G1 Marking hat noch eine Besonderheit.  Neben dem Prüfen der Erreichbarkeit wird zusätzlich die Größe der erreichten Objekte protokolliert.  In einer speziellen Count -Phase nach Abschluss des Markings wird diese Information regionsspezifisch ausgewertet.  So wird bestimmt, wie viele lebende Objekte es in einer Region gibt und wie groß sie sind.  Das ist im Kern die Information, die bei der Garbage-First Auswahl benutzt wird, um zu entscheiden, ob eine Old Region viel Müll enthält und deshalb bei der nächsten Garbage Collection berücksichtigt wird oder nicht.

Die Garbage Collection Pause

Grob betrachtet teilt sich die Garbage Collection Pause in drei Phasen:

• Verarbeiten der noch ausstehenden Remembered Set Updates für alle Regionen des Collection Sets.
• Bestimmen der lebenden Objekte im Collection Set.
• Herauskopieren der lebenden Objekte in freie Regionen.

Was in der ersten und dritten Phase, dem Remembered Set Update und dem Herauskopieren der lebenden Objekte, passiert, haben wir bereits erläutert.  Schauen wir uns an, was in der zweiten Phase geschieht, wenn die lebenden Objekte im Collection Set ermittelt werden.

Die Idee ist, dass alle Referenzen, die in den Collection Set verweisen, innerhalb des Collection Sets weiterverfolgt werden.  Die Objekte, die dabei erreicht werden, sind die lebenden Objekte des Collection Sets.  Dieser Vorgang des Weiterverfolgens der Referenzen im Collection Set wird Scanning genannt.

Was sind nun die Referenzen, die in den Collection Set verweisen?  Es gibt drei Arten davon.

• Remembered Set . Über diese Gruppe von Referenzen haben wir bereits oben ausführlich diskutiert; es geht um die Referenzen aus den Remembered Sets zu allen Regionen des Collection Sets.  Ob die aus den Remembered Sets referenzierten Objekte selbst noch leben, wird durch Abgleich mit der Marking Information geprüft.  Nicht mehr lebende Objekte werden nicht weiterverfolgt.
• Root Set. Neben den Remembered Sets müssen auch noch die Referenzen aus dem Root Set gescannt werden.  Dabei werden natürlich nur die Referenzen betrachtet, die direkt in den Collection Set verweisen.
• Mark Stack .  Mark-Stack-Referenzen, die in der Collection Pause gescannt werden müssen, entstehen, wenn ein gerade aktives Concurrent Marking durch eine Garbage Collection Pause unterbrochen wird.  Dann ist das Marking unvollständig und es gibt Referenzen, die während des Markings noch nicht verfolgt wurden.  An diesen noch nicht verfolgten Mark-Stack-Referenzen könnten lebendige Objekte hängen, die noch nicht als lebendig identifiziert wurden.  Obwohl eine solche Situation in der Praxis eher selten ist, kann sie gelegentlich auftreten, und die G1 Verwaltung muss eine solche Situation behandeln können.  Deshalb werden Mark-Stack-Referenzen, die in den Collection Set zeigen, ebenfalls in der Collection Pause gescannt.

Wenn man sich die Trace-Ausgabe (mit -verbosegc –XX:PrintGCDetails ) zu einer Garbage Collection Pause ansieht, findet man alle oben beschriebenen Aktivitäten wieder.

Abbildung 4: Trace einer Garbage Collection Pause

Abbildung 4 zeigt einen solchen Trace. Update RS   ist der Remembered Set Update zu Anfang der Pause. Dann kommt das Scanning. Ext Root Scanning ist das Scanning der Referenzen aus dem Root Set, die direkt in den Collection Set verweisen. Mark Stack Scanning ist das Scanning der Mark Stack Referenzen.  Es wird immer im Trace angezeigt, auch wenn aktuell gar kein Mark Stack existiert.  Scan RS ist das Scanning der Remembered Set  Einträge.  Bei Object Copy handelt es sich um die letzte Phase der Pause: das Herauskopierens der lebenden Objekte.

Was sich hinter Scan-Only Scanning verbirgt, wissen wir auch nicht so genau.  Tony Printezis, der Lead der G1 Entwicklung, meinte dazu nur sinngemäß, dass sie da mal was ausprobiert hatten, was aber nicht überzeugen konnte.  Eventuell wird man die Trace-Ausgabe in Zukunft deshalb auch wieder herausnehmen.

Auffallend ist noch, dass hinter jeder Aktivität zwei Zeiten stehen.  Das sind die Aufwände pro Garbage Collector Thread.  Der Trace stammt von einem Dual-Core-System, deshalb gibt es zwei Garbage Collector Threads.

Bestimmung des Starts einer Collection Pause

Schauen wir uns zuerst die Anforderungen an die Garbage Collection Pause noch einmal genauer an.  Mit Hilfe von JVM Startoptionen kann man beim G1 eine Untergrenze für den Abstand zwischen dem Start zweier aufeinander folgender Garbage Collection Pausen und eine Obergrenze für die Pause selbst vorgeben.  Die Option für den Abstand ist -XX:GCPauseIntervalMillis (Defaultwert: 500ms) und die Option für die Länge der Pause ist  -XX:MaxGCPauseMillis  (Defaultwert: 200ms).  Die Anforderungen sind keine Real-Time-Anforderungen, aber der G1 versucht die Pausen so zu steuern, dass sie den Anforderungen entsprechen.

Wie macht er das?  Zuerst einmal braucht er dafür eine Abschätzung, wie lange die nächste Garbage Collection für den aktuellen Collection Set dauern wird.  Erinnern wir uns noch mal: im aktuellen Collection Set sind je nach Modus alle Young Regions (Fully Young Mode) oder sogar alle Young Regions und zusätzlich weitere Old Regions mit hinreichend viel Garbage (Partially Young Mode).

Für die Abschätzung der Pausenlänge verwendet der G1 die Zeiten, die bei vorhergehenden Pausen entstanden sind.  Das sind die Avg , Min , Max Werte in Abbildung 4.  Dabei geht bei der heutigen Implementierung des G1s nur der Durchschnittswert (Avg) in die Abschätzung ein.  Die genauen Details der Abschätzung finden sich in / ISMM /. Wir beschränken uns hier auf eine kurze Zusammenfassung.

Bei der Young Region ist es relativ einfach. Für die Abschätzung des Aufwands wird einfach der Durchschnittswert aller vorhergehenden Garbage Collection Aufwände für Young Regions hergenommen.

Bei der Bestimmung des Aufwands für eine Old Region spielen drei Kriterien eine Rolle:

• die Anzahl der noch ausstehenden Remembered Set Updates,
• die Größe des Remembered Sets,
• die Anzahl und die Gesamtgröße der lebenden Objekte.

G1 Collection Lifecycle

Der G1 bleibt erst einmal im Fully Young Mode und die Zeitpunkte für die nächste Collection Pause werden wie gerade beschrieben bestimmt.  Wenn der Heap bis zu einem gewissen Grad benutzt ist, wird das erste Concurrent Marking angestoßen.

Wenn das Marking fertig geworden ist, schaltet der G1 in den Partially Young Mode.  Für den Zeitpunkt der nächsten Collection Pause orientiert er sich nun an GCPauseIntervalMillis ., der unteren Schranke für die Applikationslaufzeit.  Er lässt die Applikation so lange laufen, bis der Wert überschritten ist und damit die Anforderung erfüllt ist.  Dann leitet er die Garbage Collection Pause ein.  Er berechnet wie vorher schon den Aufwand für die existierenden Young Regions aus dem Produkt von Anzahl der Young Regions und bisherigem Durchschnittsaufwand.  Wenn dieses Produkt kleiner als MaxGCPauseMillis ist, nimmt er für die restliche Pausenzeit Old Regions mit in den Collections Set. Dabei verfährt er nach der Garbage-First Regel: die Regionen mit den geringsten Aufwänden zuerst.  Nachdem so der Collection Set zusammengestellt ist,  kommt die eigentliche Garbage Collection Pause.

Der G1 bleibt solange im Partially Young Mode, bis sich die Garbage Collection auf Old Regions nicht mehr lohnt, das heißt, bis es keine Old Regions mit wenigen überlebenden Objekten mehr gibt.  Dann schaltet er wieder in den Fully Young Mode  und der Zyklus beginnt von vorn.

Die in Abbildung 4 gezeigte Garbage Collection Pause erfolgte im Fully Young Mode.  Das kann man an dem (young) in der ersten Zeile erkennen.  Bei einer Pause im Partially Young Mode steht dort stattdessen (partial) .  Alle weiteren Ausgaben sind gleich, denn die Tätigkeiten während der Garbage Collection Pause sind in beiden Modi identisch.  Nur die Auswahl der Regionen unterscheidet sich.
 

Zusammenfassung und Ausblick

Beschrieben haben wir die Interna des G1, weil es den G1 erst seit JDK 1.6.0_14 gibt und derzeit Werkzeuge fehlen, die seine Trace-Ausgaben so aufbereiten können, dass man sie leicht für ein Tuning des G1 heranziehen könnte.  Man muss also gezwungenermaßen die Trace-Ausgaben selber lesen, um zu ermitteln, wie sich der G1 verhält, oder sich ein kleines Skript zur Auswertung selber schreiben.

Das Tuning selbst ist ganz anders als bei den herkömmlichen Garbage Collectoren.  Größenangaben für die verschiedenen Speicherbereiche (wie die Größe von Young Generation, Survivor Space, etc. bei den alten Collectoren) spielen beim G1 kaum eine Rolle.  Wesentlich sind die Vorgaben für die Pausen.  Auf diese Vorgaben reagiert der G1 aber nur sehr indirekt.  Meistens hält der G1 die Vorgaben nicht ein und man muss ein Gefühl dafür entwickeln, worauf der Collector wie reagiert.
 
Damit endet unsere Artikelserie zum Thema Garbage Collection.  Beim nächsten Mal werden wir uns ansehen, was es Neues im Bereich Java SE gibt, und werden einen Ausblick auf den JDK 7 wagen.
 

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)