Angelika Langer - Training & Consulting
HOME | COURSES | TALKS | ARTICLES | GENERICS | LAMBDAS | IOSTREAMS | ABOUT | NEWSLETTER | CONTACT | Twitter | Lanyrd | Linkedin
 
HOME 

  OVERVIEW

  BY TOPIC
    JAVA
    C++

  BY COLUMN
    EFFECTIVE JAVA
    EFFECTIVE STDLIB

  BY MAGAZINE
    JAVA MAGAZIN
    JAVA SPEKTRUM
    JAVA WORLD
    JAVA SOLUTIONS
    JAVA PRO
    C++ REPORT
    CUJ
    OTHER
 

GENERICS 
LAMBDAS 
IOSTREAMS 
ABOUT 
NEWSLETTER 
CONTACT 
Java Performance - Gabarge Collection

Java Performance - Gabarge Collection
Java Performance: 
Garbage Collection

Wie funktioniert Garbage Collection?

JavaSPEKTRUM, Mai und Juli 2006
Klaus Kreft & Angelika Langer

Dies ist das Manuskript eines Artikels, der im Rahmen einer Kolumne mit dem Titel "Effective Java" im JavaSPEKTRUM erschienen ist.  Die übrigen Artikel dieser Serie sind ebenfalls verfügbar ( click here ).

Jede Java-Anwendung verbringt einen gewissen Teil der Verarbeitungszeit mit Garbage Collection, d.h. mit dem Freigeben von Speicher und dem Aufräumen des Heaps.  Wir haben in den letzten Artikeln über Java-Performance nachgedacht und Techniken und Strategien für die Performance-Verbesserung diskutiert.  Auch Garbage Collection hat Auswirkungen auf die Performance.  Wenn es gelingt, den Garbage Collector so zu konfigurieren, dass er wenig Zeit in Anspruch nimmt, dann steht mehr Zeit für die eigentliche Funktionalität der Java-Anwendung zur Verfügung, d.h. die Verarbeitung ist schneller.  Das Tuning des Garbage Collectors ist daher eine der Maßnahmen, die man im Rahmen eines Performance-Profilings und –Tunings in Angriff nehmen wird.  Wir wollen uns in diesem und dem nächsten Artikel deshalb mit Garbage Collection und dem Tuning des Garbage Collectors der Sun JVM befassen.

Java-Programme fordern während ihres Ablaufs fortwährend Speicher vom Heap (dt. Freispeicher) an, um dort die für die Verarbeitung benötigten Objekte abzulegen.  Sobald die Objekte nicht mehr benötigt werden, sollen sie weggeräumt und ihr Speicher freigegeben werden.  Andernfalls hätte das Programm nach einer gewissen Zeit sein Speicherkontingent verbraucht und könnte nicht mehr weiterarbeiten.

In Java wird die Speicherfreigabe automatisch vom Laufzeitsystem erledigt.  Teil der Virtuellen Maschine ist der sogenannte Garbage Collector (dt. Speicherbereinigung, wörtlich: Müllabfuhr), der in regelmäßigen Abständen alle nicht benötigten Objekte wegräumt und wieder Platz für neue Objekte schafft.  Die automatische Speicherbereinigung ist äußerst vorteilhaft für den Programmierer; der muß sich nämlich keine Sorge um die Speicherfreigabe machen und kann unbeschwert so viele Objekte anlegen, wie er will.  Das ist in Sprachen wie C oder C++ ganz anders.  Dort muss sich der Entwickler selbst um die Lebensdauer seiner Daten kümmern und sie auch selbst wegräumen.  Das ist einerseits mühselig und fehleranfällig, andererseits ermöglicht es aber eine wesentlich genauere Kontrolle der Speicherverwaltung durch den Programmierer.

In Java nimmt die Virtuelle Maschine dem Entwickler die mühselige und fehleranfällige Arbeit der Speicherfreigabe ab.  Dafür hat der Programmierer in Java aber relativ wenig Einfluss darauf, wann und wie Speicherbereinigung betrieben wird und wie lange sie dauert.  Das ist unter dem Aspekt eines Performance-Tunings nicht unbedingt vorteilhaft – wie wir später sehen werden.  Zwar stellt die Virtuelle Maschine üblicherweise eine Reihe von Konfigurationsmöglichkeiten für den Garbage Collector zur Verfügung, aber der Einfluss bleibt relativ gering.  Die Konfigurationsmöglichkeiten wollen wir uns beim nächsten Mal am Beispiel der Sun JVM genauer ansehen.
Aber eher wir das tun, wollen wir uns erst einmal einen Überblick darüber verschaffen, wie Garbage Collection überhaupt funktioniert.  Nachfolgend erläutern wir die klassischen Garbage Collection Algorithmen mit Hinblick auf die Techniken, die in der Sun JVM verwendet werden. Dieses Hintergrundswissen ist notwendig; sonst versteht man den Sinn und Zweck der Tuning-Optionen nicht.  Wer sich darüber hinaus für Garbage Collection interessiert, dem sei das exzellente Buch von Jones & Lins (siehe / BOOK /) empfohlen.
 

