Work Stealing and Fair Scheduling

Symptom

You parallelize a recursive algorithm. Quicksort, or a tree traversal, or a divide-and-conquer numeric kernel. You have 16 cores and a central task queue, and you measure a speedup of 3.

Profiling shows the cores are mostly idle, waiting on the queue’s lock. Every task creation and every task acquisition touches one cache line that all 16 cores are fighting over, and that line is bouncing between caches thousands of times per millisecond. The queue is not slow because it is badly written; it is slow because it is shared, and a single shared point cannot serve 16 cores.

So you shard the queue, one per core. Now the cores do not contend, and instead one core has four thousand tasks while eleven have none, because the recursion is unbalanced and you have no way to know that in advance. Static partitioning requires knowing the work distribution before you start, which for a recursive algorithm is exactly what you do not have.

The fix has a proof attached, and the proof covers both time and memory.

Statement

Each worker keeps a double-ended queue. It pushes and pops its own tasks at the bottom. When its deque is empty, it picks a victim uniformly at random and steals from the victim’s top.

Define two quantities for the computation, independent of the scheduler:

• $T_1$: work, total operations, the one-processor time.
• $T_\infty$: span or critical path, the longest chain of dependencies, the time on infinitely many processors.

Blumofe–Leiserson. Randomized work stealing executes a fully strict computation on $P$ processors in expected time

$$T_P \le \frac{T_1}{P} + O(T_\infty)$$

and in space $S_P \le S_1 P$, where $S_1$ is the single-processor stack space.

Both halves matter and only the first is famous. The time bound says you get near-linear speedup whenever there is enough parallelism. The space bound says memory does not blow up, which is the property that makes it safe to spawn millions of tasks.

Argument

Why steal from the opposite end. The owner works at the bottom, taking the task it just created — depth-first, which is what the sequential program would do. A thief takes from the top, which is the oldest task, the one nearest the root of the recursion tree.

This is the design’s crux, and it buys three things at once. The oldest task is the largest remaining subtree, so a single steal transfers a lot of work and steals stay rare. The owner and thief touch opposite ends, so in the common case there is no contention at all and the fast path needs no atomic operation on most architectures. And the owner following a depth-first order is what makes the space bound hold: depth-first execution keeps the live set small, exactly as the sequential program does.

The time bound, in outline. At each step a processor is either working or stealing. Working steps total exactly $T_1$, contributing $T_1/P$ when spread across $P$ processors. For the stealing steps, the argument is a potential function over the critical path: whenever a processor steals, there is a constant probability that it hits the deque containing the next node on the critical path, so $O(P)$ steal attempts suffice in expectation to advance the critical path by one. Over the whole computation that is $O(P T_\infty)$ steal attempts, or $O(T_\infty)$ per processor. Sum the two. $\blacksquare$

Reading the bound as an engineering rule. Speedup is near-linear when $T_1/P \gg T_\infty$, that is when the parallelism $T_1/T_\infty$ substantially exceeds $P$.

Concretely, parallel mergesort on $n = 10^6$: $T_1 = \Theta(n \log n) \approx 2 \times 10^7$ operations, and with a parallel merge the span is $T_\infty = \Theta(\log^3 n)$, around $8000$. Parallelism is roughly $2500$, comfortably above any core count you have, so the bound predicts near-linear speedup and that is what is observed.

Contrast a sequential merge, giving $T_\infty = \Theta(n)$ and parallelism about $\log n \approx 20$. On 16 cores that is 1.25× the parallelism of the machine, and the $O(T_\infty)$ term dominates. The span, not the work, is what you must engineer, and the bound tells you exactly which term to attack.

Why the space bound is the underrated half. A breadth-first scheduler on a recursive computation can expand the entire frontier before finishing anything, so a divide-and-conquer over $10^6$ elements can have $10^6$ live frames. Work stealing bounds total space at $S_1 P$: sixteen cores use at most sixteen times the sequential stack. That is why spawning a million tasks in Cilk or TBB does not exhaust memory, and it is a direct consequence of the owner running depth-first.

