Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Lockfreie threadsichere Queue
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

Themenstarter:

Lockfreie threadsichere Queue

beantworten | zitieren | melden

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);
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
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
kleines_eichhoernchen
myCSharp.de - Member

Avatar #avatar-2079.jpg


Dabei seit:
Beiträge: 4055
Herkunft: Ursprünglich Vogtland, jetzt Much

beantworten | zitieren | melden

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...
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

Themenstarter:

beantworten | zitieren | melden

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)
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

Themenstarter:

beantworten | zitieren | melden

Zitat von 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.
Zitat
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!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
0815Coder
myCSharp.de - Member



Dabei seit:
Beiträge: 770

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

Themenstarter:

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
Spook
myCSharp.de - Member



Dabei seit:
Beiträge: 241
Herkunft: Esslingen a.N.

Bugfix: Referenz-Leak

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

Themenstarter:

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers