2009-02-19 11 views
31

Ich muss in einer interaktiven Anwendung CPU-lastige Jobs mit mehreren Aufgaben verwalten. Genau wie Hintergrund ist meine spezifische Anwendung eine Schnittstelle des Technikdesigns. Wenn ein Benutzer verschiedene Parameter und Optionen an ein Modell ändert, werden mehrere Simulationen im Hintergrund ausgeführt, und die Ergebnisse werden nach ihrer Fertigstellung angezeigt, wahrscheinlich sogar, wenn der Benutzer noch Werte bearbeitet. Da die multiplen Simulationen eine variable Zeit benötigen (einige sind Millisekunden, manche 5 Sekunden, manche 10 Minuten), geht es darum, möglichst schnell eine Rückmeldung zu erhalten, aber oft abgebrochene Jobs, die zuvor gestartet wurden, aber jetzt nicht mehr benötigt werden der Änderungen des Benutzers haben sie bereits ungültig gemacht. Unterschiedliche Benutzeränderungen können unterschiedliche Berechnungen ungültig machen, so dass zu jeder Zeit 10 verschiedene Simulationen ausgeführt werden können. Die Simulationen A und B können separat berechnet werden, aber ich benötige ihre Ergebnisse für die Simulation C, so dass ich darauf warten muss, dass sowohl A als auch B vor dem Start C enden.Multithread-Jobwarteschlangenmanager

Ich fühle ziemlich sicher, dass die Code-Level-Methode, um diese Art von Anwendung zu behandeln, eine Art von Multithread-Auftragswarteschlange ist. Dazu gehören Funktionen zum Übergeben von Jobs zur Ausführung, Festlegen von Aufgabenprioritäten, Warten auf den Abschluss von Jobs, Festlegen von Abhängigkeiten (diesen Job ausführen, aber erst nachdem Job X und Job Y beendet wurden), Abbrechen von Teilmengen von Jobs, die bestimmten Kriterien entsprechen Jobs bleiben bestehen, legen die Anzahl der Worker-Threads und -Prioritäten fest und so weiter. Und Multiplattform-Unterstützung ist auch sehr nützlich.

Dies sind keine neuen Ideen oder Wünsche in Software, aber ich bin in der frühen Entwurfsphase meiner Anwendung, wo ich eine Auswahl treffen muss, welche Bibliothek für die Verwaltung solcher Aufgaben verwendet werden soll. Ich habe meine eigenen groben Thread-Manager in der Vergangenheit in C geschrieben (ich denke, es ist ein Übergangsritus), aber ich möchte meine Arbeit auf moderne Tools stützen, nicht auf meine eigenen vorherigen Hacks.

Der erste Gedanke ist zu OpenMP laufen, aber ich bin mir nicht sicher, was ich will. OpenMP eignet sich hervorragend zum Parallelisieren auf einem feinen Level, zum automatischen Ausrollen von Loops und ähnlichem. Während Multiplattform, dringt es auch mit #pragmas in Ihren Code ein. Aber meistens ist es nicht für die Verwaltung großer Aufgaben ausgelegt. Insbesondere können ausstehende Jobs abgebrochen oder Abhängigkeiten angegeben werden. Möglich, ja, aber es ist nicht elegant.

Ich bemerkte, dass Google Chrome uses such a job manager for even the most trivial tasks. Das Entwurfsziel scheint zu sein, den Benutzerinteraktion Thread so leicht und flink wie möglich zu halten, so dass alles, was asynchron hervorgebracht werden kann, sein sollte. Aus der Betrachtung der Chrome-Quelle scheint dies keine generische Bibliothek zu sein, aber es ist dennoch interessant zu sehen, wie das Design asynchrone Starts verwendet, um die Interaktion schnell zu halten. Das wird ähnlich wie das, was ich mache.

Es gibt noch andere Optionen:

Surge.Act: eine Boost-artige Bibliothek für Jobs definieren. Es baut auf OpenMP auf, erlaubt aber die Verkettung von Abhängigkeiten, was gut ist. Es scheint nicht so zu sein, als ob es einen Manager gibt, der befragt werden kann, Jobs abgesagt werden usw. Es ist ein abgestandenes Projekt, also ist es beängstigend, sich darauf zu verlassen.

Job Queue ist ziemlich nah an dem, was ich denke, aber es ist ein 5 Jahre alter Artikel, keine unterstützte Bibliothek.

Boost.threads hat eine schöne plattformunabhängige Synchronisation, aber das ist kein Jobmanager. POCO hat sehr saubere Designs für den Start von Aufgaben, aber auch nicht ein voller Manager für die Verkettung von Aufgaben. (Vielleicht unterschätze ich POCO allerdings).

So, während es Optionen gibt, bin ich nicht zufrieden und ich fühle den Drang, meine eigene Bibliothek wieder zu rollen. Aber ich würde lieber etwas verwenden, das bereits existiert.Selbst nach dem Suchen (hier auf SO und im Internet) habe ich nichts gefunden, was sich richtig anfühlt, obwohl ich mir vorstelle, dass dies eine Art von Werkzeug sein muss, das oft benötigt wird, also gibt es sicherlich eine Gemeinschaftsbibliothek oder zumindest gemeinsames Design. Auf SO gab es einige posts über job queues, aber nichts, das zu passen scheint.

