���������������������� Angelika�Langer - Training & Consulting
HOME | COURSES | TALKS | ARTICLES | GENERICS | LAMBDAS | IOSTREAMS | ABOUT | 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
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