Wie funktioniert Garbage Collection?

Im einfachsten Fall funktioniert Garbage Collection über Reference Counting.  Was muß der Garbage Collector tun?  Er will all die Objekte identifizieren, die nicht mehr gebraucht werden, und sie wegräumen.  Woran kann er das erkennen?  Daran, dass benutzte Objekte referenziert werden und nicht-benötigte Objekte eben nicht.

Reference Counting GC

In Java werden alle Objekte auf dem Heap angelegt und sind über Referenzvariablen erreichbar.  Wenn es keine Referenz mehr aufs Objekt gibt, dann wird es offensichtlich nicht mehr gebraucht.  Das ist etwas vereinfacht dargestellt.  Es gibt Weak- und Soft-References, die sehr wohl auf Objekte verweisen, und die Objekte werden trotzdem als Müll betrachtet.  Aber im Fall von „normalen“ Java-Referenzen kann man an der Zahl der Verweise auf ein Objekt erkennen, ob ein Objekt weggeräumt werden kann oder nicht.  Das Einfachste wäre also, einen Referenzzähler zu jedem Objekt zu verwalten und vom Garbage Collector alle Objekte mit Referenzzähler == 0 wegräumen zu lassen.

Leider hat Reference Counting einen erheblichen Nachteil:  bei Garbage Collection über Reference Counting würden Objekte übrig bleiben, die sich zyklisch gegenseitig referenzieren.  Ein Geflecht von Objekten könnte als Ganzes unerreichbar sein, aber jedes der Objekte im Geflecht hätte einen Referenzzähler > 0.  In dem Fall wäre das gesamte Objekt-Geflecht Müll, würde aber nicht weggeräumt.  Mit anderen Worten, Reference Counting hinterläßt Memory Leaks (dt. Speicherlecks).  Das ist ein erheblicher Nachteil und deshalb wird Garbage Collection über Reference Counting in der Praxis nicht benutzt.  Statt dessen werden sogenannte Mark-and-Sweep-Algorithmen verwendet.

Mark-and-Sweep GC

Die Idee beim Mark-and-Sweep ist folgende:  man verfolgt ausgehend von einer Menge von erreichbaren Objekte (den sogenannten Roots) alle Referenzen, die man finden kann, und markiert die besuchten Objekte.  Zum Root-Set gehören beispielsweise alle statischen Referenzvariablen und die Referenzvariablen auf dem Stack des Programms.  Nach der Markierungsphase wird geprüft, welche Objekte auf dem Heap markiert sind und welche nicht.  Die markierten Objekte sind offensichtlich erreichbar und werden als „lebendige“ Objekte betrachtet.  Alles andere sind „tote“ Objekte; sie sind nicht erreichbar und damit Müll, der weggeräumt werden kann.  Das Wegräumen wird als Sweeping (dt. kehren, fegen) bezeichnet.  Daher stammt auch der Name Mark-and-Sweep.

Die Mark-and-Sweep-Technik hat den Vorteil, dass zyklische Referenzen nicht dazu führen können, dass unerreichbare Objekt-Geflechte übrig bleiben, so wie das beim Reference Counting passieren kann.  Mark-and-Sweep hat aber den Nachteil, dass für die Markierungsphase die Anwendung komplett gestoppt werden muß.  Es ist nämlich nicht möglich, die Referenzen zuverlässig zu verfolgen, wenn die Anwendung parallel dazu die Referenzbeziehungen ändert.  Also muß die Anwendung zum Zwecke der Garbage Collection angehalten werden, was ein ernsthaftes Problem ist in Anwendungen, die nahezu Realtime-Anforderungen haben und gewisse Aufgaben innerhalb einer gegebenen Zeitspanne erledigen müssen.  Wenn zum Beispiel auf einen Request innerhalb von 50 Millisekunden geantwortet werden muß und die Garbage Collection dauert allein länger als 500 Millisekunden, dann hat man ein echtes Problem.  Insbesondere die frühen Implementierungen der Virtuellen Maschine haben solche „Stop-the-World“-Effekte produziert.  Heutzutage sind die Algorithmen wesentlich pfiffiger, so dass die Garbage-Collection-Pausen nicht mehr so drastisch ausfallen.  Aber prinzipiell sind die Pausen noch immer ein potentielles Problem.

