| |
– 4 –
der Referenzen, besonders bei kurzlebigen Objekten, großen Overhead in Bezug auf die
Zeit zum Updaten der Zähler und den zusätzlichen Platzbedarf für die Zähler. Ferner
kann beim Löschen des letzten Zeigers auf ein Objekt keine Zeitdauer bis zum Ende des
Vorgangs garantiert werden, weil sich das Freisetzen von Speicherzellen rekursiv fort-
setzen kann [Jo96]. Abgesehen vom Basisalgorithmus des Reference Counting gibt es
noch weitere Algorithmen, welche die oben genannten Probleme zumindest mindern.
Für Details verschiedener Algorithmen sei dazu auf Jones und Lins [Kap.3, Jo96]
verwiesen.
2.2
Mark-Sweep
GC läuft bei einem Mark-Sweep Collector in zwei Stufen ab, die den oben vorgestellten
zwei Teilen bei der GC entsprechen. Zuerst werden bei der Garbage Detection diejeni-
gen Objekte markiert, die vom Root Set erreichbar sind (Tracing). Im zweiten Schritt
wird der Speicher von allen Objekten bereinigt, die im ersten Schritt nicht markiert
worden sind, d.h. die freigesetzten Speicherbereiche werden wie beim Reference Coun-
ting in eine Liste für freie Speicherbereiche eingetragen. Allerdings erfolgt die GC beim
Mark-Sweep Algorithmus erst, wenn der Speicherbedarf für neue Objekte nicht mehr
gedeckt werden kann.
Auch bei der Mark-Sweep GC gibt es verschiedene Schwierigkeiten, wie z.B. Fragmen-
tierung des Speichers, hohe Kosten beim Markieren aller lebenden Objekte und lange
Pausen im laufenden Programm während der GC-Phase. Durch geschickte Implementie-
rungstechniken lassen sich diese Probleme jedoch teilweise mildern [Wi94]. Außerdem
ist von Vorteil, dass der Mark-Sweep Algorithmus zyklische Garbage-Strukturen ent-
deckt und kein Overhead bei der Manipulation von Zeigern entsteht [Jo96].
2.3
Copying Garbage Collection
Ein Copying Collector teilt den Speicher bzw. den Heap1 in zwei gleichgroße Bereiche
(Semi-Spaces) auf. Ein Teil enthält aktuelle und der andere Teil veraltete Daten. Zu
Beginn der GC werden die Rollen der beiden Bereiche getauscht. Datenstrukturen in
dem vorher aktiven Bereich (Fromspace) werden traversiert und „lebende“ Zellen in
die andere Hälfte (Tospace) kopiert. Auf diese Weise wird im Tospace die aktive Da-
tenstruktur repliziert. Allerdings ist es bei Verwendung der Grundform des Copying
Algorithmus nötig, das laufende Programm zu unterbrechen bis alle aktiven Zellen in
1
In Anlehnung an Jones [Jo96] kann ein Heap als eine Region im Speicher definiert werden, in der die
Deallokation von Objekten keiner spezifischen kausalen Ordnung folgt.
|  |
|
| |
|
|
