| |
– 13 –
dass für die einzelnen Elemente S des System-Stacks jeweils eine Sperre (Lock) gesetzt
wird, während sie auf dem Mark-Stack abgelegt werden.
Während des Markierungsprozesses können vom Mutator weitere Elemente auf den
Programm-Stack gebracht bzw. neue Objekte alloziiert werden, die gegebenenfalls auch
auf den Mark-Stack gelegt werden, um vom Collector noch berücksichtigt zu werden.
Um nachzuschauen, ob der Mark-Stack leer und der Markierungsvorgang damit beendet
ist, muss der Mark-Stack in einem parallel laufenden System ebenfalls zur Überprüfung
gesperrt werden (LOCK gcstate). Sind noch Elemente auf dem Mark-Stack vorhanden,
so wird die mark1()-Funktion auch für diese ausgeführt und danach wieder der Mark-
Stack überprüft. Ist dieser leer, ist der Markierungsvorgang beendet und alle übrigge-
bliebenen weißen Objekte können beim Sweep-Vorgang aus dem Speicher entfernt
werden.
3.2.2
Baker’s Collector
Der sehr bekannte Algorithmus vo n Baker [Ba78] ist als ein kopierendes Verfahren
(vgl. Kap. 2.3) für inkrementelle GC auf seriellen Maschinen konzipiert worden. Um
das Multiple-Reader/Multiple-Writer Problem zu lösen, verwendet Baker eine Read-
Barrier, um die Zugriffe von Seiten des Mutators aufzufangen. Möchte der Mutator auf
ein Objekt zugreifen, das noch in Fromspace steht, wird es in Tospace kopiert (und da-
bei grau markiert) und seine neue Adresse an den Mutator zurückgeben. Dadurch kann
der Mutator lediglich Tospace-Objekte sehen. Aus diesem Grund ist es einem Mutator
auch nicht möglich, einen Zeiger von einem schwarzen auf ein weißes Objekt zu erstel-
len und den Collector damit zu stören. Laut Jones und Lines [Jo96] sind bei der Umset-
zung des Verfahrens noch zwei Punkte zu klären. Erstens, ob der Mutator neben
schwarzen Objekten auch (noch nicht abschließend untersuchte) graue Objekte sehen
darf und zweitens, wie viel Arbeit von der Read-Barrier verrichtet werden soll. Entwe-
der kopiert sie lediglich weiße Objekte in Tospace und färbt diese grau oder sie analy-
siert diese und ihre Zeiger vollständig, färbt die Objekte schwarz und gibt dann erst die
Adresse an den Mutator zurück.
Baker hat in seinem Algorithmus auf Cheneys Algorithmus [Kap.6.1, Jo96] zurückge-
griffen und diesen so angepasst, dass ein Mutator während der GC weiterarbeiten kann.
Dazu wird die Semi-Space Tospace so aufgeteilt, dass der freie Bereich von zwei Seiten
alloziiert werden kann, wie in Abb. 3 zu sehen ist.
|  |
|
| |
|
|
