mini|Animation einer automatischen Speicherbereinigung. Der Speicherbereich wird mit verschiedenen Objekten (mit Farben dargestellt) gefüllt, von denen einige auch wieder zerstört werden und Lücken im Speicherbereich hinterlassen. Wenn (wie in diesem Beispiel) nicht mehr genug freier Speicherplatz „am Ende“ verfügbar ist oder wenn die automatische Speicherbereinigung entscheidet, wird der Speicher „komprimiert“, wobei alle noch verwendeten Objekte an den Beginn platziert und am Ende alle Speicherlücken konsolidiert werden. Dadurch wird wieder ein großer Speicherbereich für die zukünftige Erstellung von Objekten verfügbar. Die Garbage Collection, kurz GC ( für Müllabfuhr, auch automatische Speicherbereinigung oder Freispeichersammlung genannt) bezeichnet in der Software- und Informationstechnik eine automatische Speicherverwaltung, die zur Vermeidung von Speicherproblemen beiträgt; der Vorteil wird mit einem erhöhten Ressourcenverbrauch erkauft. Unter anderem wird der Speicherbedarf eines Computerprogramms minimiert. Dabei wird zur Laufzeit versucht, nicht länger benötigte Speicherbereiche automatisch zu identifizieren, um diese dann freizugeben. Manche automatischen Speicherbereinigungen führen darüber hinaus die noch verwendeten Speicherbereiche zusammen (Defragmentierung).
Motivation In vielen Softwaresystemen wird benötigter (Arbeits-)Speicher dynamisch (bei Bedarf) reserviert. Wird er nach Abarbeitung eines Programmteils nicht weiter verwendet, so sollte der Speicher wieder freigegeben werden, um eine Wiederverwendung dieser Ressource zu ermöglichen. Bei einer expliziten, manuellen Speicherverwaltung geschieht dies durch Festlegen der Speicherreservierung und -freigabe im Programm durch den Programmierer, ein schnell komplex und damit potenziell fehlerträchtig werdendes Vorgehen. Neben dem Vergessen einer Freigabe, das längerfristig zu Speicherknappheit führen kann, führt das zu frühe Freigeben von (anderswo) noch benötigtem Speicher meist schnell zum Programmabsturz. Vergessene Speicherfreigaben führen oft nicht sofort zu Auffälligkeiten im Programmablauf – zumindest nicht während der typischerweise nur kurzen Programmläufe während der Entwicklung, sondern erst, wenn das fertige Programm vom Endanwender oft über Stunden und Tage ununterbrochen betrieben wird.
Bei manueller Speicherverwaltung ist es oft nicht möglich oder sehr aufwendig, den Speicher zu defragmentieren. Stark fragmentierter Speicher kann dazu führen, dass eine Speicherreservierung des Programms fehlschlägt, da kein ausreichend großer zusammenhängender Bereich verfügbar ist.
Beschreibung Bei der automatischen Speicherbereinigung ist die Idee, diese Aufgabe durch eine Garbage Collector genannte Routine automatisch erledigen zu lassen, ohne Zutun des Programmierers. D. h. das Speichermanagement wird von einer expliziten Festlegung zur Programmerstellungszeit (Compile-Zeit) zu einer dynamischen Analyse des Speicherbedarfs zur Laufzeit des Programms verschoben.
Üblicherweise läuft eine solche automatische Speicherbereinigung im Hintergrund (bzw. nebenläufig) in mehr oder minder regelmäßigen Zeitabständen (z. B. während Pausen im Programmablauf) und wird nicht explizit durch das Programm ausgelöst. GC kann jedoch häufig auch zusätzlich direkt ausgelöst werden, um dem Programm etwas Kontrolle über die Bereinigung zu geben, z. B. in einer Situation von Speichermangel (Out-Of-Memory).
Ansätze Es gibt verschiedene Ansätze, um eine automatische Speicherbereinigung zu implementieren. Gewünschte Anforderungen können ein möglichst geringer Speicherverschnitt, eine maximale Allozierungsgeschwindigkeit, eine Reduktion der Speicherfragmentierung und viele weitere mehr sein, die sich durchaus auch widersprechen und zu Zielkonflikten führen können. D. h. je nach Anwendungsfall kann eine automatische Speicherbereinigung sehr unterschiedlich aussehen und sicher viele Anforderungen erfüllen, manche aber auch nicht.
Typischerweise werden jedoch alle diese Varianten zwei Grundtypen von Speicherbereinigungen zugeordnet: Konservative und nicht-konservative Speicherbereinigung.
Konservative automatische 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. Zur Speicherbereinigung muss sie 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 interne Pointer (also Pointer auf unterschiedliche Teile eines Objektes) erlaubt sind, was eine Implementierung der automatischen Speicherverwaltung erschwert. Beispiele dafür sind die Sprachen C und C++. Hier sei anzumerken, dass dies nicht für die verwalteten Typen in C++/CLI gilt, da dort eigene Referenztypen für die automatische Speicherbereinigung eingeführt wurden, die es nicht erlauben, direkt die Adresse eines Objekts auszulesen.
Nicht-konservative automatische Speicherbereinigung Unter einer nicht-konservativen automatischen Speicherbereinigung (manchmal auch als exakte Speicherbereinigung bezeichnet) versteht man eine, der Metadaten vorliegen, anhand derer sie alle Referenzen innerhalb von Objekten und Stackframes auffinden kann. Bei nicht-konservativer Speicherbereinigung wird zwischen Verfolgung (tracing garbage collectors) und Referenzzählung unterschieden.
Verfolgende Algorithmen 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 (zum Beispiel 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.
mini|GC Generationen in Java HotSpot
Die Anzahl der Generationen wird heuristisch festgelegt (zum Beispiel drei in .NET, zwei für junge Objekte (auch Young-Generation genannt) und einer für alte Objekte (Tenured-Generation) 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 ein modifizierter Stop-And-Copy-Algorithmus angewandt, für die höhere Mark-And-Compact.
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.
Eigenschaften Mit einer Garbage Collection können einige häufig auftretende Programmierfehler, die beim Umgang mit dynamischer Speicherverwaltung oft gemacht werden, ganz oder zumindest teilweise vermieden werden. Besonders zu erwähnen sind hierbei Speicherlecks, die doppelte Freigabe von Ressourcen und die Dereferenzierung von versehentlich zu früh freigegebenen Ressourcen (Hängende Zeiger). Eine Freigabe noch referenzierter Objekte führt zu hängenden Zeigern, welche oft zu Programmabstürzen und undeterministischem Verhalten führen.