Referenzfolgende Garbage Collectoren sehen die Objekte als Knoten in einem Graphen an, verbunden durch gerichtete Kanten, den Referenzen. Der Graph wird nun ausgehend von einer Anzahl von Wurzelreferenzen traversiert. Alle so erreichbaren Objekte werden als noch im Gebrauch befindlich markiert. Alle nicht markierten werden nicht mehr referenziert, können also nicht mehr verwendet werden und müssen gelöscht werden.
Beim Traversieren eines Graphen gibt es die rekursiv arbeitende Tiefensuche und die Breitensuche, die eine Warteschlange verwendet. Der Algorithmus der Tiefensuche sieht so aus, daß jede Wurzelreferenz nacheinander besucht wird. Zeigt die Referenz auf ein Objekt, das bisher noch nicht besucht wurde, wird es bearbeitet. Dies heißt, es wird als besucht markiert und es werden alle Referenzen in dem Objekt ebenfalls besucht. Ein Stück Pseudo-Code dieses Algorithmus folgt:
foreach r in Alle_Wurzelreferenzen do
Besuche(r);
od
procedure Besuche(r: Referenz);
if r <> null and not r.Besucht then
r.Besucht := True;
foreach f in Alle_Felder(r) do
if IstReferenz(f) then
Besuche(f as Referenz);
fi
od
fi
Garbage Collectoren, die markieren und säubern (mark and sweep), arbeiten in diesen zwei Phasen. In der ersten Phase werden alle noch verwendeten Objekte markiert gemäß dem eben vorgestellten Algorithmus, in der zweiten Phase werden alle nicht markierten Objekte freigegeben.
Dies hat seine Vor- und Nachteile. Als erstes muß der Speicherbereich zweimal durchlaufen werden, einmal zum Markieren, einmal zum Säubern. Das Zweite ist ein lineares Durchlaufen des Speicherbereichs, indem jedes momentan belegtes Objekt genau einmal geprüft wird, ob es markiert wurde, und falls nicht der Speicher wieder als frei markiert wird. Durch das Löschen von Objekten und spätere Neuanlegen kann der Speicher fragmentieren, das Defragmentieren (compact) muß in einem Extradurchlauf erfolgen.
Dieser Algorithmus ist ein einfacher Basisalgorithmus und eine logische Schlußfolgerung oder Erweiterung von konventionellen Speichermanagern. Man kann ihn auch als Zwischenschicht verwenden, zwischen dem Anwenderprogramm und einem konventionellem Speichermanager. Diese bieten grundlegend zwei Funktionen an, eine zum Anfordern von Speicher (hier: malloc) und eine zum Freigeben von vorher angeforderten Speicherbereichen (hier: free). Will man nun einen Garbage Collector benutzen, kann man so einen einfachen Mark-and-Sweep-Algorithmus nutzen. Das free wird einfach auf eine Funktion umgeleitet, die nichts tut. Das malloc versucht mit dem zugrunde liegendem malloc Speicher anzufordern, schlägt dies fehl, wird ein Garbage Collector Durchlauf ausgeführt, und danach nochmals versucht den Speicher anzufordern, falls dies fehlschlägt kann das Programm abgebrochen werden. Die Sweep-Phase nutzt nun einfach die zugrundeliegende Funktion free zum Freigeben der Speicherbereiche. Der Garbage Collector benötigt lediglich Zugriff auf alle angeforderten Speicherbereiche, dafür kann er entweder auf Informationen der zugrunde liegenden Speicherverwaltung zurückgreifen oder muß selber eine Liste mit den Adressen und Größen der Speicherbereiche führen. Durch das Nutzen eines Garbage Collectors in Programmen, die für eine herkömmliche Speicherverwaltung ausgelegt sind, kann man auch versuchen Fehler im Programm in Bezug auf den Speicher zu ermitteln.
Bei kopierenden Garbage Collectoren wird direkt beim Durchlaufen der Referenzen jedes Objekt in einen anderen Speicherbereich verschoben. Dies bietet eine Menge Vorteile, birgt aber auch einige Nachteile und bringt zusätzliche Probleme.
Beim Kopieren wird der Speicher in zwei gleichgroße Teile aufgeteilt, einmal die zu prüfenden und kopierenden Objekt und zum anderen der Speicherbereich in dem die referenzierten Objekte kopiert werden sollen. Dafür wird natürlich zumindest kurzzeitig die doppelte Speichermenge benötigt. Dafür ist nach dem Kopieren der Speicher defragmentiert und kompakt an einer Seite des Speichers ausgerichtet, so daß neue Speicheranforderungen sofort nur durch Erhöhen des Freizeigers befriedigt werden können. Der Speicherbereich von dem kopiert wurde, wird außerdem nicht mehr gebraucht und kann komplett in einem Zug freigegen oder als frei betrachtet werden. Dies geschieht im einfachsten Fall einfach durch Vertauschen der zwei Zeiger für den aktuellen Speicherbereich und für den zum reinkopieren.
Auch gibt es bei kopierenden Garbage Collectoren nur einen Durchlauf, der zudem auch nur alle wirklich noch benötigten Objekte anfäßt, wogegen die Markierenden und Säubernden zwei Durchläufe benötigen und dazu beim Zweiten wirklich alle Objekte durchlaufen müssen.
Während des Kopierens muß jedes Objekt komplett gelesen und kopiert werden. Dies ist ein recht hoher Aufwand auch wenn nur die lebenden Objekte kopiert werden. Bei langlebigen großen Objekten kann dies zu einem starken Effizienzverlust führen, den man durch Kombination mit anderen Techniken bekämpfen muß.
Ein anderes Problem ist, daß die Referenzen zu einem kopierten Objekt umgebogen werden müssen, dies läßt sich bei indirekten Referenzen leicht lösen, da dort nur eine einzige Referenz in einer Tabelle geändert werden muß, was aber dafür aber jede Dereferenzierung verlangsamt. Bei direkt referenzierenden Systemen wird meist ein Zeiger an die alte Objektposition gespeichert, die auf das Objekt im neuem Speicherbereich zeigt, auf Dauer hilft aber auch hier nur, daß alle Referenzen geändert werden müssen. Dies kann einen komplett neuen Durchlauf benötigen nach der eigentlichen Garbage Collection. Unter bestimmten Umständen können auch einige Objekt nicht verschoben werden, beispielsweise, wenn sie gesperrt sind für den Zugriff von Modulen in Maschinencode, und grade bei später vorgestellten konservativen Garbage Collectoren is dies ein Problem.
Lokale Speicherzugriffe sind bei heutigen Computersystemen mit ihren verschiedenen Puffern (cache) auf verschiedenen Ebenen äußerst wichtig für die Effizienz des Gesamtsystem. Garbage Collectoren verstoßen leider sehr stark gegen dieses Prinzip, indem sie immer den gesamten Speicherbereich durchsuchen. Während markierende Garbage Collectoren sich immerhin darauf beschränken können, nur die Referenzen zu lesen, müssen Kopierende immer das gesamte Objekt lesen und kopieren. Dafür bieten sie aber durch das Kompaktieren und das Abspeichern in der Reihenfolge, in der sich sich gegenseitig Referenzieren, an, genau dieses Prinzip sicher zu stellen, so daß die normale Programmausführung nach dem Durchlauf dafür schneller erfolgen kann, wie auch der nächste Durchlauf. Der Garbage Collector erhöht damit also die Zugriffslokalität.
Zum äußerst effizientem Anfordern von Speicher bei einem kompaktiertem Speicher ein Pascal-Code-Schnippsel:
var ObjektSpeicher: Pointer = nil;
SpeicherGroesse: Integer = 16 * 1024 * 1024;
FreiSpeicherIndex: Integer = 0;
...
function NewObject(Size: Integer): Integer;
begin
if FreiSpeicherIndex > SpeicherGroesse - Size then
begin
GarbageCollector;
if FreiSpeicherIndex > SpeicherGroesse - Size then
raise OutOfMemoryException.Create;
end;
Result := FreiSpeicherIndex;
FreiSpeicherIndex := FreiSpeicherIndex + Size;
end;
Es gibt einen großen Speicherbereich (ObjektSpeicher), in dem alle Objekte angelegt werden, sowie eine Variable für die Größe dieses Speicherbereichs (SpeicherGroesse). Es gibt weiterhin eine Variable die den Index des ersten freien Bytes im Speicher anzeigt, oder alternativ angibt, wie viele Bytes belegt sind (FreiSpeicherIndex). Wird nun Speicher angefordert, wird die Funktion NewObject mit der Anzahl der benötigten Bytes aufgerufen, die dann einen Index mit der Position des neuen Objekts im Speicherbereich zurückgibt. Soweit die Axiome für dieses Beispiel.
Eine Speicheranforderung sieht nun so aus, daß erstmal eine einfache Abfrage geschieht, ob noch genügend freie Bytes zur Verfügung stehen. Ist dies der Fall, geschieht die gesamte Speicheranforderung in den letzten zwei Zuweisungen, also einfach eine Zuweisung und eine Addition. Es wird der Index des ersten freien Bytes zurückgegeben, an dem sich das neue Objekt nun befinden wird, und danach wird eben dieser Index um die eben belegte Anzahl von Bytes entsprechend erhöht. Die meisten Speicheranforderungen lassen sich so also in sehr wenigen Maschineninstruktionen befrieden, ohne, daß irgendwelche Freispeicherlisten durchsucht werden müssen nach passenden Speicherfragmenten. Falls doch mal nicht genug Speicher vorhanden sein sollte wird entsprechend der Garbage Collector gestartet. Nun sollte genügend Speicher vorhanden sein, ist dies trotzdem nicht der Fall, wird eine Ausnahme ausgelöst, hier kann natürlich auch der gesamte Speicherblock vergrößert werden oder andere Anpassungsmaßnahmen getroffen werden.
Mark and Compact-Garbage Collectoren sind eine Mischung aus den beiden bisher vorgestellten Algorithmen. Er versucht das sinnlose Hin- und Herkopieren von langlebigen Objekten zu verhindern, dazu muß man nun etwas über die Lebensdauer von Objekten wissen.
Untersuchungen haben hgezeigt, daß die Lebensdauern von Objekten sich in objektorientierten Sprachen sehr charakteristisch verhalten. Es gibt einige Objekte, die leben sehr lange, praktisch die gesamte Programmausführung durch. Ein gutes Beispiel dafür sind die Programmparameter, die Zeichenketten werden am Anfang angelegt, unter Umständen einmalig ausgewertet und liegen danach im Speicher ohne jemals wieder angefaßt zu werden bis das Programm durchgelaufen ist. Sehr viele Objekte leben sehr kurz, beispielsweise für Berechnungen oder nur zum Übergeben von Parametern oder Rückgabewerte. Nur wenige Objekte haben dagegen eine mittlere Lebensdauer.
Der Algorithmus arbeitet wieder in zwei Phasen, in der ersten werden wie gehabt alle noch genutzten Objekte markiert. In der zweiten Phase werden dann Lücken im Speicher von freizugebenen Objekten durch noch lebende geschlossen. Am Rand liegende Objekte müssen so nicht mehr kopiert werden, wenn zwischen ihnen und dem Rand keine anderen Objekte mehr freigegeben werden. Langlebige Objekte wandern so zum Rand und müssen nach ein paar Mal nicht mehr unnütz kopiert werden.
Durch die vorhergehende Markierphase gibt es aber wieder zwei Durchläufe, und es müssen alle Objekte mindestens einmal angefaßt werden, also auch zu löschende. Dies kann aber unter Umständen optimaler erfolgen als beim Mark and Sweep Algorithmus, da hier die Lücken nur kurzzeitig auftreten. Das Kopieren wird immerhin auf neue Objekte und solche die nach gelöschten Objekten angefordert wurden beschränkt.
Der Speicherbereich ist also weiterhin kompaktiert mit all dessen Vorteile, aber es wird nur ein Speicherbereich benötigt, nicht zwei, wie beim kopierenden Algorithmus. Die Referenzen müssen allerdings auch weiterhin umgebogen werden.
Garbage Collectoren müssen wissen, wo Referenzen sind, damit sie ihnen folgen können. Bei Systemen, die in einer virtuellen Machine laufen (wie beispielsweise Java) steht normalerweise die Information für jedes Feld zur Verfügung, ob es eine Referenz ist oder ein einfacher Datentyp. In anderen Systemen muß der Garbage Collector von jeder Speicherzelle annehmen, daß es sich dabei um eine Referenz auf einen anderen Speicherbereich handelt, um nicht Speicherbereiche freizugeben, die noch referenziert werden und damit noch genutzt werden können.
Garbage Collectoren die in allen Fällen wissen, ob es eine Referenz ist und demnach genau bestimmen können, ob ein Objekt noch verwendet werden kann, nennt man exakt (exact). Entsprechend nennt man die anderen konservativ (conservative). Aber selbst in Systemen, in denen für jedes Objekt alle Referenzspeicherplätze bekannt sind, kann nicht immer ein exakter Garbage Collector eingesetzt werden. Die offizelle JVM von Sun ist selbst ebenfalls konservativ. Dies liegt daran, daß bei den Wurzelreferenzen nicht klar erkennbar ist, ob es sich um Referenzen handelt oder um andere Werte. Dies betrifft besonders den Stack, auf dem sowohl Referenzen als auch Integer- und Fließkommazahlen gepackt werden können. Falls also einer dieser Werte zufällig der Adresse eines realexistierenden Objektes gleicht, muß angenommen werden, daß es eine Referenz ist, und dementsprechend muß dann der Graph dieser konservativen Wurzel traversiert werden, dies geschieht dafür aber exakt.
Durch solche Pseudo-Referenzen kann es also geschehen, daß Objekte die nicht mehr verwendet werden und nirgends mehr wirklich referenziert werden trotz allem im Speicher gehalten werden müssen. Bei direkt referenzierenden Systemen bedeutet dies auch, daß Objekte nicht im Speicher verschoben werden können, wenn sie durch solche möglichen Referenzen referenziert werden könnten, da diese Referenzen nicht umgebogen werden dürfen für den Falls, daß sie doch keine sind.
Dies schränkt grade bei Sprachen die nicht für Garbage Collectoren ausgelegt sind deren Brauchbarkeit ein. Beispielsweise existiert auch für C++ ein konservativer Garbage Collector. Um dies zumindest teilweise unter Kontrolle zu bringen, werden extra Listen mit Zeigern eingeführt, die nicht als Speicherblöcke zurückgegeben werden dürfen, da sie wahrscheinlich in irgendeiner Nicht-Referenzspeicherstelle als Wert drin steht und fälschlicherweise interpretiert werden würde. Trotz allem kann man leicht Fehler provozieren, z.B. indem man Zeiger nicht in Speicherstellen mit vorgegebener Ausrichtung speichert (meist vier oder acht Byte), so daß gar nicht versucht wird, diesen als Zeiger zu interpretieren.
| Alle Seminare - Inhaltsübersicht - Vorher: Abgrenzung zur Referenzzählung - Nächstes: Modifikationen und Kombinationen | Seitenanfang |