Work Stealing
Work stealing lets idle worker threads pull tasks from busy workers local queues, keeping all cores busy without global lock contention on a single shared queue.
Definition
Work stealing is a scheduling strategy where each worker owns a local deque of tasks: it pushes and pops at one end, while starving workers steal from the other end of loaded queues. Contention concentrates on steals, which are rare when load is balanced, replacing the global-queue lock that serializes all submissions.
Context and scope
The scheduler core of ForkJoinPool, Tokio, Go runtime cousins, and parallel runtimes. Explains per-worker queues in async executors and why task size affects stealing efficiency.
Common misconceptions
- Work stealing guarantees perfect balance — it statistically approaches balance; skewed task sizes still leave gaps
- It replaces all synchronization — locks remain for queue ends; the design minimizes contention rather than removing coordination
- Only CPU-bound workloads benefit — it balances any deferred computation, including async task continuations and parallel garbage collection work
Anti-patterns
- Submitting giant tasks that cannot split, leaving thieves with nothing to steal during long stretches
- Tuning worker counts far above cores and multiplying steal overhead without adding capacity
- Assuming FIFO fairness — stealing changes execution order by design; strict ordering requirements need different machinery
Related concepts
Related examples
Authoritative source
What it is
A single shared task queue makes every submit and every take contend on one lock. Work stealing decentralizes: each worker has its own deque, operates on the local end normally, and only when empty reaches into another worker deque from the far end.
How it works
The local end is accessed only by the owner — cheap, no contention. The steal end is touched only by desperate others — rare under decent balance. Victim selection scans queues randomly or by size to avoid thundering theft. Tasks must be splittable for stealing to have anything worth taking.
When it matters
Parallel computation with uneven subproblems: recursive divide-and-conquer, JSON parsing of mixed sizes, compiler pipelines, and async runtimes balancing continuation tasks. ForkJoinPool exposes it directly; commonPool parallel streams ride it implicitly.
Pitfalls
Steal granularity: tiny tasks make steal traffic dominate; huge tasks make steals useless. Blocking operations inside workers defeat stealing — the worker cannot yield its queue, which is why async runtimes pair stealing with cooperative yield points. Measure queue depths and steal counts rather than assuming balance.