imported>YMS: Änderung 259907581 von ~2025-67258-9 rückgängig gemacht; mit der Hilfe dieser Technik können Threads verteilt werden

2025-09-20T19:56:23Z

Änderung 259907581 von ~2025-67258-9 rückgängig gemacht; mit der Hilfe dieser Technik können Threads verteilt werden

Neue Seite

'''Work Stealing''' (in manchen Kontexten auch ''Task Stealing'') bezeichnet in der [[Informatik]] eine effiziente [[Scheduling]]-Technik, mit deren Hilfe [[Thread (Informatik)|Threads]] auf mehrere [[Prozessor]]en 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 [[Arbeitsspeicher|Speicherverbrauch]] führen. Des Weiteren sollten verwandte Threads auf dem gleichen Prozessor ausgeführt werden, um den [[Interprozesskommunikation|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 [[Daten]]abhä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 ==
* {{Literatur
|Autor=Robert D. Blumofe, Charles E. Leiserson
|Titel=Scheduling multithreaded computations by work stealing
|Sammelwerk=J. ACM
|Band=46
|Nummer=5
|Verlag=ACM
|Ort=New York NY
|Datum=1999-09
|ISSN=0004-5411
|Seiten=720–748
|Sprache=en-US
|DOI=10.1145/324133.324234
|OCLC=643506322
|ZDB=6759-3}}

[[Kategorie:Betriebssystemtheorie]]
[[Kategorie:Parallelverarbeitung]]

Work stealing - Versionsgeschichte

imported>YMS: Änderung 259907581 von ~2025-67258-9 rückgängig gemacht; mit der Hilfe dieser Technik können Threads verteilt werden