Work Stealing Scheduler
A work stealing scheduler gives each worker a local deque and lets idle workers steal from the back of busy ones, balancing load with cache-friendly local pops and rare remote steals.
Definition
A work stealing scheduler is a scheduling algorithm where each worker thread has a local double-ended queue of tasks, pushes and pops from the front (cache-friendly, LIFO), and when empty steals from the back of another worker queue (rare, FIFO), achieving load balancing with low contention and good locality.
Context and scope
Applied in ForkJoinPool, Go scheduler, TBB, and any parallel runtime where dynamic load balancing and cache locality both matter.
Common misconceptions
- Work stealing is just task queueing — it is task queueing with a specific topology (per-worker queues) and stealing discipline that minimizes contention
- Stealing always balances load — it balances compute load; it can hurt cache locality when a stolen task touches data on the victim core
Anti-patterns
- Creating one giant shared queue instead of per-worker queues, so every enqueue and dequeue contends on one lock
- Stealing from the front of the victim queue, competing with the victim pop and defeating the low-contention design
Related concepts
Authoritative source
What it is
A work stealing scheduler is a scheduling algorithm where each worker thread has a local double-ended queue of tasks, pushes and pops from the front (cache-friendly, LIFO), and when empty steals from the back of another worker queue (rare, FIFO), achieving load balancing with low contention and good locality. Applied in ForkJoinPool, Go scheduler, TBB, and any parallel runtime where dynamic load balancing and cache locality both matter. The central difficulty is that interleaving is nondeterministic: the set of possible executions grows super-exponentially with the number of operations, and testing samples a vanishing fraction.
How it works
Correctness is established by reasoning about happens-before relationships, not by running more tests. Synchronization primitives are chosen for the specific guarantee needed — mutual exclusion, publication, or ordering — and composed only with a documented proof of absence of deadlock. Bounded resources apply backpressure rather than unbounded queuing that hides overload until memory exhausts.
When to apply and pitfalls
Apply whenever multiple flows share mutable state or resources. The dominant pitfall is reasoning sequentially about concurrent code — “this can’t happen because A finishes before B” — when in fact the scheduler can interleave at any instruction boundary. The second is using a coarse lock for simplicity and turning parallelism back into serialization.