Die erwähnten Algorithmen für Garbage Collection werden üblicherweise aufgerufen, wenn die Anwendung nicht mehr über ausreichend freien Speicher verfügt. Hierauf wird eine Garbage Collection des gesamten Heaps beziehungsweise einer oder mehrerer Generationen ausgeführt.
Um die hierbei entstehenden Pausen möglichst weiter zu verringern, werden zwei verwandte Ansätze verfolgt:
Bei inkrementellen Algorithmen handelt es sich also, wie bei allen bisher geschilderten Algorithmen um einen ,,Stop-the-World``-Algorithmus, da alle ablaufenden Threads angehalten werden müssen, und an einen konsistenten Punkt vorgerollt werden müssen (s. Abschnitt 5.3), bevor die Garbage Collection durchgeführt werden kann. Der Algorithmus muß allerdings ,,verkraften``, daß der Heap zwischen den Teil-Abläufen durch die Anwendung verändert wird - es muß also eine Form der Kommunikation und Synchronisation zwischen Anwendung und Garbage Collector stattfinden.
Bei nebenläufigen Algorithmen ist eine noch feinere Synchronisation zwischen Anwedung und Garbage Collector vonnöten. Da Garbage Collector und Anwendung keine Kontrolle darüber haben, wann sie unterbrochen werden, muß praktisch jede Operation den Heap in einem konsistenten Zustand hinterlassen (zumindest solange die nebenläufige Collection läuft). Weiterhin darf die Anwendung in der Ausführung nicht übermäßig behindert werden - Garbage Collection sollte bescheiden (unobstrusive) sein.
Im Bereich der inkrementellen und nebenläufigen Algorithmen wird die von [Dijkstra et al., 1978] formalisierte Abstraktion des ,,tricolor marking`` häufig verwendet. Hierbei werden die bearbeiteten und noch zu bearbeitenden Objekte in drei Klassen (bzw. Farben) unterteilt.
Diese Abstraktion läßt sich auf die klassischen Algorithmen anwenden. Bei ,,Copying Collection`` sind die schwarzen Objekte jene, die bereits evakuiert und deren Referenzen angepaßt wurden, also jene, die im ,,To-Space`` unterhalb des Pointers scan liegen (s. Abbildung 2.6-(iv)). Die Objekte, die in ,,From-Space`` liegen und noch nicht evakuiert wurden, sind weiß, während die Objekte in ,,To-Space``, die sich zwischen scan und free befinden, grau sind.
Im Fall eines ,,Mark-Sweep``-Algorithmus sind die markierten Objekte schwarz, die unmarkierten weiß und die Objekte, die sich auf dem Mark-Stack befinden, grau.
Aus der gegebenen Definition der Farbmengen läßt sich eine wichtige Invariante ableiten:
Bei Verletzung dieser Farbinvarianten können fälschlicherweise lebendige Objekte collected werden. In Abbildung 4.11 ist eine Folge von Objektgraphen dargestellt, die dieses Problem illustriert. In (i) hat der Collector Objekt A vollständig besucht und befindet sich gerade in der Bearbeitung von B. Hier wird die Collection unterbrochen und der Mutator verändert den Objektgraphen zu (ii). Wenn der Collector wieder aufgerufen wird, wird er B schwarz färben, da es keine weißen Kinder mehr hat und dort die Bearbeitung beenden. Im Ergebnis wird C, obwohl es lebendig ist, collected werden, während B überlebt.
Die Farbinvariante wird von den klassischen Algorithmen nicht verletzt, ein inkrementeller oder nebenläufiger Algorithmus muß jedoch gesondert Sorge dafür tragen, daß die Invariante eingehalten wird. Dies liegt darin begründet, daß der der Heap während der Garbage Collection vom der Anwendung verändert werden kann.
Um auf eine inkonsistente Veränderung des Heaps ,,hinter dem Rücken`` des Garbage Collectors zu reagieren, werden zwei unterschiedliche Ansätze verwendet, die die Einhaltung Farbinvarianten garantieren: man unterscheidet sie je nachdem, ob sie auf ,,Read Barriers`` oder ,,Write Barriers`` basieren.
,,Read Barrier``-Methoden erhalten die Farbinvariante, indem die vermeiden, daß die Anwendung jemals weiße Objekte ,,sieht``. Dies geschieht, indem bei jedem Lesen einer Referenz aus dem Speicher geprüft wird, ob diese auf ein weißes Objekt verweist. Ist dies der Fall, so wird das Objekt durch eine Evakuierung grau gefärbt. [Baker, 1978] führt die ,,Read Barrier`` in Software aus und arbeitet dabei auf Objektebene - jeder lesende Zeigerzugriff wird getestet und das Objekt ggf. nach ,,To-Space`` bewegt. [Appel et al., 1988] verwenden den Speicherschutzmechanismus des Betriebssystems und arbeitet damit seitenorientiert: Alle Seiten, die weiße Objekte enthalten, werden geschützt. Die zugehörige Ausnahmeroutine evakuiert die gesamte Seite, wenn die Anwendung versucht, von einer geschützten Seite zu lesen.
,,Write Barrier``-Methoden prüfen bei jeder Schreiboperation, ob die Farbinvariante verletzt wird und markieren ggf. ein beteiligtes Objekt grau, um direkte Schwarz-Weiß-Referenzen zu vermeiden. Der in [Dijkstra et al., 1978] vorgestellte Algorithmus der ,,On-The-Fly Garbage Collection`` arbeitet hier wie [Baker, 1978] auf der Granularität von Objekten: Versucht die Anwendung eine Referenz auf ein weißes Objekt in ein schwarzes Objekt zu schreiben, so wird ersteres durch die in Software realisierte ,,Write Barrier`` grau gefärbt. [Boehm et al., 1991] verwenden wie [Appel et al., 1988] den Speicherschutzmechanismus des Betriebssystems und arbeiten somit seitenorientiert. Schreibende Zugriffe auf Seiten, die nur schwarze Objekte enthalten, werden abgefangen und alle Objekt der beschriebenen Seite werden als grau markiert.
,,Read Barrier``-Algorithmen verursachen einen ungleich größeren Mehraufwand zur Laufzeit als eine Write Barrier, da lesende Operation deutlich häufiger auftreten als schreibende Allerdings treten bei Verwendung von ,,Write Barrier``-Methoden in Verbindung mit Algorithmen, die Objekte bewegen, zusätzliche Synchronisationsprobleme auf. Zur Implementierung eines nebenläufigen, bewegenden Algorithmus existiert daher augenblicklich keine Alternative zur ,,Read Barrier``.
Die Ausnutzung der virtuellen Speicherverwaltung zur Implementierung einer Barrier ist prinzipiell einen elegante Lösung, da diese ohne Mehrkosten für den schnellen Ausführungspfad realisiert wird. Allerdings sind heutige Betriebssysteme nicht auf die intensive Verwendung von Ausnahmen im normalen Programmablauf optimiert, so daß die Verarbeitung einer Ausnahme üblicherweise mehrere 100 CPU-Zyklen in Anspruch nimmt.
Ein vergleichsweise neuer inkrementeller Algorithmus, der zunehmend bei der Implementierung von Java-VMs eingesetzt wird, ist der ,,Train``-Algorithmus [Hudson and Moss, 1992]. Er integriert einen ,,Write-Barrier``-basierten inkrementellen Algorithmus mit einem generationalen Garbage Collector.
Bei Verwendung des ,,Train``-Algorithmus wird lediglich die älteste Generation, der sogenannte ,,mature object space`` (MOS), inkrementell bereinigt. Zu diesem Zweck wird er in kleine Blöcke fester Größe (sog. Wagen, cars) unterteilt, die wiederum aufgrund der Verweise untereinander zu Zügen (trains) zusammengefaßt werden. Jeder Wagen verfügt über ein eigenes ,,Remembered Set`` für Verweise aus anderen Wagen und kann somit zusammen mit den jüngeren Generationen, aber unabhängig von anderen Wagen bereinigt werden.
Der ,,Train``-Algorithmus ist nicht zuletzt durch die gut beschriebene Implementierung von [Seligmann and Grarup, 1995] eine gut verstandene Methode zur Bereinigung der alten Generation. Sie wird daher zunehmend bei der Implementierung von Java-VMs eingesetzt, um die Pausen, die durch Garbage Collection des gesamten Speichers entstehen, zu reduzieren.
