Ich arbeite an einem einfachen Job-Threading-Framework, das dem in id Tech 5 Herausforderungen . Auf der grundlegendsten Ebene habe ich eine Reihe von Listen von Jobs, und ich möchte diese Liste über eine Reihe von CPU-Threads planen (mit einem Standard-Thread-Pool für die eigentliche Dispatching). Allerdings frage ich mich, wie dieses Signal / warten Zeug Innerhalb einer Warteliste kann effizient implementiert werden. Wie ich es verstehe, blockiert das Wait-Token die Ausführung der Liste, wenn das Signal-Token nicht ausgeführt wurde. Dies bedeutet implizit, dass alles bevor ein Signal beendet werden muss bevor das Signal angehoben werden kann. Nehmen wir an, wir haben eine Liste wie folgt:
%Vor%dann kann das Dispatching so gehen:
%Vor% Allerdings ist das nicht so einfach, wie es scheint, da ich einige Listen angegeben habe, müsste ich einige davon zwischen ready und waiting verschieben und auch speziellen Code haben, um alle Jobs vor einem Signal zu sammeln und etwas auf sie schreiben, so dass sie das Signal genau dann auslösen können, wenn sie alle beendet sind (zum Beispiel, dass es nicht mehr möglich ist, Jobs zur Liste hinzuzufügen, während wie folgt ausgeführt wird Signale greifen auf die zuvor eingefügten Jobs zu.)
Gibt es eine "Standard" -Möglichkeit, dies effizient zu implementieren? Ich frage mich auch, wie ich die Ausführung der Jobliste am besten planen kann. Momentan ergreift jeder Kern eine Jobliste und plant alle Jobs, was eine ziemlich gute Skalierung ergibt (für 32k Jobs à 0,7 ms bekomme ich 101%, was ich denke liegt zum Teil an der Tatsache, dass die Single-Thread-Version manchmal auf verschiedene Kerne geplant wird.)
Dies ist ein relativ geradliniger Scheduling-Algorithmus. Ein paar Probleme erscheinen auf den ersten Blick schwierig, sind es aber wirklich nicht (Signal / Warte- und Cache-Lokalität). Ich werde die Techniken erklären, dann einen Code geben, den ich geschrieben habe, um die Konzepte zu illustrieren, und dann einige abschließende Anmerkungen zum Tuning machen.
Zu verwendende Algorithmen
Das Signal zu handhaben / effizient zu warten, erscheint zunächst schwierig, erweist sich aber als äußerst einfach. Da Signal- / Warte-Paare nicht verschachteln oder sich überlappen können, können wirklich nur zwei zu einem bestimmten Zeitpunkt erfüllt sein. Um die Buchhaltung zu führen, genügt es, einen "CurrentSignal" -Zeiger auf das letzte nicht erfüllte Signal zu legen.
Es ist auch relativ einfach, sicherzustellen, dass Cores nicht zu oft zwischen Listen hin- und herspringen und dass eine gegebene Liste nicht von zu vielen Cores geteilt wird: Jeder Core nimmt Jobs aus der gleichen Liste, bis er blockiert und dann zu eine andere Liste. Um zu verhindern, dass sich alle Kerne in einer einzigen Liste zusammenschließen, wird für jede Liste ein WorkerCount geführt, der angibt, wie viele Kerne ihn verwenden, und die Listen sind so organisiert, dass Kerne Listen mit weniger Arbeitern auswählen.
Das Sperren kann einfach gehalten werden, indem Sie nur den Scheduler oder die Liste sperren, an der Sie gerade arbeiten, niemals beides.
Sie haben Bedenken bezüglich des Hinzufügens von Jobs zu einer Liste geäußert, nachdem die Ausführung der Liste bereits begonnen hat. Es stellt sich heraus, dass es fast trivial ist, dies zu unterstützen: Es genügt ein Aufruf von der Liste an den Scheduler, wenn ein Job zu einer Liste hinzugefügt wird, die gerade abgeschlossen ist, sodass der Scheduler den neuen Job planen kann.
Datenstrukturen
Hier sind die grundlegenden Datenstrukturen, die Sie benötigen:
%Vor%Beachten Sie, dass die Signalpunkte für eine bestimmte Jobliste am einfachsten getrennt von der tatsächlichen Liste der Jobs gespeichert werden.
Scheduler-Implementierung
Der Scheduler verfolgt Joblisten, ordnet sie Kernen zu und führt Jobs aus den Joblisten aus.
AddList fügt dem Scheduler einen Job hinzu. Es muss in die Warteschlange "Bereit" oder "Blockiert" gesetzt werden, je nachdem, ob es irgendwelche Aufgaben zu erledigen hat (dh, ob ihm bereits Jobs hinzugefügt wurden), also rufen Sie einfach UpdateQueues auf.
%Vor%UpdateQueues zentralisiert die Warteschlangenaktualisierungslogik. Beachten Sie den Algorithmus zum Auswählen einer neuen Warteschlange und auch die Benachrichtigung zu leeren Kernen, wenn Arbeit verfügbar wird:
%Vor%DoWork ist eine normale Scheduler-Arbeit, außer: 1. Es wählt die Jobliste mit den wenigsten Arbeitern aus, 2. Es arbeitet Jobs von einer gegebenen Jobliste bis es nicht mehr möglich ist und 3. Es speichert sowohl den JobIndex als auch die Job, sodass die Jobliste den Abschlusszustand (Implementierungsdetail) leicht aktualisieren kann.
%Vor%JobList-Implementierung
Die JobList verfolgt, wie die Signale / Wartezeiten mit den Jobs vermischt werden und verfolgt, welche Signal / Warte-Paare bereits alles vor ihrem Signalpunkt abgeschlossen haben.
Der Konstruktor erstellt einen Dummy-Signalpunkt, um Jobs hinzuzufügen. Dieser Signalpunkt wird zu einem realen Signalpunkt (und ein neuer Dummy wird hinzugefügt), wenn ein neues "Signal" hinzugefügt wird.
%Vor%AddJob fügt der Liste einen Job hinzu. Es wird im SignalPoint als unvollständig markiert. Wenn der Job tatsächlich ausgeführt wird, wird IncompleteCount desselben SignalPoint dekrementiert. Es ist auch notwendig, dem Scheduler mitzuteilen, dass sich die Dinge möglicherweise geändert haben, da der neue Job sofort ausführbar sein könnte. Beachten Sie, dass der Scheduler aufgerufen wird, nachdem die Sperre für "this" aufgehoben wurde, um Deadlock zu vermeiden.
%Vor%AddSignal und AddWait fügen Signale hinzu und warten auf die Jobliste. Beachten Sie, dass AddSignal tatsächlich einen neuen SignalPoint erstellt und AddWait nur die Wartepunktinformationen im zuvor erstellten SignalPoint ausfüllt.
%Vor%Die Ready-Eigenschaft bestimmt, ob die Liste für weitere ihr zugeordnete Kerne bereit ist. Es können zwei oder drei Kerne in der Liste arbeiten, ohne dass die Liste "bereit" ist, wenn der nächste Job auf ein Signal wartet, bevor er starten kann.
%Vor%GetNextReadyJob ist sehr einfach: Wenn wir bereit sind, einfach den nächsten Job in der Liste zurückgeben.
%Vor%MarkJobCompleted ist wahrscheinlich das interessanteste von allen. Aufgrund der Struktur der Signale und Wartezeiten befindet sich der aktuelle Job entweder vor CurrentSignal oder zwischen CurrentSignal und CurrentSignal.Next (wenn es sich nach dem letzten tatsächlichen Signal befindet, wird es am Ende zwischen CurrentSignal und dem Dummy-SignalPoint gezählt) ). Wir müssen die Anzahl der unvollständigen Jobs reduzieren. Möglicherweise müssen wir auch zum nächsten Signal übergehen, wenn diese Zahl auf Null geht. Natürlich übergeben wir niemals den Dummy SignalPoint am Ende.
Beachten Sie, dass dieser Code keinen Aufruf von Scheduler.UpdateQueue hat, da wir wissen, dass der Scheduler GetNextReadyJob in nur einer Sekunde aufrufen wird und wenn er false zurückgibt, wird er trotzdem UpdateQueue aufrufen.
%Vor%Optimierung basierend auf Listenlänge, Schätzungen der Joblänge usw.
Der obige Code berücksichtigt nicht, wie lange die Joblisten sind. Wenn es also hundert winzige Joblisten und eine große gibt, ist es möglich, dass jeder Kern eine eigene kleine Jobliste erstellt und sich dann alle versammeln auf dem großen, was zu Ineffizienz führt. Dies kann gelöst werden, indem Ready [] ein Array von Prioritätswarteschlangen auf (joblist.Jobs.Count - joblist.NextJobIndex) priorisiert, wobei jedoch die Priorität nur in normalen UpdateQueue-Situationen aus Effizienzgründen aktualisiert wird.
Dies könnte noch ausgefeilter werden, indem eine Heuristik erstellt wird, die die Anzahl und den Abstand von Signal / Warte-Kombinationen berücksichtigt, um die Priorität zu bestimmen. Diese Heuristik würde am besten durch Verwendung einer Verteilung von Jobdauern und Ressourcennutzung abgestimmt.
Wenn einzelne Jobdauern bekannt sind oder wenn für sie gute Schätzungen verfügbar sind, kann die Heuristik die geschätzte verbleibende Dauer anstelle der Listenlänge verwenden.
Schlussnotizen
Dies ist eine ziemlich Standardlösung für das Problem, das Sie präsentieren. Sie können die Algorithmen verwenden, die ich angegeben habe, und sie werden funktionieren, einschließlich der Sperrung, aber Sie können den oben beschriebenen Code aus mehreren Gründen nicht zusammenstellen:
Es ist eine verrückte Mischung aus C ++ und C # -Syntax. Ich fing ursprünglich an, in C # zu schreiben, änderte dann einen Haufen der Syntax in C ++ - Stil, da ich dachte, dass das wahrscheinlicher ist, was Sie für solch ein Projekt verwenden würden. Aber ich bin in ein paar C # -Ismen gegangen. Zum Glück kein LINQ ;-).
Die LinkedList-Details haben einige Handbewegungen. Ich gehe davon aus, dass die Liste First, Last, Add und Remove ausführen kann und dass Einträge in der Liste sowohl Zurück als auch Weiter möglich sind. Aber ich habe die tatsächliche API nicht für irgendeine echte verknüpfte Listenklasse verwendet, die ich kenne.
Ich habe es nicht kompiliert oder getestet. Ich garantiere, dass da irgendwo ein Fehler steckt.
Unterm Strich: Sie sollten den obigen Code als Pseudocode behandeln, obwohl er wie der echte McCoy aussieht.
Viel Spaß!
Wenn Sie Zugriff auf ein Arbeitsstehling-Framework in Ihrer Umgebung haben (z. B. Cilk , wenn Sie sich in Ihrer Umgebung befinden C, oder das fork / join-Framework von Doug Lea in Java), kann man leicht ein einfaches bekommen und saubere Lösung (im Vergleich zu Low-Level-Ad-hoc-Versuchen, die Sie wahrscheinlich tun müssen, wenn Sie so etwas nicht verwenden können), die Ihnen einen automatischen Lastausgleich und eine gute Datenlokalität bieten.
Hier ist eine Beschreibung einer Lösung auf hoher Ebene: Sie starten einen Thread pro Kern. Jedem wird eine Liste zugewiesen, bis sie erschöpft sind (viele Möglichkeiten, dies zu tun - das ist die Aufgabe von sehr guten gleichzeitigen Warteschlangenmechanismen, und das ist ein Grund, warum Sie Do-it-yourself-Lösungen vermeiden möchten, wenn möglich). Jeder Arbeiter durchläuft die Zeilen der Listen nacheinander:
- Zwei Warteschlangen werden verwaltet, eine für diese Jobs vor einem signal -Token und eine oder mehrere danach.
- Wenn ein Job angetroffen wird, wird er gegabelt und der entsprechenden Warteschlange hinzugefügt (abhängig davon, ob wir ein signal -Token gesehen haben oder nicht)
- Wenn ein wait -Token gefunden wird, verbinden wir alle Jobs vor dem Signal (das ist die Semantik, die Sie beschreiben, wenn ich sie richtig verstanden habe). Beachten Sie, dass ich im Code helpJoin() verwende,
es bedeutet, dass der Thread tatsächlich helfen wird (indem er gabelförmige Aufgaben öffnet und sie ausführt, bis die Verknüpfung fortfahren kann).
"Fork" bedeutet, dass die Aufgabe in eine Thread-lokale Warteschlange gestellt wird, die später entweder vom Thread selbst ausgeführt wird, oder sie kann von einem anderen Thread gestohlen werden, der nach etwas Arbeit sucht.
Zu Illustrationszwecken ist hier eine 80-Zeilen-Simulation dieses Szenarios unter Verwendung des oben erwähnten Java-Frameworks. Es erstellt so viele Threads wie verfügbare Cores und einige Listen und startet deren Ausführung. Beachten Sie, wie einfach die run () -Methode ist - während sie immer noch die Vorteile des Load Balancing bietet und dass Threads meistens Aufgaben von ihrer eigenen Liste ausführen, es sei denn, sie haben keine Arbeit mehr und beginnen zu stehlen, um einige zu bekommen. Natürlich, wenn Sie nicht in Java oder C sind, müssten Sie ein ähnliches Framework finden, aber die gleichen Kernideen würden Ihren Code unabhängig von der Sprache in ähnlicher Weise vereinfachen.
%Vor%Tags und Links multithreading performance parallel-processing scalability