Dieser Artikel bietet eine Einführung in das Thema Garbage Collection und einen Überblick darüber, wie diese in populären Programmiersprachen wie Java und Python implementiert ist.

Bevor wir in die Details abtauchen, gilt es jedoch zunächst, die Vor- und Nachteile der Garbage Collection selbst zu betrachten: Wie hat sie sich zu einer so gängigen Lösung für Fehler bei der Speicherzuweisung entwickelt? Um das zu klären, werfen wir zunächst einen Blick auf die Speicherverwaltungsprobleme, die in Sprachen wie C oder C++ drohen, die keine Garbage Collection verwenden.

Memory Management ohne Garbage Collection

Memory-Allocation-Probleme bilden nur eine Teilmenge der bei C/C++ üblichen Probleme, die potenziell Fehler und Schwachstellen verursachen - allerdings eine große und sehr lästige. Letzteres bezieht sich insbesondere darauf, diese Fehler aufzuspüren und zu beheben. Speicherzuweisungsfehler können zum Beispiel in folgenden Szenarien auftreten:

• Wenn Sie versäumen, zugewiesenen Speicher freizugeben (das kann Arbeitsspeicher fressen und nicht nur das Programm, sondern das gesamte System zum Absturz bringen).

• Wenn Sie versuchen, einen Puffer über einen Pointer zu lesen oder zu schreiben, nachdem der Speicher freigegeben wurde (was zu zufälligen Ergebnissen führt, auch bekannt als "Dangling Pointer")

• Wenn Sie einen Speicherblock doppelt freigeben (das kann Speichermanager, Programm oder auch System zum Absturz bringen).

Andere gängige C/C++-Schwachstellen sind Buffer Overruns oder String Manipulation. In beiden Fällen kann es dazu kommen, dass Code mit Daten überschrieben wird. Der "Spaß" beginnt allerdings erst dann so richtig, wenn es einem Angreifer gelingt, bösartigen Code einzuschleusen und auszuführen.

Das ist - trotz getrennter Code- und Datensegmente im geschützten Modus - unter bestimmten Umständen immer noch möglich. Zum Beispiel, wenn ein Programm ein SQL-Statement in einem String konstruiert und dann zur Ausführung an eine Datenbank schickt, was nicht selten zu einer SQL-Injection-Schwachstelle führt. Natürlich gibt es gut dokumentierte Best Practices, um das zu vermeiden. Angesichts immer neu auftauchender Schwachstellen scheint es mit deren Befolgung allerdings nicht sonderlich weit her zu sein.

Wie Garbage Collection hilft

Die größten Probleme bei der Zuweisung und Freigabe von Speicher lassen sich mit der Garbage Collection (GC) beseitigen. Das hat jedoch seinen Preis. Vor allem in Form von:

• Garbage-Collector-Overheads,

• unvorhersehbarer Verzögerungen, und

• weiteren Verzögerungen, wenn ein Serverprozess ins Stocken gerät (betrifft insbesondere Java-basierte Serverprogramme).

Der Overhead der Garbage Collection kann beträchtlich sein und stellt einen Kompromiss zwischen Memory und Performance dar. In einem Forschungspapier (PDF) von Matthew Hertz und Emery D. Berger aus dem Jahr 2005 heißt es dazu:

Appel-Style Generational Collectors sind konservative Garbage Collectors. Aggressivere GCs können manchmal mit weniger Speicher besser abschneiden.

Stalls und Verzögerungen bedeuten, dass GC-basierte Sprachen für Echtzeitprogramme und Server mit hohem Durchsatz, bei denen Verzögerungen minimiert werden müssen, suboptimal sein können. So gab es zum Beispiel mehrere Versuche mit Echtzeit-Lisp und Echtzeit-Java, die alle den Garbage Collector modifiziert oder abgeschafft haben. Kürzlich wurden mehrere Java- und Scala-Server in Nicht-GC-Sprachen neu geschrieben, etwa:

• Scylla, eine Neufassung von Cassandra in C++, und