Mark-and-Sweep hat noch einen anderen Nachteil gegenüber dem Reference Counting:  „tote“ Objekte werden nicht sofort weggeräumt, sondern erst nach einer Weile, wenn die Virtuelle Maschine beschließt, die Anwendung anzuhalten und den Gargabe Collector anzustoßen.  Beim Reference Counting kann ein „totes“ Objekt sofort in dem Moment erkannt werden, wenn der Referenzzähler von 1 auf 0 kippt.  Die Virtuelle Maschine muss ohnehin während des Programmablaufs die Referenzen verwalten, Zuweisungen ausführen und Stackframes auf- und abbauen.  Sie würde also leicht erkennen können, wann ein Objekt seine letzte Referenz verliert und könnte dann sofort fürs Wegräumen des „toten“ Objekts sorgen.  Erstens bräuchte man dann keine langen Garbage-Collection-Pausen und zweitens würde der Speicher sofort bereinigt, so dass sich keine Müllberge ansammeln könnten.  Letztlich überwiegen aber die Vorteile des Mark-and-Sweep (Vermeidung von Memory Leaks) die Nachteile (Pausen und Müllberge), so dass alle gängigen Virtuellen Maschinen Garbage Collection mit Mark-and-Sweep machen.

Über die Zeit wurden die Garbage Collection Algorithmen in Java weiter verfeinert.  Insbesondere die Erkenntnis, dass in Java die meisten Objekte jung sterben, hat zur sogenannten Generational Garbage Collection geführt.

Generational GC

In Java kann man keine Objekte auf dem Stack anlegen, sondern alle Objekte müssen auf dem Heap alloziert werden. Selbst Objekte, die nur für den Ablauf einer kurzen Methode gebraucht werden, entstehen auf dem Heap.  D.h. sie leben nicht lange.  Beim Verlassen der Methode werden sie bereits unerreichbar und sind „tot“.  Das führt zu der in Abbildung 1 gezeigten Objekt-Population eines typischen Java Programms.


Abbildung 1: Typische Objekt-Population in Java

Es gibt sehr viele Java-Objekte, die nicht sehr alt werden, und es gibt relative wenige Objekte, die sehr lange leben.  Die Objekte mit kurzer Lebensdauer sind die, die nur innerhalb einer Methode oder manchmal nur innerhalb einer Expression gebraucht werden.  Beispiele sind Iteratoren in einer Schleife oder StringBuffer fürs Zusammensetzen eines Strings.  Die Objekte mit mittlerer Lebensdauer sind solche, die in nicht-stackbasierten Verarbeitungen benutzt werden.  Ein Beispiel wäre der Conversational Session State einer Entity Bean.  Er überlebt mehrere Methoden und wird nach der Session nicht mehr gebraucht.  Man beachte, die Zahl der Objekte mit mittlerer Lebensdauer ist deutlich geringer als die der kurzlebigen Objekte.  Richtig alt werden nur ganz wenige Objekte.  Das sind typischerweise Objekte, die schon beim Programmstart (oder per Lazy Evaluation etwas später) erzeugt werden und dann bis zum Ende der Anwendung in Gebrauch bleiben.  Dazu gehören Thread Pools, Singletons und Objekte aus Frameworks, z.B. Servlet-Instanzen.

Um dieser Verteilung der Objekt-Lebenszeiten angemessen Rechnung zu tragen, werden die Objekte sogenannten Generationen zugeteilt.  Für die verschiedenen Generationen werden separate Sektionen des Heap verwendet, die unterschiedlich oft und mit jeweils eigenen Garbage Collection Algorithmen aufgeräumt werden.  Im Wesentlichen unterscheidet man zwischen einer Young Generation, die häufig bereinigt wird, und einer Old Generation, die seltener bereinigt wird.  Die häufigen Garbage Collections in der Young Generation haben den Vorteil, dass nicht immer der ganze Heap nach „toten“ Objekten durchforstet werden muss, sondern dass bereits das Aufräumen unter den jungen Objekten signifikante Mengen an Speicher freigibt.  In der Old Generation lohnt sich das häufige Aufräumen nicht.  Wenn ein Objekt erst einmal mittelalt geworden ist, dann wird es mit hoher Wahrscheinlichkeit auch noch älter.  In der Old Generation findet man deshalb nicht so häufig „tote“ Objekte und damit weniger Potential für die Speicherfreigabe. Also macht man die Bereinigung der Old Generation wesentlich seltener.

Die häufigen Bereinigungen in der Young Generation werden übrigens als Minor Collections bezeichnet. Daneben gibt es die seltener durchgeführten Major oder Full Collections, bei denen sowohl die Young als auch die Old Generation bereinigt wird. Diese Unterscheidung kann man bereits sehen, wenn man die Virtuelle Maschine mit der Option –verbose:GC aufruft.  Die Virtuelle Maschine gibt dann Information über die Garbage Collection aus (siehe Abbildung 2).


