3 Verfahren zur Speicherbereinigung

3 Verfahren zur Speicherbereinigung 21
3.1 Problemstellung 21
3.2 Verteilte Speicherbereinigung 22
3.3 Feststellung der Referenzierbarkeit 22
3.3.1 Durchwandern mittels Tiefensuche 22
3.3.2 Deutsch-Schorr-Waite 24
3.3.2.1 Herleitung nach Derschowitz 24
3.3.2.1.1 Elimination der Parameter und lokalen Variablen 24
3.3.2.1.2 Elimination der Rekursion 25
3.3.2.2 Herleitung nach Broy und Pepper 25
3.3.2.2.1 Lastcall- Optimierung 26
3.3.2.3 Vermeidung des Zählers 26
3.3.3 Durchwandern mittels Breitensuche 26
3.3.4 Referenzzähler -- ein verzögertes Markieren 26
3.3.4.1 Ein-Bit 27
3.3.4.2 Gewichtete Referenzzähler 27
3.3.4.3 Verallgemeinerte Referenzzähler 28
3.3.4.4 Deutsch-Bobrow 28
3.4 Verfahren zur Speicherrückgabe 29
3.4.1 Mark and sweep 29
3.4.1.1 Dijkstras On-the-Fly 30
3.4.1.2 Abraham und Patel 31
3.4.2 Kompaktierende Algorithmen 31
3.4.3 Knuths LISP 2 31
3.4.4 Table Compactors, Haddon & Waite, Wegbreit 31
3.4.5 Edwards Kompaktierer 32
3.4.6 Kopieralgorithmen 33
3.4.6.1 Minsky 33
3.4.6.2 Fenichel-Jochelson - Twospace Kompaktierung 33
3.4.6.3 Scavenging Algorithms 34
3.4.6.3.1 Bakers Kopieralgorithmus 34
3.4.6.3.2 Ringkompaktierung 34
3.4.6.3.3 Liebermann und Hewitt 35
3.4.6.3.4 Ungar generation scavenging 35
3.4.6.4 Anwendungen 36
3.4.7 Zeigerumkehrtechniken 36
3.4.7.1 Auffädelung 36
3.4.7.2 Morris I 38
3.4.7.3 Jonkers 41
3.4.7.4 Dewar-McCann 41
3.4.7.5 Thorelli 41
3.4.7.6 Morris II 42
3.4.7.7 Vergleich 43
3.4.8 Aufwand 44

3 Verfahren zur Speicherbereinigung

In diesem Kapitel wird versucht, eine systematische Darstellungen existierender Verfahren zu geben. Durch Kombination der unter 3.3 und 3.4 vorgestellten Algorithmen können alle bekannten Algorithmen hergeleitet oder zumindest motiviert werden. Alle Algorithmen müssen im wesentlichen zwei Aufgaben erfüllen: Die Referenzierbarkeit von Zellen muß festgestellt werden (Kapitel 3.1); und der Speicher muß reorganisiert werden (Kapitel 3.2). Eine Kombination von Algorithmen aus diesen beiden Klassen kann im einfachsten Fall das Hintereinanderausführen oder aber auch eine entsprechende Faltung [Darl81b] der Verfahren bedeuten. Leider gibt es bezüglich der Algorithmen zur Reorganisation des Speichers bisher noch keine Erfahrungen, inwieweit Techniken der Programmtransformation angewendet werden können, ähnlich, wie es sie etwa schon für Sortieralgorithmen, aber auch für die Markierungsalgorithmen gibt. Es wurde daher versucht, durch Parametrisierung einen Großteil der nötigen Transformationen herauszuheben. Dadurch können bis zu einem gewissen Grad ad hoc adaptive Varianten der Verfahren realisiert werden; eine vollständige automatische Generierung wird allerdings nur durch Techniken der Programmtransformation gepaart mit datentyporientieren Methoden i.e. der algebraischen Spezifikation [EhrMa85] möglich sein.

3.1 Problemstellung

Eine Maschine wird durch ihr Verhalten nach außen charakterisiert. Ihre Repräsentation stellt einen Zustand dar, der im allgemeinsten Fall -wie bei der Turing-Maschine- das gesamte Verhalten der Maschine bestimmt. Der Zustand wird mittels eines endlichen Speichers realisiert. Durch Transformation des Zustandes unter Beibehaltung des Verhaltens möchte man das innere Verhalten der Maschine, das heißt die Laufzeit oder die Belegung des Speichers, verbessern, entweder die Zahl der benötigten Speicherelemente vermindern, oder die Anordnung der benötigten Elemente verändern. Der Einfachheit halber wird beim Zustand einer Maschine zwischen einem während der Laufzeit der Maschine statischen Teil, dem Programm der Maschine, und einem dynamischen Teil, den Daten, unterschieden. Das Arbeiten der Maschine in einem derartigen Teilzustand heißt Ausführung des Programms.

Werden die statischen Teile der Maschine vor der Laufzeit in äquivalente Teile umgeformt, spricht man von Programmtransformation. Bei einem Spezialfall dieser Problemstellung wird eine existierende Maschine angenommen. Durch Übergang von dynamischen Teilen in statische erhält man eine Maschine mit einem "größeren" Programm. Die Umformung eines derartigen Programms in ein effizienteres also in ein kleineres oder ein schnelleres nennt man partial evaluation [Fea87].

Die Umformung der rein dynamischen Teile während der Laufzeit wird zwar wesentlich häufiger angewandt, es gibt aber für sie keine äquivalente Bezeichnung. Meist spricht man von Speicherverwaltung, im besonderen Speicherbereinigung. Eine solche Umformung könnte durch Einfügungen von dazu erforderlichen Programmteilen in das ursprüngliche Programm erklärt werden und damit als Spezialfall der Programmtransformation angesehen werden. Die Operationen der darzustellenden Maschine beschreiben meistens das Verhalten auf einer höheren Ebene, die den eigentlichen Speicher abstrahiert, sodaß eine weitere Maschine zur Verwaltung und Transformation der Daten im Speicher getrennt betrachtet werden muß. Adressen eines Prozessors in virtuellen Speichern abstrahieren etwa die Darstellung im Hauptspeicher oder auf einem externen Speichermedium. Sie werden durch eine gesonderte MMU (Memory Management Unit) verwaltet. Variablen abstrahieren die Adressen im virtuellen Speicher; Objekte die Art der sie repräsentierenden Datenstrukturen als Blöcke auf einer Speicherplatte, als Hauptspeicher oder als ein externes Gerät. Symbole abstrahieren ihre Repräsentation und die Identität dieser (zeitlichen) Repräsentation.

In der klassischen Problemstellung der Speicherbereinigung wird ein gerichteter möglicherweise zyklischer Graph, dessen Knoten durch Zellen in einem homogenen Speicher und dessen Kanten als Zeiger (Adressen) auf andere Zellen realisiert sind, verändert und erweitert. Der Speicher soll nun so umgeformt werden, daß Speicherelemente, die nicht Teil des Graphen sind, für neue Zellen wiederverwendet werden können, und daß der Graph auf einen isomorphen Graphen, möglicherweise unter Beibehaltung einer zusätzlichen Relation (meist einer Ordnung oder die Zugehörigkeit zu gewissen Mengen) abgebildet wird. Es werden bei der Beschreibung der Algorithmen Zellen sog. CONS-Zellen oder Zellen mit einer im header der Zelle erkennbaren Größe angenommen.

3.2 Verteilte Speicherbereinigung

In letzter Zeit wurden auch leicht veränderte Problemstellungen betrachtet. Bei der verteilten Speicherbereinigung werden mehrere physisch voneinander getrennte Speicher eines verteilten Systems, die miteinander unter größerem zeitlichen Aufwand kommunizieren, angenommen. Innerhalb dieser Diplomarbeit wird allerdings nicht auf diese Verfahren eingegangen. [Gu88,Sche88,Decou86] sind neuere Arbeiten auf diesem Gebiet.

3.3 Feststellung der Referenzierbarkeit

Im einfachsten Ansatz geht man davon aus, daß alle jene Elemente noch benötigt werden, auf die die Maschine entweder direkt oder über für sie erreichbare Elemente zugreifen kann. Die Referenzierbarkeit von Zellen wird also durch Zugehörigkeit zum Graphen festgelegt. In den Kapiteln 4.2.2 und 4.4 finden sich Beispiele dafür, daß dieser Begriff der Referenzierbarkeit noch nicht allgemein genug formuliert ist. Für die klassische Problemstellung reicht diese Annahme allerdings aus. Vorerst wird angenommen, daß die Maschine über eine Wurzel auf eine Struktur zugreifen kann, die durch einen gerichteten -möglicherweise zyklischen- Graphen dargestellt wird. Zur Feststellung der Referenzierbarkeit ist es erforderlich, diesen Graphen zu durchwandern. Meist wird dabei der Graph verändert oder markiert, sodaß zyklische Graphen keiner Sonderbehandlung bedürfen.