Granularity, the thing the theorem does not cover. The bound counts steal attempts, not per-task overhead. A task costing 50 ns cannot amortize a spawn costing 100 ns, so real implementations cut off recursion below a grain size — typically a few thousand operations — and run sequentially beneath it. Getting this wrong is the most common cause of a parallel version running slower than the serial one, and no scheduling theorem will save you from it.

Convergent evolution. Cilk introduced it; Intel TBB, Java’s ForkJoinPool and hence parallel streams, Go’s goroutine scheduler, Rust’s Rayon, .NET’s TPL, and Apple’s libdispatch all use work stealing. That is every major runtime arriving at the same design independently, which is unusual and is explained by the theorem: the design is optimal to within a constant, so there is nowhere else to converge to.

Where fairness enters. Work stealing optimizes throughput and says nothing about latency or fairness among unrelated tasks. A long-running task can occupy a worker indefinitely. Go’s scheduler therefore adds preemption — cooperative at function calls until 1.14, asynchronous via signals since — and a global runqueue checked periodically so that a busy local deque cannot starve global work. This is a deliberate departure from the pure algorithm to buy a property the theorem does not provide, and it is the standard shape of the compromise: pure work stealing for CPU-bound divide-and-conquer, plus fairness machinery for general-purpose task systems.

Forbids

Linear speedup on a computation with insufficient parallelism. If $T_\infty$ is large, no scheduler helps. This is Amdahl’s law arriving as the $O(T_\infty)$ term rather than as a separate observation.

Beating $\max(T_1/P, T_\infty)$. That is a lower bound for every scheduler, so work stealing is optimal up to the constant.

Unbounded space with a depth-first owner. The $S_1 P$ bound holds, which also means you cannot get more parallelism by expanding breadth-first without paying for it in memory.

Fairness guarantees from the bare algorithm. Latency-sensitive and CPU-bound work in the same pool will interfere, and separating pools is the usual answer.

Does not forbid

It does not require the runtime to know the task graph. The bound holds for computations unfolding dynamically, which is the entire point: no static partitioning, no profiling, no advance knowledge of where the work is.

It does not mean stealing is expensive in practice. The expected number of steals is $O(P T_\infty)$, and for high-parallelism computations that is a vanishing fraction of operations. The common path is a push and pop on a local deque with no atomic on most architectures, and measured steal rates on well-grained workloads are typically well under 1% of task operations.

It does not only apply to fork-join. This is the misreading that limits its perceived scope. Go’s goroutine scheduler steals for general concurrency, libdispatch for GUI and IO work, and Erlang’s BEAM does load balancing on the same principle. Any workload with dynamically created independent units qualifies.

It does not forbid combining with other strategies. Real schedulers add locality hints, NUMA-aware victim selection, and hierarchical stealing that prefers a victim on the same socket, because a steal that crosses sockets costs far more in cache traffic than the model accounts for.

It does not mean parallelism is free. The theorem bounds scheduling overhead, not the cost of contention on the data your tasks touch. False sharing, memory bandwidth saturation, and lock contention inside tasks are unaffected, and are usually what actually limits a real parallel program.

Boundary

• Fully strict computations. The proof assumes a task joins only with its parent. General DAGs, futures, and arbitrary synchronization weaken the bound.
• The model ignores memory hierarchy. A steal moves work to a core with cold caches, and on NUMA hardware the cost can dwarf the scheduling cost the theorem measures.
• Grain size is outside the theorem. Cutoffs are an empirical tuning problem.
• No fairness or latency guarantee. Priority, preemption, and starvation are separate mechanisms.
• Assumes a dedicated processor per worker. Oversubscription, other tenants, or a hypervisor descheduling a worker mid-task breaks the analysis, which is why runtimes pin workers to cores and size pools to hardware parallelism.

The rule to carry: measure your span, not just your work. If $T_1/T_\infty$ does not comfortably exceed your core count, buying more cores will not help and restructuring the algorithm to shorten the critical path will.

Read next