Abbildung 2: Garbage Collection Information per JVM-Option -verbose:GC

Man kann sehen, dass eine Full Garbage Collection selten durchgeführt wird, deutlich länger dauert als die Minor Garbage Collections, aber keineswegs mehr Speicher freischaufelt als eine Minor Garbage Collection.

In der Sun JVM wird Generational Garbage Collection betrieben und entsprechend ist der Heap in 2 Generationen (young und old) und einen Sonderbereich (perm) eingeteilt (siehe Abbildung 3).  Die Young Generationen zerfällt nochmals in Untersektionen, die mit dem Algorithmus zu tun haben, der für die Young Generation angewandt wird. Der Perm-Bereich ist keine Generation und hat mit der Alterung der Objekte nichts zu tun.


Abbildung 3: Heap-Aufteilung in eine Sun JVM

Die Young Generation besteht aus einem Bereich, der als Eden bezeichnet wird, und zwei sogenannten Survivor Spaces.  Eden ist der Teil des Heaps, aus dem der new-Operator (oder das newInstance() per Reflection) den Speicher für neu erzeugte Objekte alloziert.  Das heißt, alle neuen Objekte entstehen in Eden.

Von den beiden Survivor-Bereichen ist grundsätzlich einer immer leer. Man bezeichnet den benutzten Bereich als from-Space und den leeren Bereich als to-Space. Die Namen haben stammen daher, dass während einer Garbage Collection Objekte vom from-Space in den leeren to-Space kopiert werden.

Wenn nämlich im Rahmen einer Minor Garbage Collection überlebende Objekte in Eden und dem from-Space gefunden werden, so werden alle diese überlebenden Objekte in den to-Space kopiert.  Danach wird der vormals belegte Speicher (Eden und der from-Space) als Ganzes freigegeben.  Dabei wechseln from- und to-Space ihre Rollen.  Danach entstehen wieder Objekte in Eden, bis bei der nächsten Garbage Collection der Zyklus von vorne beginnt.

Copying GC

Die beiden Survivor-Bereiche sind typisch für sogenannte Copy-Garbage-Collection-Algorithmen.  Das Ziel eines Copy-Algorithmus ist die Vermeidung der Fragmentierung des Speichers.

Wenn der Garbage Collector in der Sweep-Phase einfach nur den Speicher aller „toten“ Objekte als „frei“ kennzeichnen würde, dann bestünde 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.  Fragmentierung lässt sich durch Kopieren oder Kompaktieren der überlebenden Objekte verweiden.

Ein fragmentierter Speicher ist ungünstig, 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 sind, dann liegt freier Speicher ungenutzt herum und es könnte im ungünstigsten Falle passieren, dass eine Speicher-Allokation scheitert, obwohl noch freier Speicher in kleinen Fragmenten vorhanden ist.  Das heißt, bei hoher Speicherfragmentierung geht der Anwendung eher als nötig der Speicher aus.  Fragmentierung ist auch deshalb ein Problem, weil sie die sogenannte Speicherlokalität verschlechtert.  Man spricht von einer guten Lokalität, wenn nacheinander allozierte Objekte im Speicher dicht beieinander liegen, so dass sie gemeinsam in einen Speicher-Cache gelegt werden können, der hochperformante Zugriffe ermöglicht.  Eine hohe Speicherfragmentierung macht solche Optimierungen unmöglich.

Ein Garbage Collection Algorithmus wird also stets bemüht sein, die Speicherfragmentierung gering zu halten.  Die Copy-Technik mit zwei Survivor-Bereichen ist eine der üblichen Strategien dafür.  Einer der Bereiche ist immer passiv, d.h. leer und unbenutzt, und im anderen aktiven Bereich werden alle neuen Objekte angelegt. Bei der Garbage Collection werden alle lebenden Objekte vom aktiven in den passiven Bereich kopiert.  Der vormals aktive Bereich wird freigegeben und ist anschließend passiv bzw. leer.  Neue Objekte entstehen dann im aktiven Bereich, bis dieser voll ist und der Zyklus von vorne beginnt.

Bei der Sun JVM ist der Algorithmus ein wenig abgewandelt.  Neue Objekte entstehen nicht im aktiven Survivor-Bereich, sondern in Eden.  Ansonsten ist das Prinzip aber das gleiche.  Die Objekte wandern mit zunehmenden Alter von Eden in einen der Survivors und wird dann zwischen den beiden Suvivors hin- und herkopiert, bis ein Schwellenwert erreicht ist und das Objekt letztlich in der Old Generation landet.

