next up previous contents
Next: Der ,,Copying Collection``-Algorithmus Up: Garbage Collection Previous: Der ,,Mark-Sweep``-Algorithmus   Inhalt


Der ,,Mark-Compact``-Algorithmus

Um das Problem der Heap-Fragmentierung zu beheben, wurde eine Reihe von ,,Mark-Compact``-Algorithmen entwickelt [Cohen and Nicolau, 1983]. Diese führen die gleiche Mark-Phase wie die ,,Mark-Sweep``-Algorithmen aus. Danach wird der Heap kompaktiert, d.h. die Objekte werden derart zusammengeschoben, daß die vorhandenen Lücken geschlossen werden (siehe Abb. 2.5-(i)).

Abbildung: Kompaktierungsphase (i) und Zeiger-Anpassungsphase (ii) des ,,Mark-Compact``-Algorithmus
\begin{figure}
\begin{center}
\epsfig{file=garbage-collection/figures/mark-compact,width=8cm} \end{center}\end{figure}

Hierzu müssen die beteiligten Objekte natürlich im Speicher verschoben werden, was bedeutet, daß alle betroffenen Referenzen von den Wurzeln und innerhalb des Heaps angepaßt werden müssen. Dies geschieht in der Zeiger-Anpassungsphase (,,Pointer Update Phase``)2.4 (siehe Abb. 2.5-(ii)).

Der Algorithmus läßt sich also in drei Phasen unterteilen:

1.
Markierung: Markieren der lebendingen Objekte. Wie bei ,,Mark-Sweep`` gilt K(MarkPhase)=O(|live|).
2.
Kompaktierung: Schliessen der Lücken im Heap durch Verschieben der einzelnen Objekte. Da der gesamte Heap durchlaufen wird, gilt die gleiche Komplexität, wie bei ,,Sweep``: K(CompactPhase)=O(heapsize).
3.
Zeiger-Anpassung: Anpassen der Referenzen aus der Wurzelmenge und dem Heap selbst und gleichzeitiges Zurcksetzen der Markierungsbits. Da hierbei nur die Zeiger in lebendigen Objekten angepaßt werden, gilt K(UpdatePhase)=O(|live|).

Ein kompaktierter Heap hat neben der fehlenden Fragmentierung noch weitere Vorteile gegenüber einer Freispeicherliste: Die Allokation wird deutlich schneller, da lediglich ein Zeiger hochgezählt werden muß, anstatt die Liste zu durchsuchen.

Ein weiterer Vorteil eines kompaktierten Speichers betrifft die Referenzlokalität [Hennessy and Patterson, 1996]. Darunter wird das Maß verstanden, in dem Zugriffe auf benachbarte Speicherzellen auch zeitlich dicht beieinander liegen. Eine hohe Referenzlokalität führt zu einer höheren Trefferquote im Cache und damit zu weniger Speicherzugriffen.

Objekte, die in zeitlicher Nähe erzeugt wurden, werden oftmals auch im weiteren Verlauf nahe nacheinander referenziert. Da der ,,Mark-Compact``-Algorithmus nacheinander allozierte Objekte nebeneinander ablegt und diese auch bei einer Garbage Collection nicht trennen wird, beeinflußt er die Lokalität des Programmes positiv.

Der ,,Mark-Compact``-Algorithmus vermeidet also Fragmentierung bei schnellerer Allokation und verbesserter Lokalität - dafür muß der Algorithmus gegenüber mark-sweep eine dritte Phase mit der Komplexität O(|live|) durchlaufen. Setzt man voraus, daß die Mark-Phasen der beiden Algorithmen, sowie Compact und Sweep jeweils die gleiche Zeit beanspruchen, so ist also ,,Mark-Compact`` um diesen zusätzliche Durchlauf langsamer als ,,Mark-Sweep``. Dieser Durchlauf kann vermieden werden, wenn nicht direkte Referenzen sondern handles verwendet werden. Diese würden den Programmablauf aber zugunsten der Garbage Collection verlangsamen und ist daher nicht zu empfehlen.


next up previous contents
Next: Der ,,Copying Collection``-Algorithmus Up: Garbage Collection Previous: Der ,,Mark-Sweep``-Algorithmus   Inhalt

2001-02-28