Laden...

Lockfreie threadsichere Queue

Erstellt von Floste vor 15 Jahren Letzter Beitrag vor 13 Jahren 13.695 Views
Floste Themenstarter:in
1.130 Beiträge seit 2007
vor 15 Jahren
Lockfreie threadsichere Queue

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]

  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);
  1. 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

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

1.361 Beiträge seit 2007
vor 15 Jahren

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

3.971 Beiträge seit 2006
vor 15 Jahren

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...

1.361 Beiträge seit 2007
vor 15 Jahren

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

49.485 Beiträge seit 2005
vor 15 Jahren

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

Floste Themenstarter:in
1.130 Beiträge seit 2007
vor 15 Jahren

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)

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

49.485 Beiträge seit 2005
vor 15 Jahren

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

Floste Themenstarter:in
1.130 Beiträge seit 2007
vor 15 Jahren

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.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

49.485 Beiträge seit 2005
vor 15 Jahren

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

0
767 Beiträge seit 2005
vor 15 Jahren

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

Floste Themenstarter:in
1.130 Beiträge seit 2007
vor 15 Jahren

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.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

S
248 Beiträge seit 2008
vor 13 Jahren
Bugfix: Referenz-Leak

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

Floste Themenstarter:in
1.130 Beiträge seit 2007
vor 13 Jahren

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.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!