- Garbage collection
-
Garbage Collection (GC, auch Automatische Speicherbereinigung oder Freispeichersammlung) ist ein Fachbegriff aus der Softwaretechnik. Er steht für ein Verfahren zur regelmäßigen automatischen Wiederverfügbarmachung von nicht mehr benötigtem Speicher und anderen Betriebsmitteln, indem nicht mehr erreichbare Objekte im Speicher automatisch freigegeben werden. Das Wort Garbage-Collection kommt aus dem Englischen und heißt wörtlich übersetzt Müllabfuhr.
Inhaltsverzeichnis
Funktionsweise
In vielen Softwaresystemen wird Speicherplatz bei Bedarf reserviert, um die Angaben zu einem Datenobjekt zu speichern. Wird nach Abarbeitung eines Programmteils das Objekt nicht mehr verwendet, so sollte der Platz für das Objekt auch wieder verfügbar gemacht werden. Diese Aufgabe erledigt eine Garbage-Collector genannte Routine automatisch, ohne dass dies explizit im Programm kodiert sein müsste. Darüber hinaus kann die automatische Speicherbereinigung in der Regel auch zu jedem Zeitpunkt in einem laufenden Programm aufgerufen werden.
Konsequenzen
Als Folge des Satzes von Rice kann die automatische Speicherbereinigung im allgemeinen Fall durch Bildung eines Speicherlecks versagen, da nicht festgestellt werden kann, ob gewisse noch referenzierte Objekte jemals wieder benutzt werden. Auch systemnahe Programmierung unter Umgehung des Laufzeitsystems kann zu einem solchen Versagen führen.
Eine automatische Speicherbereinigung kann Programme auch beschleunigen, wenn nämlich die Speicherverwaltung des Systems durch Defragmentierung entlastet wird.
Einige Programmierfehler können durch Garbage Collection seltener auftreten oder ganz vermieden werden:
- Speicherleck
- Doppelte Freigabe von Ressourcen
- Dereferenzierung von versehentlich zu früh freigegebenen Ressourcen (Hängende Zeiger)
Die Analyse und Freigabe von 10 Millionen Zeigern dauert auf modernen Rechenmaschinen mit effizienten Laufzeitsystemen nur Bruchteile einer Sekunde. Ein Nachteil, den einige Algorithmen der automatischen Speicherbereinigung mit sich bringen können, ist, dass der Zeitpunkt ihrer Durchführung unter Umständen nicht vorherzusehen ist. So ist es in Echtzeitsystemen wie zum Beispiel Eingebetteten Systemen nicht hinnehmbar, wenn die Programmausführung zu nicht voraussehbaren Zeitpunkten durch die Ausführung der automatischen Speicherbereinigung unterbrochen wird, so dass die Speicherbereinigung zum Beispiel preemptiv (z. B. im Leerlaufprozess) und inkrementell implementiert werden muss. Einfache inkrementelle Verfahren arbeiten z. B. mit der sogenannten Dreifarb-Markierung.
Verbreitung
Einige ältere (APL, LISP, BASIC) und viele moderne Programmiersprachen verfügen über eine integrierte automatische Speicherbereinigung.
Für Programmiersprachen wie C, bei denen die Programmierer die Speicherverwaltung „von Hand“ erledigen müssen, gibt es teilweise Bibliotheken, die eine automatische Speicherbereinigung zur Verfügung stellen, was bei der Programmierung aber leicht umgangen werden kann, beziehungsweise bei systemnaher Programmierung sogar umgangen werden muss. Aus diesem Grund werden in modernen Entwicklungsumgebungen systemnah programmierte Module von der automatischen Speicherbereinigung ausgenommen, indem sie explizit gekennzeichnet werden (zum Beispiel in C# mit der Option /unsafe oder in Component Pascal mit der obligatorischen Anweisung IMPORT SYSTEM).
Weitere Beispiele für Programmiersprachen mit einer automatischen Speicherverwaltung sind Haskell, Java, Oberon, OCaml, Perl, Visual Objects, ABAP und Objective-C (ab Version 2.0) sowie alle Sprachen, die für die Common Language Runtime von .NET entwickelt wurden (zum Beispiel C# oder VB.NET).
Algorithmen
Es gibt verschiedene Speicherbereinigungsalgorithmen, einige davon bekämpfen auch das Problem der Speicherfragmentierung.
Mark-and-Sweep-Algorithmus
Bei diesem Verfahren der Speicherbereinigung wird von bekanntermaßen noch benutzten Objekten ausgehend allen Verweisen auf andere Objekte gefolgt. Jedes so erreichte Objekt wird markiert. Anschließend werden alle nicht markierten Objekte zur Wiederverwendung freigegeben.
Die Freigabe kann zur Speicherfragmentierung führen. Das Problem ist hierbei jedoch etwas geringer als bei manueller Speicherverwaltung. Während bei manueller Speicherverwaltung die Deallozierung immer sofort erfolgt, werden bei Mark-and-Sweep fast immer mehrere Objekte auf einmal beseitigt, wodurch größere zusammenhängende Speicherbereiche frei werden können.
Mark-and-Compact-Algorithmus
Der Mark-and-Compact-Algorithmus benutzt ebenso wie Mark-and-Sweep das Prinzip der Erreichbarkeit in Graphen, um noch referenzierte Objekte zu erkennen. Diese kopiert er an eine andere Stelle im Speicher. Der ganze Bereich, aus dem die noch referenzierten (man spricht hier auch von „lebenden“) Objekte herauskopiert wurden, wird nun als freier Speicherbereich betrachtet.
Nachteil dieser Methode ist das Verschieben der „lebenden“ Objekte selber, denn Zeiger auf diese werden ungültig und müssen angepasst werden. Hierzu gibt es grundsätzlich wenigstens zwei Verfahren:
- Jedes Objekt wird über zwei Indirektionen (Umleitungen) angesprochen (über einen Zeiger auf einen Zeiger auf das Objekt), so dass beim Verschieben nur noch der Zeiger, der direkt auf das Objekt zeigt, angepasst werden muss.
- Alle Referenzen verweisen direkt auf das Objekt, um aufwändige Dereferenzierungen zu vermeiden, und werden nach einer Verschiebung geeignet angepasst.
Das Verschieben der Objekte hat allerdings den Vorteil, dass jene, die die Bereinigung „überlebt“ haben, nun alle kompaktiert zusammenliegen und der Speicher damit praktisch defragmentiert ist. Auch ist es möglich, sehr schnell zu allozieren, weil freier Speicherplatz nicht aufwändig gesucht wird. Anschaulich: Werden die referenzierten Objekte an den „Anfang“ des Speichers verschoben, kann neuer Speicher einfach am „Ende“, hinter dem letzten lebenden Objekt, alloziert werden. Das Allozieren funktioniert damit vergleichsweise einfach, ähnlich wie beim Stack.
Generationell
Generationelle GCs verkürzen die Laufzeit der Speicherfreigabe. Dazu wird die Situation ausgenutzt, dass in der Praxis die Lebensdauer von Objekten meist sehr unterschiedlich ist: Auf der einen Seite existieren Objekte, die die gesamte Laufzeit der Applikation überleben. Auf der anderen Seite gibt es eine große Menge von Objekten, die nur temporär für die Durchführung einer einzelnen Aufgabe benötigt werden. Der Speicher wird bei generationellen GCs in mehrere Teilbereiche (Generationen) aufgeteilt. Die Langlebigkeit wird durch einen Zähler quantifiziert, welcher bei jeder Garbage-Collection inkrementiert wird. Mit jeder Anwendung des Freigabe-Algorithmus (z. B. Mark-and-Compact oder Stop-And-Copy) werden langlebige Objekte in eine höhere Generation verschoben. Der Vorteil liegt darin, dass die Speicherbereinigung für niedrige Generationen häufiger und schneller durchgeführt werden kann, da nur ein Teil der Objekte verschoben und deren Zeiger verändert werden müssen. Höhere Generationen enthalten mit hoher Wahrscheinlichkeit nur lebende (bzw. sehr wenige tote) Objekte und müssen deshalb seltener bereinigt werden.
Die Anzahl der Generationen wird heuristisch festgelegt (z. B. 3 in .NET, 2 in der Java-VM von Sun). Zudem können für jede Generation unterschiedliche Algorithmen verwendet werden. In Java beispielsweise wird für die niedrigste Generation (auch Young-Generation genannt) ein modifizierter Stop-And-Copy-Algorithmus angewandt, für die höhere (Tenured-Generation) Mark-And-Compact.
Referenzzählung
Siehe auch Hauptartikel: Referenzzählung
Bei diesem Verfahren führt jedes Objekt einen Zähler mit der Anzahl aller Referenzen, die auf dieses Objekt zeigen. Fällt der Referenzzähler eines Objektes auf null, so kann es freigegeben werden.
Ein besonderes Problem der Freispeichersammlung mit Referenzzählung liegt in so genannten zyklischen Referenzen, bei denen Objekte Referenzen aufeinander halten, aber sonst von keinem Konsumenten im System mehr verwendet werden. Nehmen wir beispielsweise an, Objekt A halte eine Referenz auf Objekt B und umgekehrt, während der Rest des Systems ihre Dienste nicht mehr benötigt. Somit verweisen beide Objekte gegenseitig (zyklisch) aufeinander, weshalb die automatische Speicherbereinigung nicht ohne weiteres erkennen kann, dass sie nicht mehr benutzt werden. Die Folge hiervon ist, dass der Speicher somit für die Dauer der Programmausführung belegt bleibt. Es gibt unterschiedliche Algorithmen, die solche Situationen erkennen und auflösen können, zumeist nach dem Prinzip der Erreichbarkeit in Graphen.
Konservative und nicht-konservative Speicherbereinigung
Unter einer konservativen automatischen Speicherbereinigung versteht man eine, die nicht zuverlässig alle nicht-referenzierten Objekte erkennen kann. Diese hat meistens keine Informationen darüber, wo sich im Speicher Referenzen auf andere Objekte befinden.
Während einem nicht-konservativen Kollektor (manchmal auch als „exakter Kollektor“ bezeichnet) Metadaten vorliegen, anhand derer er alle Referenzen innerhalb von Objekten und Stackframes auffinden kann, muss ein konservativer den Speicher auf mögliche Referenzen durchsuchen. Jede Bitfolge, die eine gültige Referenz in den Speicher sein könnte, wird als Referenz angenommen. Es kann dabei nicht festgestellt werden, ob es sich dabei nicht doch um ein Zufallsmuster handelt. Daher erkennen konservative Kollektoren gelegentlich Objekte als referenziert, obwohl sie es eigentlich nicht sind. Da eine automatische Speicherbereinigung niemals Objekte entfernen darf, die noch gebraucht werden könnten, muss sie konservativ annehmen, dass es sich bei der erkannten Bitfolge um eine Referenz handelt.
Insbesondere wenn eine automatische Speicherbereinigung auch dringlichere Ressourcen als Speicher freigeben muss (siehe Finalisierung), kann ein konservativer Kollektor ein Risiko darstellen. Im Allgemeinen findet man konservative GCs dort, wo eine Implementierung der automatischen Speicherverwaltung schwierig ist, zum Beispiel für die Sprachen C++ und C. (Anmerkung: Dies gilt nicht für die „verwalteten Typen“ in C++/CLI, da dort eigene Referenztypen für die automatische Speicherbereinigung eingeführt wurden, die es nicht erlauben, direkt die Adresse eines Objekts auszulesen.)
Finalisierung
Die in vielen Systemen verbreitete Technik, Objekte mit Hilfe der automatischen Speicherbereinigung zu deinitialisieren, bezeichnet man auch als Finalisierung. Beispielsweise verfügen Objekte in der Programmiersprache Java über eine spezielle Methode namens finalize, die für eben diese Zwecke verwendet wird.
Dieses Verfahren, also Objekt-Deinitialisierungen von der automatischen Speicherbereinigung erledigen zu lassen, wird mittlerweile als Design-Fehler betrachtet und in neueren Architekturen vermieden.
Probleme, die sich durch Finalisierung ergeben, sind:
- Objekte, die eine Finalisierung benötigen, haben eine längere Lebensdauer als andere. Diese Lebensdauer kann sogar deutlich über der von Objekten ohne Finalisierung liegen. (Das Objekt kann erst nach seiner Finalisierung freigegeben werden.) Werden knappe Ressourcen damit verwaltet, dann kann dies zu blockierenden Zuständen innerhalb des Programmablaufs führen.
- Finalisierung erzeugt zusätzliche Rechenlast für die automatische Speicherbereinigung.
- Es gibt keine definierte Finalisierungsreihenfolge. Daher kann es geschehen, dass während der Finalisierung auf andere Objekte zugegriffen wird, die ebenfalls der Finalisierung unterworfen sind, zu diesem Zeitpunkt aber überhaupt nicht mehr existieren.
- Es gibt je nach Implementierung (z. B. in der Programmiersprache Java) keine Garantie dafür, dass die Finalisierungsroutine von der automatischen Speicherbereinigung überhaupt aufgerufen wird.
Aus diesen Gründen versucht man neuerdings, komplett auf Finalisierung zu verzichten. Die Verwaltung anderer Betriebsmittel als Speicher hält man von der automatischen Speicherbereinigung fern. Der automatischen Speicherbereinigung fällt dann also ausschließlich die Aufgabe der Speicherverwaltung zu.
Fragmentierung
Traditionelle Speicherverwaltungen neigen im Laufe der Zeit zur Fragmentierung. Verursacht wird dieses Problem durch die unterschiedliche Lebenszeit von Objekten. Die Speicherverwaltung führt Buch darüber, welche Stellen „freien Speicher“ repräsentieren, also alloziert werden können und welche bereits von Objekten belegt sind. Durch das explizite Freigeben von Speicherstellen entstehen Lücken, die nicht immer sofort wieder aufgefüllt werden können. Wenn neue Objekte größer sind als die freigewordenen Lücken, muss an anderer Stelle ein nicht allozierter Bereich gesucht werden.
Probleme, die bei Fragmentierung auftreten können:
- Es bleibt ein gewisser Teil des zur Verfügung stehenden Speichers ungenutzt.
- Das Allozieren von Speicher dauert länger, wenn die Datenstrukturen, über die der Heap verwaltet wird, komplexer werden. Das Suchen nach einer freien Speicherstelle von passender Größe gestaltet sich aufwändiger.
- Es kommt immer wieder vor, dass nacheinander allozierte Objekte nicht nebeneinander im Speicher stehen (man spricht hierbei von schlechter Speicherlokalität). Untersuchungen haben gezeigt, dass nacheinander erzeugte Objekte oft gleichzeitig für eine bestimmte Operation gebraucht werden. Wenn sie nicht nahe genug beieinander liegen, werden Zugriffe anstatt auf den schnellen Cache-Speicher auf den dahinterliegenden, langsameren Speicher umgeleitet, was den Zugriff stark bremsen kann.
Durch kompaktierende Algorithmen kann eine Fragmentierung jedoch komplett vermieden werden. Siehe dazu Mark and Compact. Dies führt zwar zu einer längeren Verzögerung beim Freigeben von Speicher, reduziert allerdings die Allozierungsdauer. Um die Speicherfreigabe möglichst kurz zu halten, wird darauf geachtet, möglichst selten große Speicherbereiche aufzuräumen. Deshalb werden diese Algorithmen bevorzugt in Kombination mit generationellen Verfahren eingesetzt.
Siehe auch
Speicherverwaltung, Destruktor
Literatur
- Richard Jones, Rafael Lins: Garbage Collection. John Wiley and Sons Ltd, 30. April 1996, ISBN 0-471-94148-4
Weblinks
Wikimedia Foundation.
