Welche Algorithmen stehen hinter der Low-Pause-GC?

12

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.

deadalnix
quelle

Antworten:

16

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:

Falke
quelle
5

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 ...

Mücke
quelle
5

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.

TMN
quelle
Nett ! Schade, dass ich keinen Zugang zu ACM habe. Dieser Artikel sieht wirklich interessant aus.
Deadalnix
2

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.

DeadMG
quelle
Dies ist nicht ausreichend, solange diese Referenz jederzeit von einem Thread aktualisiert werden kann.
Deadalnix