3.3.1 Durchwandern mittels Tiefensuche

Die rekursive Variante beschreibt den Markierungsvorgang am einfachsten. 
mark(ptr z) {
   int i;
   if(!z->marked){/* nach head */
	z->marked = true;
	for (i = 0; i < size(z); i++)
	    mark(z->args[i]);
   }
}
Durch Vermeidung der letzten Rekursion können flache Listen ohne Speicherbelegung des Prozedurstacks markiert werden. Üblicherweise wird der Rekursionsaufruf durch explizite Stackmanipulation ersetzt. Mit diesem Algorithmus kann zumindest (worst case) ein Graph bestehend aus n Listenelementen durch n Elemente am Stack markiert werden. Bei einer Struktur beliebiger Größe wird der Stack um einen Faktor größer werden. %% Nur von Baumtiefe abhängig 
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;
}
Der Nachteil dieser Technik ist, daß gerade zum Zeitpunkt der Garbage Collection kaum freier Platz für einen derart großen Stack vorhanden sein wird. Eine Verbesserung wird durch die Entfaltung einer Rekursionsebene erreicht, wodurch bei einer Listenstruktur mittels n Stackelementen bereits 2n Listenelemente markiert werden. In [Kuro81] wird ein ähnliches Verfahren für Lisp 1.9 angegeben. 
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 könnte den Algorithmus auf Kosten höherer Laufzeit analog weiter entfalten. Häufig werden auch adaptive Verfahren eingesetzt, die möglichst lange mit dieser einfachen Variante auszukommen versuchen. Falls der Stack überläuft, werden andere Verfahren angewandt [Knu73]. Kurokawa [Kuro81] überprüft dann etwa den Stack auf redundante Einträge.

3.3.2 Deutsch-Schorr-Waite

Während der Markierung des Graphen mittels des naiven rekursiven Algorithmus gelten folgende Behauptungen: Einerseits sind alle Elemente, die am Stack stehen, bereits markiert, andererseits können alle noch nicht markierten zum Graph gehörigen Elemente von den Elementen am Stack erreicht werden. Auf dem Stack steht stets der Pfad, der von der Wurzel zur gerade markierten Zelle führt. Der aktuelle Stack stellt also die Kopie eines Teils des vollständigen Graphen dar:


Markierung des Graphen; am Stack steht der aktuelle Pfad

Der Deutsch-Schorr-Waite Algorithmus nützt diese Redundanz der Darstellung aus und faltet den Stack in den Graphen. Durch Programmtransformation zeigte Veillon (laut [Co81]) und Derschowitz [Der79], daß dieser Algorithmus direkt aus der rekursiven Variante herleitbar ist. Es wird das Verfahren von Derschowitz erläutert und dann kurz auf das Verfahren von Broy und Pepper [Bro82] eingegangen. In [Bro82] Kapitel 7 findet sich auch eine umfangreiche Übersicht über andere Arbeiten zu diesem Algorithmus.

3.3.2.1 Herleitung nach Derschowitz

3.3.2.1.1 Elimination der Parameter und lokalen Variablen

Der Stack, der die einzelnen Knoten beschreibt, wird direkt in den Graphen gefalten, die Laufvariable für die Argumente kann entweder zu jeder einzelnen Zelle gespeichert werden -dies ist naheliegend, wenn nur Listen (ld(2) = 1bit ) verwaltet werden sollen- oder auf einen eigenen wesentlich kleineren Stack gelegt werden. Der Einfachheit halber wird im folgenden Programm angenommen, daß ein Knoten einen zusätzlichen Eintrag der Größe ld(maxarg) besitzt. Bei der rekursiven Variante wurde der Zeiger auf den aktuellen Knoten über den Parameter der Prozedur übergeben. Nun wird diese Übergabe in ein Argument des Knotens geschrieben. Da der Knoten ja bereits markiert wurde, ist es unmöglich, dieses veränderte Argument innerhalb der darauffolgenden Rekursion anzutreffen. Bei der Rückkehr werden alle Zeiger wieder in den ursprünglichen Zustand versetzt; das nächste Argument kann markiert werden. 
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;
	}
   }
}

3.3.2.1.2 Elimination der Rekursion

Die Prozedur t_mark() konnte entweder von mark() oder t_mark() aufgerufen werden. Bei der Elimination der Rekursion müssen wir daher diese beiden Fälle der Rückkehr unterscheiden. Da x nur beim Aufruf in mark() den Wert nil besitzen kann, genügt eine entsprechende Überprüfung, falls kein weiteres Argument oder keine weitere nichtmarkierte Zelle gefunden werden kann. 
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;
}

3.3.2.2 Herleitung nach Broy und Pepper

Broy und Pepper [Bro82] formulieren die Problemstellung noch wesentlich allgemeiner als Derschowitz. Sie gehen von einer mathematischen Spezifikation des Problems aus, der Berechnung der reflexiven und transitiven Hülle einer Relation und erhalten als Ergebnis ein effizientes prozedurales Programm. Die Entwicklung ist in einige Phasen, abhängig von der verwendeten Beschreibungs- resp. Programmiersprache, unterteilt. Ausgehend von der mathematischen Spezifikation wird ein rekursiver Algorithmus mittels Tiefensuche hergeleitet, der in ein funktionales Programm transformiert wird, das letzten Endes zu einem nichtrekursiven prozeduralen Programm umgeformt wird. Durch die Verwendung von abstrakten Datentypen im funktionalen Programm wird die Herleitung der Zeigermanipulationen unterstützt. In den meisten anderen Ansätzen oder bei der Beschreibung von Algorithmen zur Zeigermanipulation werden ja üblicherweise keinerlei Typisierungen vorgenommen. Durch eine gesonderte (und bewiesene) Transformationregel werden die Rekursionen aufgelöst. Generalization bzw. embedding (die Verallgemeinerung der Problemstellung zu einem einfacher lösbaren Problem, konkret wird z.B. eine neue Funktion definiert, die die zu implementierende Funktion durch konkrete Parameter bzw. durch einen Teil ihres Resultats einschließt) wird in fast allen Transformationsschritten verwendet.

3.3.2.2.1 Lastcall- Optimierung

In den meisten Anwendungen dieses Markierungsalgorithmus hat man es größtenteils mit listenartigen Strukturen zu tun. Um eine einfache Liste zu markieren, benötigt man keinen Stack: Das erste Argument der Liste ist eine Konstante, nur das letzte Argument enthält einen Zeiger. Nur [Bro82 Kapitel 5, "Tuning the Solution"] bemerken ausdrücklich, daß der Deutsch-Schorr-Waite Algorithmus ebenfalls diese Lastcall-Optimierung nachvollziehen kann. Durch ihre sehr abstrakte Herleitung ist es auch kein Problem, diese Optimierung zu erkennen. Die Behauptung von Cohen [Co81], der Deutsch-Schorr-Waite Algorithmus würde jede Zelle drei- statt zweimal besuchen, bezieht sich also nur auf die ihm vorliegende Literatur.

3.3.2.3 Vermeidung des Zählers

Eine andere Variante könnte pro Speicherzelle anstatt des Zählers für die Gesamtstruktur ein zusätzliches Markierungsbit mit sich führen, das angibt, ob das nächste Element noch zur Struktur gehört. Ein derartiges Verfahren wurde von [Appleby88] entwickelt, ohne sich aber der Ähnlichkeit mit dem Deutsch-Schorr-Waite Algorithmus bewußt zu sein. Dieses Verfahren ist besonders effizient, wenn vor allem nur sehr kleine Knoten vorkommen, die nicht durch mögliche große Knoten belastet werden sollen. Vor Ausführung der Markierung müssen alle mark_me Bits false sein. Das erste Argument wird nicht markiert, damit ein Knoten, der direkt davor liegt nicht irrtümlich dieses Argument betrachtet. Diese Verfahren ist effizienter, wenn man vor allem zweielementige Strukturen markieren muß.

3.3.3 Durchwandern mittels Breitensuche

Bereits Verfahren mit Tiefensuche wurden durch die Größe des Stacks in ihrer Verwendbarkeit begrenzt. Eine Breitensuche würde noch wesentlich mehr Platz benötigen. Es müßten während des Durchwanderns der Tiefe n alle Zellen auf dieser Tiefe zwischengespeichert werden. Der Algorithmus von Baker [Bak78] macht sich diese Tatsache zunutze, indem er mit dem Markieren zugleich auch das Kopieren der Strukturen verbindet.

3.3.4 Referenzzähler -- ein verzögertes Markieren

