Work stealing

Work Stealing (in manchen Kontexten auch Task Stealing) bezeichnet in der Informatik eine effiziente Scheduling-Technik, mit deren Hilfe Threads auf mehrere Prozessoren verteilt werden können. Sie wurde von Charles Leiserson und Robert D. Blumofe entwickelt.

Ein Scheduling-Algorithmus muss sicherstellen, dass es genügend aktive Threads gibt, die auf die Prozessoren verteilt werden können. Gleichzeitig können zu viele aktive Prozesse zu unverhältnismäßig hohem Speicherverbrauch führen. Des Weiteren sollten verwandte Threads auf dem gleichen Prozessor ausgeführt werden, um den Kommunikationsaufwand klein zu halten. Diese Ziele sind zum Teil gegenläufig und müssen vom Scheduler ausgeglichen werden.

Im Gegensatz zu Work-Sharing bemüht sich jeder Prozessor im Work Stealing-Algorithmus aktiv um Threads, deren Berechnungen er ausführen kann. Dies kann immer dann nötig werden, wenn ein bearbeiteter Thread zu einem Ende kommt oder wegen Datenabhängigkeiten pausiert wird. In diesem Fall sucht sich dieser Prozessor bei einem beliebigen anderen Prozessor einen bereiten, aber nicht arbeitenden Thread, den er dann „entwendet“.

Eine genauere Beschreibung findet sich in Blumofe et al., wenngleich mit starkem Bezug auf die theoretischen Grundlagen.

Work Stealing wird zum Beispiel in der Programmiersprache Cilk oder in leicht abgewandelter Form in der Bibliothek Threading Building Blocks verwendet.

Literatur

• Robert D. Blumofe, Charles E. Leiserson: Scheduling multithreaded computations by work stealing. In: J. ACM. Band 46, Nr. 5. ACM, September 1999, ISSN 0004-5411, OCLC 643506322, ZDB-ID 6759-3, S. 720–748, doi:10.1145/324133.324234 (amerikanisches Englisch).