Work stealing
Work stealing (in some contexts also task stealing ) describes an efficient scheduling technique in computer science , with the help of which threads can be distributed to several processors . It was developed by Charles Leiserson and Robert D. Blumofe .
A scheduling algorithm must ensure that there are enough active threads that can be distributed to the processors. At the same time, too many active processes can lead to disproportionately high memory consumption . Furthermore, related threads should be executed on the same processor in order to keep the communication overhead low. These goals are partially contrary and must be balanced by the scheduler.
In contrast to work sharing , each processor in the work stealing algorithm actively tries to find threads whose calculations it can perform. This can always be necessary when a processed thread comes to an end or is paused due to data dependencies . In this case, this processor looks for a thread that is ready but not working from any other processor, which it then “steals”.
A more detailed description can be found in Blumofe et al., Albeit with a strong reference to the theoretical principles.
Work Stealing is used, for example, in the Cilk programming language or in a slightly modified form in the Threading Building Blocks library.