Die bisher aufgezeigten Verfahren zur Bestimmung der Referenzierbarkeit waren in ihrer Laufzeit stets von der Größe des zu betrachtenden Graphen abhängig. Um möglichst frühzeitig nicht mehr referenzierte Zellen zu erkennen, müßte man nach jeder Operation auf dem Graphen einen entsprechenden Markierungsalgorithmus anwenden. Zur Lokalisierung dieses Aufwands kann man sich vorerst darauf beschränken, nur die veränderten Teile zu beobachten. Das Programm, das den Graphen bearbeitet, muß bei jeder Veränderung des Graphen zusätzlich Operationen ausführen. Die so erhaltenen Informationen können zumindest sicher entscheiden, daß ein Element nicht mehr benötigt wird.

Pro Zelle wird ein Zähler verwendet, der gleich der Summe aller auf diese Zelle zeigenden Zellen ist. Bei jeder Manipulation eines Zeigers auf die Zelle wird der Referenzzähler entsprechend verändert. Der Aufwand für die Markierung wird also gleichmäßig auf alle Zeigeroperationen verteilt. Das Programm muß daher um einen Faktor langsamer laufen. Weizenbaum [Wei62,63] verwendete als einer der ersten dieses Verfahren für die Listenmanipulationssysteme SLIP und KLS. Schon in [McB63] wurde dieses Verfahren kritisiert, da es zur Erkennung von Zyklen wesentlich ineffizienter ist. %% als was. Nicht eindeutig? %%%

Man betrachte daher den Referenzähler nur als ein Mittel, um eine eigentliche Markierung aufzuschieben. Durch Betrachten der Anzahl der Zeiger auf eine spezielle Zelle kann man nicht entscheiden, ob die Zelle noch zum aktiven Graphen gehört. Sie kann ja Teil eines unabhängigen zyklischen Graphen geworden sein. Falls die Anzahl der Zeiger die Kapazität des Zählers überschreitet, kann die Zelle auch nicht mehr freigegeben werden. Bei einem beschränkten Adressraum stellt dies zumeist aber kein Problem dar.

3.3.4.1 Ein-Bit

Die Beobachtung, daß fast alle Zellen nur genau einmal referenziert werden, führt zu einer vereinfachten Variante. Statt die genaue Anzahl der Zeiger zu verwalten, wird nur zwischen den Fällen unterschieden, daß eine Zelle genau einmal oder mehr als einmal referenziert wird. Falls eine Referenz auf diese Zelle zerstört wird und die Zelle nur genau einmal referenziert wurde, kann diese Zelle sofort freigegeben werden. Im anderen Fall bleibt das Zählbit gesetzt, da sie ja noch mehr als diese eine Referenz besitzen kann. Zellen, die mehr als einmal referenziert wurden, müssen durch einen anderen Algorithmus freigegeben werden. Da das Zählbit nur von Interesse ist, wenn genau ein Zeiger vorhanden ist, kann es in den Zeiger hineingezogen werden. Beim Kopieren des Zeigers muß nur mehr der Zeiger selbst verändert werden, die referenzierte Zelle wird dazu nicht benötigt. Der Vorgang des Kopierens eines Zeigers wird dadurch zu einer lokalen Operation wie in einer Implementierung ohne GC. Ein erweitertes Verfahren findet sich in [Wi77].

3.3.4.2 Gewichtete Referenzzähler

Die Idee, die notwendigen Operationen auf die Referenzen zu verschieben, kann noch etwas verallgemeinert werden. Jede Referenz besitzt statt des Bits ein Gewicht. Die Summe der Gewichte der Zeiger einer Zelle ist stets gleich dem Wert des Referenzzählers. Beim Kopieren eines Zeigers wird der Wert des Gewichts auf beide Zellen aufgeteilt P beispielsweise halbiert. Falls eine Zelle freigegeben wird, wird der Referenzzähler um den Wert des Gewichts verkleinert. Dieses Verfahren kann solange angewendet werden, bis eine Referenz mit einem nicht mehr aufteilbaren Gewicht kopiert werden soll. In diesem Fall kann der Referenzzähler, falls möglich, erhöht werden. Das Gewicht der zu kopierenden Referenz wird um den gleichen Betrag erhöht, sodaß die Summe aller Gewichte wieder gleich dem Referenzzähler ist. Bei einer ganzzahligen Halbierung der Gewichtung bei jedem Kopieren und einem anfänglichen wie maximalen Wert n und minimalen Wert 1 des Referenzzählers muß frühestens (worst case ) eine andere Strategie nach 2log2(n)+1neuen geschaffenen Zeigern aktiviert werden. Der anfängliche Wert des Referenzzählers muß natürlich nicht dem maximalen Wert entsprechen.

3.3.4.3 Verallgemeinerte Referenzzähler

Referenzzähler können zusammenfassend durch folgende Parameter an die Eigenheiten des Systems angepaßt werden:

Aus diesen Überlegungen sieht man, daß der gewöhnliche Referenzzähler, wie auch der ein-Bit-Algorithmus einen Spezialfall des gewichteten Referenzzählens darstellen: Die Aufteilungsstrategie stößt immer auf einen unteilbaren Wert des Gewichts, sodaß der Referenzzähler stets um 1 erhöht werden muß. Der Anfangswert des Referenzzählers beträgt ebenfalls 1. Gerade bei objektbasierten verteilten Systemen z.B. [Balt87] können die einander widersprechenden Anforderungen von flüchtigen und permanenten Daten durch ein deratig parametrisiertes Implementierungsschema, das durch eine entsprechende Klassenhierarchie zur Verfügung gestellt werden kann, vereint werden.

3.3.4.4 Deutsch-Bobrow

Aufbauend auf der Erfahrung, daß die meisten Zellen nur genau einmal referenziert werden, halten Deutsch und Bobrow [Deu76] diese Information statt in einem Bit in zwei Tabellen fest, die die Adressen der entsprechenden Zellen enthalten. Die Tabelle mit den Zellen, auf die mehrere Zellen zeigen, kann zudem noch getrennt Zähler für jede Zelle enthalten. Beim Verändern von Zeigern wird in der entsprechenden Tabelle nach der Zelle über ihre Adresse als Hashwert gesucht. Diese Änderungsoperationen können auch vollkommen getrennt von einem eigenen Prozessor durchgeführt werden. Eine Analyse in [But87] hat dennoch ergeben, daß dieses Verfahren bei objektbasierten Datenbanken mit Kopieralgorithmen nicht vergleichbar ist. Dafür wird dieses Verfahren in einigen LISP Systemen verwendet [All78,Gab85]. Sannsonnet [San82] implementierte eine leicht erweiterte Variante mit einem 3-Bit Zähler. Bei ihrem mit LEM (Language for Emulation) realisierten Lisp-System wurde in dem M3L-Projekt gezeigt, daß 98% aller Zellen mit diesem Zähler auskommen. Die temporären Referenzen aus Registern werden in einem gesonderten Bit verwaltet.

3.4 Verfahren zur Speicherrückgabe

In diesem Kapitel wird angenommen, daß durch eine der in Kapitel 3.3 erwähnten Methoden nicht mehr referenzierbare Zellen bereits erkannt wurden. Der freiwerdende Platz kann daher wieder für neue Objekte vergeben werden. Im wesentlichen bieten sich hier zwei Richtungen an:
i) Die freien Zellen können über eine eigene Verwaltung direkt für neue Zellen verwendet werden.
ii) Man verlegt die referenzierten bzw. freien Zellen in einen geschlossenen Bereich.

Je nach Beschaffenheit der Zellen, ihrer Größe, ihrer Lebenserwartung und der Anzahl der in ihnen enthaltenen Zeiger auf andere Zellen und der Charakeristika des Speichermediums von schnellem cache bis zu langsamen Archiven und Netzwerken wird man eine Variante zwischen i) und ii) wählen. In dieser Arbeit wird nur auf jene Verfahren eingegangen, die bei der Implementierung von flüchtigen Datenstrukturen applikativer Sprachen von Interesse sein könnten; andere Verfahren finden bei der Implementierung von permanenten (persistent) Datenstrukturen, wie etwa bei Filesystemen, Anwendung. Eine sehr umfangreiche Analyse dieses Problembereichs und zahlreiche Algorithmen findet sich in [Wie87].

3.4.1 Mark and sweep