Copy-Garbage-Collection hat den Vorteil, dass die Vermeidung der Fragmentierung relativ einfach ist.   Die lebenden Objekte in einen frischen Speicherbereich zu kopieren, ist unkompliziert und schnell.  Man spricht bei diesen Algorithmen auch von Scavenging (dt. wörtlich: Mülleimer plündern, Aas fressen).  Der Scavenger pickt sich einfach das Beste aus dem Müll 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 to-Space), als tatsächlich gebraucht wird.  Das ist für Anwendungen mit engen Speicherbedingungen ein ernstes Problem.
Soweit zur Young Generation; sie besteht in der Sun JVM aus Eden und den zwei Survivor-Bereiche, auf denen eine Copy-Garbage-Collection gemacht wird.   Die Old Generation besteht aus nur einem Speicherbereich und verwendet einen anderen Algorithmus, nämlich einen Mark-and-Compact Garbage Collection Algorithmus.

Mark-and-Compact GC

Die Idee des Mark-and-Compact ist es, den hohen Speicherverbrauch des Copy-Algorithmus zu vermeiden.  Statt die lebendigen Objekte nach der Markierungsphase in einen zweiten, bereitstehenden Speicherbereich zu kopieren, wird der aktive Speicherbereicht reorganisiert.  Die lebendigen Objekte werden so arrangiert, dass sie kompakt zusammen liegen und keine Fragmentierung auftritt.  Das ist relativ aufwändig und nimmt entsprechend viel Zeit in Anspruch.  Da müssen Objekte verschoben werden, es muss eine Forward-Adresse hinterlassen werden und am Ende sind die Objekte über Pointer auf Pointer zu erreichen, was die Zugriffe während des Programmablaufs nicht unbedingt beschleunigt.  Mit wachsendem Alter nimmt das Problem zu, da immer mehr Objekte dann schon x-mal hin- und herkopiert worden sind.

Da die Old Generation sowieso nur selten aufgeräumt wird und nicht allzu viele Objekte in der Old Generation sterben, ist ein Compact-Algorithmus für die Old Generation durchaus angemessen.  Alle Objekte per Copy-Algorithmus jedes Mal umzukopieren, wäre ineffizient.  Mark-and-Copy ist nur dann effizient, wenn es nur wenige Überlebende gibt, also nur wenig zu kopieren ist.  Genau das ist aber in der Old Generation nicht der Fall. Je länger eine Anwendung läuft, desto älter werden viele Objekte, d.h viele Objekte sind dann praktisch speicher-resident.  Bei hoher Speicher-Residenz ist ein Copy-Algorithmus aber nicht mehr günstig (siehe Abbildung 4).


Abbildung 4: Effizienz von Copy vs. Mark-Sweep bei wachsender Speicher-Residenz der Objekte

Am Rande sei noch erklärt, was der ominöse Perm-Bereich in Abbildung 3 ist.  In diesem Bereich werden permanent existierende Daten abgelegt.  Dort legt der Class Loader beispielsweise die Klassenobjekte ab, d.h. die Instanzen von Class<T>.  Der Perm-Bereich wird im Rahmen einer Full Garbage Collection aufgeräumt und kompaktiert, wenn er voll wird.

Die verschiedenen Speicherbereiche mit ihren Algorithmen kann man über diverse Tools überwachen.  In Java 5.0 steht dafür jconsole zur Verfügung (siehe Abbildung 5). Das ist ein Tool, das mit dem JDK ausgeliefert wird (siehe / JCONS ) und auf die Standard Management Beans in Java 5.0 aufsetzt.


Abbildung 5: Anzeige der Speicher-Generationen in der Sun JVM mit jconsole

Man kann anhand der Grafiken verfolgen, wie sich die Auslastung der verschiedenen Bereiche über die Zeit entwickelt.  Man kann beispielsweise sehen, wie die Survivor-Bereiche langsam überlaufen, bis eine Auslagerung in die Old Generation (hier Tenured Generation genannt) erfolgt.

Die oben beschriebenen Algorithmen, Mark-and-Copy und Mark-and-Compact, sind nur eine Annäherung an die heute verfügbaren Techniken.  Seit der Sun JVM 1.4.1 gibt es Garbage Collection Algorithmen für Multiprozessor-Architekturen.   Auf einer Multiprozessor-Maschine ist es verschwenderisch, die gesamte Anwendung anzuhalten und die Garbage Collection in nur einem einzigen Thread auf einem einzigen Prozessor ablaufen zu lassen.  Wenn schon mehrere Prozessoren zur Verfügung stehen, dann sollte man diese doch auch für die Garbage Collection nutzen, um die Pausen zu reduzieren und den Durchsatz zu erhöhen.  Also wurden parallele und konkurrierende Garbage Collection Algorithmen entwickelt.

