Der ,,Mark-Sweep``-Algorithmus

,,Mark-Sweep`` ist ein sehr einfacher Algorithmus zur Garbage Collection, der aber in Abwandelungen auch in aktuellen Systemen Verwendung findet. Sein Name ergibt sich aus den beiden Phasen benannt, in denen die Garbage Collection ausgeführt wird:

1.

Mark: In der ersten Phase werden alle Objekte, die von den System-Roots erreichbar sind - die also live sind - markiert (Siehe Abb. 2.4-(i) und 2.4-(ii)). Üblicherweise werden zu diesem Zweck alle Wurzeln auf einen Stack gelegt und dann die jeweils oberste Referenz bearbeitet, bis der Stack leer ist. Bei der Bearbeitung wird zunächst geprüft, ob das referenzierte Objekt bereits markiert wurde. Ist das nicht der Fall, so wird sein ,,Mark Bit`` gesetzt (dies ist üblicherweise ein Bit im Objektkopf) und alle Referenzen, die in diesem Objekt enthalten sind, werden auf den Stack gelegt. Wenn die Mark-Phase abgeschlossen ist, sind alle erreichbaren Objekte besucht worden, die Komplexität K dieser Phase ist also proportional zur Größe der Menge live (siehe Formel 2.1). Es gilt also $K(MarkPhase) \in O(\vert live\vert)$. Nach der Mark-Phase geht der Algorithmus in die Sweep-Phase über.

Abbildung: Ablauf des ,,Mark-Sweep``-Algorithmus

2.

Sweep: In dieser Phase wird der Heap linear durchlaufen und unmarkierte Speicherbereiche werden einer oder mehreren Freispeicherlisten zugefügt - folgende Allokationen werden dann aus diesen Listen bedient. Während der linearen Suche durch den Heap werden weiterhin alle Markierungen zurückgesetzt, damit diese bei der nächsten Garbage Collection zur Verfügung stehen (siehe Abb. 2.4-(iii)). Die Komplexität dieser Phase ist proportional zur Zahl der Objekte, und damit gilt $K(SweepPhase) \in O(heapsize)$.

Der Vorteil dieses Algorithmus ist seine Einfachheit (ein Vorteil den man nicht unterschätzen sollte, da die Fehlersuche im Garbage Collector auch bei einfachen Algorithmen bereits sehr komplex ist). Er leidet aber unter einer Vielzahl von Nachteilen - so kann der zur Markierung verwendete Stack schlimmstenfalls auf die Größe des Heaps wachsen. Es existieren verschiedene Erweiterungen des Algorithmus, die dieses Problem beheben oder zumindest abmildern. [Knuth, 1973] schlägt vor, den Stack zyklisch zu verwenden, muß allerdings den Heap nach Referenzen von markierten auf unmarkierte Objekte in Kauf nehmen, wenn der Stack leerläuft. [Schorr and Waite, 1967] entwickelten den ,,Pointer-Reversal``-Algorithmus , der einen Graphen mit konstantem Platz markieren kann. Hierbei geht aber leider die Einfachheit der ursprünglichen Mark-Phase verloren.

Weiterhin tritt bei der Verwendung von Objekten unterschiedlicher Größe eine Fragmentierung des Heaps ein, die zu einem wesentlich größeren Heap führen kann, als eigentlich vom Programm benötigt wird, da ungenutzte Lücken im Heap entstehen (siehe Abb. 2.4-(iii)).