AngelikaLanger.com - Der Garbage-First Garbage Collector (G1) - Details (original) (raw)

Der Garbage-First Garbage Collector (G1) - Details

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

In unserem letzen Artikel haben wir uns bereits die Heap-Aufteilung des G1 angesehen. Hier noch mal eine kurze Wiederholung zum Einstieg. Der gesamte User-Heap wird beim G1 in lauter gleichgroße Regionen (regions) aufgeteilt. In den ersten Versionen des G1 waren die Regionen ein MByte groß. Seit dem Release 1.6.0_18 können die Regionsgröße nun 1 bis 32 MByte sein (zusätzlich muss es auch eine Potenz von 2 sein).

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.

Abbildung 1: 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

Kommen wir nun zu den Details des G1. Natürlich kann man dabei beliebig in die Tiefe gehen. Wir haben uns an den Trace-Ausgaben des G1 orientiert und werden die interne Arbeitsweise des G1 soweit erklären, dass man seine Trace-Ausgaben verstehen kann. Da es derzeit keine Werkzeuge gibt, die die Trace-Ausgaben des G1 verstehen und verarbeiten können, ist man beim Tuning des G1 darauf angewiesen, zwecks Überprüfung der Tuning-Ergebnisse den Trace selber auszuwerten. Deshalb sollte man ihn grob verstehen. Um dies zu ermöglichen, wollen wir einige der internen Mechanismen des G1 erläutern.

Remembered Sets

Wer die bisherige Artikelserie über Garbage Collection aufmerksam verfolgt hat, erinnert sich vielleicht, dass wir den Begriff Remembered Set schon einmal bei der bisherigen Young Generation Garbage Collection erwähnt haben (siehe /GC2/). Damals war es eine Verwaltung, die alle Referenzen von der Old Generation in die Young Generation erkennt; diese „Cross Generational References“ sind für anschließende Collections auf der Young Generation von besonderer Bedeutung.

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: Remembered Sets

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;

ausgeführt wird, muss sich der G1 (in Form einer Write Barrier) fragen, ob dadurch eine neue Referenz über Regionsgrenzen etabliert wird. Dazu muss er prüfen, ob this und theOtherObjectin der gleichen Region liegen. Wenn sie nicht in der gleichen Region liegen, muss er in dem Remembered Set für die Region, in der theOtherObject liegt, this als externe Referenz eintragen.

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

Das Konzept des Marking bei der Garbage Collection haben wir bereits diskutiert, als wir uns die bisherigen Garbage Collector Algorithmen der Sun JVM in den vorhergehenden Artikeln angesehen haben (/GC2/, /GC3/, /GC4/). Daher nur kurz eine Zusammenfassung: Beim Marking werden ausgehend vom Root Set alle erreichbaren Objekte markiert. Damit erhält man den Graph aller lebenden Objekte.

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

Nun haben wir gesehen, was Remembered Sets und Marking beim G1 bedeuten. Was passiert jetzt im Detail während der Garbage Collection Pause? Dabei werden die Informationen aus Remembered Sets und Marking benutzt.

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. Generell werden die in den einzelnen Phase anstehenden Arbeiten in parallel-ausführbare Sub-Tasks zerlegt, um sie in mehren Garbage Collector Threads ausführen zu können. Dabei werden so viele Garbage Collector Threads verwendet, wie Prozessorkerne auf der Plattform zur Verfügung stehen.

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

Bis jetzt haben wir uns intensiv mit den Details der Garbage Collection Pause und der dazugehörigen Verwaltungsinformation des G1 beschäftigt. Nun fehlt noch, wie dies mit den Anforderungen an Pausenzeiten (die wir im letzten Artikel bereits diskutiert hatten) und den beiden Collection Modi (Fully Young und Partially Young) zusammenhängt.

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. Die ersten beiden Werte kann der G1 aus der Remembered Set Verwaltung direkt ermitteln. Die letzten beiden Werte wurden, so wie oben bereits beschrieben, beim Marking ermittelt. Nun werden pro Region die Anzahl der noch ausstehenden Remembered Set Updates mit den bisher ermittelten Durchschnittskosten für einen Remember Set Update multipliziert, genauso die Größe des Remembered Sets mit den Durchschnittskosten des Remember Scanning und die Gesamtgröße der lebenden Objekte mit den durchschnittlichen Kopierkosten pro Byte. So ergibt sich eine Abschätzung für die individuellen Kosten der Garbage Collection jeder einzelnen Old Region. Old Regions mit hinreichend geringen Kosten werden im Partially Young Mode mit in den Collection Set genommen. Man sieht also, die Garbage-First Auswahl betrachtet nicht nur die überlebenden Objekte in der Region, sondern auch die Aufwände, die im Zusammenhang mit dem Remembered Set stehen.

G1 Collection Lifecycle

Jetzt haben wir alle Informationen zusammen und schauen, wie der G1 über die gesamte Laufzeit der JVM funktioniert. Er startet im Fully Young Mode. Das bedeutet, dass der Collection Set aus allen Young Regions besteht. Die Pause dauert also: (Anzahl der Young Regions) x (bisheriger Durchschnittsaufwand). Der G1 lässt die Applikation laufen, bis sich so viele Young Regions angesammelt haben, dass dieses Produkt aus Anzahl und Durchschnittsaufwand gerade noch unter MaxGCPauseMillis, der Schranke für die maximale Pause, liegt. Dann macht er eine Fully Young Garbage Collection Pause. Dabei orientiert der G1 sich überhaupt nicht an GCPauseIntervalMillis. Wenn der Wert nicht eingehalten worden ist, erhält die Anwendung weniger Laufzeit als spezifiziert.

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

In diesem Artikel haben wir uns die Details des Garbage-First (G1) Garbage Collectors soweit angesehen dass man seine Trace-Ausgaben verstehen kann. Dabei haben wir nicht alle Aspekte erwähnt. Zum Beispiel wird man beim Blick in die Trace-Ausgaben gelegentliche Full Garbage Collections finden, die wir nicht erwähnt haben. Verglichen mit den Full Garbage Collection Pausen, die beim CMS vorkommen, sind die entstehenden Pausen aber beim G1 relativ kurz.

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)