| |
– 22 –
Kindknoten mit der Markierung fertig ist, generiert er eine Up-Tree- Task, die weiter
nach oben propagiert wird.
Abb. 5: Propagierung in Hudak und Kellers Mark-Tree
In Abb. 5 ist zu sehen, dass Knoten A eine Up- Tree Task weiter nach oben propagiert,
während Knoten B noch wartet. Weil für beide Tasks, die an die Kind-Knoten von A
geleitet wurden, wieder Up-Tree Tasks zurückkamen, wurde der Knoten schwarz ge-
färbt, und von ihm seinerseits eine Up-Tree Task erzeugt und an seinen Elternknoten
geschickt. Knoten B ist noch grau gefärbt, da er selbst von den Eltern eine Task be-
kommen hat und auf die Up-Tree Task von seinem Kind-Knoten wartet. Wird auch von
allen Knoten des Root Sets eine Up-Tree-Task an einen übergeordneten Dummy-
Knoten produziert, so ist der Markierungsvorgang zu Ende. In der Sweep-Phase wird
dann der belegte Speicher der weißen Knoten freigegeben und die Tasks, die auf weiße
Knoten zeigen, terminiert.
4.2.2
Distributed Reference Counting
Beim verteilten (distributed) Reference Counting wird bei der Erstellung einer neuen
Referenz auf ein Objekt und beim Löschen des Verweises eine Nachricht an das Objekt
geschickt werden, damit es seinen Referenzzähler inkrementiert bzw. dekreme ntiert. Ein
Algorithmus in einem VS sollte Fehler berücksichtigen, die beim Verschicken von
Nachrichten über ein Netzwerk auftreten können. Beispielsweise kann eine umgedrehte
Nachrichtenreihenfolge dazu führen, dass eine Nachricht über den Löschvorgang der
letzten Referenz eine Nachricht eines Kopiervorgangs überholt (Race Conditions) und
deshalb ein Objekt fälschlicherweise gelöscht wird [Jo96]. Außerdem können Nachrich-
tenduplikate und verlorene Nachrichten für das Distributed Reference Counting prob-
lematisch sein.
In dem Artikel „Garbage Collecting the World“ beschreiben Lang et al. einen fehlerto-
leranten, hybriden verteilten Collector. Dieser besteht erstens aus (beliebigen) lokalen
Eltern
# Tasks=2
Farbe
A
Eltern
# Tasks=1
Farbe
B
Up-Tree
Task
Up-Tree
Task
|  |
|
| |
|
|
