Work Stealing
Work Stealing is the dynamic load-balancing scheduling strategy where idle processor threads "steal" tasks from the queues of busy threads — enabling near-optimal parallel utilization for irregular workloads without static partitioning, achieving provably efficient O(T₁/P + T∞) expected time where T₁ is serial work, P is processor count, and T∞ is the critical path length.
How Work Stealing Works
1. Each thread maintains a double-ended queue (deque) of tasks.
2. When a thread spawns new tasks → pushed onto the bottom of its own deque.
3. When a thread finishes a task → pops next task from the bottom of its own deque (LIFO — locality).
4. When a thread's deque is empty → it becomes a thief and steals from the top of a random victim's deque (FIFO — steals largest tasks).
Why LIFO for Self, FIFO for Stealing?
- Self (LIFO): Most recently spawned tasks are small and cache-warm → good locality.
- Steal (FIFO): Oldest tasks are typically the largest (top of divide-and-conquer tree) → stealing one large task creates enough work to keep the thief busy.
- Combined: Minimizes steal frequency while maximizing work per steal.
Implementations
| System | Language | Work Stealing Variant |
|---|---|---|
| Cilk/Cilk Plus | C/C++ | Classic randomized work stealing |
| Intel TBB | C++ | Task arena with work stealing |
| Java ForkJoinPool | Java | RecursiveTask + deque stealing |
| Tokio (Rust) | Rust | Multi-threaded async work stealing |
| Go runtime | Go | Goroutine scheduler steals from local queues |
| .NET ThreadPool | C# | Work stealing queue since .NET 4 |
Theoretical Guarantees
- Expected running time: $E[T_P] = T_1/P + O(T_\infty)$.
- Expected steals: $O(P \cdot T_\infty)$ — steals are rare relative to total work.
- Space: $O(P \cdot S_1)$ where S₁ is serial stack space.
- These bounds are near-optimal and proven mathematically.
Practical Considerations
- Contention: Multiple thieves may target the same victim — lock-free deque implementations (Chase-Lev deque) minimize contention.
- Cache Effects: Stolen tasks may lack cache locality on the thief's core — cache-warm scheduling variants exist.
- Granularity: If tasks are too fine-grained, stealing overhead dominates — use sequential cutoffs for small tasks.
Work stealing is the dominant scheduling strategy for task-parallel runtimes — its combination of theoretical efficiency, practical simplicity, and automatic load balancing has made it the default scheduler in nearly every modern parallel computing framework.