| |
– 3 –
Speicherbereiche wieder zurückgefordert und für das laufende Programm verfügbar
gemacht. Um die „Lebendigkeit“ von Objekten zu bestimmen, wird meist untersucht,
welche Objekte sich, ausge hend vom sogenannten Root Set, welches globale und lokale
Variablen im Programm-Stack und Werte in Prozessorregistern beinhaltet, über Pointer
erreichen lassen. Die Erreichbarkeit der Objekte wird häufig in einem Graphen darge-
stellt. Sind Objekte nicht vom Root Set erreichbar, werden Sie als überflüssig betrachtet
und der von ihnen verwendete Speicher wird für andere Objekte freigemacht.
Eine fundamentale Anforderung an GC-Techniken ist, die Siche rheit der lebenden, noch
benutzten Objekte zu gewährleisten. Speicherbereiche lebender Objekte dürfen nicht
freigegeben werden, weil sonst Referenzen anderer Objekte auf die freigegebenen
Zellen nicht mehr gültig sind und Fehler im Programmablauf auftreten können. Wie
umfassend der Speicher von Garbage-Objekten bereinigt wird, ist je nach verwendeter
GC-Technik unterschiedlich. Ebenso gibt es Unterschiede, inwieweit GC-Algorithmen
Overhead während der Programmausführung erzeugen und, z.B. bei interaktiven
Programmen, Programmpausen verursacht. Für die weitere Arbeit sollen hier zwei
Begriffe eingeführt werden: Collector, für den GC-Prozess und Mutator, für den
Prozess, der einen Benutzerprozess ausführt und somit Werte und Zeiger im Speicher
verändern kann.
Im Folgenden werden grundlegende Techniken zur GC ansatzweise dargestellt, auf de-
nen die in den nächsten Kapiteln beschriebenen Algorithmen für verteilte und parallele
Systeme aufbauen. Die Techniken unterscheiden sich vor allem darin, auf welche Art
die Identifizierung von Garbage unterstützt wird.
2.1
Reference Counting
Beim Reference Counting wird für jedes Objekt mitgezählt, wie viele Referenzen, d.h.
Zeiger von anderen Objekten, es auf das betrachtete Objekt gibt. Falls der Zähler eines
Objekts auf null steht, kann der vom Objekt verwendete Speicher freigegeben werden,
weil keine Zeiger mehr auf das Objekt zeigen und dieses somit vom laufenden Pro-
gramm nicht mehr erreicht werden kann [Wi94]. Bevor der Speicher freigesetzt wird,
werden allerdings noch alle Zähler derjenigen Objekte dekreme ntiert, zu denen von dem
Garbage-Objekt eine Referenz besteht.
Charakteristisch für das einfache Reference Counting ist, dass zyklische Garbage-
Strukturen nicht erkannt werden und somit auch nicht der von ihnen belegte Speicher
freigegeben wird. Zudem bringt einerseits die Verwendung von Zählern den Vorteil,
dass Reference Counting inkrementell arbeitet. Andererseits erzeugt die Buchführung
|  |
|
| |
|
|