• Redpanda, ein Kafka-Plug-in-Ersatz, der hauptsächlich in C++ geschrieben wurde.

Sowohl bei Scylla als auch bei Redpanda hat sich die Verzögerung im Vergleich zu den ursprünglichen Servern drastisch verringert. Beide benötigen außerdem viel kleinere Cluster für dieselbe Last.

Algorithmen für die Garbage Collection

Es gibt Dutzende von Algorithmen für die Garbage Collection. Im Folgenden werfen wir einen Blick auf einige der wichtigsten und ihre Merkmale.

Reference Counting

Beim Reference Counting speichert das Programm die Anzahl der Referenzen, Pointer oder Handles auf eine Ressource (als Teil der zugewiesenen Ressource) und erhöht oder verringert diese entsprechend, wenn Referenzen hinzugefügt oder entfernt werden. Wenn der Referenzzähler Null erreicht, kann die Ressource freigegeben werden. Memory Garbage Collection ist nur eine Applikation des Reference Counting - sie kommt unter anderem auch für die Freigabekontrolle von Systemobjekten, Windows-COM-Objekten und Dateisystemblöcken oder -dateien verwendet.

Reference Counting birgt zwei große Nachteile, nämlich:

• übermäßig häufige Aktualisierungen und

• zirkuläre Referenzen.

Eine Möglichkeit, die Frequenz der Aktualisierungen zu kontrollieren, besteht darin, dem Compiler eine Batch-Verarbeitung verwandter Objekte zu ermöglichen. Zirkuläre Referenzen - die verhindern, dass eine Zählung Null erreicht - lassen sich hingegen mit Hilfe einer gelegentlichen Tracing Garbabe Collection umgehen.

Tracing Garbage Collection

Tracing GC ist die wesentliche Alternative zum Reference Counting und umfasst alle folgenden Algorithmen - sowie noch einige mehr. Die allgemeine Idee der Tracing-Garbage-Collection: Der Prozess beginnt mit einigen Stammobjekten (wie den aktuellen lokalen und globalen Variablen sowie Funktionsparametern) und folgt den Referenzen, um festzustellen, welche Objekte erreichbar sind. Alle nicht erreichbaren Objekte fließen dann in die Garbage Collection.

Tracing Garbage Collection ist inzwischen so gängig, dass sie manchmal schlicht als Garbage Collection bezeichnet wird.

Mark and Sweep

Der Mark-and-Sweep-Algorithmus wurde ursprünglich im Jahr 1960 veröffentlicht und geht auf John McCarthy und Lisp (PDF) zurück. Das Konzept: Zunächst wird das System "eingefroren" und dann alle über Root erreichbaren Objekte als "in-use" markiert. Im nächsten Schritt wird der gesamte Speicher nach unmarkierten Blöcken durchsucht und diese freigegeben. Schließlich wird das "In-Use"-Bit in allen verbleibenden Speicherblöcken gelöscht, um die nächste Collection vorzubereiten - und das System kann fortfahren. Für Echtzeitsysteme ist dieser Ansatz folglich ungeeignet:

CC0, Link

Eine Mark-and-Sweep-Variante nutzt drei "Colors" of Memory:

• weiße Blöcke sind unerreichbar und müssen freigegeben werden, wenn sie sich am Ende des Algorithmus noch in der weißen Menge befinden;

• schwarze Blöcke sind über Root erreichbar und referenzieren nicht auf Objekte der weißen Menge;

• graue Blöcke sind über Root erreichbar, müssen aber noch nach Referenzen auf weiße Objekte durchsucht werden.

Nach Abschluss des Algorithmus landen die grauen Blöcke alle in der schwarzen Menge. In der Regel werden bei der ersten Markierung alle Blöcke, auf die die Roots verweisen, in die graue und alle anderen Blöcke in die weiße Menge eingeordnet.

Der Algorithmus der dreifarbigen Mark-and-Sweep-Variante besteht aus drei Schritten:

1. Wählen Sie ein Objekt aus der grauen Menge und verschieben Sie es in die schwarze Menge.

