Work stealing

Work stealing is a scheduling strategy for multithreaded programs in parallel computing. It lets a dynamically multithreaded computation, one that can spawn new threads of execution, run efficiently on a machine with a fixed number of processors or cores, in terms of execution time, memory use and communication between processors. Each processor keeps a queue of work items; new items spawned by a running item go on that processor's own queue, and a processor that runs out of work looks at the queues of other processors and steals items from them. This spreads the scheduling work over idle processors, so no scheduling overhead occurs while all processors are busy. It contrasts with work sharing, where each item is assigned to a processor when it is spawned, and it reduces process migration compared with that approach. The idea goes back to the Multilisp implementation and parallel functional programming work in the 1980s, and it is used in the scheduler of the Cilk language, the Java fork/join framework, the .NET Task Parallel Library and the Rust Tokio runtime.