Meine Post hier ist, Sie alle zu fragen, welche vorhandenen Werkzeuge ich vermisst habe, und/oder wie Sie Ihre eigene solche Multithread-Auftragswarteschlange gerollt haben.

Antwort

5

Ich rollte meine eigenen, basierend auf Boost.threads. Ich war ziemlich überrascht, wie viel Knall ich davon hatte, so wenig Code zu schreiben. Wenn Sie nicht etwas Vorgefertigtes finden, haben Sie keine Angst, selbst zu rollen. Zwischen Boost.threads und Ihrer Erfahrung seit dem Schreiben Ihres eigenen, könnte es einfacher sein, als Sie sich erinnern.

Für vorgefertigte Optionen, vergessen Sie nicht, dass Chromium ist sehr freundlich lizenziert, so dass Sie möglicherweise in der Lage, Ihre eigenen generischen Bibliothek um den Code zu rollen.

1

einen Blick auf boost::future nehmen (aber auch dieses discussion und proposal sehen), die für Parallelität (insbesondere wie eine wirklich schöne Grundlage sieht so scheint es, eine hervorragende Unterstützung zu bieten C-depends-on-A-und-B-Situationen).

Ich sah OpenMP ein bisschen, aber (wie Sie) war nicht überzeugt, dass es gut für alles außer Fortran/C numerischen Code funktionieren würde. Intels Threading Building Blocks sah für mich interessanter aus.

Wenn es dazu kommt, ist es nicht zu schwer roll your own auf boost :: thread. [Erklärung: ein Thread farm (die meisten Leute würden es einen Pool nennen) zieht Arbeit von einem thread-sicheren queue von Funktoren (Aufgaben oder Jobs). Beispiele finden Sie in den Artikeln tests und . Ich habe einige zusätzliche Komplikationen, um Aufgaben mit Prioritäten (optional) zu unterstützen, und der Fall, in dem das Ausführen von Aufgaben mehr Aufgaben in die Arbeitswarteschlange bringt (das macht es ein bisschen problematischer, zu wissen, wann alle Arbeiten tatsächlich abgeschlossen sind). sind diejenigen, die mit dem Fall umgehen können). Könnte Ihnen trotzdem ein paar Ideen geben.]

+0

Excellent. boost :: future sieht POCOs ActiveResults (http://pocoproject.org/poco/docs/Poco.ActiveResult.html) sehr ähnlich. Auch dies ist kein Manager für die Arbeitswarteschlange, aber trotzdem ein großartiges Werkzeug. Boost: Thread-Basis fühlt sich wie das beste Low-Level-Toolkit für die Erstellung eines benutzerdefinierten Managers an. –

3

Wäre etwas wie threadpool für Sie nützlich? Es basiert auf boost :: threads und implementiert im Grunde eine einfache Task-Warteschlange, die Worker-Funktionen an die gepoolten Threads weitergibt.

2

Sie möchten vielleicht Flow-Based Programming betrachten - es basiert auf Datenabschnitten, die zwischen asynchronen Komponenten strömen. Es gibt Java und C# Versionen des Treibers sowie eine Reihe von vorcodierten Komponenten. Es ist intrinsisch Multithread - in der Tat ist der einzige single-threaded Code innerhalb der Komponenten, obwohl Sie Timing-Einschränkungen zu den Standard-Zeitplanungsregeln hinzufügen können. Auch wenn es zu feinkörnig sein kann für das, was Sie brauchen, kann es hier Dinge geben, die Sie verwenden können.

0

Ich weiß nicht, ob Sie nach einer C++ - Bibliothek suchen (was ich denke, Sie sind), aber Doug Leas Fork/Join-Framework für Java 7 ist ziemlich raffiniert und macht genau das, was Sie wollen. Sie könnten es wahrscheinlich in C++ implementieren oder eine vordefinierte Bibliothek finden.

Mehr Infos hier: http://artisans-serverintellect-com.si-eioswww6.com/default.asp?W1

17

Wir hatten unser eigenes Job-Queue-System aufzubauen Anforderungen gerecht zu werden ähnlich wie bei Ihnen (UI-Thread immer innerhalb 33ms reagieren muss, können Aufträge von 15-15000ms laufen), weil es wirklich Es war nichts da draußen, das unseren Bedürfnissen entsprach, geschweige denn war es performant.

Leider ist unser Code über proprietäre gesetzlich geschützt wird, aber ich kann Ihnen einige der wichtigsten Merkmale geben:

  • Wir starten einen Thread pro Kern zu Beginn des Programms. Jeder zieht Arbeit aus einer globalen Jobwarteschlange. Jobs bestehen aus einem Funktionsobjekt und einem Glob der zugehörigen Daten (wirklich eine Ausarbeitung auf einem func_ptr und void *). Thread 0, die schnelle Client-Schleife, darf nicht an Jobs arbeiten, aber die anderen greifen wie sie können.
  • Die Jobwarteschlange selbst sollte eine locklose Datenstruktur sein, z. B. lock-free singly linked list (Visual Studio comes with one). Vermeiden Sie die Verwendung eines Mutex; Die Konkurrenz für die Warteschlange ist überraschend hoch, und Mutexe zu greifen ist teuer.
  • Packen Sie alle notwendigen Daten für den Job in das Job-Objekt selbst - vermeiden Sie Zeiger aus dem Job zurück in den Haupt-Heap, wo Sie mit Konflikten zwischen Jobs und Sperren und all diesen anderen langsam beschäftigen müssen nerviges Zeug. Zum Beispiel sollten alle Simulationsparameter in den lokalen Datenblock des Jobs gehen. Die Ergebnisstruktur muss offensichtlich etwas sein, das den Job überdauert: Sie können damit umgehen, indem Sie entweder a) die Jobobjekte hängen lassen, nachdem sie ausgeführt wurden (so dass Sie ihre Inhalte aus dem Hauptthread verwenden können), oder b) Zuweisen einer Ergebnisstruktur speziell für jeden Job und Einfügen eines Zeigers in das Datenobjekt des Jobs. Auch wenn die Ergebnisse selbst nicht im Job leben, gibt dies dem Job exklusiven Zugriff auf seinen Ausgabespeicher, so dass Sie nicht mit Sperren zu kämpfen brauchen.

  • Eigentlich vereinfache ich ein bisschen darüber, da wir genau choreographieren müssen, welche Jobs auf welchen Cores laufen, so dass jeder Core seine eigene Job-Queue bekommt, aber das ist wahrscheinlich unnötig für dich.

