Lockfreie threadsichere Queue

Beschreibung:

Besonders einfache threadsichere Warteschlange, die ohne Locks auskommt:

C#-Code:

public class LockFreeQueue<T>     {         public LockFreeQueue()         {             first = new Node();             last = first;         }         Node first;         Node last;         public void Enqueue(T item)         {             Node newNode = new Node();             newNode.item = item;             Node old= Interlocked.Exchange(ref first, newNode);             old.next = newNode;         }         public bool Dequeue(out T item)         {             Node current;             do             {                 current = last;                 if (current.next == null)                 {                     item=default(T);                     return false;                 }             }             while (current != Interlocked.CompareExchange(ref last, current.next, current));             item = current.next.item;             current.next.item = default(T);             return true;         }         class Node         {             public T item;             public Node next;         }     }

[Edit 12.8.2010]
1. Einen Vorschlag aufnenommen, im Enqueue Interlocked.Exchange anstatt einer Schleife mit CompareExchange zu verwenden -> performanter
2. Folgende Zeile ergänzt, damit nicht das zuletzt aus der Queue genommene Element noch referenziert wird: current.next.item = default(T);
3. Klasse public gemacht, die Klasse ist schließlich allgemein verwendbar.


Siehe auch:
 Lockfreier threadsicherer Stack
 Interlocked modify & threadsichere events

Lock free queue, non blocking, lockfree

Hallo floste,
was gefällt dir an lock und LinkList<T> nicht?

Hallo floste,

[EDIT]Der folgende Einwand ist unberechtigt, wie sich weiter unten zeigt.[/EDIT]

ich glaube nicht, dass die Implementierung sicher ist. Nachdem im Enqueue first per Interlocked.CompareExchange umgesetzt wurde und bevor old.next = newNode; ausgeführt wird, ist die Queue in einem inkonsistenten Zustand, der beliebig lange andauern kann. Im Prinzip können von verschiedenen Threads sogar mehrere Enqueues hintereinander ausgeführt werden, die alle zufällig vor dem old.next = newNode; unterbrochen werden. Spätestens dann fallen aber mehrere Dequeues hintereinander auf die Nase. Ich sehe leider auch erstmal nicht, wie sich das Problem lösen lässt.

herbivore

Hallo floste,

Zitat:

Wenn man also nach dir geht, kann man auch mit Locks nichts Threadsicher machen

doch, das lock ist ja gerade dafür, dass während eines inkonsistenten Zustands kein anderer zugreifen kann. Gerade dadurch wird es mit lock thread-sicher.

Zitat:

Wenn der Thread zu diesem Zeitpunkt plötzlich wartet, sind neue Elemente solange unzugänglich, bis der Thread fortfährt.

Ja, du hast Recht und ich nehme meine anders lautende Vermutung zurück. Und um das auch noch einzugestehen: Eine Queue mit lock wäre in dem geschilderten Fall des lange unterbrochenen Threads deiner Queue unterlegen, weil solange überhaupt keine Operation auf der Queue möglich wären. Bei deiner wären immer noch weitere Enqueues möglich.

Zitat:

public bool Dequeue(ref T item)

Einen habe ich trotzdem noch. :-) Du solltest ref in out ändern.


Hallo zusammen,

Zitat:

Applikation mit Warteschlange

der Unterschied zu der Queue von floste ist, dass bei meiner Queue ein Aufruf von Dequeue absichtlich solange blockiert, bis ein neues Element verfügbar ist. Damit vermeidet man inbesondere beim Einsatz als Job-Queue das Busy-Waiting auf neue Elemente (Jobs).

herbivore

Hallo floste,

du hast mich falsch verstanden. Aber das müssen wir auch hier unter Projekte nicht ausdiskutieren, zumal ich denke, dass inbesondere mein letzter Beitrag klar genug war. Da habe ich ja auch schon eingestanden, dass lock in dem speziellen Fall die Threads blockieren würde.

Zitat:

Das habe ich nicht gemacht, da nicht in jedem Fall der Wert verändert wird, da ja nicht in jedem Fall etwas abgerufen werden kann.

Das ist bei TryParse genauso und trotzdem wird out verwendet. Du kannst und solltest, in dem Fall, dass kein Wert zurückgegeben werden kann, default (T) verwenden.

herbivore

Zitat:

ist doch Busywaiting mit Prozessorlast auf 100%... (Es sei denn dass das CompareExchange direkt selber wartet)... jedenfalls ist es Polling und das sollte man auch vermeiden.

Ja, busy schon aber nicht wie üblich, dass er darauf wartet, dass eine Veränderung eintritt, sondern darauf, dass keine Veränderung eintritt, was wohl bedeutend häufiger der Fall ist.
Er prüft, ob der wert geändert wurde und ersetzt wenn nicht den Wert. Ansonsten wird die Prozedur wiederholt. Dass der Wert geändert wurde, heißt aber, dass ein anderer Thread den Wert geändet hat und dadurch aufhört zu warten.
Das heißt durch einen Aufruf von Enqueue/Dequeue eines Threads müssen alle anderen Threads maximal einen Schleifendurchlauf warten.

Ein Element, das etwas später freigegeben wird, verbraucht in den meisten Fällen nicht soo viel Speicher, aber da dies offensichtlich einigen Leuten wichtig ist, habe ich deine Zeile ergänzt.