Garbage Collection für Systemprogrammierer (2023)

Einführung in RCU

• Betriebssysteme gehören tagtäglich zu den performancekritischsten Programmen überhaupt.
• Betriebssysteme können immer schneller werden, und Kernel- sowie Treiberentwickler arbeiten kontinuierlich an der Optimierung ihres Codes.
• Betriebssysteme benötigen ein hohes Maß an Nebenläufigkeit, planen User-Space-Prozesse und Threads und verfügen über eigene Threads sowie Interrupt-Handler, die mit der Hardware interagieren.

Wie RCU funktioniert

• Wenn Daten, die häufig gelesen, aber selten geschrieben werden (z. B. aktuell angeschlossene USB-Geräte), atomar geändert werden müssen, wird die Strategie RCU (Read, Copy, Update) verwendet.
• Die Daten werden gelesen, kopiert und verändert, danach wird der Pointer atomar auf die neue Version aktualisiert.
• Diese Methode ist einfach zu verwenden und verursacht keine Wartezeiten, kann jedoch zu Memory Leaks führen.

Das Problem der Memory Leaks lösen

• Um Memory Leaks zu vermeiden, kann das Löschen alter Daten statt direkt in der Update-Funktion so lange verschoben werden, bis es keine Reader mehr gibt, die gerade lesen.
• Während Reader die Daten lesen, wartet der Writer mit dem Löschen der Daten, um den Speicher sicher zu verwalten.

RCU in der Praxis

• RCU wird in Linux zehntausendfach eingesetzt und kommt auch in Facebooks Folly-C++-Bibliothek sowie in Rusts crossbeam-epoch zum Einsatz.
• RCU wird durch Anforderungen an Performance und Latenz motiviert und bietet ein Speichermanagement, das Garbage Collection ähnelt.

Missverständnisse über Garbage Collection

• Die verbreitete Annahme, Garbage Collection sei langsamer als manuelles Speichermanagement, bricht bei genauer Betrachtung der Details schnell zusammen.
• Die Funktion free() ist nicht kostenlos, und Memory Allocators müssen intern viel Zustand verwalten.
• Moderne Garbage Collectors bieten kompaktierende und generationenbasierte Optimierungen und liefern dadurch hohen Durchsatz sowie gute Cache-Performance.

Die Illusion der Kontrolle

• Entwickler wollen gelegentlich Echtzeitsysteme bauen, haben in Wirklichkeit aber keine vollständige Kontrolle über das Speichermanagement.
• Das Betriebssystem kann nur die Absicht des Entwicklers bei der Speicherallokation erraten, und manchmal kann schon ein einfacher Pointer-Zugriff zu Disk-I/O werden.

Fazit

• Nicht jede Software profitiert von Garbage Collection, aber sie ist ein nützliches Werkzeug und sollte auch unter Systemprogrammierern nicht länger gefürchtet werden.

Meinung von GN⁺

• RCU ist eine effektive Technik, um in Multithreading-Umgebungen die Datenkonsistenz zu wahren und gleichzeitig die Nebenläufigkeit zu erhöhen. Das ist ein sehr wichtiger Faktor in High-Performance-Computing und Echtzeitsystemen.
• Das Beispiel von RCU, das mit verbreiteten Annahmen über Garbage Collection aufräumt, eröffnet Entwicklern eine neue Perspektive auf Speichermanagement. Das gilt besonders im Bereich der Systemprogrammierung, in dem Speichermanagement besonders wichtig ist.
• Andere Projekte mit ähnlicher Funktionalität wie RCU sind etwa Javas ConcurrentLinkedQueue oder .NETs ConcurrentBag, die ebenfalls lock-free Datenstrukturen bereitstellen.
• Bei der Einführung von RCU sollten die Anforderungen des Systems und die Performance-Ziele berücksichtigt werden, und man sollte die Vorteile sowie die potenziellen Kosten dieser Technik verstehen.
• Dieser Artikel kann Entwicklern helfen, Speichermanagement und Nebenläufigkeit besser zu verstehen, bestehende Annahmen zu hinterfragen und neue Lösungen zu erkunden.

[GN⁺]

Hacker-News-Kommentare

• Vorschlag, sich die innovativen parallelen Garbage-Collection-(GC)-Techniken für MPL und MaPLe anzusehen

  • Ausgezeichnet mit dem Distinguished Paper Award auf der POPL 2024 und dem ACM SIGPLAN Paper Award 2023
  • Die wichtigsten Vorschläge sind:
    • „disentanglement“ auf Basis einer nachweislich effizienten parallelen Garbage Collection
    • nachweislich effiziente automatische Granularitätskontrolle

• Es ist interessant, RCU als Motivation für Garbage Collection zu verwenden

  • Es ist sinnvoll, die Verantwortung für die Speicherfreigabe vom schreibenden Worker auf den letzten lesenden Worker zu übertragen
  • Für eine bessere Leistung sollte man möglicherweise erwägen, die Speicherfreigabe nicht auf den lesenden Worker, sondern auf einen dedizierten Batch-Prozess zu verlagern

• Allgemeine Missverständnisse über Speicherverwaltung

  • der Glaube, dass Programmierer die optimale Pausenzeit für die Speicherverwaltung kennen
  • bei Spielen und Krypto-Handelsprogrammen könnten Programmierer die optimale Pausenzeit tatsächlich kennen

• Der RCU-Anwendungsfall ist überzeugend, aber die Erfahrungen mit Garbage Collection in anderen Situationen sind nicht gut

  • Es liest sich wie die Behauptung, dass maßgeschneiderte Speicherverwaltungslösungen die beste Leistung liefern können
  • Diskussion über das Missverständnis, dass ein Aufruf von free() den Speicher an das OS zurückgibt

• Bei der Verwendung von Garbage Collection erfolgen neue Allokationen aus dem RAM statt aus dem Cache

  • Das kann große Auswirkungen auf die Leistung haben
  • Ein Benchmark-Beispiel aus der Sprache Julia wird genannt

• Gute Tracing-Garbage-Collector übertreffen die manuelle Speicherverwaltung beim Durchsatz schon seit Langem

  • In jüngerer Zeit ist auch die Latenz für die meisten Anwendungen auf ein akzeptables Niveau gesunken
  • Der Speicherverbrauch ist der wichtigste Aspekt

• Eines der Dinge, die gut zu Garbage Collection passen, ist async/await

  • Die Verwendung von async/await in Rust verursacht in Verbindung mit der Speicherverwaltung Probleme

• Nach der Motivation über RCU zu einer Diskussion über allgemeine Garbage Collection zu wechseln, ist etwas überraschend

• Bei der Softwareentwicklung werden zwei Fälle betrachtet

  • Für den Hot Path verwendet man einen benutzerdefinierten Allocator, und für den Rest ist Garbage Collection praktisch

• Der Wechsel von RCU zu allgemeiner Tracing-Garbage-Collection wirkt wie eine geschickte Strategie

  • Manuelle Speicherverwaltung umfasst mehr als nur Aufrufe von malloc/free

• Für Systemprogrammierer ist es schwierig zu erkennen, wann etwas Garbage-Collected werden kann

• Die Lifecycle-Management-Werkzeuge von Rust und C++ helfen dabei, die Speicherfreigabe zu automatisieren, vereinfachen die Komplexität aber nicht