Kapitel 3 der Diplomarbeit
Zusammenfassung von Kapitel 3.3
Feststellung der Referenzierbarkeit
Rainer Rabenstein 9025614
Der erste Schritt einer Garbage Collection ist es, festzustellen, welche Teile des Speichers noch verwendet werden, und welche nicht.
Das heisst in diesem Fall, wenn die Maschine eine Speicherzelle direkt oder indirekt referenzieren kann, wird die Zelle noch benoetigt.
Es wird angenommen, dass die Maschine von der Wurzel aus ueber einen gerichteten Graphen auf die einzelnen Zellen zugreift.
Um nun die Referenzierbarkeit der Speicherzellen feststellen zu koennen, muss man diesen Graphen durchwandern, dann werden alle noch benoetigten Zellen markiert.
Bei diesem Vorgang ergeben sich allerdings Speicher- und Performance-Probleme, wobei gerade Speicherknappheit zum Zeitpunkt der GC ein ernstes Problem darstellt.
Es sollen 4 Gruppen von Loesungsansaetzen behandelt werden:
Durchwandern mittels Tiefensuche
Deutsch-Schorr-Waite
Durchwandern mittels Breitensuche
Referenzzaehler
1. Durchwandern mittels Tiefensuche
Am einfachsten beschreibt diesen Vorgang ein rekursiver Algorithmus, der von der Wurzel ausgehend alle Nachfolger der Zelle zuerst in die Tiefe, und dann in die Breite markiert.
mark(ptr z) {
int i;
if(!z->marked){/* nach head */
z->marked = true;
for (i = 0; i < size(z); i++)
mark(z->args[i]);
}
}
Der Algorithmus ist denkbar einfach, aber durch die Rekursivitaet sehr speicheraufwendig.
Oft wird die Rekursion auch durch explizite Stack-Aufrufe ersetzt, was zwar den Prozedur-Stack entlastet, aber dennoch sehr speicheraufwendig ist, der zum Zeitpunkt der GC oft nicht vorhanden ist.
Es koennen bei diesem Algorithmus
mark(ptr z) {
stack s;
init(s);
L1: if(!z->marked){/* nach head */
z->marked = true;
if(list(z)){
push(z->tail,s); z = z->head; goto L1;
}
}
if (s == empty) return;
z = pop(s); goto L1;
}
bei Gebrauch von n Stackelementen genau n Zellen markiert werden.
Eine Verbesserung, naemlich die Markierung von 2n Elementen bei gleichem Speicheraufwand ergibt sich durch Entfaltung einer Rekursionsebene:
mark(ptr z) {
stack s;
init(s);
L1: if(!z->marked){/* nach head */
z->marked = true;
if(list(z)){
L2: y = z->head; x = z->tail;
if (y->marked)
z = x;
else {
y->marked = true;
if (list(y)){
if (!x->marked){
x->marked = true;
if (list(x))
push(x,s);
}
z = y;
} else z = x;
}
goto L1;
}
}
if (s == empty) return;
z = pop(s); goto L2; /* z ist sicher eine Liste */
}
Man kann den speicherbedarf durch Entfaltung auf Kosten hoeherer Laufzeit weiter vermindern. Es werden aber auch adaptive Verfahren, die auf das Speicherangebot reagieren, verwendet.
2. Deutsch-Schorr-Waite
Waehrend der Markierung des Graphen mit den obengenannten Algorithmen gelten folgende Behauptungen:
Alle Elemente am Stack sind markiert
Alle Elemente des Graphen, die nicht am Stack liegen, koennen von Elementen am Stack erreicht werden
Am Stack steht der Pfad von der Wurzel zur aktuellen Zelle
Der Stack stellt eine Kopie eines Teilgraphs dar:
Der DSM-Algorithmus faltet nun den Stack in den Graphen. Einige Methoden dafuer sind:
2.1 Herleitung nach Derschowitz
Elimination der Parameter und lokalen Variablen
Der Stack wird direkt in den Graphen gefaltet, die Laufvariable fuer die Nachfolger-Knoten wird entweder in einem eigenen, kleineren Stack gefuehrt, oder mit den Zellen gespeichert.
Bei der folgenden Variante wird der Zeiger auf das aktuelle Element nicht ueber den Parameter der Prozedur uebergeben, sondern direkt in ein Argument des Knotens geschrieben.
mark(ptr p){
z = p;
x = nil;
t_mark();
}
t_mark() {
if(!z->marked){/* nach head */
z->marked = true;
for(z->count=0; z->countcount++){
t = z->args[z->count];
z->args[z->count] = x;
x = z;
z = t;
t_mark();
t = x->args[x->count];
x->args[x->count]= z;
z = x;
x = t;
}
}
}
Elimination der Rekursion
Um nun den Unterschied, ob t_mark() von t_mark() oder von mark() aufgerufen wurde, abzufangen und verschiedene Punkte anspringen zu koennen, muss man ein Kriterium finden, das diese Unterscheidung ermoeglicht: x ist nur dann nil, wenn der Funktionsaufruf durch mark() erfolgte.
t_mark() {
L1: z->marked = true;
for(z->count = 1; z->count=count++){
t = arg(z->count,z);
if (!t->marked){
arg(z->count,z) = x; x = z; z = t;
goto L1;
L2: t = arg(x->count,x);
arg(x->count,x) = z;
z = x;
x = t;
}
}
if (x != nil) goto L2;
}
2.2 Herleitung nach Broy und Pepper
Broy und Pepper gehen von einer mathematischen Spezifikation des Problems aus, der Berechnung der reflexiven und transitiven Huelle einer Relation.
Das Ergebnis ist ein effizientes prozedurales Programm.
Ausgangspunkt ist ein rekursiver Tiefensuch-Algorithmus, der in ein funktionales Programm und dieses zu einem nichtrekursiven prozeduralen Programm umgeformt wird.
Das Ergebnis kann noch optimiert werden:
Lastcall-Optimierung
Da es sich in den meisten Anwendungen dieses Algorithmus um listenaehnliche Strukturen handelt, braucht man keinen Stack; das erste Element ist eine Konstante, nur das letzte ein Zeiger.
Es laesst sich zeigen, dass der DSW-Algorithmus diese Optimierung nachvollziehren kann.
Vermeidung des Zaehlers
Statt des Zaehlers wird ein Markierungs-Bit mitgefuehrt, das angibt, ob das naechste element noch zur Struktur gehoert.
Dieses Verfahren ist vor allem dann sehr effizient, wenn kleinere Knoten vorkommen, die nicht durch grosse belastet werden sollen. Diese Vorgangsweise ist sehr effizient, wenn man vor allem 2-elementrige Strukturen markieren muss.
3. Durchwandern mittels Breitensuche
Die Breitensuche benoetigt noch wesentlich mehr Speicherplatz als die Tiefensuche.
Der Algorithmus von Baker bedient sich der Tatsache, dass waehrend des Durchwanderns der Tiefe n alle Zellen auf dieser Tiefe gespeichert werden muessen, indem er mit dem Markieren der Zellen auch das Kopieren verbindet.
4. Referenzzaehler
Die Laufzeit der bisher betrachteten Verfahren ist stets von der groesse des Graphen abhaengig. Um unnoetige Zellen moeglichst bald erkennen zu koennen, muesste man nach jeder Operation auf den Graphen einen Markierungs-Algorithmus anwenden. Stattdessen kann das Programm, das den Graphen bearbeitet bei jeder Veraenderung Operationen ausfuehren, die Informationen u.a. darueber liefern, ob ein Element noch benoetigt wird.
Pro Zelle wird ein Zaehler verwendet, der angibt, wieviele Zeiger gerade auf die Zelle zeigen, und sich bei jeder Manipulation anpasst. Das Programm laeuft dadurch natuerlich etwas langsamer.
Diese Referenzzaehler koennen die eigentliche Markierung nur aufschieben, da eine Zelle wohl durch mehr als 0, also mindestens einen Zeiger referenziert werden kann und dennoch nicht zum aktiven Graphen gehoert, wenn sie zum Beispiel teil eines vollstaendig inaktiven Teilgraphen ist. Auch koennte die Kapazitaet des Zaehlers durch die Anzahl der Zeiger ueberschritten werden.
Moegliche Realisierungen dieser Tehorie sind:
4.1 Ein-Bit
Es wird nur unterschieden, ob eine Zelle genau einmal, oder aber mehr als winmal referenziert wird.
Wird nun die einzige Referenz geloescht, kann die Zelle sofort freigegeben werden, ist die Zelle mehrfach referenziert, muss sie durch einen anderen Algorithmus behandelt werden.
4.2 Gewichtete Referenzaehler
Statt dem Referenz/Bit besitzt die Referenz ein Gewicht. Die Summe der Gewichte der Zeiger einer Zelle ist gleich dem Weryt des Referenzzaehlers.
Beim Kopieren eines Zeigers wird das Gewicht des Quell-Zeigers auf Quelle und Ziel aufgeteilt.
Wird eine Zelle freigegeben, wird der Referenzzaehler um das Gewicht verkleinert. Soll eine Referenz mit nicht teilbarem Gewicht kopiert werden, muss der Wert des Referenzzaehlers erhoeht werden. Dieser Fall tritt aber fruehestens nach 2log2(n)+1 neuen Zeigern ein, wobei n der maximale und 1 der minimale Wert des Referenzzaehlers seien.
4.3 Verallgemeinerte Referenzzaehler
Referenzzaehler koennen durch folgende Parameter an das System angepasst werden:
Wahl der Datentypen der Referenz und der Gewichte
Wahl der Aufteilungsstrategie der Gewichte
Wahl des Anfangswertes
Daraus erkennt man, dass sowohl der gewoehnliche Referenzzeaehler, als auch der Ein-Bit-Algorithmus einen Spezialfall des gewichteten Referenzzaehlers darstellen.
4.4 Deutsch-Bobrow
Die Erfahrung zeigt, dass die meisten Zellen nur einmal referenziert werden Deutsch und Bobrow halten die Information ueber die Anzahl der Zeiger pro Zelle statt in einem Bit in 2 Tabellen fest, die die Adressen der entsprechenen Zellen beinhalten.
Die Tabelle mit den Zellen, kdie mehrmals referenziert werden, kann zusaetzlich noch Zaehler fuer jede Zelle enthalten.
Wird ein Zeiger veraendert, wird in der entsprechenden Tabelle nach der Zelle mit ihrer Adresse als Hash-Wert gesucht.
Sannsonnet implementierte eine leicht erweiterte Variante mit einem 3-Bit-Zaehler, es werde gezeigt, dass 98% aller Zellen mit diesem Zaehler auskommen.
Materialordner
HTML-Anleitung
