Work Stealing Schedulers
A work stealing scheduler balances tasks across worker threads without a central queue. Each worker owns a private double ended queue of tasks, called a deque. When a worker has nothing to do it steals a task from another worker.
The clever part is which end of the deque each side uses:
- The owner pushes and pops from one end, the bottom, like a stack. This keeps recently created tasks hot in cache and needs no synchronization in the common case.
- A thief takes from the opposite end, the top. Stealing the oldest task tends to grab a large chunk of remaining work, so steals are rare.
Because owner and thief touch opposite ends, contention is low and most operations are lock free. This design suits fork join parallelism, where a task splits into subtasks that pile onto the local deque.
Benefits and costs:
- Automatic balancing Idle cores find work without a coordinator.
- Cache friendliness Local tasks stay near recently used data.
- Steal overhead A steal crosses cores and may invalidate cache, so the scheduler steals only when truly idle.
Work stealing powers many runtimes, from Java fork join pools to Rust and Go schedulers.
Key idea
Work stealing gives each worker a private deque and lets idle workers steal old tasks from the far end, balancing load with little contention.