Der ,,Copying Collection``-Algorithmus

Die bisher beschriebenen Algorithmen arbeiten als ,,Müllsammler``, da sie nach der Mark-Phase den Speicher durchlaufen und den ungenutzten Speicher ,,einsammeln``. Der Algorithmus ,,Copying Collection`` verfolgt dabei den umgekehrten Ansatz: er evakuiert die lebendigen Objekte in einen anderen Datenbereich und gibt den Ausgangsbereich auf einmal frei. Damit ist er in seiner Komplexität lediglich von der Menge live abhängig. Die hier dargestellte Variante des Algorithmus geht auf [Cheney, 1970] zurück.

Kopierende Garbage Collection unterteilt den zur Verfügung stehenden Speicher in zwei gleich große Halbräume (,,semi spaces``): diese heißen ,,from-space`` und ,,to-space``. Dabei wird vom Programm immer nur der Quellbereich verwendet - alle Objekte befinden sich hier und auch neue Objekte werden hier abgelegt (siehe Abb. 2.6-(i)). Findet eine Garbage Collection statt, so werden die lebendigen Objekte in den freien Zielraum kopiert. Danach werden die Rollen der beiden Bereiche getauscht.

Abbildung: Ablauf einer ,,Copying Collection``

Dabei wird folgendermaßen vorgegangen: Zunächst werden zwei Zeiger scan und free auf den Anfang von ,,to-space`` initialisiert. scan markiert dabei, bis wohin ,,to-space`` fertig bearbeitet wurde, während free anzeigt, wohin das nächste evakuierte Objekt angelegt werden soll.

Danach werden alle Objekte, die von den Wurzeln direkt referenziert werden, nach free kopiert und der Zeiger entsprechend erhöht (Abb. 2.6-(ii)). An der ursprünglichen Adresse der Objekte werden Vorwärtsreferenzen (sogenannte forwarder) hinterlassen, die auf die neue Adresse des kopierten Objektes verweisen. Das Originalobjekt wird also durch die Vorwärtsreferenz überschrieben.

Jetzt wird der Zeiger scan Objekt für Objekt vorbewegt. Jedes Objekt A, das überstrichen wird, wird auf die enthaltenen Zeiger überprüft. Für einen Zeiger ergeben sich prinzipiell zwei Möglichkeiten:

1.

Er zeigt auf ein Objekt B in ,,from-space``, das noch nicht kopiert wurde. In diesem Fall wird B evakuiert, d.h. es wird nach ,,to-space`` kopiert und der Freispeicherzeiger free wird entsprechend erhöht. An der alten Adresse von B wird eine Vorwärtsreferenz hinterlassen. In A wird die neue Adresse von B eingetragen (Abb. 2.6-(iii) und Abb. 2.6-(iv)).

2.

Er zeigt auf eine Vorwärtsreferenz, die ihrerseits auf ein Objekt B in ,,to-space`` zeigt. In diesem Fall wird lediglich die neue Adresse von B in A eingetragen (Abb. 2.6-(iv) und Abb. 2.6-(v)).

Der Zeiger scan wird auf diese Weise solange erhöht, bis der Zeiger free erreicht wird und damit alle Zeiger innerhalb nach ,,to-space`` zeigen (Abb. 2.6-(vi)).

Als letzter Schritt des Algorithmus werden die Rollen der beiden Halbräume getauscht. Die Freispeichergrenze wird auf free initialisiert und das Programm fortgesetzt (Abb. 2.6-(vii)).

Der Algorithmus von Cheney hat eine Vielzahl von Vorteilen: Zum einen ist er in seiner Komplexität nur von |live| abhängig, nicht aber von heapsize. [Appel, 1987] hat in einem einfachen Rechenbeispiel gezeigt, daß die Kosten der Garbage Collection bei Verwendung von ,,Copying Collection`` durch die Erhöhung des verwendeten Hauptspeichers beliebig verringert werden können.

Ein weiterer Vorteil besteht darin, daß die Speicherzuteilung sehr einfach implementiert werden kann: wie bei ,,Mark-Compact`` muß lediglich ein Zeiger erhöht werden, wenn ein neues Objekt anzulegen ist. Positiv ist auch die Tatsache zu bewerten, daß kein Markierungs-Stack benötigt wird, denn der Algorithmus führt eine Breitensuche über den Speicher aus, wobei ,,to-space`` als Zwischenspeicher verwendet wird.

Diesen Vorteilen steht der große Speicherverbrauch der Methode gegenüber: der doppelte Platz muß zur Verfügung stehen. Außerdem verursacht das wiederholte Kopieren von langlebigen oder großen Objekten einen erheblichen Aufwand.

Nichtsdestotrotz bildet der ,,Copying Collection``-Algorithmus wegen der genannten Vorteile und seiner Einfachheit die Basis für zahlreiche ausgefeilte Implementierungen von Garbage Collection [Jones and Lins, 1996].