Generationale Garbage Collection

Gerade bei interaktiven Systemen kann sich Garbage Collection mit den vorgestellten Algorithmen als störende Unterbrechung erweisen. Generationalen Garbage Collection [Lieberman and Hewitt, 1983,Moon, 1984,Ungar, 1984] ist als Antwort auf dieses Problem entwickelt worden. Sie beruht auf der Beobachtung, daß die meisten erzeugten Objekte in typischen Programmläufen nach relativ kurzer Zeit unerreichbar werden (die Altershypothese: ,,most objects die young``). Daher lohnt es, die Garbage Collection vor allem auf junge Objekte zu konzentrieren.

Zu diesem Zweck wird der Heap in mehrere Segmente unterteilt, in denen die Objekte nach Alter^4.3 gruppiert werden. Jedes einzelne Segment wird als Generation bezeichnet und enthält Objekte, die grob der gleichen Altersklasse angehören. Neue Objekte werden in der jüngsten Generation angelegt und, nachdem sie ein gewisses Alter erreicht haben, in die nächste Generation ,,befördert``.

Um nun eine Generation G_n unabhängig von den anderen bereinigen zu können, müssen die Referenzen von Objekten aus allen anderen Generationen ${G}_{m \not = n}$ mit in die Wurzelmenge der zu bereinigenden Generation einbezogen werden. Die Information über Zeiger zwischen Generationen (inter-generational pointers) muß also bei der Garbage Collection mit geringem Aufwand bereitgestellt werden, d.h. sie muß zur Verfügung stehen, ohne die anderen Generationen zu durchsuchen. Um dieser Anforderung zu genügen, müssen die Operationen, die einen Zeiger in ein Objekt schreiben während des Programmablaufes protokolliert werden. Dies geschieht in der Regel durch das Errichten einer ,,Write Barrier`` -- ein Programmstück in der virtuellen Maschine, das bei jeder Schreiboperation ausgeführt wird und dann die entsprechende Protokollierung durchführt.

Um den Aufwand möglichst gering zu halten, wird eine weitere Eigenschaft typischer Programme ausgenutzt: Referenzen verweisen überwiegend von jüngeren auf ältere Objekte. Diese Eigenschaft wird ausgenutzt, indem zusammen mit einer Generation G_n auch alle jüngeren Generationen G_m<n bereinigt werden. Damit benötigt der Garbage Collector lediglich die Pointer von ,,alt`` nach ,,neu``, d.h., daß während des Programmablaufs nur über die selteneren Referenzen von älteren auf jüngere Generationen Buch geführt werden muß. In Abbildung 4.8 sind diese gestrichelt dargestellt.

Ein großer Vorteil dieser Vorgehensweise ist die Tatsache, daß Zeigeroperationen in der jüngsten Generation überhaupt nicht mehr protokolliert werden müssen, da diese ohnehin in jede Garbage Collection mit einbezogen wird. Da die meisten schreibenden Zeigeroperationen auf der jüngsten Generation zu erwarten sind, wird hierdurch ein Großteil der Protokollierung gespart.

Abbildung: Generational Collection: Die Referenzen aus der alten Generation müssen berücksichtigt werden.

Für die Protokollierung der Referenzen von älteren auf jüngere Generationen werden zwei Methoden unterschieden:

,,Remembered Sets`` [Ungar, 1984]:

Hierbei wird für jede Generation die Menge von Objekten älterer Generationen zusammengefaßt, die in diese Generation verweisen (s. Abb. 4.9). Diese Menge (das sogenannte ,,Remembered Set``) stellt einen Teil der Wurzelmenge der entsprechenden Generation dar und wird somit bei der Garbage Collection berücksichtigt.

Abbildung 4.9: Remenbered Set.

Das ,,Remembered Set`` einer Generation muß bei jedem Speichern eines Zeigers in diese Generation in ein Objekt einer älteren Generation angepaßt werden. Dies wird durch eine ,,Write Barrier`` erreicht, deren Aufgabe ist,

1.

zu prüfen, daß nicht in ein Objekt der jüngsten Generation geschrieben werden soll. Diese Operation braucht wie beschrieben nicht protokolliert zu werden.

2.

zu prüfen, daß der zu schreibende Zeiger in eine jüngere Generation verweist.

3.

zu prüfen, daß das betroffene Objekt nicht bereits im ,,Remembered Set`` der fraglichen Generation enthalten ist.

4.

das ,,Remembered Set`` der betroffenen Generation zu aktualisieren, wenn obige Bedingungen zutreffen.

Diese Operationen lassen sich mit 17 MIPS-Assembler-Instruktionen implementieren, was zuviel ist, um die Barriere bei jeder Speicherinstruktion vom Compiler inline plazieren zu lassen. Daher schlagen [Hosking et al., 1992] die Verwendung eines sogenannten ,,Sequential Store Buffer`` vor. Hierbei handelt es sich lediglich um ein Array von Zeiger-Paaren (das Zielobjekt und der gespeicherte Zeiger), zu dem bei jeder Speicheroperation ohne vorherigen Test ein neues Element hinzugefügt wird. Läuft der Puffer über, wird er geleert, indem die entsprechenden Tests ausgeführt und die betroffenen ,,Remembered Sets`` aktualisiert werden. Kann der Überlauf des ,,Sequential Store Buffer`` ähnlich wie bei der Allokation (s. Abschnitt 4.1) durch Verwendung einer geschützten Speicherseite von der Hardware erkannt werden, kann eine reduzierte Assembler-Sequenz von nur drei MIPS-Instruktionen vom Compiler inline plaziert werden. Dabei ist zu bedenken, daß die Prüfungen weiterhin ausgeführt werden müssen, sie werden aber nicht mehr inline ausgeführt, sondern konzentriert bei einem Überlauf bzw. vor einer Garbage Collection.