Eine einfache Implementierung, die Punkt 1 gerecht wird, stellen etwa Freispeicherlisten dar. Nach der Markierungsphase werden alle nichtmarkierten Zellen in die Freispeicherliste gestellt. Die Organisation der Freispeicherliste kann direkt mit dem Algorithmus zur Feststellung der Referenzierbarkeit gekoppelt werden. Die einfachste Variante -mark and sweep- wurde bereits von McCarthy [McC60] verwendet. Eine Analyse von komplexeren Verfahren zur Verwaltung von Zellen unterschiedlicher Größe findet sich etwa in [Niel77]. Ein großer Nachteil dieser Verfahren stellt die Fragmentierung des Speichers dar. Gerade bei virtuellem Speicher sind diese Verfahren mit Vorsicht einzusetzen, da der Speicher bei flüchtigen Datenstrukturen schnell "altert", da ja die verbleibenden referenzierten Zellen über den gesamten Adressbereich verstreut sein können. Das Verfahren hat u.U. bei Datenbanken den Vorteil, daß die einzelnen Zellen von Anfang an fest an ihre Adresse gebunden sind (pinned down). Dadurch kann eine Indirektion beim Zugriff auf die Zelle vermieden werden, ohne die dazugehörigen Zeiger jemals verändern zu müssen. Der Aufwand zum Anlegen einer Speicherzelle hängt von der Komplexität der Freispeicherliste ab. Davies[Dav84] zeigte, daß die Fragmentierung des Speichers bei einer first fit-Strategie gar nicht so sehr von der unterschiedlichen Größe der Zellen abhängt, als von der Verteilung der Lebenserwartungen.

Durch vollkommene Parallelisierung der Markierungs-und Reorganisationsphase haben sich etwa [Dijk78] erhofft, den mark and sweep Algorithmus zu verbessern. Die Nachteile bezüglich der Freispeicherorganisation wurden bereits erwähnt. [Dijk78] betonen allerdings ausdrücklich, daß sie sich kaum praktische Anwendungen für ihr Verfahren erhoffen. Um nicht durch die Synchronisation die Unabhängigkeit der Prozessoren, und damit die erhoffte Parallelisierung einzuschränken gelang es Dijkstra u.a. einen Algorithmus ohne jegliche Synchronisation auf Programmebene zu entwickeln. Auf Prozessorebene muß allerdings noch immer der exklusive Zugriff auf eine Speicherzelle zugesichert werden. Man beachte den Unterschied zwischen verteilten Algorithmen, die auf unabhängigen Teilen arbeiten, und parallelen Algorithmen, bei denen zugleich auf einem Speicherbereich gearbeitet wird.

3.4.1.1 Dijkstras On-the-Fly

Eine Zelle kann drei unterschiedliche Zustände annehmen, die durch die Farben weiß (unmarkiert), schwarz (markiert) und grau (Die Zelle wurde vom Programm benötigt) dargestellt werden. Die grauen Zellen können u.U. schwarz werden. Wenn das Programm (mutator) eine weiße Zelle verwendet, setzt es diese grau. Falls keine freien Zellen mehr vorhanden sind, muß der mutator u.U. auf den collector warten, um eine neue freie Zelle zu bekommen. Der collector markiert die verwendeten Zellen, die Zellen der Freispeicherliste und jede graue Zelle wie folgt: Die verwendeten (=aktiven) Zellen und die Zellen der Freispeicherliste werden schrittweise grau gefärbt, dabei wird die vorhergehende Zelle, von der man gekommen ist, schwarz gefärbt. Danach werden die verbleibenden weißen Zellen in die Freispeicherliste eingehängt und alle schwarzen Zellen auf weiß gesetzt. Inaktive graue Zellen werden daher vorerst schwarz und dann weiß. Im nächsten Zyklus des collectors können sie dann freigegeben werden.

Ein besonders großer Nachteil dieses Verfahrens ist die Tatsache, daß die Zellen in der Freispeicherliste genauso aufwendig behandelt werden müssen wie tatsächlich referenzierte Zellen. Ein derartiger Durchlauf wird daher stets ähnlich viel Zeit benötigen. Bei einer großen Menge von referenzierten Zellen, wird der collector häufig gleichzeitig mit dem mutator auf eine Zelle zugreifen wollen, wodurch sich auch bei Hardwareversionen Verzögerungen beim Speicherzugriff ergeben.

Allein der Entwicklungsaufwand für diesen (scheinbar) einfachen Algorithmus war laut [Dijk78] sehr hoch. Hickey und Cohen[Hick84] analysieren das Verhalten von On-the-Fly mit bedingten Differentialgleichungen unter der etwas realitätsfernen Annahme, daß ein gleichförmiger Speicher mit konstanter Zugriffszeit vorhanden wäre. Die Alterung des Speichers wird also nicht beachtet. Als Vergleichsbasis wird der mark and sweep Algorithmus herangezogen; auch nicht unbedingt der schnellste existierende Algorithmus. Die Produktivität läßt sich laut ihrer Analyse um zumindest 150% (bei doppelter Prozessorleistung) steigern. Da der mutator auch bei der Zuweisung einer referenzierten schwarzen Zelle an eine andere diese grau färbt, werden unnötigerweise schwarze Zellen wieder grau. Ehn [Ehn89] stellt einen diesbezüglich verbesserten Algorithmus vor. Ben [Ben84] vereinfacht On-the-Fly, um einen einfacheren Beweis, der in [Snep87] noch weiter vereinfacht wird, für seine Korrektheit zu erhalten. %% unklar?? Ben erhält zudem eine inkrementelle Variante, bei der nicht immer alle Zellen besucht werden müssen. Falls genügend freie Zellen gefunden worden sind, kann Ben die nachfolgenden Zellen grau färben und so ihre Markierung verschieben.

Der Aufwand von On-the-Fly ist im wesentlichen abhängig von der Flüchtigkeit der Datenstrukturen (Cohen verwendet den Begriff throughput für die Anzahl der neu angelegten, bzw. freiwerdenden Zellen). Je kurzlebiger diese sind, umso zweifelhafter ist der Einsatz dieses Algorithmus. Eine potentielle Verdopplung der Geschwindigkeit durch Entlastung des mutators steht in keinem Verhältnis zu dem schwerwiegendsten Nachteil, der Fragmentierung des Speichers. Dies gilt ebenso für die entwickelten Mehrprozessorversionen. Auch im festen RAM kann dieser Algorithmus gerade bei applikativen Sprachen unmöglich eingesetzt werden. Der collector müßte sofort jede kurzlebige Datenstruktur erkennen, um mit dem mutator Schritt halten zu können. Wadler [Wad76] zeigte, daß der collector zumindest doppelt so schnell sein müßte, um Wartezeiten des mutators zu vermeiden. Vor allem wegen der flüchtigen Datenstrukturen muß der collector schneller sein. Die einzige kommerzielle Implementierung einer leichten Modifikation dieses Algorithmus dürfte George Bosworths Digitalk* Smalltalk-Implementierung für den IBM-PC "Methods" gelungen sein [Bos88]. Seine nachfolgenden Implementierungen verwenden allerdings ausschließlich Ungars [Un84] Generation Scavenging Algorithmus. On-the-Fly dürfte also, wenn überhaupt, nur mit anderen Hardware-Voraussetzungen zu effizienten Implementierungen führen. Dies gilt aber auch für alle anderen Verfahren. Mittels eines assoziativen Speichers könnte die Verwendung einer Freispeicherliste entfallen. Auch die grauen Zellen könnten so wesentlich schneller erkannt werden [Shin87].

3.4.1.2 Abraham und Patel

Abraham und Patel [Abr87] trennen in ihrem System mutator und collector vollständig voneinander, da ja der collector auch in einer älteren Version nichtreferenzierte Zellen erkennen kann. Unterstützt durch virtuellen Speicher können so seitenweise die Freispeicherlisten aufgebaut werden. Solange der mutator keine Zelle einer Seite verändert, wird für beide Systeme dieselbe Seite verwendet. Falls auf eine Seite vom mutator geschrieben wird, muß die Repräsentation der Seite aufgeteilt werden. Im nachhinein werden die beiden Versionen der Seite wieder zusammengesetzt, indem die Werte für die referenzierten Zellen vom mutator übernommen werden; die für die nichtreferenzierten Zellen vom collector. Ein derartiges Verfahren kann sehr leicht auf herkömmlichen System mit virtuellem Speicher in einem lokalen Netzwerk realisiert werden.

3.4.2 Kompaktierende Algorithmen

Die in diesem Kapitel vorgestellte Klasse von Algorithmen versucht die Menge der aktiven Zellen in einem möglichst kleinen Bereich zu halten. Dadurch können insbesondere in virtuellen Speichern [Co67, Bob67] wesentlich bessere Ergebnisse erzielt werden. Durch die Lokalität der Referenzen wird aber auch der cache besser ausgenützt. Die Erhaltung der Ordnung der Zellen untereinander ist ein -für die meisten Prologsysteme- wichtiges Kriterium.

3.4.3 Knuths LISP 2

