How Does Work-Stealing Scheduling Balance Multi-Core Tasks?

Work-stealing scheduling is a decentralized load-balancing strategy used in parallel computing to distribute dynamic workloads across multiple processor cores. Instead of relying on a single central queue that can become a bottleneck, each processor core maintains its own local double-ended queue of tasks. When a core finishes all the work in its own queue and becomes idle, it actively looks for another busy core and steals a task from the opposite end of that core's queue. This approach minimizes contention, preserves cache locality, and keeps all cores productive without requiring a global coordinator.

The Structure of Local Task Queues

In a work-stealing runtime, each of the \(P\) processor cores owns a double-ended queue, commonly called a deque. The owner core interacts with the bottom of its own deque using last-in, first-out (LIFO) operations:

  • Push: When a core spawns a new subtask, it pushes the task onto the bottom of its local deque.
  • Pop: When a core is ready to execute its next task, it pops a task from the bottom of its local deque.

Using LIFO order for the local core is intentional. A newly spawned task often shares data with the parent task that just created it, meaning the relevant data is likely still warm in the core's L1 or L2 cache. Executing the most recently created task first maximizes temporal and spatial cache locality.

How Idle Cores Steal Work

When a core's local deque becomes empty, it transitions into a thief state. The idle core selects a victim core—typically chosen uniformly at random among the other \(P - 1\) cores—and attempts to steal a task from the top of the victim's deque.

Stealing from the top of the deque follows first-in, first-out (FIFO) order. This design provides two major advantages:

  1. Reduced Contention: The owner core operates at the bottom of the deque, while thieves operate at the top. As long as the deque contains more than one task, the owner and a thief do not touch the same memory location, allowing lock-free or minimal-synchronization implementations.
  2. Coarser Task Granularity: In divide-and-conquer algorithms, tasks near the top of the deque represent larger, earlier splits of the computation. Stealing a large task gives the idle core a substantial amount of work, which reduces the frequency of future steal attempts.

Performance and Theoretical Guarantees

Work-stealing is widely used in classical parallel frameworks such as Cilk, Intel Threading Building Blocks (TBB), and Java's ForkJoinPool because it offers strong theoretical bounds. For a computation with total work \(T_1\) (the time required on a single core) and critical-path length \(T_\infty\) (the time required on an infinite number of cores), the expected execution time \(T_P\) on \(P\) cores is bounded by:

\[T_P = O\left(\frac{T_1}{P} + T_\infty\right)\]

This bound shows that work-stealing achieves near-linear speedup whenever the available parallelism \(\frac{T_1}{T_\infty}\) is significantly larger than the number of cores \(P\). Because idle cores only incur synchronization overhead when they run out of local work, busy cores execute at full speed with minimal scheduling interference.

Handling Synchronization and Edge Cases

While the common case requires little coordination, edge cases still require careful handling. When a victim's deque has only one task remaining, both the owner core (popping from the bottom) and a thief core (stealing from the top) may race for that same task. Modern implementations resolve this using atomic compare-and-swap (CAS) instructions on the deque's top and bottom indices, ensuring that each task is executed at most once.

If a steal attempt fails because the victim's deque is empty or another thief won the race, the idle core backs off briefly or immediately picks another random victim. This randomized polling prevents thundering-herd effects and ensures that dynamic, unpredictable task trees—such as those found in graph traversal, ray tracing, or recursive sorting—are balanced automatically across all available cores.