thread-safe producer/consumer queue
-
Ich schätze mal, dass die meisten, die mit Multithreading Kontakt hatten, auch irgendwann mal mit Message-Queues, Producer/Consumer Queues, Event Queues und derartigem zu tun hatten. Ich suche für mein Projekt grade eine möglichst lockfreie Implementierung für eine Eventqueue auf der Basis von Boost + MSVC's C++0x features.
Dabei bin ich mir auch noch nicht ganz sicher, wie das Interface auf Consumer-Seite am Ende aussehen soll: blocking "Event getEvent()", ggf. incl. "bool hasEvent()", oder Übergabe eines Handlers und abarbeiten aller vorliegenden Events oder wie auch immer.
Meine Rahmenbedingungen sind auf jeden Fall, dass es einen Producer und einen Cosumer geben soll - mehrere Consumer wären möglich, möchte ich aber erstmal nicht supporten.Wer hat Erfahrungen mit sowas gemacht?
-
Ich hatte gerade vor kurzem das Vergnügen, allerdings nicht mit C++. Programmiere die Queue selbst; es ist weniger Aufwand, als man meint.
Gib deiner Queue das normale Interface einer Queue; mach nichts spezielles draus. Für eine "lockfreie" Implementierung gibt es tausend Varianten. Ich würde empfehlen, mit Semaphore zu arbeiten. Du brauchst 3 davon: Einen Get-Semaphor, einen Put-Semaphor und einen Mutex für das Handling einer Critical Section.
Dann musst nur den Ausschluss korrekt programmieren: Beim Einfügen die Put-Semaphore acquiren und die Get-Semaphore releasen, beim Entfernen genau umgekehrt. Dazu jegliche Zugriffe auf den Inhalt selbst mit dem Mutex synchronisieren.
MfG
-
lockfrei: keine Ahnung. Geht das überhaupt? Also, auch ohne Spin-Locks?
Wenn jemand eine Lösung parat hat, die auch ohne Spin-Locks auskommt, würde mich das interessieren.
-
einen Producer und einen Cosumer
Gab es da nicht mal vor Jahren einen Artikel in DrDobbs. http://www.gotw.ca/publications/ (2008, #EC15), das Rad muss nicht neu erfunden werden. Andere Artikel auf der Seite zu Multitasking sind vielleicht auch interessant. Wenn dir Software transactual memory zur verfuegung steht (als Lib beispielsweise), dann ist die Implementation trivial (wie Simon Peyton-Jones mal anmerkte).
Geht das überhaupt?
Ja, das Zauberwort heisst compare-and-swap (oder xchange, ... ).
-
knivil schrieb:
Geht das [ohne Spin-Locks] überhaupt?
Ja. das Zauberwort heisst compare-and-swap (oder xchange, ... ).
Das ist mir natürlich ein Begriff. Die Frage ist nur: Kommst Du damit aus? (Edit: Was ich damit meine, kommst du ohne CAS-loops aus?)
Zitat aus dem einleitenden Teil von Herb Sutters Dr Dobbs Artikel:
[...] We'll use ordered atomic variables (C++0x atomic<>, Java/.NET volatile) directly instead of prefabricated mutexes, but functionally we're still writing spinlocks; we're just writing them by hand. Although this means it's not a purely "lock-free" or nonblocking algorithm, it's still quite concurrent because we'll arrange the code to still let multiple consumers and multiple producers make progress at the same time by arranging to do as much work as possible outside the small critical code region that updates the head and tail, respectively.
Hmm... klingt erstmal widersprüchlich zu Deiner Antwort. Aber vielleicht muss ich auch erst mal den ganzen Artikel lesen...
-
Soll ich dir jetzt die zig Paper raussuchen? Es geht. Was es bringt? Fraglich, bzw. anwendungsspezifisch. Beispielsweise hier: http://www.research.ibm.com/people/m/michael/podc-1996.pdf, habe das Paper aber nur ueberflogen. Ansonsten http://en.wikipedia.org/wiki/Non-blocking_algorithm unter External links.
Leider oeffnet sich der Artikel grad bei mir nicht, deswegen kann ich nicht genau nachsehen, was er mit "functionally" Spinlocks mein.
-
Lockfreies blocking getEvent()
Versteh ich nicht.
Ich habe für solche Geschiten eine sehr simple Queue mit
boost::condition_variable. Das ist wirklich sehr einfach. Ob das jetzt vielleicht ganz kompliziert noch vieel toller geht.. keine Ahnung.
-
"Lockfreies blocking" alias "busy waiting". Wenn eine Critical Section eben kaum belegt ist bzw. schnell wieder freigegeben wird, dann lohnt ein Mutex nicht. Das lock und unlock erzeugt sehr viel Overhead, da das Betriebssystem mit involviert ist.
-
krümelkacker schrieb:
Hmm... klingt erstmal widersprüchlich zu Deiner Antwort. Aber vielleicht muss ich auch erst mal den ganzen Artikel lesen...
Die Frage ist wie du ein Spin Lock definierst. Du brauchst eine Art synchronisation. Wenn du es über CAS machst, hast du dennoch das Problem, dass gerade jetzt die Daten von einem anderen thread geschrieben wurden - das erkennt CAS und schreibt die Daten nochmal. Jetzt kann es natürlich sein dass wieder ein anderer Thread dich unterbrochen hat, CAS erkennt das und schreibt die Daten neu...
Im Prinzip ist das ein Spin Lock - nur dass er idR nie spint. Deshalb nennt man es gemeinhin Lock Free. Da du nie lockst (im Sinne von Context Switch) aber dennoch musst du irgendwie die Daten synchronisieren.
Ein herkömmlicher SpinLock lockt ja ohne Context Switch - deshalb "Spin". Was CAS macht ist, einfach nochmal die Daten zu schreiben und zu verifizieren. Prinzipiell wartet man nie auf ein Ereignis wie bei einem herkömmlichen Lock sondern versucht solange ein Ergebnis zu erreichen bis man es geschafft hat.
PS:
Danke an knivil - da war ein Tipfehler drin der die Logik etwas verdreht hat.
-
knivil schrieb:
Soll ich dir jetzt die zig Paper raussuchen?
Das wär nett.
knivil schrieb:
Es geht.
Vielleicht. Vielleicht nicht. Nimm es nicht persönlich, dass ich die Wahrscheinlichkeit eines Irrtums Deinerseits höher als Du selbst einschätze. So groß ist die auch nicht wirklich. Aber sie ist nicht klein genug, dass ich Deine Aussage bei mir als Wahrheit abspeichern könnte.
knivil schrieb:
"Lockfreies blocking" alias "busy waiting".
Watt'n Scherzkeks! Reden wir etwa aneinander vorbei?!
Edit: Es scheint so.
-
Shade Of Mine schrieb:
Datei [..] Daten
Es handelt sich um Daten. Nicht, das jemand von dem Fluechtigkeitsfehler verwirrt wird.
-
Der Link zu knivils Artikel geht übrigens wenn man das Komma am Schluss weglässt.
-
krümelkacker schrieb:
knivil schrieb:
Geht das [ohne Spin-Locks] überhaupt?
Ja. das Zauberwort heisst compare-and-swap (oder xchange, ... ).
Das ist mir natürlich ein Begriff. Die Frage ist nur: Kommst Du damit aus? (Edit: Was ich damit meine, kommst du ohne loops aus?)
Zitat aus dem einleitenden Teil von Herb Sutters Dr Dobbs Artikel:
[...] We'll use ordered atomic variables (C++0x atomic<>, Java/.NET volatile) directly instead of prefabricated mutexes, but functionally we're still writing spinlocks; we're just writing them by hand. Although this means it's not a purely "lock-free" or nonblocking algorithm, it's still quite concurrent because we'll arrange the code to still let multiple consumers and multiple producers make progress at the same time by arranging to do as much work as possible outside the small critical code region that updates the head and tail, respectively.
Hmm... klingt erstmal widersprüchlich zu Deiner Antwort. Aber vielleicht muss ich auch erst mal den ganzen Artikel lesen...
Ich habe den Artikel nur mal quergelesen, ich denke das ist wirklich eine ganz normale Implementation mit Spin-locks, die nur versucht, etwas cleverer zu sein; so das möglicherweise die negativen Effekte (etwa dead-lock durch priority inversion) weniger wahrscheinlich sind.
Eine wirklich lockfreie Liste ist tatsächlich eine recht komplizierte Angelegenheit. Ohne die Hilfe von hazard pointern wird es noch schwieriger, und DWCS ist bekanntlich auf vielene Architekturen nicht verfügbar.