,,Card Marking`` [Chambers, 1992,Hölzle, 1993]:

Bei dieser Methode wird jede Generation in eine Menge von Karten der Größe $card\_size$ unterteilt, wobei $card\_size$ eine Potenz von 2 sein muß. Weiterhin wird ein Bit-Array map der Länge $\frac{heap\_size}{card\_size}$ angelegt und jedes Element auf 1 initalisiert. Jedes Bit entspricht also einer Karte. Wird nun eine Speicheroperation in der Karte i ausgeführt, so wird durch die ,,Write Barrier`` ohne weitere Prüfungen das entsprechende Bit auf 0 gesetzt. Bei der nächsten Garbage Collection wird jedes Objekt in einer so markierten Karte als Teil der Wurzelmenge angesehen, jedoch nur, wenn es tatsächlich in eine jüngere Generation verweist. Die von [Chambers, 1992] im SELF-System verwendete ,,Write Barrier`` kann mit nur 3 SPARC-Instruktionen implementiert werden (s. Abb. 4.10), wobei hier aus Effizienzgründen ein Byte-Array anstatt eines Bit-Arrays verwendet wird.

Abbildung: Die von [Chambers, 1992] verwendete ,,Write Barrier``

Da die Kartengröße eine Potenz von 2 ist kann die Division zum Ermitteln des Indices effizient durch die Schiebe-Operation sra implementiert werden.

Beide geschilderten ,,Write Barriers`` verlagern einen Teil der zu leistenden Arbeit auf die Garbage Collection, um den Code möglichst kurz zu halten. ,,Card Marking`` hat gegenüber ,,Remembered Set`` den Nachteil, daß bei der Garbage Collection immer eine ganze Karte durchsucht werden muß, auch wenn möglicherweise nur ein enthaltenes Objekt einen Zeiger in die jüngere Generation enthält. Weiterhin besteht bei Sprachen ohne Markierung das Problem, den Anfang des ersten Objektes auf einer bestimmten Karte zu finden - beides bedeutet einen weiteren Mehraufwand für die Garbage Collection. Hingegen hängt die Arbeit, die dem Collector durch Pointer-Stores entsteht nicht von der Anzahl der ausgeführten Speicheroperationen, sondern von der Anzahl der markierten Karten ab. Bei wiederholtem Speichern in ein bestimmtes Objekt steigt der Aufwand bei der Verwendung eines ,,Sequential Store Buffers`` also stetig an, während er bei der Verwendung von ,,Card Marking`` konstant bleibt.

Generationale Garbage Collection hat sich zu einem De-Facto-Standard bei der Implementierung virtueller Maschinen entwickelt. So verwenden alle für einen produktiven Einsatz vorgesehenen Maschinen in Anhang A einen generationalen Algorithmus mit 2 Generationen. Dabei werden für die Bereinigung der jeweiligen Generationen unterschiedliche Algorithmen gewählt: Üblicherweise wird für die jüngere Generation ein kopierender Algorithmus verwendet, während für die ältere Generation ein Algorithmus verwendet wird, der Objekte mit einer geringeren Wahrscheinlichkeit bewegt (z.B Abwandelungen von ,,Mark-Sweep``). Die HotSpot VM [Meloan, 1999] verwendet hier einen inkrementellen Algorithmus (siehe Abschnitt 4.4), um auch Pausen für die ältere Generation möglichst kurz zu halten. Weiterhin findet die Allokation vielfach in einem festen Bereich der jüngsten Generation statt, aus dem die Objekte bei ihrer ersten Garbage Collection in den Hauptbereich der jüngsten Generation evakuiert werden. Die Verwendung dieses $\rightarrow$eden oder $\rightarrow$nursery genannten Bereichs erhöht die Lokalität bei der Initialisierung von Objekten und ermöglicht effizienteren Code für die Überlaufprüfung, da die Grenze ein konstanter Wert ist.

[Demers et al., 1990] haben eine Implementierung eines generationalen Algorithmus vorgestellt, die Objekte nicht bewegt und sich damit auch zum Erstellen von konservativen und ,,On-The-Fly``-Algorithmen (siehe Abschnitt 4.4) eignet. Dabei entfällt zwar der positive Effekt der Heap-Kompaktierung und der damit verbundenen erhöhten Lokalität und schnellen Allokation, ein generationaler Ansatz verspricht aber, allein aufgrund des verringerten Working-Sets des Collectors, eine Verkürzung der Programmpausen und der insgesamt aufgewendeten Zeit für Garbage Collection.

Generationale Garbage Collection erreicht bei Erfüllung der Altershypothese deutlich verkürzte Unterbrechungen durch Garbage Collection -- [Ungar, 1984] gibt den Faktor 20, [Appel, 1989b] sogar Faktor 50 an. Dabei wird nicht nur die Zeit der meisten Unterbrechungen verringert, sondern auch die Zeit, die insgesamt zur Garbage Collection aufgewendet wird (2% statt 30% bei [Ungar, 1984]). Wird die Hypothese jedoch nicht erfüllt, so können häufige Bereinigungen des gesamten Speichers auftreten. [Ungar and Jackson, 1991] haben beobachtet, daß auch in normalen Programmabläufen übergangsweise Zustände eintreten können, in denen die Altershypothese nicht erfüllt ist. Dies hat zur Folge, daß häufiger alle Generationen im System müssen bereinigt werden, was sogar zu einer Verschlechterung der Performance gegenüber einem nicht-generationalen Algorithmus führen kann.