| |
– 8 –
lectors erreicht, so wird es grau markiert. Nachdem alle Objekte, auf die von einem
grauen Objekt gezeigt wird, untersucht und auch grau markiert worden sind, wird das
graue Objekt schwarz markiert [Wi93]. Für die GC bedeuten die Farben folgendes: Ist
ein Objekt an Ende der Garbage Detection-Phase noch weiß, so wurde es bei der Tra-
versierung des Collectors nicht erreicht und ist somit überflüssig. Graue Objekte müssen
vom Collector noch mal untersucht werden, weil entweder die direkten Referenzen ihrer
Zeiger noch nicht untersucht wurden oder die Erreichbarkeit zu den restlichen Objekten
vom Mutator im Hintergrund verändert wurde. Schwarze Objekte sind vom Collector
schon vollständig abgearbeitet, d.h. sie wurden vom Collector erreicht und ihre unmit-
telbaren Nachfolger sind auch bereits untersucht worden [Kap. 8, Jo96].
Das in Abb. 1 dargestellte Beispiel, hat gezeigt, dass es zu Konsistenzproblemen kom-
men kann, wenn der Mutator Zeiger von Objekten, die vom Collector schon abschlie-
ßend untersucht und schwarz markiert worden sind, auf weiße, d.h. noch nicht erreichte,
Objekte, setzt (Zelle A in Abb. 1 b). Deshalb spricht man von der sogenannten
Schwarz-Weiß-Invariante oder der Drei-Farben-Invariante [MMN02] - als Eigenschaft
eines Verweisgraphen, dass keine Kante von einem schwarzen Knoten zu einem weißen
existiert.
3.1.3
Barrier-Methoden
Grundsätzlich gibt es zwei Verfahren, die einen Mutator daran hindern sollen, einen
Zeiger von einem schwarzen auf ein weißes Objekt zu setzen. Mit Hilfe einer Read-
Barrier (Lesebarriere) wird verhindert, dass ein Mutator überhaupt weiße Objekte sieht.
Möchte der Mutator auf weiße Objekte zugreifen, werden diese zuerst vom Collector
bearbeitet, bevor der eigentliche Zugriff erfolgt.
Bei der zweiten Methode, der Write-Barrier (Schreibbarriere), wird aufgezeichnet, wel-
che Zeiger der Mutator während der GC von schwarzen Objekten auf weiße Objekte
herstellt. Der Garbage Collector kann dann betroffene Knoten analysieren bzw. noch
mal neu untersuchen. Ohne eine Write-Barrier (und Read-Barrier) kann es vorkommen,
dass ein weißes Objekt fälschliche rweise als Garbage klassifiziert wird, wenn erstens
ein Zeiger von einem schwarzen zu dem weißen Objekt gesetzt wird (Bed. 1) und
zweitens der Originalverweis (z.B. von einem anderen grau markierten Knoten zu dem
weißen) ze rstört wird (Bed. 2) (vgl. Abb. 1), bevor der Collector diesen sieht. Laut
Wilson [Wi94] gibt es zwei unterschiedliche Ansätze für eine Write-Barrier, die sich
auf diese beiden Bedingungen konzentrieren. Zum einen gibt es den Snapshot-at-
beginning Collector, der aktive Datenstrukturen zu Beginn der GC statisch sichert. Da-
mit wird siche rgestellt, dass der Collector Originalreferenzen zu weißen Objekten auch
|  |
|
| |
|
|
