Share via

Work-Stealing in .NET 4.0

  • Article

There is some truly amazing support for parallel programming in .NET 4.0.  One of the compelling new features of the Thread Pool in .NET 4.0 is work-stealing, which allows work to be processed by worker threads more efficiently. 

First of all, in addition to the global queue, there are local queues for each worker thread. 

WorkStealing1

Let's say that the main program thread generated 2 tasks, which are added to the global queue. 

WorkStealing2

Then each worker thread can take a task to process. 

WorkStealing3

Then, suppose that Task 2 spawns three subtasks: Task 3, Task 4, and Task 5.  These tasks are placed on the local queue of Worker Thread 1. 

WorkStealing4

Next, assume Worker Thread 1 completes Task 2.  It looks at its local queue, and takes the last task (Task 5) off to process.  It purposefully takes the last task, the point being that the last task might still be in the cache, while it is likely that the first task (Task 3) is out of the cache.  Hence, there are performance improvements in processing local queues in a LIFO order. 

WorkStealing5

Now, assume Worker Thread p completes Task 1.  It looks first at its local queue, and there are no tasks there.  Then it looks at the global queue...no tasks there either.  Finally, it looks at other local queues.  This is the concept of work-stealing: it can "steal" tasks from those queues.  So Worker Thread p would take Task 3 to process. 

Note also that it steals work from the top of the queue (taking the first in), while Worker Thread 1 is processing from the bottom of the queue (taking the last in).  That is to reduce contention.  It also optimizes for caching: Worker Thread 1 is taking the tasks that are likely still in its cache, and Worker Thread p is taking the tasks that are least likely to be in Worker Thread 1's cache. 

WorkStealing6

Finally, if Task 3 had further subtasks, they would be placed on Worker Thread p's local queue. 

WorkStealing7

To learn more about the support for parallel programming in .NET 4.0, check out Daniel Moth's talk from PDC 2008 at https://channel9.msdn.com/pdc2008/TL26/.  It was one of my top 2 favorite talks from PDC last year...Daniel is an amazing presenter and the functionality is just so cool. 

Other Resources on Work-Stealing Queues:

https://www.danielmoth.com/Blog/2008/11/new-and-improved-clr-4-thread-pool.html

https://www.bluebytesoftware.com/blog/2008/08/12/BuildingACustomThreadPoolSeriesPart2AWorkStealingQueue.aspx

Comments

  • Anonymous
    July 01, 2009
    Quite interesting !!! Excellent Write up. Thank you Raghuraman

  • Anonymous
    June 24, 2010
    Ha Ha! Jennifer you make all this sound so simple :) Wonderful post.

  • Anonymous
    June 20, 2011
    Thank U ... this explain work stealing in a very simple manner...!!! n understandable..!!

  • Anonymous
    November 28, 2012
    Great abstraction, it really helps.

  • Anonymous
    October 12, 2014
    Thanks a lot for simplified explanation. Great job.