Grundbegriffe der Garbage Collection für virtuelle Maschinen

Allen Implementierungen von Garbage Collection ist ein Modell der ,,Lebendigkeit`` (liveness) von Daten gemein. Um eine Speicherzelle wiederverwenden zu können, muß der Collector beweisen, daß sie vom laufenden Programm (dem sogenannten mutator) nicht mehr benötigt wird. Dieser Beweis wird in der Regel auf Basis der Erreichbarkeit dieser Speicherzelle geführt. Ist die Zelle von einer Wurzel im System aus transitiv erreichbar, so wird sie als lebendig (live) bezeichnet. Ist dies nicht der Fall, so kann sie von der Anwendung nicht mehr erreicht werden und somit dem Freispeicher zugeführt werden. Als Wurzeln können dabei näherungsweise alle globalen und lokalen Variablen der in der Ausführung befindlichen Funktionen verwendet werden^2.3. In [Jones and Lins, 1996] wird die folgende Formel für eine formalere Definition von liveness angeführt. Die lebendigen Objekte bezeichnen die kleinste Menge live, die unter Referenzierung abgeschlossen ist:

$$live = \{ N \in Nodes \ \vert \ ( \exists r \in Roots.r \rightarrow N ) \vee ( \exists M \in live.M \rightarrow N ) \}$$ (2.1)

Dabei bezeichnet Nodes die Menge aller Speicherzellen, Roots bezeichnet die Menge der Wurzeln im System. Um nun die Menge live eindeutig bestimmen zu können, muß die Relation ,,$\rightarrow$`` (,,referenziert``) konkret definiert und diese Information dem Garbage Collector zugänglich sein. D.h. der Collector muß zum Zeitpunkt der Collection für alle Wurzeln und alle Knoten entscheiden können, welche anderen Knoten von ihnen referenziert werden. Anders ausgedrückt muß er für jede bei der Garbage Collection besuchte Speicherzelle bestimmen können, ob sie eine Referenz oder einen Skalar (z.B. einen Integer) enthält.

Ist der Collector aufgrund mangelnden Wissens über seine Umgebung nicht immer in der Lage, diese Information zu erlangen, so muß er eine sichere Annahme treffen -- ein solche Implementierung wird als daher $\rightarrow$konservativ bezeichnet. Kann hingegen den Typ jeder Speicherzelle (Referenz oder Skalar) zum Zeitpunkt der Garbage Collection bestimmt werden, so spricht man von $\rightarrow$exakter oder type accurate Garbage Collection.

Konservative Garbage Collection wird beispielsweise zur Speicherverwaltung in C-Programmen eingesetzt, da hier der Compiler und das Laufzeitsystem keine Typinformationen über die einzelnen Speicherzellen bereitstellen. Konservative Garbage Collection muß alle Speicherzellen, deren Typ nicht zweifelsfrei bestimmt werden kann, als Referenz behandeln. Da es sich hierbei jedoch um einen ,,Irrtum`` handeln könnte, es sich also doch um einen Skalar handeln könnte, darf er den Inhalt der Zelle keinesfalls ändern. Daraus ergibt sich einen große Schwäche konservativer Collectoren: sie dürfen in diesem Fall Objekte auf dem Heap nicht bewegen, was bei länger Programmausführung zu einer Fragmentierung des Speichers führt - würden sie nämlich ein Objekt bewegen, so müßten sie alle Referenzen auf dieses anpassenen und würden dabei Gefahr laufen, einen Skalar des ablaufenden Programmes zu verändern, der zufällig wie eine Referenz auf das bewegte Objekt ,,aussah``.

Diese Problem kann umgangen werden, indem nicht direkte Referenzen sondern Indirektionen (handles) verwendet werden. Hierbei werden alle Objekte von einer Tabelle aus referenziert. Referenzen zwischen den einzelnen Objekten werden indirekt als Indizes in die Objekttabelle realisiert. Wird ein Objekt bewegt, so muß lediglich der Eintrag in der Objekttabelle modifiziert werden, da dieser die einzige echte Referenz auf das Objekt darstellt. Diese Methode verlangsamt also die häufige Operation der Dereferenzierung und wird daher in modernen virtuellen Maschinen nur selten verwendet.