Um die Zellen in einem Bereich zu kompaktieren, ist es naheliegend, bei jeder Zelle ihre neue Adresse in einem eigenen Feld abzuspeichern, das auch zur Markierung verwendet wird [Knu73]. Pro zu verwaltender Zelleinheit benötigt man daher einen weiteren Zeiger; bei Prolog würde man also fast den doppelten Speicherplatz benötigen. In der ersten Phase werden die Markierungsbits der einzelnen Zellen betrachtet und die neuen Adressen zu jeder Zelle gespeichert. Zur Beschleunigung des Verfahrens werden u.U. zusammenhängende nichtreferenzierte Zellen zusammengefaßt. Durch getrennte Verwaltung der Markierungsbits kann man auch ohne Sortieren diese Phase beschleunigen. Die zweite Phase richtet alle Zeiger auf die neuen Adressen, in der dritten Phase werden schließlich alle Elemente blockweise kopiert. Die zwei letzten Phasen könnten auch, falls sehr viele Zeiger existieren, zusammengefaltet werden.

3.4.4 Table Compactors, Haddon & Waite, Wegbreit

Anstatt für jede Speicherzelle die zukünftige Adresse zu berechnen, wird in dem von Haddon und Waite [Weg72,Fitc78] entwickelten Algorithmus gleich mit dem Verschieben der Zellen begonnen. In den freiwerdenden Zellen wird diese Verschiebung, das Paar <ursprüngliche Adresse,Offset> für einen verschobenen Block, der aus mehreren Zellen bestehen kann, registriert. Damit man ohne zusätzlichen Speicherplatz auskommt, muß die kleinste freiwerdende Zelle zumindest einen derartigen Eintrag enthalten können. Um nicht die gesamte Tabelle bei jedem Schritt neu zu kopieren, wird man nur die Einträge am Rand zu den kompaktierten Zellen kopieren. Die Tabelle wird so durch den freiwerdenden Speicher "gerollt", hin und wieder kommen neue Einträge auf einer Seite hinzu. Nach dieser Phase sind alle Zellen bereits an ihrem zukünftigen Ort. Die Tabelle der Verschiebungen befindet sich geschlossen im freien Bereich, die Einträge innerhalb der Tabelle sind aber leider "durcheinandergeschüttelt" worden.


Table-Compactor während Phase I

In der zweiten Phase werden die Einträge daher sortiert, damit man in der dritten Phase alle Zeiger über diese Tabelle auf ihre entsprechenden Zellen setzten kann. [Fitc78] gibt als Obergrenze für den Aufwand dieses Verfahrens n logn an, mit n der Größe des gesamten Speicherbereichs. Allerdings gilt ebenso, daß dieser Algorithmus in Abhängigkeit von n referenzierten Zellen ebenso n logn benötigt. Je weniger markierte Zellen über einen Bereich verstreut sind, umso viel besser wird sich dieser Algorithmus verhalten. Da durch das Rotieren und Einfügen von Elementen in die Verschiebungstabelle üblicherweise ein Großteil der Ordnung erhalten bleibt, wird man zum Sortieren der Einträge Shells Sortieralgorithmus oder Smoothsort [Gon84] verwenden.

Viele weitere Heuristiken können in diesen Algorithmus einfließen: Durch ein lookahead bei der Kompaktierung kann ein Großteil des Rollens der Tabelle vermieden werden, indem man Verschiebungseinträge hinter die gerade zu kopierende Zelle in einen unmarkierten Bereich setzt. Die Beobachtung, daß zumeist größere zusammenhängende Bereiche auf einmal frei werden, kann das Kopieren der gesamten Tabelle in einen solchen Bereich, unter Beibehaltung der inneren Ordnung, ermöglichen. Auch für Algol 68 wurde dieses Verfahren verwendet [Wo71].

3.4.5 Edwards Kompaktierer

Dieser Kompaktierer [Knu73] verwendet zwei Zeiger, die den zu kompaktierenden Bereich nach markierten Zellen in einer Richtung und in entgegengesetzter Richtung nach freien Zellen sucht. Falls eine markierte Zelle auf der einen Seite gefunden wird, wird diese an die Stelle der ersten freien Zelle auf der anderen Seite kopiert und ein Vorwärtszeiger auf die neue Position in der alten Zelle hinterlassen. Falls die beiden Zeiger zusammentreffen, sind alle Zellen kompaktiert. In der darauffolgenden Phase werden die Zeiger im kompaktierten Bereich gesucht, die auf verschobene Zellen zeigen und durch den an ihrer Stelle befindlichen Zeiger ersetzt. Dieser Algorithmus behält also nicht die Ordnung der Elemente bei. Trotz Kompaktierung werden bei einer größeren Anzahl von Zellen die Zugriffe nicht lokal erfolgen können, da ja die Zellen in willkürlicher Reihenfolge kompaktiert wurden. Kopieralgorithmen vermeiden diesen Nachteil. Eine parallele Variante [Ste75] wurde von Steele entwickelt.

3.4.6 Kopieralgorithmen

Kopieralgorithmen falten die Markierung und das Kopieren der Zellen. Beim Markieren eines Graphen muß man die gesamte Struktur durchwandern. Das gilt auch für das Kopieren einer Struktur. Also ist es naheliegend, diese beiden Phasen zu falten (fusion). Nach dem vollständigen Durchlaufen der referenzierten Zellen befinden sich sämtliche aktive Zellen in einem durchgehenden Block, in dem auch alle Zeiger gerichtet sind. Der restliche Speicher ist der neue Freispeicher. Im Wesentlichen benötigt man bei den gefalteten Kopieralgorithmen nur mehr genau eine Phase, deren Aufwand im direkten Verhältnis zur Anzahl der referenzierten Zellen steht.

Durch die Verwendung einer Freispeicherliste zerfällt der Speicher in kleine unzusammenhängende Stücke (Fragmentierung). Bei der Verwendung von virtuellem Speicher wird allein die Bearbeitung von aktiven Datenstrukturen durch das häufige Laden von Seiten (thrashing) untragbar. Schon sehr früh [Co67] begann man sich daher mit diesem Phänomen auseinanderzusetzen. Die folgenden Algorithmen wurden alle in Hinblick auf die Bewahrung der Lokalität von Referenzen entwickelt.

3.4.6.1 Minsky

1963 entwickelte Minsky [Co81] den ersten Algorithmus dieser Klasse. Die vorhandenen Zellen werden markiert, und für jede CONS-Zelle wird ein Tripel bestehend aus der zukünftigen Position der Zelle und ihrer Zeiger auf z.B. ein File geschrieben. In der im Hauptspeicher verbleibenden Zelle wird ebenfalls die zukünftige Adresse gespeichert.

3.4.6.2 Fenichel-Jochelson - Twospace Kompaktierung

Der zu verwaltende Speicher wird in zwei gleich große Bereiche A und B aufgeteilt. In A werden sämtliche Speicherelemente angelegt. Falls der Speicherbereich von A verbraucht wurde, werden sämtliche aktive Zellen nach B kopiert. An ihren alten Plätzen in A werden wiederum Verweise in den neuen Speicherbereich gesetzt. Falls man beim Kopieren auf einen solchen Zeiger nach B stößt, wird dieser Zeiger als Wert genommen. Dadurch verweisen nach dem Kopieren alle Zeiger in B wieder auf die entsprechenden Zellen in B. B wird danach nun der aktive Bereich und A wird bis zum nächsten Kopieren nicht mehr verwendet. Durch Adressvergleich kann so ohne ein gesondertes Markierungsbit festgestellt werden, ob eine Zelle bereits markiert worden ist. Zum Durchwandern der Zellstrukturen wird der rekursive Algorithmus verwendet. Es wäre, wie angemerkt wird, bei Listen auch denkbar, in den CDR der Liste den Deutsch-Schorr-Wait Algorithmus zu integrieren. Eine weitere Verbesserung des Kopierens ohne einen Stack findet sich in [Cla76].

Verglichen mit den mark-scan Algorithmen besitzen Kopieralgorithmen wesentlich bessere Laufzeiten. Sie sind nur mehr von der Anzahl der momentan aktiven Zellen abhängig und nicht mehr von der Anzahl aller vorhandenen Zellen. Besonders flüchtige Datenstrukturen können durch diese Algorithmen sehr effizient verwaltet werden. Bei permanenten Datenstrukturen ist der Aufwand proportional zur Zeitdauer der verwendeten Daten. Es besteht nun die Möglichkeit, diese permanenten Zellen von einem getrennten System verwalten zu lassen oder aber adaptive Varianten zu entwickeln, die sich sowohl für flüchtige als auch für permanente Daten akzeptabel verhalten.

3.4.6.3 Scavenging Algorithms

3.4.6.3.1 Bakers Kopieralgorithmus

