Work Stealing
Subject: Computer and Technology noun /ˈwɜːrk ˌstiː.lɪŋ/ 1 definition
- parallel-computing
- concurrency
- task-scheduling
- runtime-systems
-
Definition (noun)
Entry #341 · UpdatedWork Stealing is a decentralized dynamic load-balancing scheduling strategy used by parallel and concurrent runtimes to distribute tasks efficiently across multiple processor cores. Instead of contending on a single global task queue, each worker thread maintains a local double-ended queue (deque), pushing newly spawned subtasks and popping its own work from the local end in LIFO order to preserve CPU cache locality and avoid synchronization in the common path. When a worker exhausts its local queue, it becomes a thief and asynchronously pulls an older task from the opposite FIFO end of a busy peer's deque, typically acquiring a coarser-grained unit of computation while minimizing contention with the owner thread. Its primary purpose is maintaining high core utilization on irregular, recursive, or dynamically spawned workloads without the lock bottlenecks of centralized work-sharing queues, though its efficiency relies on tasks being largely independent and granular enough to amortize cross-core stealing and memory-barrier overhead.
Common Forms
Classic Chase-Lev Deque Stealing: Employs a lock-free, resizable circular-array deque in which the owner thread pushes and pops at the bottom with minimal fencing while concurrent thieves steal from the top via compare-and-swap (CAS) operations—widely used in Cilk, Java
ForkJoinPool, and Rust's Rayon.Randomized Victim Selection: Picks target worker deques uniformly at random using a fast per-thread PRNG whenever a thread runs idle, achieving provably near-optimal load balance and low coordination overhead without maintaining global queue-depth metadata.
Locality- and Topology-Aware Stealing: Biases steal attempts toward sibling threads sharing an L2/L3 cache or residing on the same NUMA socket before probing remote sockets, reducing cross-socket interconnect traffic and cache-coherency misses on multi-socket servers.
Adaptive and Batch-Stealing Variants: Transfers multiple tasks (often half of a victim's deque) per steal or throttles idle probing with exponential backoff and thread parking to cut atomic contention on imbalanced workloads and prevent wasted CPU cycles when work is scarce.
Example
Inside an 8-thread Rust
rayonpool (ThreadPoolBuilder::new().num_threads(8)), callingrecords.par_iter().map(...)recursively splits 10 million telemetry events across each worker thread's local Chase-Lev deque. When worker 3 drains its own LIFO task stack early, it selects worker 1 pseudo-randomly and performs an atomic compare-and-swap on the FIFO head of worker 1's deque to steal an unprocessed batch of events.