Alle Seminare
- Inhaltsübersicht
- Vorher: Multithreading
- Nächstes: Aussicht und Tips
Übersicht: Praktische Garbage Collectoren
Suns Java Virtual Machine (JVM) (Version 1.4.1) benutzt verschiedene
Algorithmen und Kombinationen von Garbage Collectoren. Welche
genutzt werden und mit welchen Parametern ist einstellbar. Es wird
immer eine Aufteilung der Objekte in junge und alte Generationen
vorgenommen, falls die Garbage Collection inkrementell durchgeführt
werden soll, geschieht eine weitere Aufteilung (in trains und
cars). Für jeden Bereich können dann verschiedene
Algorithmen eingesetzt werden, je nachdem, ob die JVM nur auf einen
oder mehreren Prozessoren läuft.
Um Referenzen in alten Objekte auf neue Objekte zu erkennen, wenn sie
zugewiesen werden benutzt die JVM einen Algorithmus, der für jede
Referenzzuweisung einen extra Aufwand bedeutet. Alle Objekte
liegen in Karten (cards) innerhalb des Speichers, wird nun eine
Referenz in einem Objekt geändert, wird ein Bit zu der zugehörigen
Karte gesetzt. Beim Gabage Collector Durchlauf werden als erstes alle
so markierten Karten älterer Generationen geprüft und alle Referenzen
auf die jüngeren Objekte als Wurzelreferenzen verwendet, so daß sie
nicht gelöscht werden. Alternativ könnte man auch die meist vorhandene
Verwaltung des virtuellen Speichers nutzen, um die Referenzveränderungen
effizienter überwachen zu können.
IBMs Java Virtual Machine (Version 1.3.1) benutzt einen Mark and Sweep
Garbage Collector. Nach dem Durchlauf kann ein
Kompaktierung erfolgen. Dies kann per Einstellung gefordert oder
unterbunden werden, der Garbage Collector entscheidet ansonsten von
alleine, ob sie durchgeführt wird. Um die Anzahl der nötigen
Durchläufe zu verringern, wird außerdem ein Speicherbereich ständig
frei gehalten (wilderness preservation), so daß Speicheranfragen
meistens direkt befriedigt werden können wenn sich ein Garbage
Collector Durchlauf nicht lohnen würde.
Funktionale Sprachen bieten einige spezielle Vorteile bei Benutzung eines
Garbage Collectors. In Funktionalen Sprachen sind alle Objekte
unveränderlich (immutable), dies bedeutet, daß Referenzen innerhalb von
Objekten niemals umgebogen werden können um ein anderes Objekte zu
referenzieren. Dadurch hat ein Garbage Collector eine deutlichere Trennung
zwischen alten und jungen Objekten und braucht keine Veränderungen der
Referenzen zu überwachen.
Entsprechend den vielen verfügbaren Algorithmen für Garbage Collectoren,
muß eine möglichst effiziente Kombination für ein gegebenes Programm oder
Umgebung ausgesucht werden. Wie so oft ist nicht jeder Algorithmus ist für
jeden Anwendungsfall optimal. Bei der Bewertung kann man folgende
Kriterien zu Rate ziehen:
- Pausezeiten:
Stoppt der Garbage Collector die gesamte Ausführung der
Anwenderprogramme und für wie lange? Ist es möglich eine Obergrenze für
die Pausezeit zu definieren?
- Pausevorhersagbarkeit:
Können die Pausen so eingelegt werden, wie es für das Anwenderprogramm
am Besten wäre, anstatt sich zufällig nach dem Garbage Collector zu
richten.
- Prozessorauslastung:
Wieviel Prozent der Leistung wird für den Garbage Collector
benötigt? Untersuchungen in dern 70er und 80ern ergaben bei größeren
Lisp-Prgorammen Werte zwischen 25%-40% nur für den Garbage Collector.
Bei modernen Algorithmen sollten die Werte deutlich niedriger
liegen.
- Speicherbedarf:
Manche Algorithmen benötigen extra Speicher. Kopierende Garbage
Collectoren benötigen beispielsweise zumindest zeitweise den doppelten
Speicher während des Kopierens. Dazu kommen häufig verschiedene
Verwaltungsinformationen, die es aber auch bei der konventionellen
Speicherverwaltung gibt. Dadurch kann der Speicherbedarf des
Programms ansteigen. Durch Kompaktieren/Defragmentieren kann dieser
jedoch auch wieder gesenkt werden.
- Interaktion mit Virtuellem Speicher:
In Systemen mit unzureichendem Hauptspeicher wird der virtuelle Speicher
auf der Festplatte ausgelagert. Während eines Durchlaufs des Garbage
Collectors müssen die Objekte angefaßt und überprüft werden, das
erforderliche Ein- und Auslagern sollte möglichst minimiert werden. Das
heißt einerseits, daß keine unnötigen Zugriffe erfolgen (z.B. auf zu
löschende Objekte), anderseits die Zugriffslokalität möglichst hoch
ist.
- Interaktion mit Puffern:
Selbst wenn noch kein Speicher auf die Fesplatte ausgelagert werden
muß, so kann ein Durchlauf doch dazu führen, daß Benutzerdaten in den
verschiedenen Puffern (Caches) ersetzt werden, dies kann die Effizenz
des Anwenderprogramms verringern.
- Zugriffslokalität:
Garbage Collectoren können während des Säubern des Speichers diesen auch
gleich für den Zugriff optimieren und die Lokalität von zusammengehörigen
Daten erhöhen, so daß diese möglichst auf der selben Seite des virtuellen
Speichers liegen und so ein Zugriff von einem Objekt zu einem
referenziertem Objekt direkt aus den verschiedenen Puffern erfolgen kann.
Dies optimiert nicht nur das Anwenderprogramm, sondern auch den nächsten
Durchlauf. Kopierende und Kompaktierende Garbage Collectoren verschieben
Objekte und können diese Optimierung gut dabei erledigen.
- Compilerunterstützungs- and Laufzeitbedarf:
Einige Algorithmen benötigen eine Unterstützung durch den Compiler,
beispielsweise zum Erzeugen von zusätzlichen Befehlen zum Erhöhen und
Verringern von Referenzzählern. Dies verlangt nicht nur zusätzliche
Arbeit vom Compiler, sondern auch Leistung zur Laufzeit, um diese Befehle
auszuführen. Dies verringert vielleicht nicht nur direkt die Effizienz des
Programms durch zusätzliche Befehle, sondern verhindert unter Umständen
auch die Optimierung der erzeugten Befehlsfolge durch den Compiler.