Auch hier wird der Speicher wieder in zwei gleich große Bereiche aufgeteilt. Anstatt sofort alle Zellen in den neuen Bereich zu kopieren wird nur eine fixe Anzahl von Elementen kopiert und die Ausführung der Programme fortgesetzt. Beim Anlegen einer neuen Zelle wird eine konstante Anzahl von Elementen mitkopiert, bis sich sämtliche Zellen im neuen Bereich befinden. Beim Zugriff auf eine Zelle wird sichergestellt, daß sie sich bereits im neuen Speicherbereich befindet. Falls nicht, wird sie in diesen Bereich kopiert. Das Programm verhält sich so als ob sofort nach Aufruf der Speicherbereinigung alle Zellen in den neuen Bereich kopiert worden sind.

Sämtliche im neuen Bereich befindlichen Zellen werden nach alten etwaigen Referenzen durchsucht und die verbleibenden Referenzen kopiert. Um bei diesem Kopiervorgang einen Stack zu vermeiden, werden die Zellen direkt in den neuen Bereich kopiert. Das Verfahren durchsucht nun sämtliche Referenzen des neuen Bereichs, und damit auch die gerade kopierten Zellen. Auf diese Weise werden die Zellen implizit mittels Breitensuche kopiert.

3.4.6.3.2 Ringkompaktierung

Es handelt sich hier [Bek86] um eine einfache Verallgemeinerung des Bakerschen Algorithmus, die für MALI [Bek86] entwickelt wurde. Anstatt die Zellen zwischen zwei abgegrenzten Bereichen hin und her zu kopieren, ist es genausogut möglich, einen Ringspeicher zu nehmen. Der aktive Bereich arbeitet sich in einer Richtung durch den Speicher. Auf der einen Seite werden neue Elemente angelegt, die andere Seite läßt nur mehr "tote" Zellen zurück. Bildlich kann man sich diesen Algorithmus durch eine quergelegte Tonne vorstellen, in der sich Sand befindet. Durch das Rollen der Tonne fallen die Sandkörner von der einen Seite zurück und bewegen so den Sand weiter. Sandkörner, die an der Tonne kleben bleiben -nichtreferenzierte Zellen- werden so von den aktiven Zellen getrennt. Im allgemeinen wird dieses Verfahren sich ähnlich verhalten wie der two-space-Kompaktierer Bakers.


MALI's Ringkompaktierer

Bakers Algorithmus ermöglicht es zwar, den Kopiervorgang auf kleinere Schritte aufzuteilen, dennoch muß innerhalb eines Zyklus die Gesamtheit aller aktiven Zellen bewegt werden.

3.4.6.3.3 Liebermann und Hewitt

Die bekannte Beobachtung, daß es besonders kurzlebige (flüchtige) und permanente Datenstrukturen gibt, legt nahe, die kurzlebigen Zellen in einem gesonderten Bereichen zu halten. Durch Aufteilung des Speichers in viele kleinere Bereiche können so [sowohl] die flüchtigen Datenstrukturen besonders effizient verwaltet werden -unter ihnen wird es kaum referenzierte Zellen geben- , als auch die permanenten Datenstrukturen. In [Lieb83] wird dieser Algorithmus vorgestellt. Jede derartige Generation von Zellen kann für sich bereinigt werden, ohne ältere Generationen zu stören, jüngere Generationen können so häufiger bereinigt werden. Es werden viele kleine Speicherbereiche verwendet, die jeweils durch eine Generations- und Versionnummer gekennzeichnet sind. Die Garbage Collection beginnt in einem Bereich, indem erreichbare Zellen aus diesen Bereich kopiert werden, falls sie während der Ausführung des Programms gefunden werden. Wie auch in Bakers Algorithmus müssen hier entsprechende Verweise auf den neuen Ort der Zelle zurückgelassen werden.

Um alle erreichbaren Zellen möglichst schnell zu erkennen, werden die Zeiger nach ihrer Richtung unterschieden. In LISP-Systemen werden ja fast nur Zeiger von jüngeren Zellen auf ältere erzeugt. Dadurch können nun die jüngeren Generationen vollkommen unabhängig von den älteren behandelt werden. Falls dennoch ältere Zellen auf jüngere zeigen, müssen diese über eine eigene Tabelle pro Bereich geführt werden. Bereiche könne so unabhängig voneinander berarbeitet werden. Wie [Un88] anmerkt, gibt es leider noch keine praktischen Erfahrungen mit diesem Algorithmus. In Prolog jedoch werden derartige Generationen schon von der Semantik der Sprache benötigt: Jeder Wahlpunkt muß den momentanen Zustand der Daten bewahren. Alle Änderungen werden auf dem Trail ohnehin schon markiert. Es ist daher besonders einfach Liebermanns Verfahren für Prolog zu adaptieren, ohne auch nur den geringsten Mehraufwand zur Laufzeit in Kauf nehmen zu müssen [Bru84,Pit85].

3.4.6.3.4 Ungar generation scavenging

Dieses Verfahren [Ung84] wurde in Hinblick auf Berkeley Smalltalk entwickelt. Man versuchte hier einen einfacher zu implementierenden Algorithmus zu entwickeln, der ebenfalls auf die typische Verteilung der Lebenserwartung einer Zelle eingeht. Jede Zelle wird entweder als neu oder alt klassifiziert. Alte Zellen befinden sich in einem eigenen Gebiet. Alte Zellen, die auf neue Zellen verweisen, gehören einer eigenen Menge (remembered set) an. Falls eine alte Zelle eine Referenz auf eine neue zugewiesen bekommt, wird sie in diese Menge aufgenommen. Zellen aus dieser Menge, die nicht mehr auf neue Zellen zeigen, werden zum Zeitpunkt der Bereinigung (scavenge ) aus dieser Menge herausgenommen. Alle erreichbaren neuen Zellen müssen über dieses remembered set erreichbar sein. Zur Feststellung der Referenzierbarkeit kann man also bei dieser Menge beginnen. Die neuen Zellen selbst werden in drei verschiedene Bereiche unterteilt:

Während der Bereinigung werden die erreichbaren Zellen aus NewSpace und PastSurvivorSpace nach FutureSurvivorSpace kopiert. FutureSurvivorSpace und PastSurvivorSpace werden hierauf miteinander vertauscht. Wenn eine Zelle lang genug als neu markiert war, wird sie in den Bereich der alten Zellen kopiert. Diese Entscheidung wird tenuring (tenure: Besitzdauer) genannt. Die alten Zellen werden sehr selten auf ihre Referenzierbarkeit überprüft. Dadurch ist es möglich, daß etwas länger lebende Zellen als alt anerkannt werden, und dennoch bald nicht mehr benötigt werden.

Die meisten existierenden Smalltalksysteme basieren auf diesem äußerst einfachen Algorithmus. Zur Vermeidung von nichtreferenzierten Zellen im alten Bereich können spezielle Zellen (bitmaps und strings) gesondert behandelt werden. Durch adaptive Varianten kann dieses Verfahren noch wesentlich beschleunigt werden. Abhängig von der Anzahl der überlebenden Zellen werden neue Zellen früher oder später den alten Zellen zugeordnet. Dadurch können längere Pausen fast vollständig vermieden werden. Insgesamt haben allerdings die Analysen von Ungar [Un88] ergeben, daß dieses Verfahren primär für interaktive Anwendungen Verwendung finden sollte.

3.4.6.4 Anwendungen

Kopieralgorithmen haben sich vor allem bei funktionalen und objektorientierten Sprachen bewährt. Untersuchungen für objektbasierte Datenbanken finden sich in [But87]. Der Mechanismus der Vorwärtsreferenzen wird in einigen Lisp-Systemen sogar hardwaremäßig unterstützt. Der Explorer* (trademark of Texas Instruments Inc.) stellt etwa die Konsistenzüberprüfung parallel zum Schreiben zur Verfügung. Wenn in einen alten Bereich geschrieben wird, wird der entsprechende Exception-Handler aufgerufen. Durch eine Unzahl von Heuristiken [Moon84,Cour88] können diese Verfahren noch weiter verbessert werden. [Appel87] diskutiert effiziente Implementierungen innerhalb des Massive Memory Machine-Projektes für Standard-ML. Hier wurde auch gemessen, daß eine Vergrößerung des Hauptspeichers einen überproportionalen Gewinn für die Effizienz der Kopieralgorithmen darstellt. In [Appel89] stellt er eine Implementierungsvariante für konventionelle Architekturen vor.

3.4.7 Zeigerumkehrtechniken

Diese Techniken beruhen auf der Tatsache, daß zur Verschiebung einer Zelle k die nötige Information in den auf sie zeigenden Zellen selbst abgespeichert werden kann. Durch Auffädelung der Zellen auf eine Liste und Rücksetzung nach Verschiebung von k kann man die Position von Zellen beliebig verändern.