Parallel GC

Unter paralleler Garbage Collection versteht man Techniken, bei denen die Speicherbereinigung von mehreren Thread gleichzeitig abgewickelt wird.  In der traditionellen Garbage Collection hat nur ein Thread, der sogenannte Reaper-Thread, Garbage Collection gemacht.  Bei paralleler Garbage Collection teilen sich mehrere Threads die Arbeit.  Das bedeutet allerdings nicht, dass die Speicherbereinigung konkurrierend zur Anwendung laufen würde.  Parallele Garbage Collection ist immer noch eine „Stop-the-World“-Aktion, bei der die Anwendung angehalten wird.  Allerdings dürften die Pausen auf einer Multiprozessor-Maschine bei paralleler Garbage Collection tendenziell kürzer sein.  Auf einer Single-Processor-Architektur dürfte parallele Garbage Collection hingegen kontraproduktiv ausfallen, weil die Threads sich natürlich synchronisieren müssen, was zusätzlichen Aufwand erfordert, der sich aber ohne die Nutzung mehrerer Prozessoren nicht auszahlt.

Parallele Garbage Collection wird in der Sun JVM in erster Linie für die Young Generation angewendet.   Dabei wird sowohl die Markierungs- als auch die Kopierphase in Teilaufgaben aufgeteilt, die auf die verschiedene Threads verteilt werden.  Beispielsweise kann jeder Root-Pointer einem eigenen Thread zugeteilt werden, der dann die von diesem Pointer aus erreichbaren Objekte markiert.  Beim Sweep geht das so ähnlich.  Jedem Thread wird ein Teil des Survivor-Bereichs zugeteilt, in den er die lebendigen Objekte kopieren darf.  Bei dieser Aufteilung läßt sich ein gewissen Maß an Fragmentierung nicht vermeiden, aber die Zerstückelung hält sich in Grenzen.

Concurrent GC

Unter konkurrierender Garbage Collection versteht man Techniken, die parallel zur Anwendung ablaufen.  Das Ziel der konkurrierenden Garbage Collection ist es, die „Stop-the-World“-Pausen zu vermeiden bzw. soweit wie möglich zu reduzieren.  Es wird versucht, möglichst viele der Gargabe Collection Aufgaben parallel zur Anwendung zu erledigen, ohne die Anwendung anhalten zu müssen.  Das geht natürlich nicht vollständig.  Die Markierung wird immer ungestört ablaufen müssen,  weil man nicht im Garbage Collector die Referenzbeziehungen verfolgen kann, während diese gleichzeitig von der Anwendung geändert werden.  Eine konkurrierende Garbage Collection ist daher immer quasi-konkurrierend.

Sie beginnt mit einer initialen nicht-konkurrierenden Markierungsphase, in der die Root-Pointer ein Stück weit verfolgt werden.  Danach folgt eine konkurrierende Markierungsphase, die allerdings nicht exakt ist.  Während die Referenzen verfolgt werden, entstehen neue Root-Pointer und neue Referenzbeziehungen, die nicht erfasst werden.  Deshalb erfolgt eine abschließende nicht-konkurrierende Markierungsphase, die versucht, möglichst allen Unschärfen auszubügeln.  Es bleiben aber trotzdem gewisse Objekte stehen, die nicht erreichbar sind, was aber leider nicht festgestellt werden konnte.  Man bezeichnet diese Überbleibsel als Floating Garbage  Sie stellen kein großes Problem dar; sie bleiben einfach länger im Speicher  als nötig und werden erst bei der nächsten Garbage Collection freigegeben.

Nach den Markierungsphasen folgt eine konkurrierende Sweep-Phase, in der aber nicht kompaktiert wird. Konkurrierende Garbage Collection ist kein Mark-and-Compact-Algorithmus, sondern ein einfacher Mark-and-Sweep-Algorithmus.  Das liegt daran, dass die Kompaktierung Synchronisation zwischen dem Garbage-Collector und den Threads der Anwendung erfordern würde.  Beide arbeiten ja gleichzeitig auf dem Heap und müßten sich koordinieren.  Für die einfache Freigabe der „toten“ Objekte ist keine Koordination nötig, weil die „toten“ Objekte von der Anwendung aus ohnehin nicht mehr zu erreichen sind.  Ohne die Kompaktierung besteht natürlich wieder die Gefahr der Speicherfragmentierung.  Es wird versucht, die Fragmenierung mit aufwändigeren Allokationsverfahren und Free-Listen gering zu halten, aber eine echte Kompaktierung bietet konkurrierende Garbage Collection nicht.  Falls die Fragmentierung überhand nimmt oder an sich nicht mehr genug Heap-Speicher zur Verfügung steht, fällt die konkurrierende Garbage Collection wieder auf den nicht-konkurrierenden Mark-and-Compact-Algorithmus mit seinen langen Pausen zurück.

