Bei objektorientierten Sprachen zeigt sich normalerweise ein sehr charakteristisches Bild der Lebensdauern der erzeugten Objekte, wie bereits beim Mark and Sweep-Algorithmus aufgeführt. Fast alle Objekte sind sehr kurzlebig und werden bereits kurz nach dem Anlegen nicht mehr benötigt und können wieder freigegeben werden. Einige Objekte sind dafür sehr langlebig, und durchleben meist fast die gesamte Programmdauer. Beispiele sind die interne Darstellung der Programmparameter und initialisierte Konstanten und nicht verwendeten Variablen. Nur wenige Objekte haben eine mittlere Lebensdauern.
Ein Beispiel warum eine zusätzliche Optimierung des allgemeinen Garbage Collectors von Nöten ist, ist recht einfach konstruiert. Man stelle sich eine Schleife mit sehr vielen Iterationen vor, im Schleifenrumpf wird temporär ein Objekt für Berechnungen erzeugt, das am Ende der Iteration nicht mehr verwendet wird. Ein naiver Garbage Collector würde davon erst etwas bei einem Durchlauf mitbekommen, dafür müßten erstmal eine große Anzahl von Objekten mit der Schleife erzeugt werden, bis der Speicher bis zu einem gewissen Grade gefüllt ist. Dann würde der Garbage Collector diese ganzen temporären Objekte wieder aufräumen dürfen nachdem er sämtliche Objekte geprüft hat. Danach kann das ganze Spiel erneut beginnen. Dies scheint etwas zuviel Aufwand, wenn man bedenkt, daß für die gesamte Schleife eigentlich nur Speicher für ein einziges Objekt benötigt wird. Hier ein kleines Beispiel in Java, in der pro Durchlauf zumindest ein String- und ein StringBuffer-Objekt erstellt wird. Dies geschieht hier implizit, bzw. der Compiler erzeugt zum Handhaben der Strings automatisch entsprechende Anweisungen:
for (int i = 0; i < 1000000000; ++i)
System.out.println(" Test: " + i);
Die Lösung ist die Objekte in Generationen einzuteilen. Dafür werden Objekte beim Anlegen erstmal in einen Speicherbereich für neue Objekte erzeugt. Stellt sich nach einiger Zeit heraus (meist einigen Durchläufen des Garbage Collectors), daß sie noch verwendet werden im Gegensatz zu den meisten anderen, werden sie in einen Speicherbereich für langlebige Objekte verschoben.
Wird nun irgendwann Speicher angefordert, und dieser kann nicht in dem Speicherbereich für neue Objekte befriedigt werden, muß erstmal nur ein Durchlauf für diesen Bereich gemacht werden. Er meist relativ klein daher ist der Durchlauf recht schnell. Und da die meisten Objekte kurzlebig sind, wird auch meist genügend Speicher freigegeben um die Anforderung erfolgreich zu bearbeiten. Ist dies nicht der Fall, muß ein kompletter Durchlauf auch mit Prüfung der langlebigen Objekte erfolgen.
Durch das Aufteilen in zwei oder mehrere Speicherbereiche für verschiedene Objekte, kann man auch verschiedene Algorithmen auf sie anwenden. So eignen sich kopierende Garbage Collector bei dem Speicherbereich für neue Objekte gut, da dieser nur die noch lebenden Objekte durchlaufen muß, wovon es dort nicht allzu viele geben sollte. Außerdem ist der Speicherbereich relativ klein, so daß der doppelte Speicherbedarf nicht so auffällt. Da hier auch sehr häufig Speicher angefordert wird, kann dies aufgrund des kompaktierenden Algorithmus auch sehr effizient erledigt werden. Beim Kopieren können hier auch gleich länger lebende Objekte statt dessen in den langlebigen Bereich verschoben werden.
Beim Speicher für langlebige Objekte bietet sich ein markierender Algorithmus an, da hier eh die meisten Objekte noch leben und so nicht alles unnütz unverändert kopiert werden muß. Die kompaktierende Variante bietet sich ebenfalls an, da durch das seltene löschen einmal kompaktierte Anteile meist auch so verbleiben und ein Kopieren ebenfalls entfällt. Der Speicherbereich ist trotzdem kompakt mit der entsprechenden effizienten Bearbeitung von Speicheranforderungen in diesem Bereich. Wenn man sich nun überlegt, wann hier Speicher angefordert wird, ist dies auch sehr wichtig. Der Speicher wird hier genau dann angefordert, wenn Objekte aus dem Bereich der jungen Objekte hierher verschoben werden, also bedeuten effiziente Speicheranforderungen hier schnellere Garbage Collector-Durchläufe über den jungen Bereich.
Während eines Durchlaufs in einer jüngeren Generation, müssen alle Objekte die von Objekten in älteren Generationen referenziert werden ebenfalls als Wurzeln angesehen werden. Da hierbei nicht jedesmal alle alten Objekte nach Referenzen durchsucht werden können, das würde ja den ganzen Sinn der Aufteilung entgegenwirken, muß entsprechend eine Liste aller so referenzierten Objekte verwaltet werden. Solche Referenzen können in zwei Fällen entstehen. Entweder wird ein junges Objekt nach einer Zeit zu einem alten Objekt, in dem Fall kann der Garbage Collector selber das Objekt prüfen und die Liste aktualisiert halten, oder einem alten Objekt wird eine Referenz auf ein junges zugewiesen. In diesem Fall muß jede Zuweisung überwacht werden, dies kann entweder mit Compilerunterstützung geschehen, ähnlich wie bei der Referenzzählung, aber es bietet sich zumindest in innerhalb einer virtuellen Maschine (VM) ablaufenden Programmen an, dies durch die VM machen zu lassen. Dadurch bleibt der erzeugt Code unabhängig vom eingesetzten Garbage Collector, so daß dieser beliebig ausgetauscht werden kann. Funktionale Sprachen bieten hier natürlich Vorteile, da dort keine Werte verändert werden können.
Der Durchlauf eines Garbage Collectors kann bei großen Datenmengen eine längere Zeit beanspruchen und zu Pausen während der Programmausführung führen. Dies ist bei Programmen, die mit dem Benutzer interagierend oder in Realzeit reagieren müssen, nicht hinnehmbar. Die Aufteilung der Speicherbereiche für Objektgenerationen kann diese Pausen schon stark verringern, wünschenswert wäre aber ein Algorithmus der Vorhersagen von halbwegs garantierten maximalen Wartezeiten zuläßt.
Bei inkrementiellen Garbage Collectoren wird bei jeder Speicheranforderung vom anfordernden Thread ein wenig Arbeit für den Garbage Collector erledigt. Das heißt es wird eine Wurzel oder eine bestimmte Anzahl and Objekten an sich geprüft und gefolgt und markiert oder kopiert. Durch diese Aufteilung auf viele kleine Arbeitsschritte, gibt es keine oder nur selten etwas längere Pausen, aber niemals so lange, wie bei einem kompletten Durchlauf. Dies kann auch beispielsweise so umgesetzt sein, daß die Mark-Phase inkrementell abläuft, ist diese abgeschlossen, wird die Sweep- oder Compact-Phase ohne Unterbrechung durchgeführt, die Pausezeit ist dann immer noch deutlich reduziert. Der Durchlauf sollte so optimiert werden, daß er etwa dann abgeschlossen ist, wenn der Speicher voll ist, so daß die Anzahl der Durchläufe minimiert werden kann.
Statt jeweils nur eine bestimmte Anzahl von Objekten zu prüfen, kann auch eine stärkere Aufteilung der Objekte erfolgen. So gibt es dann nicht nur zwei Speicherbereich für junge und alte Objekte, sondern in sehr viele für verschieden alte Versionen. In Suns JVM wird diese Aufteilung in Zügen (trains) und dann wiederum in Waggons (cars) vorgenommen. Jeder einzelne Waggon steht für eine Objekt-Generation und kann einzeln aufgeräumt werden, was sehr kurze Pausen ermöglicht.
Zu beachten gilt allerdings, daß hierdurch zwar die Pausen verkürzt werden, dafür aber die gesamte Bearbeitungszeit zunimmt. Auch werden am Ende eines Durchlaufs dann garantiert nur die Objekte freigegeben, die am Anfang des Durchlaufs nicht mehr verwendet wurden, so kann es also bis zu zwei Durchläufe dauern, bis ein Objekt wirklich freigegeben wird.
Heutige Unternehmensserver und auch vermehrt andere Computersysteme sind mit mehreren Prozessoren ausgestattet. Aber auch auf Systemen mit nur einem Prozessoren kann öfters Nebenläufigkeit genutzt werden, wenn einer der Threads beispielsweise auf externe Geräte, Benutzereingaben oder Netzwerkübertragungen warten muß.
Unter diesen Vorraussetzungen muß der Garbage Collector in der Lage sein, seinen Durchlauf auf mehreren Threads zu verteilen, so daß jeder Prozessor genutz wird. In manchen Fällen wäre es auch bei Einprozessorsystemen interessant den Garbage Collector parallel zum Anwenderprogramm laufen zu lassen um so längere Pause im Anwenderprogramm zu vermeiden. In dem Fall muß er also damit klar kommen, daß das Anwenderprogramm jederzeit neue Objekte anlegen oder Referenzen ändern kann. Und auch hierbei gilt, daß am Ende eines Durchlaufs garantiert nur die Objekte freigegeben werden, die am Anfang des Durchlaufs nicht mehr verwendet wurden.
Mehr dazu auf der nächsten Seite.
Wirklich effizient werden Garbage Collectoren erst durch die Kombination der verschiedenen Algorithmen. Das Aufteilen der Objekte in verschiedene Generationen ist dabei die wichtigste Lösung. Diese Technik ist bereits über 20 Jahre alt und außer dem Aufteilen des Speichers in mehreren einzeln zu säubernde Speicherbereiche ist es so auch möglich für jeden der Bereiche eigens optimierte Algorithmen anzuwenden. Die Länge der Pausen werden ebenfalls verkürzt, da jeder Speicherbereich einzeln gesäubert werden kann.
Welche Kombinationen genutzt werden können und sollten hängt dabei stark von der Umgebung ab. Wenn das Programm in einer virtuellen Maschine abläuft bietet sich an, beim Design dieser VM gleich den Garbage Collector mit einzuplanen.
| Alle Seminare - Inhaltsübersicht - Vorher: Referenzfolgende Garbage Collectoren - Nächstes: Multithreading | Seitenanfang |