| |
– 26 –
5
Zusammenfassung und Ausblick
In der vorliegenden Arbeit wurde Garbage Collection in parallelen und verteilten Sys-
temen beschrieben. Das Ziel von parallelen Verfahren ist, die Pausen einer Programm-
ausführung während der GC zu verringern [Jo96], wobei andere Ziele wie z.B. Korrekt-
heit
u
nd eine möglichst umfassende Speicherbereinigung nicht außer Acht gelassen
werden dürfen, um einen ungestörten Programmablauf auch mit GC zu gewährleisten.
Dazu wurden eben inkrementellen Algorithmen für sequenzielle Architekturen auch
mehrere verbreitete Algorithmen vorgestellt, die auf Multiprozessorsystemen eine echt
parallele Ausführung von Mutator und Collector erlauben. Allerdings bedürfen beide
Verfahren einer Synchronisation der beiden Prozesse, welche zusätzliche Kosten her-
vorruft. Durch eine unterschiedliche Sicht von Mutator auf Collector bezogen auf die
Lebendigkeit von Objekten können die Kosten zur Synchronisation jedoch verringert
werden. Aber dafür kann - je nach Konservativität des Collectors
großer Anteil von sogenanntem Floating Garbage bis zum nächsten GC-Zyklus „überle-
ben“.
Während Mark-Sweep-Algorithmen meist mit einer Write-Barrier (Incremental- Update
oder Snapshot-At-Beginning) zusammenarbeiten, wird für kopierende Verfahren eine
aufwendigere Read-Barrier nötig, um den Mutator vor Änderungen des Collectors zu
schützen. Beispielsweise steht in Bakers kopierendem Algorithmus (vgl. Kap. 3.2.2) die
Korrektheit des Verfahrens im Vo rdergrund und weniger die Effizienz. Deshalb wird
für seine feingranulare Write-Barrier auch oft eine Hardwareunterstützung gefordert
[Jo96]. Der von Appel, Ellis und Li konstruierte Algorithmus (vgl. Kap. 3.2.3) fußt auf
Bakers, verwendet aber eine Read-Barrier, die auf ganzen Speicherseiten (Pages) statt
auf einzelnen Zellen arbeitet und dazu Hardware für virtuelle Speicherunterstützung
nutzt. Auch die konkurrente Arbeitsweise fördert einen Effizienzgewinn gegenüber Ba-
kers Algorithmus.
Allerdings ist auc h von Bedeutung, wie konservativ die Allokation neuer Objekte gere-
gelt wird. Während beispielsweise Dijkstra in seinem Mark-Sweep Collector neue Ob-
jekte direkt schwarz oder grau färbt, was bedeutet, dass sie auf jeden Fall bis zum
nächsten GC-Zyklus erhalten bleiben, können bei Steele neue Objekte auch weiß initia-
lisiert werden (vgl. Kap. 3.2.1). Dadurch ist ihnen die Möglichkeit gegeben, während
des aktuellen GC-Zyklus zu „sterben“, und der von ihnen belegte Speicher kann noch
freigegeben werden.
Bakers Treadmill- Algorithmus (vgl. Kap. 3.2.5) setzt die aus Copying Collectors be-
kannten vier Objektmengen (bereits abschließend untersuc hte; zwar erreichte, aber noch
nicht vollständig analysierte Objekte; nicht erreichte Objekte; freie Speicherbereiche)
|  |
|
| |
|
|
