multithreaded lockfree job queue mit abbrechbaren Jobs
-
Wenn Deine Jobs so lange laufen, dass Du darüber nachdenken musst, sie abbrechen zu wollen: Warum um alles in der Welt möchtest Du dann eine lock free queue verwenden?
Ansonsten: Bevor Du irgend welche IDs generierst, mit denen Du dann das Flag zum Abbrechen ansprichst, nimm doch einfach einen shared_ptr auf einen bool und häng den an den Job und behalte eine Kopie des shared_ptr dort, wo Du abbrechen möchtest.
-
Es kann sehr lange dauern, es kann aber auch sehr schnell gehen und es können auch viele kleine Jobs nacheinander laufen. Die Jobs sind sehr heterogen. Abbruch vieler Jobs und Neustart der nächsten muss auf alle Fälle maximal flüssig funktionieren, da all das in einer Realtime-Anwendung laufen soll.
Was ist der Nachteil der IDs?
shared_ptrwirken für mich gerade wie der größere Overhead. Und falls ja, wäre thread-safety überhaupt schon geregelt? Bräuchte ich nicht eher einenshared_ptr<atomic<bool>>?
-
Naja, die Reservierung der IDs müsstest Du ja auch über alle threads synchronisieren um dann damit letztendlich wieder "nur" auf den passenden bool (atomic<bool>) zu kommen.
-
AddJob und AbortJob sind nicht thread-safe.
Und dass die Jobs nie gelöscht werden würde mich persönlich schon Sorgen machen.
Bzw. wenn du so wenige Jobs/Sekunde brauchst, dass es Wurst ist, dann sollte auch der Overhead einer Mutex Wurst sein.
-
hustbaer:
Wieso sind sie das nicht, könntest du das ausführen? Es gibt nur einen Thread, der Jobs hinzufügt, was vermutlich eine notwendige Ergänzung ist.Torsten:
Wo müsste ich denn die Reservierung der IDs denn synchronisieren, was ich nicht schon habe, wenn nur ein Thread Jobs posten kann?
-
Eisflamme schrieb:
Wo müsste ich denn die Reservierung der IDs denn synchronisieren, was ich nicht schon habe, wenn nur ein Thread Jobs posten kann?
Wenn Du wirklich nur einen thread hast, der Jobs erzeugt und nur einen hast, der Jobs konsumiert und wirklich Jobs nicht löschst, dann brauchst Du natürlich keine Synchronisation.
Aber: dann brauchst Du auch keine IDs. Die ID ergibt sich dann ganz einfach als `jobs.size()`. Dann brauchst Du aber auch keine lineare Suche über eine kontinuierlich wachsende Liste (dann reicht auch `jobs[id]`). Einfach eine Referenz (pointer) auf den Job (oder eben auf das Flag) zu behalten würde auch reichen. Und wenn das tatsächlich so funktioniert, dann brauchst Du wahrscheinlich auch überhaupt keine 2 threads.
-
Es können aber doch mehrere Jobs gequeued sein, wer sagt denn, dass ich immer nur den letzten abbrechen möchte? Ich finde das aus Nutzersicht komfortabel. Aber stimmt schon, ein Zeiger auf den Job ist noch besser!
Dass ich keine zwei Threads brauche, verstehe ich nicht. Ich brauche ja dennoch eine Jobqueue, die den Hauptthread nicht blockiert. Und SPSC ist doch häufig in Verwendung, da gibt es doch stets natürlich nur einen Producer und Consumer (wie der Name ja sagt) und das ist trotzdem im Threadumfeld aktiv. Klingt für mich etwas so, als würdest du dem die Berechtigung absprechen. Korrigiere mich bitte.
-
Eisflamme schrieb:
hustbaer:
Wieso sind sie das nicht, könntest du das ausführen? Es gibt nur einen Thread, der Jobs hinzufügt, was vermutlich eine notwendige Ergänzung ist.Ja, ich meinte wenn es mehrere Producer gibt. Dass es nur einen gibt war ja nicht klar (du hattest nur geschrieben dass es nur einen Worker gibt).
Bzw. nicht threads-safe bleiben sie trotzdem, nur so lange nur ein Thread in die Klasse rein-ruft, müssen sie es natürlich auch nicht sein.
-
Tut mir Leid, da hast du recht. Das einzige Indiz war, dass ich die
spsc_queuevon boost verwende, im Text hatte ich es ganz vergessen.
Fällt denn sonst ein Leak, ein Race o.ä. auf für mein SPSC-Setting? Bei multithreading checke ich lieber doppelt und dreifach.
-
Eisflamme schrieb:
Fällt denn sonst ein Leak, ein Race o.ä. auf für mein SPSC-Setting? Bei multithreading checke ich lieber doppelt und dreifach.
Ja natürlich. Du löschst nie Elemente aus `jobs`. Du must mal Deinen ungewöhnlichen use-case beschreiben. Auf der einen Seite muss es eine lock-free queue sein, weil ganz viele kleine Jobs durch die Queue gehen. Auf der anderen Seite können die Jobs aber auch sehr lang sein, so dass sie abbrechbar sein müssen. Dass ganze läuft aber nur kurz, sodass das Gesamtmenge der Jobs nicht groß wird.
Ich bin gespannt
-
Da sehe ich weder Leak noch Race, ein Job ist ja winzig.
Ist halt eine User-Application und der User ändert häufig Parameter. Bei einer Parameteränderung soll automatisch eine Berechnung angestoßen werden (und alte abgebrochen), sodass man stets die aktuellen Ergebniszahlen oder ein Ladesymbol sieht. Je nach Parametern kann eine Berechnung in 100-200 ms fertig sein (das könnte für lockfree natürlich immer noch kein Anreiz sein, da lasse ich mich gerne aufklären).
Oder der User ist mit seinen Parametern eben zufrieden, dann wartet er vielleicht auch bei komplexeren Settings eine längere Zeit auf die Ergebnisse.
Lockfree muss es prinzipiell nicht sein. Ich wollte nur die Performance optimieren. Die schlechte Lösung, die ich einmal hatte, war, dass für jeden Job ein neuer Thread gespawned wurde und da hat man bei mehreren Abbrüchen dann schon deutlich gemerkt, dass die gesamte Applikation sehr, sehr langsam wurde. Aber mit einem Workerthread oder Threadpool, der über Mutex und CV synchronisiert ist, wäre das wohl auch schnell.
Jedenfalls wollte ich die lockfree-Variante als eine Möglichkeit haben und damit gegen eine Variante mit Mutexes benchmarken - nur ist letztere Variante eben leichter zu implementieren, sodass das hier nicht Gegenstand des Threads ist.
Während der Zeit, die ein Benutzer das Programm nutzt, werde ich jedenfalls niemals so viele Jobs anhäufen, dass es Speicherprobleme gäbe, da ein Job selbst ja nur wenig Speicher benötigt. (Mittlerweile stört mich das jedoch auch, sodass ich hier ohnehin umstrukturieren werde, aber dennoch interessiert mich, ob das hier schon mal stabil laufen würde - mit meinen Annahmen)
-
Wenn ein Job immer den evtl. vorherigen abbricht, dann ist das Interface doch aber ein ganz anderes. Dann hast Du eigentlich noch nicht mal eine Queue. Ein Mutex, eine Condition Variables, ein thread, zwei Jobs und ein atomic< bool > sollten dann reichen, um das zu implementieren.
-
Ja, stimmt, nur habe ich verschiedene Arten von Jobs und davon können schon mehrere in der Queue sein, nur bricht jeder Jobtyp den vorherigen ab. Und wie gesagt, ich bin an einer möglichst lockfree Lösung interessiert (mit CV, Mutex ist es mMn ja eher einfach).
-
Das würde dann ggf. für mehrere "Queues" sprechen.
Warum um alles in der Welt möchtest Du eine lock free-Lösung? Du hast doch überhaupt keine contention auf der queue. Lock-free macht nur dann Sinn, wenn Du ganz viele konkurrierende Zugriffe auf etwas hast oder eine queue hast, die nie leer sein wird. In Deinem Fall verbrennt der Workerthread sinnfrei CPU beim Warten auf der queue. Dass mag die Latenz um einige nano-Sekunden verringern, nervt den Anwender aber, wenn andauernd der Lüfter des Rechners läuft.
-
Na ja, nach der ganzen (sehr aufschluss- und lehrreichen, übrigens, danke schon mal :)) Diskussion hier beschränkt sich die Frage nach einer solchen lockfree Lösung fast nur noch auf persönliches Interesse. Wie gesagt würde ich gerne benchmarken und dadurch sehen, was besser passt. Mittlerweile erledigt sich die Frage jedoch vermutlich fast von selbst.
Wieso empfiehlst du denn mehrere Queues für mehrere Jobtypen, wenn du eben noch von zwei Threads (ganz ohne Queue) für einen Jobtyp sprachst? Oder meinst du das damit?
-
Ich schrieb "Queue" in Anführungszeichen, damit ich für dieses Konstrukt, dass eben keine Queue ist keinen Namen finden muss (Queue != "Queue").
Wenn Du relativ wenig dieser Jobtypen hast, und diese unabhängig von einander laufen können, dann könntest Du eine relativ einfache "Queue" (oder job_executer oder single_job_queue) implementieren und diese dann halt für jeden Typen instanziieren.
