| |
– 9 –
nach Überschreiben eines Zeigers noch nachverfolgen kann. Zum anderen geht der so-
genannte Incremental-Update Collector problematische Verweise direkter an, indem er
bei Verweisen von schwarzen auf weiße Objekte das Ziel (die weißen Objekte) betrach-
tet. Dazu können entweder die weißen Objekte sofort grau markiert oder das ursprüng-
lich schwarze Objekt wieder grau markiert werden. Auf jeden Fall wird dadurch sicher-
gestellt, dass ein neuer Zeiger von einem schwarzen auf ein weißes Objekt bei der Gar-
bage Detection-Phase berücksichtigt wird, weil eins der beiden Objekte unmittelbar
grau gefärbt wird. Je nachdem, welcher GC-Ansatz verfolgt wird, werden entweder
Read-Barrier-Methoden oder die verschiedenen Write-Barrier-Methoden für die GC
eingesetzt, wobei die eingesetzte Methode einen großen Einfluss auf den Overhead von
inkrementeller GC haben kann. Im nächsten Abschnitt werden deshalb neben den GC-
Algorithmen auch die jeweils eingesetzten Barrier-Methoden erläutert.
3.2
Algorithmen für parallele und inkrementelle GC
In diesem Abschnitt sollen unterschiedliche parallele GC-Algorithmen vorgestellt wer-
den. Reference Counting Algorithmen sind zwar aufgrund ihrer engen Kopplung von
Mutator und Collector prinzipiell gut für inkrementelle GC geeignet. Jedoch ersche inen
sie aufgrund mehrerer Nachteile, wie z.B. Probleme beim Auffinden zyklischer Struktu-
ren, enge Kopplung mit dem Benutzerprogramm und hohe Kosten zum Updaten der
Zähler, weniger zweckmäßig für nebenläufige Umgebungen. Das Updaten der Zä hler
muss in einer atomaren Aktion erfolgen, um beispielsweise Race Conditions zw ischen
Threads zu vermeiden. Durch das dazu notwendige Sperren von Objekten, die von meh-
reren Threads verwendet werden, erhöhen sich die Kosten für Zeigeranweisungen zu-
sätzlich. Aufgrund der geringen Verbreitung von konkurrenten Reference Counting-
Verfahren wird hier nur auf Jones und Lins [Kap. 8.4, Jo96] verwiesen. Details zu einer
Untersuchung der Tauglichkeit von Reference Counting für Modula-2+ können bei
DeTreville [De90] gefunden werden. Im Folgenden werden verschiedene Mark-Sweep-
Algorithmen, bei denen ein Mutator nicht vor Änderungen des Collectors geschützt
werden muss, und Bakers Algorithmus und der Appel- Ellis- Li Algorithmus als Beispie-
le für kopierende Verfahren vorgestellt, bei denen auch die Collector schreibend auf
Datenstrukturen zugreifen. Abschließend werden noch grundsätzliche Punkte zu Repli-
cation Copying Collector erwähnt und Bakers Treadmill- Algorithmus vorgestellt.
3.2.1
Mark-Sweep Collectors
Es gibt verschiedene, nicht-kopierende Verfahren zur parallelen GC, die auf dem Mark-
Sweep-Prinzip beruhen. Viele Algorithmen sind
u
rsprünglich für Multi-Prozessoren
|  |
|
| |
|
|