3.4.7.1 Auffädelung

Durch Auffädelung (threading) aller auf k zeigenden Referenzen, nämlich
S[i_1] = S[i_2]= ... =S[i_n]=k "Die n Zellen i_1 ... i_n zeigen auf Zelle k"
S[k] = v "Die Zelle k hat den Wert v"
durch Ausführung der folgenden Operation für jedes der n Elemente in beliebiger Reihenfolge,
S[i_j] := S[k], S[k] :=i_j, j = 1 ... n 1)
wird eine Liste ausgehend vom zu verschiebenden Element erzeugt, sodaß die letzte Zelle der Liste den ursprünglichen Wert v der Zelle k erhält, also
S[k] := i_j, S[i_j] := i_k, ..., S[i_l] := v "Kette; die erste der umgekehrten Zellen enthält den ursprünglichen Wert v." (j,k,l, bezeichnen alle Zellen)
gilt.


Auffädelung der Zellen

Nach erfolgreicher Verschiebung der Zelle von k nach k' kann nun nach Übernehmen des Wertes v die Liste bestehend aus den n Zeigern wieder auf k' gerichtet werden. n-mal wird daher ein Element aus der Liste ausgehängt und auf die neue Adresse gesetzt.

t := S[S[k]], S[S[k]] := k', S[k] := t 2)
k', die neue Position der Zelle, wird in den vorgestellten Algorithmen in einem kontinuierlichen Bereich bestimmt, in dem alle zu bewegenden Zellen in gleicher Reihenfolge wie zuvor angelegt werden. Es wäre allerdings auch denkbar eine Freispeicherliste zu verwenden.


nach Auflösung der Liste; die Zeiger sind bereits auf die neue Position der Zelle gerichtet

Fisher[Co81] entwickelte anfänglich einen derartigen Algorithmus allerdings nur für gleichgerichtete Zeiger. Um die folgenden zwar sehr einfachen, aber anfangs nicht leicht verständlichen Algorithmen besser darstellen zu können, werden die Zellen, bei denen angenommen wird, daß sie genau aus einem Zeiger bestehen, durch eine Adjazenzmatrix dargestellt. Ein Eintrag in der i-ten Zeile und k-ten Spalte bedeutet, daß die i-te Zelle einen Zeiger auf die k-te Zelle besitzt. Dadurch ist es sehr einfach, die Menge der Aufwärts- und Abwärtszeiger darzustellen. Die Zellen, die auf sich selbst zeigen, befinden sich auf der Diagonale, Zellen mit Aufwärtszeigern entsprechend oberhalb.


Unterscheidung von Aufwärts und Abwärtszeigern mittels Matrixdarstellung

Eine spezielle Struktur wäre etwa wie folgt dargestellt:


Darstellung der Zeiger durch Pfeile vs. Matrix

Diese Notation hat zudem den Vorteil, nicht nur einen speziellen Fall, sondern die Menge aller möglichen Zeigerkombinationen in einer Zeichnung darstellen zu können. Für den im Folgenden vorgestellten Algorithmus wird in [Mor78] auch ein teilweise ausgeführter Beweis für seine Korrektheit angegeben. Durch die graphische Darstellung kann man informell genau die einzelnen Zusicherungen des Beweises darstellen und "induktiv" zeigen, daß während der einzelnen Phases des Algorithmus die Zusicherungen gelten und das angestrebte Ziel erreicht wird.

3.4.7.2 Morris I

Der ursprüngliche Algorithmus betrachtet eine Menge von Zellen, die genau einen Zeiger enthalten können. Da die Ordnung der einzelnen Zellen untereinander erhalten bleibt, können komplexere Zellstrukturen den gleichen Algorithmus verwenden; jeder Zellteil stellt für den Algorithmus eine eigene Zelle dar. Aufwärts- und Abwärtszeiger werden getrennt in zwei Phasen behandelt. Zuvor müssen sämtliche Zellen bereits markiert worden sein. Durch die Anzahl der markierten Zellen kann bereits der Bereich berechnet werden, in den die kompaktierten Zellen verschoben werden sollen.
Phase I
Die in Leserichtung befindlichen Aufwärtszeiger werden nach 1) aufgefädelt. Alle aufgefädelten Zellen werden gesondert markiert. Falls man auf eine bereits markierte Zelle stößt, hat man alle in Leserichtung befindlichen Zeiger auf diese Zelle hinter sich und kann diese bereits auf den neuen Ort der Zelle richten und den Wert der Zelle wiederherstellen. Diese Zelle kann entweder einen Zeiger in Leserichtung enthalten, dann wird der Zeiger gemäß 1) aufgefädelt, oder aber einen Zeiger gegen die Leserichtung oder auf sich selbst enthalten; in diesem Fall kann die Zelle übergangen werden.


während Phase I in Morris I: Auffädelung der Aufwärtzeiger. Alle Aufwärtszeiger bis zur aktuellen Zelle sind bereits auf die neue Position gesetzt; mittels der bisher besuchten nichtreferenzierten Zellen wird die neue Position berechnet; es gibt keine Zeiger auf nichtmarkierte Zellen (schwarze Balken)

Nach dieser Phase zeigen alle Aufwärtszeiger bereits auf die richtige neue Position.


nach Phase I in Morris I: Alle Aufwärtszeiger sind auf die neue Position gesetzt

Phase II
Es wird in umgekehrter Richtung vorgegangen. Zeiger in Leserichtung werden nun so aufgefädelt, daß auf sie bereits an ihrem zukünftigen Ort verwiesen wird.


während Phase II in Morris I: Auffädelung der Abwärtszeiger; alle Zeiger außer die Abwärtszeiger vor die aktuelle Zelle zeigen bereits auf die neuen Positionen

Nach dieser Phase sind auch sämtliche Aufwärtszeiger richtiggestellt, und man kann die Zellen in einer weiteren Phase kompaktieren.


nach Phase II in Morris I: Alle Zeiger sind auf die neuen Positionen der Zellen gerichtet

Betrachtet man den Ablauf der zweiten Phase, so erkennt man, daß alle Zellen, die bereits besucht worden sind, sowie alle Aufwärtszeiger nicht mehr verändert werden. Lediglich die Abwärtzeiger, die vor die aktuelle Position zeigen, müssen noch verändert werden. Es ist daher naheliegend, das Kopieren der einzelnen Zellen in die Phase II zu falten. Anstatt wie bei Phase I bei der Zeigerumkehrung den momentan gültigen Zeiger auf die Zelle zu verwenden, werden für die Abwärtszeiger ihr neuer Wert, der Zeiger auf die gerade berechnete Zelle verwendet.


nach Phase II bzw. III: die Zellen sind in den unteren Bereich verschoben

Die Zellen werden also alle in zur Phase II entgegengesetzten Richtung kompaktiert.

Morris verbindet direkt die II. Phase mit dem Verschieben der Zellen. Es ist leider unmöglich, Phasen direkt weiter zusammenzufalten. Man beachte jedoch, daß die durch Umkehrung aufgebaute Liste erst zum Zeitpunkt ihrer Auflösung benötigt wird. In der Zwischenzeit können die einzelnen Elemente dieser Liste beliebig mit anderen Werten überschrieben werden, da der Algorithmus zum Einhängen eines Elements nur vom Inhalt der Zelle abhängt, auf die gezeigt wird. Falls bereits Zeiger auf diese Zelle umgekehrt worden sind, steht in dieser Zelle bereits ein umgekehrter Zeiger, der in die neu ankommende Zelle kopiert wird. Die alten aufgefädelten Zeiger sind von dieser Operation nicht betroffen und können daher, wie noch in Kapitel 4.2.4.1 gezeigt werden wird, für andere Zeigerketten verwendet werden.

Unter erleichterten Bedingungen ist es direkt möglich, effizientere Algorithmen zu entwickeln. In einigen Systemen und Programmiersprachen -etwa Snobol- werden komplexere Zellen als die cons-Zellen von Lisp benötigt. Pro Zelle müssen Informationen -etwa über die Größe und den Typ der Zelle, ähnlich auch in Prolog- verwaltet werden, die sicher keine Referenzen enthalten. Unter diesen Umständen bestehen wesentlich mehr Möglichkeiten, den Algorithmus den vorhandenen Strukturen besser anzupassen. Auch fallen die Probleme mit selbstreferenzierenden Zellen weg. Während der Auffädelung der Zellen könnte der freie Bereich etwa zur -teilweisen- Faltung der beiden Phasen verwendet werden. Der nach Morris I von Jonkers veröffentlichte Algorithmus[Jon79] nützt diese Tatsache aus:

3.4.7.3 Jonkers

