Beschreibung:
Besonders einfache threadsichere Warteschlange, die ohne Locks auskommt:
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]
Siehe auch:
Lockfreier threadsicherer Stack
Interlocked modify & threadsichere events
Lock free queue, non blocking, lockfree
Hi floste,
Gefällt mir sehr 👍
Was mir noch einfällt:
Die Ähnlichkeit zwischen Enqeue und Dequeue ist zwar einerseits sehr schön.
Aber folgendes sollte doch ebenfalls gehen (und damit die Einfachheit der besonders einfachen Queue weiter erhöhen): 🙂
public void Enqueue(T item)
{
Node newNode = new Node();
newNode.item = item;
Node old = Interlocked.Exchange(ref first, newNode);
old.next = newNode;
}
beste Grüße
zommi
Hallo floste,
was gefällt dir an lock und LinkList<T> nicht?
Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...
Hi nochmal.
Prinzipiell sollten die Interlocked-Konstrukte performanter sein. Weil es (bei passender CPU-Unterstützung) direkt Befehle dafür gibt. Zudem bedeutet ein lock auch immer etwas zusätzlichen Overhead. (Und gerade bei Collections sollte so ein Overhead immer klein gehalten werden)
Zudem stellt sich bei locks immer die Frage nach privaten oder offentlichen. Und zu guter letzt muss man auch noch auf Deadlocks achten.
All das entfällt bei obiger Variante. Wenn man also mal eine LinkedList selbst implementieren muss und wegen den genannten Gründen auf locks gerne verzichten möchte, ist das Snippet oben sehr schön.
beste Grüße
zommi
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
Wenn der Thread zu diesem Zeitpunkt plötzlich wartet, sind neue Elemente solange unzugänglich, bis der Thread fortfährt. (Falls er nie fortfahren sollte für immer.) Wenn zu diesem Zeitpunkt weitere Threads Enqueue aufrufen, werden die Elemente zwar angefügt, sind aber durch die Unterbrechung unzugänglich. Sobald der Thread fortfährt, sind alle Elemente wieder zugänglich und es sind keine verloren gegangen.
Das gleiche Problem hat man aber auch bei Locks, da die Standardqueue auch einen inkonsistenten Zustand hat, während Enquene aufgerufen wird. 😉
Wenn man also nach dir geht, kann man auch mit Locks nichts Threadsicher machen (Applikation mit Warteschlange)
Hallo floste,
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.
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.
public bool Dequeue(ref T item)
Einen habe ich trotzdem noch. 😃 Du solltest ref in out ändern.
Hallo zusammen,
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
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.
Du hast es aber einen inkonsistenten Zustand genannt, dass man neuere Elemente solange nicht abrufen kann, bis der Thread fortfährt. (So habe ich es verstanden.)
Bei lock wäre nichtnur das der Fall sondern es würden auchnoch alle zugreifenden Threads blockiert.
Also: Entweder kann man mit locks nichts threadsicher machen,da inkonsistente Zusände auftreten, oder ich habe dich falsch verstanden es treten bei mir keine inkonsistenten Zustände auf.
Einen habe ich trotzdem noch. 😃 Du solltest ref in out ändern.
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.
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.
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
abgesehen von diesen Problemen...
das hier:
while (old != Interlocked.CompareExchange(ref first, newNode, old));
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.
loop:
btst #6,$bfe001
bne.s loop
rts
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.
Hallo,
man sollte Dequeue noch so erweitern, dass vor dem Verlassen der Methode das zurückgegebene Element aus der Datenstruktur entfernt wird:
...
item = current.next.item;
current.next.item = default(T);
return true;
}
Bei Dequeue wird die Verkettete Liste um eine Element verschoben (effektiv: last wird zu last.next). Dabei wird diese Node zum neuen "Anker" der Liste und wird NICHT vom GC abgeräumt - auch nicht das darin enthaltene Element.
Grüße
spooky
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.