Warum automatische Garbage Collection ABA-Problem beseitigt?

Question

Ich habe ABA Problem in Concurrency in der Praxis Buch untersucht, in wikipedia und ich habe folgende post

lesen Wie ich die Ursache für ABA Problem, dass in algoritm wir diesen Zustand gleiche überprüfen verstehen wie vorher war, aber Algorithmus impliziert, dass staatliche war unberührt.

Beispiel mit Stack:

Element hinzuzufügen, zu stapeln, verwenden wir folgende Algoritm:

create new stack node(save to `newNode` variable) 

while(true) { 
    oldHead = stack.get(); 
    newNode.next = oldHead; // point_1 
    if(stack.compareAndSet(oldhead, newNode)) { // atomically replace head if now head same as was in start of iteration 
     break; 
    }  
} 

Schritte, die LEED zum ABA Problem:
Ausgangszustand

a->b->c // a-head, c- tail. 

1. Thread_1 versucht, den Werthinzuzufügenauf den Stapel und OS suspendieren den Faden vor compareAndSet Betrieb (Point_1)

2. Thread_2 dann auszuführen pop (Thread_1 noch suspendierte)

   b-> c // B-Kopf, c- tail.

3. Thread_3 dann pop auszuführen (Thread_1 noch suspendierte)

   c // C-Kopf, c- tail.

4. Thread_4 führt dann schieben a (Thread_1 noch suspendierte)

   a-> c // a-Kopf, c- tail.

5. Thread_1 wacht auf und der Cas-Vorgang wird erfolgreich ausgeführt, obwohl dies in einigen Fällen unerwünscht sein kann.

Althoug this post akzeptiert Ich verstehe nicht, warum automatische Garbage Collection, das Problem beseitigt.

Obwohl ich kein Experte in C bin, verstehe ich, dass in C Sie nicht einen Speicherbereich für zwei verschiedene Objekte zuweisen können.

Können Sie es klarer klären?

Answer 1

Ein Teil Ihrer Verwirrung kommt wahrscheinlich von dem Punkt, dass Sie die Datenstruktur selbst mit Inhalten vermischen.

In 'ordnungsgemäße' Implementierung, haben Sie Stack-Knoten mit Daten, nicht selbst Daten sein. Also, was du am Ende hast, ist Knoten (a), Knoten (b) usw. - wenn also ein Thread c zum Stapeln drückt, wird c passieren, aber es wird Knoten (c) sein, der tatsächlich geschoben wird.

Dies bedeutet, daß in einer solchen Umgebung, was in Stapel bei Schritt 4 eingegeben werden nicht nur a, sei es new Node(a) sein wird, die unterschiedliche Zeiger von Node(a) sein wird, die anderen Thread in Schritt gesehen 1. Diese Objekte können sehr gut geschäftsmäßig gleich sein (so wird in java zum Beispiel die equals-Methode wahr zurückgegeben), aber der zeigerweise Vergleich wird sich unterscheiden. Und hier kommen wir zum Teil, wo automatische GC einen Unterschied macht. Der blockierte Thread von Schritt 1 enthält immer noch einen Verweis auf die alte Instanz von Node (a) auf Stack/Registern, auch wenn er später aus dem Stack entfernt wurde und keine starken Referenzen auf ihn irgendwo im Heap vorhanden sind. Dies verhindert, dass der Knoten gelöscht wird und die Speicheradresse wieder verwendet wird, was CAS täuschen würde.

Bitte beachten Sie, dass eine schlechte Situation, die Sie hier erwähnen, nur in Nicht-GC-Sprache auftreten könnte, wenn Sie den ursprünglichen Knoten (Speicher) löschen, während sich Thread 1 noch im kritischen Bereich befindet. Dies ist ziemlich schwierig - Sie verlassen Thread mit Zeiger auf freigegebenen Speicherblock und müssen wirklich, wirklich sicher sein, dass es zu keinem späteren Zeitpunkt dereferenziert wird, da es mit viel schlechterem Ergebnis enden würde, dass ABA (Sie könnten lesen jeder Müll aus dem freigegebenen Block).

Wenn Sie keine Schicht von Indirection in Form von Node (x) implementieren und Clientaufrufe nur erlauben, interne Knoten direkt zu drücken/zu verschieben/modifizieren, dann sind alle Wetten aus - Client kann zum Beispiel denselben Knoten zweimal drücken , was später zur Endlosschleife führt. In Ihrem Beispiel würde es zuerst den gleichen Knoten löschen und dann später wieder einfügen, aber es wird ein großer Leckstatus zwischen Datenstruktur und Client-Code angenommen - sehr gefährlich in Multithread-Umgebungen, besonders wenn Sie mit Lock-Free-Strukturen experimentieren wollen .

Zusammenfassend schützt die automatische GC nicht vor allen Fällen von ABA. Es schützt vor einem sehr spezifischen Fall von ABA, der mit der Speicherwiederverwendung durch malloc zusammenhängt, für einen aggressiv optimierten, lockfreien Code, der Verweise auf tote Objekte enthält.