Moderne Computer haben mehrere Rechenkerne. Angenommen, es gibt genügend Verarbeitung, so dass jeder Kern kontinuierlich beschäftigt bleiben kann. Ihnen wird eine Warteschlange mit Rechenarbeitsaufgaben zugewiesen. Oder Threads, die vom Planer abgeschlossen werden müssen.
Während der Ausführung dieser Threads ist es möglich, neue Threads oder Arbeitselemente zu erzeugen. Dies sind separate Threads, die gleichzeitig verarbeitet werden können. Sie müssen möglicherweise Ergebnisse an die Laichprogramme zurückgeben oder auf unbestimmte Zeit vollständig getrennt bleiben. Typischerweise werden diese untergeordneten Threads demselben Verarbeitungskern wie der übergeordnete Thread zugewiesen.
All dies setzt voraus, dass alle Kerne beschäftigt sind. Dies geschieht, wenn keine Threads enden oder neue Threads mit der gleichen Rate oder schneller erzeugt werden, als vorhandene Threads enden. In der realen Welt ist die langfristige Arbeitsbelastung jedoch selten so einfach, insbesondere bei Endbenutzer-Computergeräten. Schließlich wird ein Verarbeitungskern wahrscheinlich alle zugewiesenen Aufgaben erledigen. Wenn dies passiert, anstatt im Leerlauf zu sitzen und potenzielle Leistung zu verschwenden, überprüft es stattdessen die Arbeitswarteschlangen der anderen Verarbeitungskerne und stiehlt ihnen ein Arbeitselement.
Vorteile und Nachteile
Arbeitsraub bedeutet, dass ein im Leerlauf befindlicher Verarbeitungskern aktiv nach Arbeit sucht, die er erledigen muss. Dies verhindert, dass ein möglicherweise großer Teil des gesamten Prozessors im Leerlauf bleibt, was hilfreich ist. Das Stehlen von Arbeit kann jedoch mit einigen Kosten verbunden sein. Beispielsweise muss der neue Verarbeitungskern wahrscheinlich alle relevanten Daten in seinen Cache-Speicher laden.
Dies kann einige Zeit dauern, insbesondere wenn es vom System-RAM angefordert werden muss, anstatt von einem gemeinsam genutzten Cache-Tier bedient zu werden. Es ist möglich, dass der ursprüngliche Prozessor dieses Arbeitselement in diesem Zeitrahmen hätte fortsetzen können, was zu einer schnelleren Gesamtausführung geführt hätte. Dies kann sogar der Fall sein, wenn der Verarbeitungskern, von dem das Arbeitselement gestohlen wurde, noch nie mit seiner Verarbeitung begonnen hatte. Einige zwischengespeicherte Werte können zwischen übergeordneten und untergeordneten Threads identisch sein.
Implementierungen
Mehrere Programmiersprachen haben Laufzeiten, die die Arbeit direkt auf dedizierten Prozessoren planen können. Das können beispielsweise die Programmiersprache Cilk, die Runtime Rust Tokio und die .Net Task Parallel Library. Alternativ kann das Betriebssystem für die Planung der tatsächlichen Prozessorzeit zuständig sein. Mit dem Programm werden einfach Aufgaben zu einem Pool von „Worker-Threads“ hinzugefügt, die selbst vom Betriebssystem geplant werden.
Dies geschieht in Systemen, in denen das Programm keinen dedizierten direkten Zugriff auf Verarbeitungskerne hat, sondern den Zugriff mit anderen Prozessen teilen muss. In diesem Szenario muss besonders darauf geachtet werden, dass ein Thread nicht wiederholt gestohlen wird, während er sich im Leerlauf befindet.
Es gibt verschiedene Ansätze, wie Arbeitselemente zum Diebstahl ausgewählt werden. Im ursprünglichen Konzept bestand der Ansatz darin, einen anderen zufälligen Kern auszuwählen. Wenn es ein oder mehrere Arbeitselemente in seiner Warteschlange hatte, nehmen Sie das letzte. Abhängig von der Präferenz, ob ein untergeordneter Prozess sofort vom ursprünglichen Prozessor ausgeführt wird. Oder wenn es in die Warteschlange des Prozessors verschoben wird und der übergeordnete Prozess weiterhin ausgeführt wird, wird der übergeordnete oder untergeordnete Thread gestohlen.
Alles lässt sich als Work Stealing zusammenfassen, eine Lastausgleichstechnik, die sicherstellt, dass die Wortlast gleichmäßig auf die verfügbaren Prozessoren verteilt wird. Auf diese Weise tun alle Prozessoren etwas, um zu helfen.
Fazit
Work Stealing ist ein Prozess, der in Multicore-CPUs automatisch abläuft. Jeder Kern hat eine Reihe von auszuführenden Aufgaben. Wenn ein Prozessor seine Aufgaben erledigt, stiehlt er dann eine andere Aufgabe aus der Warteschlange eines anderen Verarbeitungskerns. Dies hilft zu verhindern, dass der Prozessor einige Kerne im Leerlauf hat, während andere noch eine Warteschlange mit Aufgaben zu erledigen haben.