| |
– 21 –
4.2
Beispielalgorithmen
Im Folgenden wird der Distributed Mark-Sweep Collector von Hudak und Keller
[Hu82] und der Algorithmus aus dem Artikel „Garbage collecting the world“ von Lang
[La92], als ein Beispiel für verteiltes Reference Counting, vorgestellt. Neben weiteren
GC-Algorithmen, die auf Mark-Sweep oder Reference Counting basieren, sind bei Jo-
nes und Lins [Jo96] auch Erläuterungen zur verteilten Copying-GC und Anwendungen
des Actor-Modells zur verteilten GC zu finden. Mehr Informationen zum SVM-Modell
sind beispielsweise bei Zhou et al. [Zh92] und Levelt et al. [Le92] zu finden.
4.2.1
Distributed Mark -Sweep
Zu den verteilten (distributed) Mark-Sweep Algorithmen werden die Verfahren gezählt,
die erstens von Original-Mark-Sweep Algorithmen (vgl. Kap. 2.2) abstammen und
zweitens solche, die auf Dijkstras On the Fly Collector (vgl. Kap. 3.2.1) basieren [Jo96].
Hudak und Kellers Mark-Tree Collector [Hu82] ist ein verteilter Algorithmus für funk-
tionale Sprachen, der sich auf Dijkstras Collector abstützt und im Folge nden in Anleh-
nung an Jones und Lins beschrieben wird.
In der Hudak-Keller Architektur werden mehrere Prozessorknoten miteinander verbun-
den, wobei Nebenläufigkeit in jedem Knoten so realisiert wird, dass entweder Collector
und Mutator auf einem Multiprozessorsystem mit gemeinsamem Speicher parallel aus-
geführt werden können oder bei einem einzelnen Prozessor die Operationen beider Pro-
zesse miteinander verknüpft werden. So kann die Speicherbereinigung parallel zur Pro-
grammausführung erfolgen. Außerdem können mit Hilfe des Algorithmus auch aktive
Prozesse, die für die Programmausführung nicht mehr benötigt werden, gefunden und
terminiert werden. Unter Verwendung eines virtuellen Adressraums kann für knoten-
übergreifende Tasks eine Referenz auf andere Knoten hergestellt werden. Garbage wird
- erstens ausgehend vom Root Set und zweitens ausgehend von Tasks - gesucht. Dabei
können unerreichbare Knoten, aber auch irrelevante Tasks gefunden werden, die auf-
grund von spekulativem Parallelismus (z.B. Auswertung von unbenötigten Argumenten
einer Funktion) entstanden sind. Geht man bei der Traversierung von Tasks aus, können
auch sogenannte schlafende Subgraphen gefunden werden, denen von keiner Task aus
jemals Arbeit zugewiesen werden kann, obwohl sie vom Root Set aus erreichbar sind.
Zur Kooperation von Mutator und Collector wird ein Markierungsbaum (mark tree) mit
dem Drei-Farben-Schema verwendet, in dem ein verteilter Mutator Zweige hinzufügen
darf. Das Verfahren ähnelt dem konventionellen rekursiven Markieren, wobei für jeden
rekursiven Schritt eine Markierungs-Task für die Kindknoten erzeugt wird. Wenn ein
|  |
|
| |
|
|
