Welche Algorithmen stehen hinter der Low-Pause-GC?

Einige Sprachen, zum Beispiel Java, führten eine Low-Pause-GC ein.

Diese GC können den größten Teil der Arbeit erledigen, ohne die ganze Welt anzuhalten. Dies ist offensichtlich ein ziemlich schwieriges Problem, da es erforderlich ist, den Speicher zu analysieren, wenn der Thread geändert wird. Dies führt dazu, dass Daten zu Beginn des Prozesses verwendet werden können und nicht mehr, wenn der Vorgang abgeschlossen ist, oder Daten, bei denen es sich anscheinend um Müll handelt Die Referenz wurde in den Speicher verschoben und ist nie dort erschienen, wo der GC gesucht hat.

Was steckt also im Grunde dahinter?

Forschungsarbeiten oder der Link zu einem wirklich technischen Artikel gelten als gültige Antwort, da dieses Thema wirklich technisch ist.

Was steckt also im Grunde dahinter?

Es ist im Grunde ein Mark-and-Sweep-Algorithmus, der "nur" gleichzeitig in einem separaten Thread ausgeführt wird.

Zu den Forschungsarbeiten zu diesem Thema:

• Sehr gleichzeitige Markierungs- und Sweep-Garbage-Sammlung ohne feinkörnige Synchronisation

• Concurrent Mark-Sweep Garbabe Collector (enthält Links zu zwei Papieren, von denen eines unten aufgeführt ist)

• Implementieren eines Garbage Collector im laufenden Betrieb für Java

• Portable, unauffällige Garbage Collection für Multiprozessorsysteme (Doligez Leroy, Powerpoint Presentation)

• On-the-Fly-Müllabfuhr: Eine Übung in Kooperation (von Edsger Wybe Djikstra)

Soweit ich weiß, verwendet Java G1 Garbage Collector so genannte Heap-Regionen , um ein Anhalten der gesamten Welt zu vermeiden. So wie ich es sehe, wird eine der Regionen durch Bereinigung gesperrt, während die Speicherzuweisung in einer anderen Region erfolgt.

Hier ist eine Erklärung von Jeremy Manson :

Das Prinzip ist einfach: Der Collector teilt den Heap in Regionen mit fester Größe auf und verfolgt die Live-Daten in diesen Regionen. Es hält eine Reihe von Zeigern - die "erinnerte Menge" - in und aus der Region. Wenn ein GC als notwendig erachtet wird, erfasst er zuerst die Regionen mit weniger Live-Daten (daher "Garbage First"). Dies kann häufig bedeuten, dass eine gesamte Region in einem Schritt erfasst wird: Wenn die Anzahl der Zeiger auf eine Region Null beträgt, muss diese Region nicht markiert oder gewobbelt werden ...

• Hier ist ein technisches Dokument von Sun-Ingenieuren, in dem das Design erläutert wird: Garbage-First Garbage Collection

IBMs Echtzeit-JVM verwendet einen Garbage Collector namens Metronome , der die GC-Aktivität in diskrete Quanten aufteilt und diese mit der Anwendungsverarbeitung verschachtelt. Anstelle von periodischen (und nicht deterministischen) Stop-the-World-GC-Pausen wird die Anwendung also etwas langsamer ausgeführt, während der GC parallel ausgeführt wird.

Es gibt einen weiteren GC, der eine dynamische Defragmentierung durchführt und die Echtzeitanforderungen erfüllt. Die einzige Referenz, die ich finden kann, ist hier (ACM-Mitgliedschaft erforderlich).

Ein interessanter Echtzeit-Garbage Collector ist ohne Unterbrechung . Es verwendet den traditionellen Mark-and-Sweep-Ansatz, ist jedoch für die Verwendung auf Multiprozessorsystemen konzipiert und unterstützt gleichzeitig gesperrtes Multithreading.

Der Grund dafür ist, dass in Java nur der GC Speicher freigeben kann, der möglicherweise GC-Referenzen enthält. Das heißt, solange Sie Objekte in einem separaten Thread sicher lesen können, müssten Sie das Programm nur anhalten, um die Referenzen auf dem Stapel zu beobachten.

Ich würde für Mutationen vorschlagen, dass sie eine Art Copy-on-Write implementieren, um den GC über die Änderung zu informieren.