Work stealing (original) (raw)
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. 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 oder in leicht abgewandelter Form in der Bibliothek Threading Building Blocks verwendet.
| Property | Value |
|---|---|
| dbo:abstract | 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 oder in leicht abgewandelter Form in der Bibliothek Threading Building Blocks verwendet. (de) In parallel computing, work stealing is a scheduling strategy for multithreaded computer programs. It solves the problem of executing a dynamically multithreaded computation, one that can "spawn" new threads of execution, on a statically multithreaded computer, with a fixed number of processors (or cores). It does so efficiently in terms of execution time, memory usage, and inter-processor communication. In a work stealing scheduler, each processor in a computer system has a queue of work items (computational tasks, threads) to perform. Each work item consists of a series of instructions, to be executed sequentially, but in the course of its execution, a work item may also spawn new work items that can feasibly be executed in parallel with its other work. These new items are initially put on the queue of the processor executing the work item. When a processor runs out of work, it looks at the queues of the other processors and "steals" their work items. In effect, work stealing distributes the scheduling work over idle processors, and as long as all processors have work to do, no scheduling overhead occurs. Work stealing contrasts with work sharing, another popular scheduling approach for dynamic multithreading, where each work item is scheduled onto a processor when it is spawned. Compared to this approach, work stealing reduces the amount of process migration between processors, because no such migration occurs when all processors have work to do. The idea of work stealing goes back to the implementation of the Multilisp programming language and work on parallel functional programming languages in the 1980s. It is employed in the scheduler for the Cilk programming language, the Java fork/join framework, the .NET Task Parallel Library, and the Rust Tokio runtime. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Fork-join_computation.svg?width=300 |
| dbo:wikiPageID | 39335158 (xsd:integer) |
| dbo:wikiPageLength | 16890 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1063271772 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preemption_(computing) dbr:Multithreading_(software) dbr:Double-ended_queue dbr:Compiler dbr:Rust_(programming_language) dbr:Cilk dbr:Multilisp dbr:Continuation dbr:Process_migration dbr:Livelock dbr:Call_stack dbr:Functional_programming dbr:Parallel_computing dbr:Starvation_(computer_science) dbc:Processor_scheduling_algorithms dbr:Threading_Building_Blocks dbr:Tokio_(software) dbr:Cilk_Plus dbr:Locality_of_reference dbr:Lock_(computer_science) dbr:Expected_value dbr:Fork–join_model dbr:Java_(programming_language) dbr:Task_Parallel_Library dbc:Parallel_computing dbr:Directed_acyclic_graph dbr:OpenMP dbr:Operating_system dbr:Randomized_algorithm dbr:Multiprogramming dbr:Thread_pool dbr:Scheduling_(computing) dbr:Non-blocking_algorithm dbr:Software_library dbr:Processor_core dbr:Chip_multiprocessor dbr:Expected_time dbr:File:Fork-join_computation.svg |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Math dbt:Mono dbt:Mvar dbt:R dbt:Reflist dbt:Rp |
| dcterms:subject | dbc:Processor_scheduling_algorithms dbc:Parallel_computing |
| gold:hypernym | dbr:Strategy |
| rdf:type | dbo:VideoGame |
| rdfs:comment | 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. 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 oder in leicht abgewandelter Form in der Bibliothek Threading Building Blocks verwendet. (de) In parallel computing, work stealing is a scheduling strategy for multithreaded computer programs. It solves the problem of executing a dynamically multithreaded computation, one that can "spawn" new threads of execution, on a statically multithreaded computer, with a fixed number of processors (or cores). It does so efficiently in terms of execution time, memory usage, and inter-processor communication. (en) |
| rdfs:label | Work stealing (de) Work stealing (en) |
| owl:sameAs | freebase:Work stealing wikidata:Work stealing dbpedia-de:Work stealing https://global.dbpedia.org/id/2SER7 |
| prov:wasDerivedFrom | wikipedia-en:Work_stealing?oldid=1063271772&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Fork-join_computation.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Work_stealing |
| is dbo:wikiPageRedirects of | dbr:Work-stealing |
| is dbo:wikiPageWikiLink of | dbr:Double-ended_queue dbr:Load_balancing_(computing) dbr:Threading_Building_Blocks dbr:Tokio_(software) dbr:ParaSail_(programming_language) dbr:Fork–join_model dbr:Parallel_Extensions dbr:Paris_Kanellakis_Award dbr:Work-stealing |
| is foaf:primaryTopic of | wikipedia-en:Work_stealing |
