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.

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.

Quellen

• Scheduling multithreaded computations by work stealing, Robert D. Blumofe, Charles E. Leiserson