+0

würde es Ihnen etwas erklären, "genau zu choreografieren welche Jobs auf welchen Cores laufen, also bekommt jeder Core seine eigene Job Queue", was ist der Grund, ist es für Prozessor Affinität (https://en.wikipedia.org/wiki/Prozessoraffinität)? – athos

+1

@athos Es ist umgekehrt: Prozessoraffinität sagt uns, welcher Job auf welchem ​​Kern läuft. Wir müssen die Dinge genau choreographieren, so dass die beiden Echtzeit-Threads kontinuierlich auf ihren Kernen ohne Vorkaufsrisiko laufen können, während andere Jobs bestimmten Hardware-Cores zugewiesen werden, um Cache-Lokalität, Hyperthreading-Effizienz usw. zu maximieren eine feste Hardware-Plattform kann so sehr eng optimieren. – Crashworks

4

Microsoft arbeitet an einer Reihe von Technologien für die nächste Version von Visual Studio 2010 namens Concurrency Runtime, die Parallel Pattern Library und die Asynchronous Agents Library, die wahrscheinlich helfen wird. Die Concurrency Runtime bietet eine richtlinienbasierte Planung, dh Sie können mehrere Scheduler-Instanzen verwalten und erstellen (ähnlich wie Thread-Pools, aber mit Affinitisierung und Load Balancing zwischen Instanzen), die Parallel Pattern Library bietet task-basierte Programmierung und parallele Schleifen mit einer STL Programmiermodell. Die Agents-Bibliothek bietet ein akteursbasiertes Programmiermodell und unterstützt das Erstellen von gleichzeitigen Datenfluss-Pipelines, d. H. Das Verwalten der oben beschriebenen Abhängigkeiten. Leider ist dies noch nicht veröffentlicht, so dass Sie es auf unserer team blog lesen können oder sehen Sie sich einige der Videos on channel9 an, es gibt auch ein sehr großes CTP, das ebenfalls zum Download zur Verfügung steht.

Wenn Sie heute nach einer Lösung suchen, sind Intels Thread Building Blocks und Boosts Threading-Bibliothek beide gute Bibliotheken und ab sofort verfügbar. JustSoftwareSolutions hat eine Implementierung von std :: thread veröffentlicht, die mit dem C++ 0x-Entwurf übereinstimmt, und natürlich ist OpenMP weit verbreitet, wenn Sie eine feinkörnige, loopbasierte Parallelität betrachten. Die wirkliche Herausforderung, auf die andere Leute bereits hingewiesen haben, ist die korrekte Identifizierung und Zerlegung von Aufgaben in gleichzeitig ausführbare Aufgaben (dh kein ungeschützter gemeinsamer Zustand), Verständnis der Abhängigkeiten zwischen ihnen und Minimierung der Konflikte, die bei Engpässen auftreten können (ob der Engpass ist protecting shared state oder sicherzustellen, dass die Dispatch-Schleife einer Arbeitswarteschlange gering oder frei von Sperren ist ... und dies ohne Planung von Implementierungsdetails, die in den Rest Ihres Codes eindringen.

-Rick

1

Es gibt viele verteilte Ressourcen-Manager ist. Die Software, die fast alle Ihre Anforderungen erfüllt, ist Sun Grid Engine. SGE wird auf einigen der weltweit größten Supercomputer eingesetzt und befindet sich in aktiver Entwicklung.

Es gibt auch ähnliche Lösungen in Torque, Platform LSF und Condor.

Es klingt, als ob Sie Ihre eigenen rollen möchten, aber es gibt viele Funktionen in allen oben genannten.