Die erste Phase läuft ähnlich wie Morris I ab. In der zweiten Phase werden ein weiteres Mal in derselben Leserichtung die Zellen nach umgekehrten Zeigern durchsucht und dann an ihren neuen Ort kopiert. Der Vorteil dieses Algorithmus liegt darin, daß in der zweiten Phase pro Zelle nur der u.U. aufgefädelte Zeiger betrachtet werden muß, während bei Morris I auch in der II. Phase jede einzelne Speicherzelle betrachtet werden muß.

Kompaktierungsalgorithmen werden üblicherweise gemeinsam mit einer vorhergehenden Markierungsphase verwendet. Da es ja offensichtlich unmöglich ist, die beiden letzten Phasen der beschriebenen Algorithmen weiter zu falten, ist es naheliegend, die erste Phase mit der Markierungsphase zu falten. Auf dieser Tatsache beruhen eine Menge von Algorithmen, die im besonderen für Snobol Verwendung finden.

Die einfachste Realisierung dieser Idee wurde von Dewar und McCann [Dew77] -ein Jahr vor Morris I- mit einem Hinweis auf Knuths Lisp 2-Algorithmus entwickelt.

3.4.7.4 Dewar-McCann [Dew77]

Es werden Zellen mit einem zeigerfreien Teil verwaltet, die in einer Leserichtung im Speicher unabhängig von den auf sie zeigenden Zellen erkannt werden können. Auf Teile der Zellen dürfen keine zu verändernden Referenzen existieren. Zeiger im Wertteil der Zelle müssen erkennbar sein. (Bei der Realisierung von arrays in Snobol müssen daher zur array-Zelle relative Adressen verwendet werden.)
Phase I: Markierung und Auffädeln
Beim Durchlaufen des Graphen werden alle Referenzen gemäß 1) aufgefädelt.
Phase II: Zeigerumsetzung
Der gesamte Speicher wird in Leserichtung nach markierten Zellen durchsucht; diese können durch Zeiger -statt des eigentlichen Wertes- erkannt werden. Zum Zeitpunkt des Auffindens einer derartigen Zelle ist bereits die zukünftige Adresse bekannt -die Summe der Größe aller bisher gefundenen Zellen. Mittels 2) werden alle existierenden Referenzen auf die neue Adresse gesetzt. Für die nächste Phase werden, ähnlich wie in Lisp 2, die markierten Zellen durch eine Kette im nicht benötigen Speicher verbunden.
Phase III: Kopieren
Durch die Kette der markierten Zellen werden die Blöcke von Zellen kopiert.

Hanson [Han77] verwendet eine sehr ähnliche Variante, kombiniert mit dem Deutch-Schorr-Waite Algorithmus.

3.4.7.5 Thorelli

Zur gleichen Zeit wurde auch von Thorelli fast der gleiche Algorithmus entwickelt[Thor76]. Neben einer ausführlicheren Beschreibung des Verfahrens, wird auch eine Beweis der Korrekheit des Algorithmus angegeben. Es wird bewiesen, daß die referenzierte Struktur nicht verändert wird, und keine "Löcher" im referenzierten Bereich verbleiben. Im Algorithmus selbst verwendet Thorelli statt der Liste der referenzierten Blöcke ein Markierungsbit. Wenn auch die Algorithmen von Dewar-McCann,Thorelli und Hanson bereits die Markierungsphase für 1) nützen können, müssen sie dennoch zwei weitere Phasen realisieren. Sie benötigen zumindest das Zurücksetzten einiger aufgefädelter Zellen. Da allerdings nicht festgestellt werden kann, ob die betrachteten Zellen bereits bewegt werden können, ist eine weitere Phase für das Bewegen der Zellen erforderlich. Morris schlägt nun, ähnlich wie in seinem ersten Algorithmus Morris I eine Trennung in Aufwärt- und Abwärtzeiger vor. Dadurch werden insgesamt nur mehr zwei Phasen benötigt.

3.4.7.6 Morris II

Unter den Voraussetzungen von Dewar-McCann und einem zusätzlichen Markierungsbit [Mor82].
Phase I Markierung und Auffädeln von Abwärtszeigern.
Alle Abwärtszeiger werden entsprechend aufgefädelt, aber nicht, wie in Morris I wieder zurückgesetzt.


nach der Markierungsphase in Morris II: Alle Abwärtszeiger sind aufgefädelt; eine Zelle kann hier n Zeiger enthalten, entsprechend müßte jeder Eintrag in die Matrix aus n Teilen bestehen

Phase II Auffädeln in Aufwärtsrichtung und Kopieren
In Aufwärtsrichtung werden nun die Zeiger auf die Header der einzelnen Zellen gesetzt. Für die Argumente einer Zelle wird wie in Morris I vorgegangen: Die Aufwärtsreferenzen werden aufgefädelt, während bei den Abwärtsreferenzen nur mehr der Zellteil an seinen neuen Ort kopiert werden muß.


während der Kompaktierungsphase in Morris II : Alle Aufwärtszeiger der Zellen bis zur aktuellen Zelle sind aufgefädelt; die Abwärtszeiger auf Zellen bis zur aktuellen sind bereits auf die neue Position gesetzt 

void mark(int i) {
   int p,j;
   p = S[i];
   if (ispointer(p)) {
	if (!marked[i]) {
	    marked[i] = true;
	    for(j = p + 1; j < p + size(p); j++)
		mark(j);
	)
	if (p < i) {
	    S[i] = S[p];
	    S[p] = i;
	}
   }
}

int i, old, new, t, z;
for(i = 1; i =< r; i++) mb[i] = false;
mark(ex1);...;mark(exn);
old = new = l;
while( old =< r)
   if (marked[old]) {
	while(!isheader(S[old]) {
	    t = S[old]; S[old] = S[t];S[t] = new;
	}
	z = size(old);
	S[new] = S[old];
	for (i = 1; i < z; i++)
	    if(ispointer(S[old+i]) && S[old+i] > old) {
		S[new+i] = S[S[old + i]];
		S[S[old + i]] = new + i;
	    } else S[new + i] = S[old + i];
	new = new + z; old = old + z;
   } else old = old + size(old);
}

3.4.7.7 Vergleich

Man beachte, daß Jonkers, Dewar et al. und Morris II im wesentlichen dieselben Zeigermanipulationen durchführen. Bei Jonkers und Dewar kann in der zweiten Phase auf ein Durchsuchen der Argumente verzichtet werden. Morris II hat zwar gegenüber Dewar et al. nur zwei Phasen, muß aber in beiden Phasen sämtliche Argumente einer Zelle lesen. Je nach Größe der Zellen dürfte daher entweder Morris II -bei kleineren Zellen- ,oder Dewar et al. der Vorzug gegeben werden.

3.4.8 Aufwand

Der traditionelle mark-and-sweep Algorithmus benötigt Zeit proportional zur Anzahl der erreichbaren und unerreichbaren Zellen. Die in den letzten Abschnitten vorgestellten Algorithmen hängen allerdings nur von der Zahl der erreichbaren Zellen ab. Bei den Zeigerumkehrungsalgorithmen kommt zwar ein sehr geringer Faktor abhängig von der Größe des zu bearbeitenden Speichers hinzu, ihre Vorteile liegen jedoch in der Bewahrung der Reihenfolge der Elemente. Beide Klassen von Algorithmen müssen allerdings alle referenzierten Zellen bearbeiten. Diese werden bei der entsprechenden Kompaktierung in einen zusammenhängenden Block gebracht. Durch die Einteilung in Generationen, im allgemeinen durch aging läßt sich auch dieser Aufwand verringern.

In praktischen Anwendungen bei nichtsymbolischen Sprachen kommen verschiedenste Typen von Zellen vor, die sich auch völlig unterschiedlich verhalten. In diesen Fällen zahlt es sich aus, aus mehreren Strategien zusammengesetzte Algorithmen zu verwenden. Boehm [Boe88] verwendet je nach Größe der Zelle andere Verfahren zum Anlegen der Zellen. Nach seinen Erfahrungen kann man auch in herkömmlichen Applikationen stop and collect, bzw. copy-Verfahren verwenden. Nilsen [Nil88] betrachtet eine ähnliche Problemstellung für die Verwaltung von Strings, bei welchen Zeiger auch auf Teile existieren dürfen. Ein Großteil der besprochenen Algorithmen wird auch tatsächlich in der Praxis eingesetzt. Die meisten von ihnen können auch auf traditioneller Hardware respektable Ergebnisse erzielen. Die diversen Kopieralgorithmen werden wie schon bemerkt für Smalltalk und Lisp-Systeme verwendet, die Kompaktierungsalgorithmen werden von Algol68, Lisp, Snobol bis Prolog eingesetzt. Die bestechende Schlichtheit dieser Algorithmen ist sicher auch mit ein Grund, warum diese in kommerziellen Systemen Verwendung finden.