| |
– 6 –
3
Garbage Collection in Parallelen Systemen
3.1
Parallelität beim Garbage Collection
Parallelität in Bezug auf GC betrifft unterschiedliche Anwendungsfelder. Erstens kann
damit für eine sequenzielle Architektur gemeint sein, dass der Collector einen laufe nden
Prozess nicht für den gesamten GC-Vorgang unterbricht, sondern Stück für Stück vor-
geht und der Prozess (Mutator) zwischenzeitlich weiterarbeiten kann. Durch das inkre-
mentelle Vorgehen des Collectors können die durch GC verursachten Programmpausen
verringert werden. Zweitens können für parallele Multiprozessorsysteme und für Uni-
prozessorsysteme mit Thread-Parallelität konkurrente (concurrent) GC-Algorithmen
beschrieben werden [Jo96]. In inkrementellen Algorithmen werden Tätigkeiten von
Collector und Mutator ineinander verschachtelt, wobei nie beide gleichzeitig Daten le-
sen bzw. ändern. Im Unterschied dazu dürfen bei konkurrenten Verfahren beide simul-
tan auf Daten arbeiten [GL02]. Während in diesem Kapitel inkrementelle Tracing-
Verfahren und konkurrente Algorithmen, sowohl für Multiprozessor- bzw. Multithrea-
ded-Systeme mit gemeinsamem Speicher als auch für sequenzielle Architekturen, be-
handelt werden, folgt im vierten Kapitel eine Beschreibung von GC-Algorithmen, die
speziell für verteilte Systeme konzipiert sind, in denen mehrere Rechner mit eigenem
Speicher über ein Netzwerk interagieren .
Unabhängig davon, ob Parallele GC-Algorithmen inkrementell oder echt nebenläufig
konzipiert sind, muss eine Synchronisation zwischen Mutator und Collector stattfinden,
um Konsistenzprobleme zu vermeiden [Jo96].
3.1.1
Synchronisation
In Anlehnung an Jones und Lins [Jo96] ist unten in Abb. 1 beispielhaft dargestellt, wel-
che Probleme die Aktivitäten eines Mutators ohne Synchronisation mit dem Collector
hervorrufen können. Im Beispiel wird angenommen, dass vom Root Set eine Referenz
auf zwei Zellen, A und B, besteht. In dem rechten Teil der Zelle A ist zu Beginn (Abb. 1
a) ein Zeiger auf Zelle C enthalten. Im weiteren Programmablauf wird zuerst im rechten
Feld von Zelle B ein Verweis auf C gesetzt und der Zeiger von A auf C entfernt (Abb.
1 b) und anschließend im zweiten Schritt wieder von A auf C verwiesen und der Zeiger
von B auf C gelöscht (Abb. 1 c). Wenn ein Collector im ersten Schritt die Zelle A unter-
sucht hat (siehe schwarze Markierung in Abb. 1 b) und im zweiten Schritt Zelle B vor-
nimmt, könnte der Collector fälschlicherweise schließen, dass Zelle C Garbage ist, weil
er keinen Weg vom Root Set aus über A oder B nach C gefunden hat. Folglich muss die
|  |
|
| |
|
|
