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.