Versuchen, eine Lock-Free-Liste einfach verknüpft zu schreiben, Probleme mit der Entfernung

Question

Ich versuche, eine Sperre frei einzigen verknüpften Liste zu schreiben. Eventuelle Konsistenz ist kein Problem (jemand durchquert eine Liste, die falsche Elemente enthalten könnte).

Ich denke, dass ich das Hinzufügen Element rechts (Schleifen und Interlocked.CompareExchange).

Aber ich kann nicht herausfinden, wie Knoten (irgendwo in der Liste) entfernt werden, da ich das vorherige Element abrufen muss und sie sein Next Feld auf dem aktuellen Knoten Next Feld festlegen.

class Node 
{ 
    Node Next; 
    object Value; 
} 

class SinglyLinkedList 
{ 
    Root _root; 

    public void Add(object value) 
    {} 

    public void Remove(object value) 
    {} 
} 

dh

a -> b -> c

zu

a -> c

Pseudo-Code:

Node prev; 
Node node = _root; 
while (node.Value != nodeValue) 
{ 
    prev = node; 
    node = node.Next; 
} 
prev.Next = node.Next; 

wie kann ich machen Dies ist eine atomare Operation (d.h. Stellen Sie sicher, dass prev.Next = node.Next aufgerufen wird, ohne dass entweder next oder prev dazwischen von einem anderen Thread entfernt wird)?

Ich könnte stattdessen ReaderWriterLockSlim verwenden, aber ich fand dieses Problem interessant, da ich weiß, dass es gibt frei verknüpfte Listen.

My betrifft:

Das Folgende passieren kann, wenn der aktuelle Thread zwischen der Schleife und der Zuordnung aufgehängt ist:

• prev selbst kann von einem anderen Thread entfernt wurden.
• node wurde möglicherweise durch einen anderen Thread entfernt.
• Node.Next könnte wurden
entfernt

Answer 1

Ja, ist das Hinzufügen eine einfache Zwei-Stufen-Schleife mit CAS auf der vorhergehenden .Next pointer; aber das Entfernen ist schwer!

Eigentlich können Sie es nicht tun, ohne eine zusätzliche Information und Logik zu verwenden.

Harris hat die Lösung für dieses Problem erstellt, indem er ein Markierungsbit hinzufügt, das es niemandem erlaubt, den Knoten zu modifizieren. Das Entfernen wird in zwei Schritten durchgeführt: Zuerst (CAS) markieren Sie den entfernten Knoten, um zu verhindern, dass irgendjemand ihn ändert (insbesondere seinen .Nächsten Zeiger); zweiter CAS der vorherige Knoten. Nächster Zeiger, der jetzt sicher ist, weil der andere Knoten markiert wurde.

Das Problem ist jetzt, dass in C Harris die beiden am wenigsten signifikanten Bits des .Next-Zeigers als Marker verwendet haben. Dies ist schlau, weil sie bei 4-Byte-ausgerichteten Zeigern immer unbenutzt sind (d. H. 00) und da sie in den 32-Bit-Zeiger passen, können sie mit dem Zeiger selbst atomar sein, was der Schlüssel zu diesem Algorithmus ist. Natürlich ist dies in C# nicht möglich, zumindest ohne unsicheren Code zu verwenden.

Die Lösung wird ein wenig komplizierter und beinhaltet einen zusätzlichen Verweis auf eine unveränderliche Klasse, die die beiden Felder enthält (.Next + Marker).

Statt in einer langen Erklärung, warum diese Ideen zu gehen, habe ich einige Referenzen im Internet zu finden, die in allen Details gehen, die Sie benötigen, finden Sie unter:

Lock-free Linked List (Part 1) erklärt das Problem;

Lock-free Linked List (Part 2) Erklärt die C-Lösung + die Spinlock-Lösung;

Lock-free Linked List (Part 3) Erklärt die unveränderliche Zustandsreferenz;

Wenn Sie wirklich neugierig auf das Thema sind, gibt es wissenschaftliche Arbeiten mit verschiedenen Lösungen und Analyse ihrer Leistung, z. dieses: Lock-free linked lists and skip lists