Work-Stealing Task Schedulers are dynamic load-balancing systems where idle processors steal tasks from the queues of busy processors, enabling efficient parallel execution of irregular and recursive workloads without static task assignment — work stealing achieves provably optimal load balance with minimal overhead for a wide range of parallel programs.

Core Algorithm:

• Double-Ended Queue (Deque): each worker thread maintains a local deque of tasks — new tasks are pushed onto the bottom of the deque, and the worker pops tasks from the bottom (LIFO order for locality)
• Stealing Protocol: when a worker's deque is empty, it randomly selects another worker and attempts to steal a task from the top of that worker's deque (FIFO order) — stealing the oldest task typically gets the largest unit of work
• Randomized Selection: the victim for stealing is chosen uniformly at random — provably achieves O(P × T_infinity) total steal attempts where P is the number of processors and T_infinity is the critical path length
• THE Protocol: Arora, Blumofe, and Plaxton's lock-free deque protocol uses compare-and-swap to coordinate between the local worker (bottom access) and thieves (top access) — eliminates lock contention in the common case of no stealing

Theoretical Guarantees:

• Space Bound: work stealing uses at most P × S_1 stack space where S_1 is the sequential stack space — each processor's deque depth is bounded by the critical path length
• Time Bound: expected completion time is T_1/P + O(T_infinity) where T_1 is the total work and T_infinity is the span — achieves linear speedup when T_1/T_infinity >> P
• Communication Bound: total number of steals is O(P × T_infinity) — each steal transfers O(1) tasks, so communication overhead is proportional to the critical path, not the total work
• Optimality: work stealing is within a constant factor of the optimal schedule for fully strict (well-structured) computations — no online scheduler can do asymptotically better

Major Implementations:

• Cilk/Cilk Plus: the original work-stealing runtime — cilk_spawn creates a task that can be stolen, cilk_sync waits for all spawned tasks — compiler transforms recursive parallelism into work-stealing deque operations
• Intel TBB (Threading Building Blocks): task-based parallelism with work stealing — provides parallel_for, parallel_reduce, parallel_pipeline built on work-stealing scheduler
• Java Fork/Join Framework: ForkJoinPool implements work stealing for Java — ForkJoinTask.fork() spawns tasks, join() collects results — foundation of Java's parallel streams
• Tokio (Rust): async task runtime using work-stealing scheduler for I/O-bound concurrent workloads — each worker thread maintains a local queue with cross-thread stealing

Task Granularity Management:

• Coarsening Threshold: if task granularity is too fine, stealing overhead dominates — sequential cutoff switches to serial execution below a threshold (e.g., sort recursion switches to insertion sort below 1000 elements)
• Lazy Task Creation: don't actually create a task object until a steal occurs — the spawning thread continues serial execution and only splits work when another thread needs it
• Adaptive Granularity: monitor steal frequency and adjust granularity dynamically — high steal rates suggest tasks are too coarse (insufficient parallelism), low rates suggest they may be too fine
• Task Coalescing: batch multiple fine-grained tasks into a single coarser task — reduces deque operations and steal overhead by amortizing scheduling costs

Advanced Techniques:

• Locality-Aware Stealing: prefer stealing from physically nearby processors (same NUMA node, same socket) to minimize data movement — hierarchical stealing reduces cache miss overhead by 40-60%
• Leapfrogging: instead of stealing a task, the thief helps execute the victim's continuation — preserves sequential execution order and improves cache behavior for divide-and-conquer algorithms
• Affinity-Based Scheduling: remember which processor last executed a task and preferentially schedule it there again — exploits warm caches for iterative workloads
• Priority Work Stealing: extend deques with priority levels — critical-path tasks get higher priority, ensuring that the longest chain of dependent tasks progresses even under contention

Work stealing is the dominant scheduling strategy for task-parallel runtimes because it combines provable theoretical guarantees with excellent practical performance — idle processors find work in O(1) amortized time, busy processors operate on their local deque without synchronization overhead, and the randomized stealing protocol naturally balances load across heterogeneous workloads.