Wie geht ein gleichzeitiger Garbage Collector mit Variablen um?

8

Nehmen wir an, es handelt sich um einen gleichzeitigen Mark-and-Sweep-Garbage-Collector.

Wenn ein solcher GC konstante Zeiger verarbeitet, geht er nur durch diese (ausgehend von den Wurzeln) und markiert jeden angetroffenen Datenblock. Dann fegt alles unmarkiert. Ein Client-Code sollte die Datenblöcke markieren, die er als Roots verwendet.

Aber was tun mit Variablen? Hier ist eine Situation:

  1. Vist eine Variable, die einen Zeiger auf ein Objekt speichert A.
  2. Thread 1liest Vund suspendiert.
  3. Thread 2ändert Vund zeigt auf das Objekt B.
  4. Der Garbage Collector führt seine "Mark" -Phase aus und trifft auf Begegnungen, auf die Anicht mehr verwiesen wird. Anschließend wird die Zuordnung während der "Sweep" -Phase aufgehoben.
  5. Thread 1erwacht und versucht zu verwenden A(bereits aus VSchritt 2 gelesen ), indem es als root markiert wird. Und scheitert , weil Aes nicht mehr existiert.

Wie geht man damit um?

Das Thread 2kann das ersetzte Objekt Amit einem speziellen Nicht-Entfernen-Flag markieren (ein ähnliches Flag wird für neu zugewiesene Objekte verwendet). Aber wann sollte diese Flagge entfernt werden? Das Thread 1könnte ich natürlich tun. Aber Thread 2nichts weiß Thread 1, und somit nicht sicher sein kann , dass dies jemals geschehen wird. Dies kann dazu führen, Adass niemals befreit wird. Und wenn GC dieses Flag entfernt, verhindert nichts, dass Aes entfernt wird, wenn GC zum zweiten Mal ausgeführt wird ...

Die spontanen Mark-and-Sweep-Garbage-Collector-Beschreibungen, die ich gelesen habe, erwähnen nur, dass das ersetzte Objekt "grau" sein sollte. Aber ohne Einzelheiten. Ein Link zu einer detaillierteren Beschreibung der Lösung wäre sehr willkommen.

garbage-collection lorus
quelle

Antworten:

4

Abhängig von den genauen Details der Garbage Collector-Implementierung ist dies in Schritt 4 möglicherweise überhaupt kein Problem. In Schritt 2 liest beispielsweise Thread 1 vermutlich Vin ein Register. Der Garbage Collector muss wahrscheinlich den Inhalt der Register auf alle aktiven (laufenden und angehaltenen) Threads untersuchen, um festzustellen, ob ein Verweis auf ein in den Registern enthaltenes Objekt vorhanden ist.

Eine Garbage Collector-Implementierung ist unweigerlich eng an die Betriebsumgebung (und die Threading-Umgebung) gekoppelt, in der sie ausgeführt wird. Es gibt viele Implementierungstechniken, um sicherzustellen, dass alle gespeicherten und vorübergehenden Referenzen berücksichtigt werden.

Greg Hewgill
quelle
Aber gibt es eine Möglichkeit, dies plattformunabhängig zu tun? Das Register kann die Daten enthalten, die nur wie ein Zeiger aussehen, aber tatsächlich nicht. Meine GC-Implementierung ist genau und basiert auf der Tatsache, dass jeder Zeiger, den sie verarbeitet, auf einen Datenblock einer bestimmten Struktur verweist.
Lorus
Hmm, aber das ist eine Idee! Ich kann einen solchen Zeiger auf eine bekannte Stelle im Stapel (oder eine thread-lokale Variable) setzen und GC veranlassen, ihn zu untersuchen.
Lorus
@lorus - Für viele Garbage Collectors teilen die vom Compiler generierten Tabellen dem GC mit, welche Register an einem bestimmten Punkt in einer Methode Zeiger enthalten. Für andere läuft der GC nur an einem "sicheren Punkt", der den Registerinhalt implizit ungültig macht. Außerdem sind GC-Implementierungen auf einer bestimmten Ebene von Natur aus plattformabhängig.
Stephen C
@StephenC Nun, ich glaube nicht , so Allzweck - Algorithmus wie Garbage Collection erfordert so plattformabhängig zu sein. Atomoperationen und Speicherbarrieren - ja. Aber direkter Zugang zu Registern? Nein, das glaube ich nicht. Es wäre effizient, aber ich glaube, es ist nicht unbedingt erforderlich. Ich würde gerne mehr über solche plattformunabhängigen Algorithmen erfahren.
Lorus
0

Sie müssen lokale Variablen irgendwann während der Markierungsphase markieren. Alle lokalen Variablen, einschließlich derjenigen, die normalerweise auf einem Stapel leben. Irgendwie.

Ich denke außerdem, dass dies während der synchronen Phase (alle Mutatoren gestoppt) des Scannens modifizierter Objekte erfolgen muss. Tatsächlich kann das gleiche Problem auch ohne Berücksichtigung lokaler Variablen / Register auftreten. Betrachten Sie Objekt A, das auf Null zeigt, und Objekt B, das auf C zeigt. Jetzt scannen Sie Objekt A, ein Mutator-Thread kommt, kopiert den Verweis auf C von B nach A, macht B null. Und jetzt kommen Sie zum Scannen von B. Und C rutschte aus unter deinen Fingern.

Ich kenne keine Möglichkeit, damit umzugehen, bei der die Mutatoren nicht gestoppt werden müssten. Die übliche Technik besteht darin, am Ende der Markierungsphase alle Mutatoren zu stoppen und alle Objekte, die sie während der Hauptmarkierungsphase mutiert haben, erneut zu markieren. Und fügen Sie Stapel und Register hinzu.

Das Markieren von Registern wird normalerweise umgangen, indem es synchron ausgeführt wird, indem manchmal der Kollektor im Thread aufgerufen wird. Innerhalb der Collector-Funktion können sich nur eigene lokale Variablen (die keine Roots sind) in Registern befinden. Alle anderen lokalen Variablen in der Aufrufkette befinden sich im Stapel, sodass Sie den Stapel durchlaufen können.

Alternativ können Sie ein Signal an den Thread senden. Der Signalhandler erzwingt erneut alle Variablen auf dem Stapel, sodass Sie sie durchlaufen können. Nachteil dieser Methode ist, dass sie plattformabhängig ist.

Jan Hudec
quelle
Ja. In der Situation, über die gesprochen wurde, geht es jedoch nicht um eine lokale Variable. Es handelt sich um eine globale Version, auf die gleichzeitig von verschiedenen Threads zugegriffen und Änderungen vorgenommen werden können.
Lorus
Wenn Thread1 V gelesen hat und A nicht in einer lokalen Variablen von Thread1 enthalten ist, ist A nicht erreichbar, nachdem Thread2 V geändert hat, sodass es trotzdem zur Sammlung bereit ist
Ratschenfreak
@lorus: Wenn ein Thread etwas in das Register lädt, ist das Register seine lokale Variable. Es spielt keine Rolle, ob es in einer übergeordneten Quelle erwähnt oder vom Compiler hinzugefügt wurde. Sie behandeln es einfach als lokale Variable.
Jan Hudec
@ JanHudec Ok. Jetzt habe ich es verstanden. Das Aufrufen des Kollektors im (Client-) Thread ist also tatsächlich eine Art globale Sperre?
Lorus
1
@ JanHudec, es sei denn, die Threads arbeiten mit dem GC und können Objekte zu einer zu markierenden Warteschlange hinzufügen, jedes Mal, wenn ein Thread eine Referenz liest
Ratschenfreak