Lock-Frei und doch Strom sparend?

[kristof]

Hi Leute,

ich experimentiere gerade etwas mit einem parallelen Job System herum. Mehrere Producer erzeugen Jobs die in einer Queue abgelegt, und dann von mehreren Consumern abgearbeitet werden. Streng genommen sind in meinem Fall die Producer und Consumer die gleichen Threads aber ich glaube das ändert nichts am Problem selbst.

Ohne wirklich schon so weit zu sein definitive Aussagen zum Verhalten des gesammten Systems machen zu können, erwarte ich allerdings, dass es Phasen geben wird in denen die Queue gut gefüllt ist und somit alle Consumer beschäftigt sind. Es wird allerdings auch Phasen geben, in denen über längere Zeit keine Jobs in der Queue sind.

Angenommen ich hätte nun eine Lock freie Queue um im gefüllten Fall die beste Performance zu erzielen. Gibt es eine Möglichkeit die Consumer schlafen zu legen, falls die Queue leer ist, ohne, dass dabei der schnelle Pfad (also gefüllte Queue) beeinträchtigt wird und gleichzeitig sicher gestellt wird, dass kein Job der in die Queue gepusht wird verpasst werden kann?

Mein erster Gedanke war natürlich eine Condition Variable die von den Producern notified wird wenn ein neuer Job in der Queue liegt.
Allerdings kann es nun passieren, dass ein Consumer eine leere Queue sieht und entscheidet sich schlafen zu legen. Genau in diesem Moment und noch bevor der Consumer tatsächlich schläft legt nun ein Producer einen neuen Job in die Queue und ruft notify auf. Erst jetzt legt sich der Consumer tatsächlich Schlafen und hat somit den neuen Job verpasst. Mir scheint also nichts anderes übrig zu bleiben als die Queue mit einem Mutex zu schützen...

Gibt es da noch andere Ansätze? Hat das Problem vielleicht einen Namen unter dem man Papers und so zu dem Thema finden könnte? Ich verwende C++, bin aber eher generell an Lösungen interessiert.

[Schrompf]

Ich hab das bei mir genau so gemacht, wie Du das beschrieben hast: Mutex ziehen (muss für die condition_variable eh sein), dann Queue checken, dann evtl. auf CV warten. Ob und wie das Ding unter Last performt, weiß ich aber noch nicht.

[Chromanoid]

Das ist jetzt aus der Java-Welt, aber vielleicht ist http://disruptor.googlecode.com/files/Disruptor-1.0.pdf / https://lmax-exchange.github.io/disruptor/ ganz interessant. https://github.com/LMAX-Exchange/disrup ... strategies sind deren Wartestrategien, aber die erkaufen sich die besseren Aufwachverhalten auch mit CPU-Cycles...

[kristof]

@Cromanoid Danke dir, das kannte ich noch nicht. Ganz interessant fand ich in dem PDF auch den Teil darüber dass bei einer komplett leeren Queue alle Teilnehmer gezwungen sind auf der gleichen Cache Line zu arbeiten, was zu viel teurer Kommunikation zwischen den Cores führen kann. Da hatte ich noch nicht drüber nachgedacht.
Ich hab noch nicht alles gelesen, aber die genannten Wartestrategien machen klar, dass es wohl immer auf ein Abwägen zwischen Performance und dem sparen von CPU Cycles hinaus läuft.

@Schrompf Ich werde wohl auch erstmal bei einer Condition Variable bleiben denke ich. Wenn ich merke, dass mich die Queue ausbremst kann ich ja immer noch nach effizienteren Lösungen suchen. So eine Lock freie Queue bringt schließlich auch einen ganzen Rattenschwanz an neuer Komplexität mit.

[Schrompf]

Den Rest kann ich nicht beurteilen, aber was die Lockfree Queue angeht, kann ich moodycamel::ConcurrentQueue empfehlen: scheiße schnell, ziemlich [1] stabil, nur ein einzelner Header.

[1] Der Autor selbst schreibt etwas von einem komischen Bug, der sehr selten auftritt, wenn er bulk schreibt und liest. Bei mir bisher nicht aufgetreten, aber wer weiß. Sollte man jedenfalls nicht ignorieren.

[NytroX]

Hi,

ich habe vor kurzem was ganz ähnliches gemacht, aber in Java.
Dort gibt es eine BlockingQueue, d.h. man macht ein "take()" auf die Queue und der call blockiert einfach solange, bis was in der Queue ist.
D.h. man kann mehrere Threads starten (Pool), die einfach Items von der Queue take()n und dann quasi dadurch automatisch so lange schlafen, bis es einen neuen Job gibt.
http://docs.oracle.com/javase/7/docs/ap ... Queue.html
Natürlich wäre das noch besser, wenn man es wait-free hinbekommt, wie bei der ConcurrentLinkedQueue.
Hier jedenfalls das Paper dazu, ist relativ Programmiersprachen-unabhängig: http://research.ibm.com/people/m/michael/podc-1996.pdf

Vielleicht findest du was ähnliches für C++, so wie das hier im MSDN (C#) (ein wenig älter):
http://blogs.msdn.com/b/toub/archive/20 ... ueues.aspx

Hier ist auch noch ein Talk von der CPPCON 2015 zum Thema "work stealing" (Youtube):https://www.youtube.com/watch?v=iLHNF7SgVN4
sourcecode, etc dazu gibts auch: https://github.com/cppcon/cppcon2015

Aber wie ihr schon gesagt habt, je nach Performance-Ansprüchen kann das Thema halt super komplex werden.
Vielleicht reicht es ja, wenn es etwas weniger performant, dafür aber wesentlich einfacher ist.
Also wie immer: Erst mal machen dass es geht, dann erst benchmarken und tunen, falls nötig :D

[Chromanoid]

@NytroX: Wenn es "nur" um die Ausführung von "Jobs" geht, wäre doch ein ExecutorService einfacher gewesen (siehe z.B. https://docs.oracle.com/javase/8/docs/a ... gPool-int-) oder hattest Du Spezialanforderungen?

[NytroX]

@Chromanoid: ja, hatte ich irgendwie, ich wollte Kontrolle über die Queue, daher hab ich einfach ein bissel rumgebastelt (bin eigentlich nicht so der Java-Typ)
Vielleicht liege ich da falsch, aber anscheinend kann der fixedThreadPool nicht von einer BlockingQueue mit fester Größe (z.B. ArrayBlockingQueue) lesen; ich wollte den Producer übers "put()" blockieren, wenn zu viel Zeugs kommt... OutOfHeapSpace ist echt uncool; Threads neu zu erzeugen auch; und damit fallen viele der Executors raus, wenn man nicht noch irgendeine Art Sicherung davorschaltet.
Aber wenn du (oder auch irgendjemand anderes) was besseres weißt, würde mich das sehr glücklich machen, immer her damit :D
Evtl. sollten wir aber nicht einfach diesen Thread dafür übernehmen 8-)

[Chromanoid]

Du kannst Dir auch eigene ExecutorServices etwas detaillierter mit ThreadPoolExecutor zusammenbasteln.

[NytroX]

Stimmt, cool, danke. Man lernt nie aus :-)
Sieht halt etwas kompliziert aus mit dem ganzen überladen fürs Customizing (meine Lösung hat mehr oder weniger nur 6 LOCs und ich musste nicht 10 Seiten API-Doku lesen), aber ich gehe mal davon aus, dass das dann vielleicht auch sinnvoller implementiert ist als bei mir (zumindest im Oracle/OpenJDK).

moodycamel::ConcurrentQueue sieht für C++ tatsächlich super-interessant aus.