In virtuellen Maschinen befinden sich Laufzeitsystem, dynamischer Compiler und Garbage Collector gemeinsam unter der Kontrolle der Maschine, d.h. einen Kooperation zur Erstellung von Typinformationen zur Garbage Collection ist prinzipiell möglich. Da exakte Garbage Collection, wie oben erwähnt, den Vorteil hat, Objekte auf dem Heap bewegen zu können, wird Garbage Collection in modernen virtuellen Maschinen prinzipiell durch diese Technik implementiert.

Da für exakte Garbage Collection Typinformationen zu jeder besuchten Speicherzelle benötigt werden, müssen Laufzeitsystem oder Compiler diese Informationen bereitstellen. Hier werden prinzipiell zwei Wege unterschieden:

1.

Markierung (tagging): Jeder Wert enthält die Typinformation selbst. Ein oder mehrere Bits der Repräsentation des Wertes werden für die Speicherung der Typinformation verwendet. Beispielsweise ließe sich das niedrigstwertige Bit folgendermaßen verwenden: ist es gesetzt, so handelt es sich um einen nach links verschobenen Skalar, ist es nicht gesetzt, so handelt es sich um eine Referenz. Um zu garantieren, daß Referenzen immer auf 0 enden, wird der gesamte Heap dabei so verwaltet, daß alle im Heap gespeicherten Objekte an durch vier teilbaren Positionen beginnen (sie sind word aligned); moderne Prozessorarchitekturen unterstützen oftmals ohnehin nur solche Wortzugriffe. Diese Methode hat den Vorteil, daß die Typinformation eines Wertes direkt in diesem enthalten ist. Damit ist der Typ jedes Wertes stets einfach zu ermitteln -- ungeachtet dessen, ob er im Heap, im Runtime-Stack oder in Registern gespeichert ist. Nachteilig erweisen sich der Verlust an Darstellungsbreite oder -Präzision sowie vor allem die zusätzlichen Bitverschiebungen, die vor und nach arithmetischen Operationen zur Konversion ausgeführt werden müssen.

2.

Referenztabellen (reference maps): Die Typinformation wird in einem zugeordneten Speicherbereich gehalten. Jeder Speicherzelle wird ein bestimmter Bereich zugeordnet, aus der ihr Typ hervorgeht. Dies kann z.B. durch den Verweis eines Heap-Objektes auf seine Klassenbeschreibung zur Beschreibung der Objektfelder geschehen. Für Stacks und Register werden üblicherweise Zuordnungstabellen (stack maps, register maps) angelegt, die den Typ des jeweils enthaltenen Wertes beschreiben. Diese Methode hat den Vorteil, daß die arithmetischen Operationen der genutzten Hardware unverändert angewandt werden können. Das bedeutet auf der anderen Seite, daß nur an Punkten, für die solche Tabellen vorliegen, eine Garbage Collection durchgeführt werden kann. Solche Punkte heißen dementsprechend ,,GC Points``. Ist der Typ einer Stack- oder Registervariablen nur vom aktuellen Punkt der Codeausführung abhängig, so besteht eine control point dependency. Bestimmt hingegen der Weg, auf dem dieser Punkt erreicht wurde, den Typ einer Zelle, so besteht eine $\rightarrow$control path dependency. Eine Coderepräsentation ohne control path dependency ist für die Verwendung von reference maps vorzuziehen, da so einer Instruktion fest eine solche Tabelle zugeordnet werden kann - diese Zuordnung kann ggf. bereits vom Compiler vorgenommen werden. Enthält der Code hingegen control path dependencies, so müssen dynamisch Typinformationen gepflegt werden oder eine Garbage Collection an zweideutigen Positionen verhindert werden.

Exaktheit ist also ein wünschenswertes Attribut eines Collectors - um diese Exaktheit zu erzielen ist jedoch ein gewisser Aufwand zu treiben.