Konkurrierende Garbage Collection wird in der Sun JVM für die Old Generation verwendet.  Das ist auch angemessen.  Erstens sind bei einem klassischen nicht-konkurrierenden Mark-and-Compact auf der Old Generation die Pausen relativ lang, so dass die konkurrierende Garbage Collection hier eine spürbare Verbesserung bringt.  Die Pausen durch Minor Collections auf der Young Generation sind ohnehin schon relativ kurz, deshalb würde konkurrierende Garbage Collection in der Young Generation nicht viel bringen.  Das Problem der Fragmentierung durch die konkurrierende Garbage Collection ist in der Old Generation auch nicht so schlimm wie es in der Young Generation wäre, weil Objekte in der Old Generation nur durch Kopieren aus der Young Generation entstehen.  Alle von der Anwendung erzeugten Objekte – und das ist die große Masse der Objekte -  entstehen sowieso in Eden.  Dort wäre das Fragmentierungsproblem wesentlich gravierender als in der Old Generation.

Die verschiedenen Phasen der konkurrierenden Garbage Collection können anhand der JVM-Ausgaben über die Optionen –verbose:GC und –XX:+PrintGCDetails verfolgt werden (siehe Abbildung 6).


Abbildung 6: Information zur Concurrent Mark-and-Sweep (CMS) Garbage Collection per JVM-Option –XX:+PrintGCDetails

Angesichts der vielen verschiedenen Phasen kann man erahnen, wie aufwändig die Verwaltung der benötigten Informationen für eine konkurrierende Garbage Collection ist. Dabei wird ein sogenannter Tricolor-Algorithmus für die Kennzeichnung der besuchten Knoten verwendet:  die besuchten und definitiv erreichbaren Objekte werden „schwarz“ markiert, Objekte, die von der Anwendung geändert wurden und deshalb noch einmal besucht werden müssen, werden als „grau“ markiert, und alles was nicht erreicht wurde, ist „weiß“ markiert.  Diese Markierungen müssen natürlich während des Programmablaufs von der Virtuellen Maschine für die spätere Garbage Collection gesetzt werden.  Dazu werden sogenannte Lese- und Schreib-Barrieren benutzt. Insgesamt führt die konkurrierende Garbage Collection zwar zu kürzeren Pausen, erfordert aber spürbaren Mehraufwand in der Virtuellen Maschine und reduziert damit den Durchsatz der Anwendung.

Incremental GC

Neben der konkurrierenden Garbage Collection gibt es auch noch eine inkrementelle Garbage Collection., die ebenfalls das Ziel verfolgt, die Pausen zu reduzieren.  Die Idee dabei ist, dass nicht der gesamte Heap auf einmal durchsucht wird, sondern nur Teile davon.  Die inkrementelle Garbage Collection muss, ähnlich wie die konkurrierende Garbage Collection, mehr Aufwand in die Verwaltung der Markierungen stecken und reduziert den Durchsatz erheblich.  Die inkrementelle Garbage Collection wird in der Sun JVM für die Old Generation angeboten.  Sowohl die nicht-konkurrierende als auch die konkurrierende Garbage Collection können in diesem inkrementellen Modus ablaufen.  Die nicht-konkurrierende inkrementelle Garbage Collection wird in der Sun JVM als Train-Collector bezeichnet (siehe Abbildung 7).  Sie ist „deprecated“, das heißt, sie wird voraussichtlich ab der JVM-Version 6.0 nicht mehr unterstützt.  Die konkurrierende inkrementelle Garbage Collection wird als i-cms-Collector bezeichnet (incremental concurrent mark-and-sweep).


Abbildung 7: Information zur inkrementellen Garbage Collection per JVM-Option –XX:+PrintGCDetails

Damit aber nicht genug.  Es gibt zusätzlich einen parallelen Modus für die Old Generation Garbage Collection.  Dabei werden die verbleibenden „Stop-the-World“-Phasen der konkurrierenden Garbage Collection von mehreren Threads bearbeitet statt von nur einem Thread, ähnlich wie in der parallelen Garbage Collection in der Young Generation.
 

Zusammenfassung

Wir haben uns in diesem Beitrag einen Überblick über die Prinzipien der Garbage Collection verschafft.  In Java ist es üblich, die Objekte auf dem Heap in einer Young und einer Old Generation zu verwalten.  Jeder Generation sind separate Bereiche des Heaps zugeordnet und für jede Generation werden andere Garbage Collection Algorithmen verwendet. Alle Algorithmen sind Variationen des Mark-and-Sweep-Prinzips, bei dem erreichbare Objekte markiert werden und nicht-erreichbare Objekte freigegeben werden.  Wie aufwändig das Markieren oder das Sweeping ist, hängt vom jeweiligen Algorithmus ab.