2. Verschieben Sie jedes weiße Objekt, auf das erstgenanntes Objekt verweist, in die graue Menge. Auf diese Weise stellen Sie sicher, dass weder dieses Objekt noch die Objekte, auf die es verweist, in der Garbage Collection landen können.

3. Wiederholen Sie die letzten beiden Schritte, bis die graue Menge erschöpft ist.

CC BY-SA 4.0, Link

Gibt es keine grauen Objekte mehr, können alle weißen Blöcke freigegeben werden. Der dreifarbige Algorithmus kann im Hintergrund ausgeführt werden. Dabei entsteht zwar immer noch Overhead - aber immerhin steht die Welt steht nicht still.

Copying Collection

Die wesentliche Idee von Copying Collection (auch als "Semi-Space-Garbage-Collection" (PDF) bekannt), besteht darin, den Speicher in zwei gleich große Bereiche zu unterteilen:

• den "from-space" und

• den "to-space".

Im "to-space" werden nacheinander Blöcke zugewiesen, bis er voll ist - dann eine Collection durchgeführt. Dadurch werden die Rollen der Regionen vertauscht und die lebenden Objekte aus dem from-space in den to-space kopiert, wobei am Ende des to-space ein Block mit freiem Speicherplatz verbleibt (der dem von allen unerreichbaren Objekten belegten Speicher entspricht).

Bei Copying Collection gibt es Komplikationen: Die größte Schwierigkeit besteht darin, dass sich beim Kopieren von Blöcken deren Adresse ändert. Eine Lösung dafür wäre es, eine Tabelle mit Weiterleitungsadressen zu führen. Ein noch größeres Problem: Im Vergleich zu Mark and Sweep wird doppelt so viel Speicher benötigt. Copying Collection ist nur schneller als Mark and Sweep, wenn das Gros des Speichers Garbage ist.

Mark and Compact

Dabei handelt es sich im Wesentlichen um Copying Collection - innerhalb eines einzigen Speicherbereichs. Der Mark-and-Compact-Collector sucht nach allen erreichbaren Objekten und komprimiert sie am unteren Ende des Heaps. So steht der obere Teil für den Verbrauch zur Verfügung. Der größte Nachteil von Mark and compact ist die Zeit, die diese Methode benötigt.

Generational Collection

Bei der Generational Collection wird der Heap in mehrere Bereiche (in der Regel zwei oder drei) unterteilt, die auf dem Alter der Objekte basieren. Im Allgemeinen sind neuere Objekte mit höherer Wahrscheinlichkeit Garbage als ältere. Es ist also sinnvoll, die neueren Objekte zu durchsuchen. Einige Generational Collectors verwenden unterschiedliche Scan-Frequenzen und/oder Sammelalgorithmen für verschiedene Generationen.

Diese Sprachen nutzen Garbage Collection

Beliebte Garbage-Collection-Sprachen sind unter anderem:

• Java

• Python

• .NET/C#

• Go

• Ruby

• D

• OCaml

• Swift

• Lisp

• Scala

Dabei gehören die drei erstgenannten Programmiersprachen zu den populärsten, die eine Garbage Collection implementieren:

• Die Java Virtual Machine (JVM) bietet vier verschiedene Garbage Collectors: Serial, Parallel, Concurrent Mark and Sweep sowie G1GC. Letztgenannter ist inzwischen Standard in Java. Es handelt sich um einen regionalisierten und generationenübergreifenden, Parallel-Compacting-Collector, der (weiche) Echtzeitziele erreicht.

• Python - insbesondere die Standardimplementierung von CPython - kombiniert Reference Counting mit einer dreistufigen Generational Collection, die sich nur darauf konzentriert, Containerobjekte zu bereinigen.

• Die .NET CLR (common language runtime) verwendet einen dreistufigen Mark-and-Compact-Algorithmus. Die CLR unterteilt Speicherobjekte auch in zwei Heaps: Einen für große (85.000 Byte oder mehr) und einen für kleine Objekte.

(fm)

Dieser Beitrag basiert auf einem Artikel unserer US-Schwesterpublikation Infoworld.