Parallelen Zugriff auf verkettete Liste (Add/Remove) korrekt synchronisieren

Wofür meinst du das verwenden zu wollen?
Nicht alles was man in Java macht, ist in .NET Nötig, oder genauso zu machen.

Hi,

also folgendes Beispiel.

Ich habe eine verkettete Liste, in der jedes Element eine Referenz auf das nächste Element hat.

public class Node 
{
   int i;
   Node next;
}

In der Liste sind 4 Elemente (A,B,C,D). Zudem gibt es einen Topzeiger der aufs erste Element zeigt.

Top->A->B->C->D->null

Jetzt kommt Thread 1 und will Element A aus der Liste löschen, also den Topzeiger auf B umlenken.
Das macht er atomar mit CompareExchange.
Irgendwie so:

 Node oldTop = top;
 Node newTop = oldTop.Next;
 Node tmp = Interlocked.CompareExchange(ref top, newTop, oldTop);

Zur gleichen Zeit versucht aber Thread 2 ein Element E direkt hinter Element A einzufügen. Auch atomar.

Wenn ich alles richtig verstanden habe, könnte folgendes passieren.

Wenn nach der Zeile:

 Node newTop = oldTop.Next;

der Thread 1 unterbrochen wird und der Thread 2 ein neues Element nach A einfügt, merkt Thread 1 an dieser Stelle:

 Node tmp = Interlocked.CompareExchange(ref top, newTop, oldTop);

NICHT das sich der Nextzeiger des Knotens A geändert hat und biegt den Topzeiger auf das Element B um.

Damit hat man folgende List:
Top->B->C->D->null

Thread 2 denkt aber er hätte E korrekt nach A eingefügt und A wäre noch Teil der Liste.

Mit der MarkableReference in Java, kann man einem Element markieren, damit können andere Threads erkennen das Sie den nextzeiger nicht verändert dürfen, bzw. das jemand anderes ihn verändert hat.

Oder merkt die Interlocked.CompareExchange-Methode, dass der Nextzeiger der Node-Klasse geändert wurde?

Ich hoffe das war nicht zu kompliziert erklärt 😃

Hallo akunz,

Interlocked.CompareExchange (ref location1, value, comparand) ist doch gerade dafür da, dass der Wert von location1 nur geändert wird, wenn er zu Beginn der unteilbaren Operation immer noch den erwarteten Wert comparand hat.

Ob deine Synchronisierung in allen Fällen korrekt ist, habe ich mir nicht angeschaut, aber CompareExchange tut, was ich beschrieben habe. Insofern würde CompareExchange merken, wenn sich der Wert von location1 (durch einen anderen Thread) geändert hat.

BTW: Sicherheitshalber sollten alle gemeinsamen Variablen volatile sein.

herbivore

...wobei man im Falle einer zwischenzeitlichen Änderung das ganze wiederholen muss.

Am einfachsten geht's mit: Interlocked modify & threadsichere events

Hi akunz,

du hast schon erkannt, dass eine Lock-freie Linked-List mit Möglichkeit überall zu Löschen und Einzufügen nicht einfach runterprogrammiert werden kann. (LIFO-Stack und FIFO-Queue sind da einfacher)

Bei dir ergibt sich ja das Problem, dass du beim Löschen von A die Referenz _auf _A veränderst aber beim Einfügen hinter A die Next-Referenz _in _A manipulierst. Und diese Operationen beeinflussen sich, obwohl es unterschiedliche Referenzen sind. Und da hilft CompareAndSwap (CAS) [aka CompareAndExchange] allein nicht weiter, weil das immer nur eine Referenz allein behandelt.

Bei Stack und Queue fässt man nur die Top/First oder die Last/Bottom Referenz an. Schließlich gibt es keine Referenz auf Top.

Na egal, so viel zum Hintergrund. Deshalb findest du hier im Forum schöne, prägnante, kurze lockfreie Queue oder lockfreie Stack-Implementierungen mit CAS oder auch die lockfreien Events, wobei da ausgenutzt wird, dass beim Verketten von Delegaten ein neuer entsteht und man nicht wahlfrei irgendwo in der Mitte einen neuen Delegaten reinschieben kann. Also wir eine gewisse Immutability haben, die bei deinen Linked-List-Nodes nicht gegeben ist.

Es gibt meines Wissens unterschiedliche Ansätze für eine Lock-Free Linked List.1.Die 2-stufige Variante mit A) Markieren und B) Wirklich löschen. A Pragmatic Implementation of Non-Blocking Linked-Lists 1.Eine Variante mit zusätzlichen Zwischen-Knoten. Lock-Free Linked Lists Using Compare-and-Swap

Für das erste Verfahren ist die Java AtomicMarkableReference gedacht. Die kannst du dir aber sicher einfach in C# nachbauen.
Ich habe mir zwar nicht beide Paper detailiert durchgelesen, aber nach dem "pragmatic" im Titel und dem weitaus längeren zweiten Paper scheint das andere "more sophisticated" zu sein. Also vielleicht performanter, aber sicherlich schwieriger in der Implementierung.

beste Grüße
zommi

😄, wie sie alle meine snippets verlinken^^

Die kannst du dir aber sicher einfach in C# nachbauen.

Ganz so einfach geht das eben nicht. Problem ist, dass CompareExchange in .net nur primitive typen bis 64 bit oder einzelne referenzen austauschen kann. Auf einem 64bit-system braucht man aber theoretisch 65 bit, um sowas zu direkt implementieren. Ansonsten muss man eben rumtrixen:

a) Einen immutable referenztyp zwischenschalten
b) Assemblercode in c# einbauen (^.)
c) Davon ausgehen, dass gchandles niemals ihr erstes bit gesetzt haben

Option a sieht da doch noch am freundlichsten aus, kommt aber lustigerweise auf zommis option 2 raus^^

class MarkableReference<T>
{
    public MarkableReference(T value, bool marked)
    {
        this.Value=value;
        this.Marked=marked;
    }

    public T Value{get;private set;}
    public bool Marked{get;private set;}
}

Die klasse ist immutable, sodass man compare and swap anwenden kann^^

du hast schon erkannt, dass eine Lock-freie Linked-List mit Möglichkeit überall zu Löschen und Einzufügen nicht einfach runterprogrammiert werden kann. (LIFO-Stack und FIFO-Queue sind da einfacher)

Hi,
danke schonmal für deine Antwort. Ich prgrammier auch gar keine LinkedList wo man überall löschen kann. Es geht nur um eine Aufgabenstellung, wie man dieses Problem in C# lösen würde. Die Jav und C++ Lösungen sind mir bekannt.

Ich werde mir deine Links auf jeden Fall anschauen.

a) Einen immutable referenztyp zwischenschalten
b) Assemblercode in c# einbauen (^.)
c) Davon ausgehen, dass gchandles niemals ihr erstes bit gesetzt haben

...

Aha. Danke!