In der Sun JVM werden 3 Heap-Bereiche mit jeweils verschiedenen Algorithmen aufgeräumt:
 
Heap-Bereich
Garbage Collection Algorithmus
Young Generation


(Eden + from-Space + to-Space)

Mark-and-Copy im Rahmen einer Minor oder Major Garbage Collection 


(wahlweise parallel, d.h. in mehreren GC-Threads)

Old Generation
Mark-and-Compact im Rahmen einer Major Garbage Collection 


(wahlweise konkurrierend, d.h. quasi-parallel zur Anwendung, und/oder wahlweise inkrementell)

Perm-Space
Mark-and-Compact im Rahmen einer Full Garbage Collection)


(weder parallel noch konkurrierend noch inkrementell)

Auf alle in diesem Artikel beschriebenen Garbage Collectoren kann über JVM-Optionen in gewissem Rahmen Einfluss genommen werden.  Diese Optionen sehen wir uns im nächsten Beitrag an und besprechen, wie man sie für das Tuning der Garbage Collection verwenden kann.
 

Literaturverweise und weitere Informationsquellen

/BOOK/
Garbage Collection
Richard Jones & Rafael Lins
John Wiley & Sons, September 1996
ISBN : 0471941484
URL: http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html
/JONES/
The Garbage Collection Page"
Eine Webseite von Richard Jones mit einer umfangreichen Materialsammlung zu Garbage Collection.
URL: http://www.cs.kent.ac.uk/people/staff/rej/gc.html
/JCONS/
Using jconsole
URL: http://java.sun.com/j2se/1.5.0/docs/guide/management/jconsole.html
/LINKS/
Weitere nützliche Links zum Thema “Java Performance”
URL: http://www.AngelikaLanger.com/Resources/Links/JavaPerformance.htm

Die gesamte Serie über Java Performance:

/KRE1/  Java Performance, Teil 1: Was ist ein Micro-Benchmark?
Klaus Kreft & Angelika Langer
Java Spektrum, Juli 2005
URL: http://www.AngelikaLanger.com/Articles/EffectiveJava/21.MicroBenchmarking/21.MicroBenchmarking.html
/KRE2/  Java Performance, Teil 2: Wie wirkt sich die HotSpot-Technologie aufs Micro-Benchmarking aus?
Klaus Kreft & Angelika Langer
Java Spektrum, September 2005
URL: http://www.AngelikaLanger.com/Articles/EffectiveJava/22.JITCompilation/22.JITCompilation.html
/KRE3/  Java Performance, Teil 3: Wie funktionieren Profiler-Tools?
Klaus Kreft & Angelika Langer
Java Spektrum, November 2005
URL:  http://www.AngelikaLanger.com/Articles/EffectiveJava/23.ProfilingTools/23.ProfilingTools.html
/KRE4/ Java Performance, Teil 4: Performance Hotspots - Wie findet man funktionale Performance Hotspots?
Klaus Kreft & Angelika Langer
Java Spektrum, Januar 2006
URL:  http://www.AngelikaLanger.com/Articles/EffectiveJava/24.FunctionalHotSpots/24.FunctionalHotSpots.html
/KRE5/ Java Performance, Teil 5: Performance Hotspots - Wie findet man Memory Hotspots?
Klaus Kreft & Angelika Langer
Java Spektrum, März 2006
URL:  http://www.AngelikaLanger.com/Articles/EffectiveJava/25.MemoryHotSpots/25.MemoryHotSpots.html
/KRE6/ Java Performance, Teil 6: Garbage Collection - Wie funktioniert Garbage Collection?
Klaus Kreft & Angelika Langer
Java Spektrum, Mai/Juli 2006
URL:  http://www.AngelikaLanger.com/Articles/EffectiveJava/26.GarbageCollection/26.GarbageCollection.html
/KRE7/  Java Performance, Teil 7: Garbage Collection - Das Tunen des Garbage Collectors
Klaus Kreft & Angelika Langer
Java Spektrum, September 2006
URL:  http://www.AngelikaLanger.com/Articles/EffectiveJava/27.GCTuning.html/27.GCTuning.html

 
 

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)
 
  © Copyright 1995-2008 by Angelika Langer.  All Rights Reserved.    URL: < http://www.AngelikaLanger.com/Articles/EffectiveJava/26.GarbageCollection/26.GarbageCollection.html  last update: 26 Nov 2008