The question this answers
Why does a runtime give each worker a private queue instead of sharing one, and what does an idle worker do about it?
A recursive quicksort over 40 million elements, decomposed into a few hundred thousand subtasks whose sizes vary by three orders of magnitude because the pivots were unlucky.
Each worker's deque is *mostly* private: the owner touches one end, thieves touch the other. The deque's two indices are the shared state, and the only place they overlap is when one element is left.
Every task pushed onto any deque is executed exactly once — an owner pop and a thief steal must never both return the same task, and no task may be left in a deque that nobody will ever visit.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Private ends, shared far end
A shared central queue is a correctness-simple, contention-terrible design: every push and every pop hits one lock, so with sixteen workers doing fine-grained recursive work the lock becomes the program. Work stealing removes the common-case coordination entirely by giving each worker its own double-ended queue. The owner pushes new subtasks onto its bottom and pops from its bottom — a stack discipline — and in the common case is the only actor touching that end.
Two consequences fall out for free. Popping the *bottom* means a worker runs the task it most recently created, which is the one whose data is still in its L1 cache and whose depth-first traversal keeps the live set small — the same reason recursion uses a stack. And stealing from the *top* means the thief takes the oldest, largest, least-recently-created task, which is usually the coarsest available chunk, so one steal buys a lot of work and steals are rare.
This is why fork-join runtimes — Fork/Join, Cilk-style schedulers, Java's ForkJoinPool, Rust's rayon, Go's goroutine scheduler — all converge on it. It is not that stealing is clever; it is that it makes the *fast path lock-free and the slow path self-balancing*, which is exactly the pair a recursive decomposition needs when subtask sizes are unpredictable.
- Owner: LIFO on its own end — best locality, smallest live set, no synchronization in the common case.
- Thief: FIFO from the far end — takes the oldest and typically coarsest task, so steals are infrequent.
- Victim selection is usually randomised; scanning every deque in order makes all thieves converge on the same victim.
- A worker that finds nothing anywhere parks rather than spinning forever, or you have built Busy Waiting.
The last element: where owner and thief collide
The deque is only *mostly* private. When exactly one task remains, the owner popping the bottom and a thief stealing the top are reaching for the same element, and the whole exactly-once invariant rests on that one case. This is why the fast path can be lock-free but not synchronization-free: the standard protocol has the owner speculatively decrement the bottom index, then check whether it has crossed the top, and if it has, resolve the conflict with a compare-and-swap that exactly one of the two parties can win.
The schedule below shows what a naive implementation — pop the bottom, then decrement — does instead. Both parties read consistent indices, both take t3, and the task is sorted twice. In a pure quicksort that is merely wasted work; in a task whose body has a side effect it is a duplicate write, and in a task that frees a node it is a double free.
The lesson generalises beyond deques: a "mostly private" data structure still needs a protocol for the moment it stops being private, and that moment is always the boundary case that testing at high load never reaches, because at high load the deque is rarely down to one element. See Compare-and-Swap and the Retry Loop for the resolution primitive and Atomics Are Not Magic for why an atomic index alone would not have saved this.
| # | Worker 1 (owner) | Worker 3 (thief) | State |
|---|---|---|---|
| 1 | deque state: one task left | · | top=3 bottom=4 slot[3]=t3 |
| 2 | · | read top (3) | thief sees top=3 |
| 3 | read bottom (4), target slot 3 | · | owner sees bottom=4 owner target=3 |
| 4 | · | load slot[3] → t3 | thief task=t3 |
| 5 | load slot[3] → t3 | · | owner task=t3 ✕ Owner and thief both hold t3; the deque had one task and returned it twice. |
| 6 | · | write top = 4 | top=4 |
| 7 | write bottom = 3 | · | top=4 bottom=3 |
| 8 | execute t3 (sort partition [0..2M)) | · | t3 executions=1 |
| 9 | · | execute t3 concurrently on the same slice | t3 executions=2 ✕ Two workers sorting the same array slice in place — interleaved swaps leave the partition unsorted and the join reports success. |
What stealing buys, and what locality it costs
The payoff is load balance without a scheduler that knows anything. Nobody estimated task sizes, nobody partitioned the input evenly, and the imbalance from unlucky quicksort pivots is absorbed automatically: workers that finish early take work from workers that did not. The timeline below contrasts a static even split against work stealing on the same skewed decomposition.
The cost is locality, and it is real. A stolen task's data was warmed in the victim's cache, and the thief's first pass over it is a stream of cache misses — worse across a NUMA boundary, where the memory may be physically attached to the victim's socket (NUMA: Not All Memory Costs the Same, Parallelism Can Destroy Locality). This is why stealing is designed to be rare rather than efficient: LIFO on the owner's end keeps the hot task local, and a thief takes the coarsest available task so one expensive migration amortises over a lot of work.
The failure case worth naming: fine-grained tasks turn stealing into thrashing. If every task is 5 µs, the steal overhead plus the cache miss stream exceeds the task, workers spend their time hunting rather than working, and throughput collapses. The fix is a sequential cutoff in the decomposition — below some size, recurse serially and do not create tasks at all — which is the same fix as Parallel Overhead and the reason every fork-join tutorial has a threshold constant in it.
Key points
- Each worker owns a deque, pushes and pops its own end, and steals from the far end of a random victim only when it runs dry.
- LIFO on the owner's end gives cache locality and a small live set; FIFO stealing takes the coarsest task so steals stay rare.
- The exactly-once invariant is at risk only at the last element, which is why the bug never reproduces under load.
- Stealing balances load without anyone estimating task sizes — the reason fork-join runtimes use it for irregular decompositions.
- The cost is locality: a stolen task arrives cold, and across a NUMA boundary it arrives very cold.
- Fine-grained tasks make stealing thrash; a sequential cutoff in the decomposition is the fix, not a better scheduler.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Each worker maintains a double-ended queue of ready tasks, initially seeded from the root decomposition.
- • On creating a subtask, the worker pushes it onto the bottom of its own deque — no synchronization on the fast path.
- • To get work, the worker pops from its own bottom (most recently created, hottest cache).
- • On finding its deque empty, it selects a victim at random and attempts to take from the victim's top using a compare-and-swap on the top index.
- • When the owner's bottom would cross the top, the owner also uses a CAS so exactly one of owner and thief wins the last element.
- • A thief that fails repeatedly backs off and eventually parks, so an idle pool does not burn cores hunting.
- • Owner and thief both read consistent indices at size one, both load the same slot, and the task executes twice — the last-element race.
- • Owner and thief both CAS the contested index; exactly one succeeds, the loser retries or reports empty, and the invariant holds. This is the correct version of the same schedule.
- • Two thieves target the same victim simultaneously: both CAS the top, one wins, the loser picks a new victim — correct, but the reason victim choice is randomised rather than sequential.
- • A worker pushes a subtask, and before it pops anything a thief steals it; the owner then works on a different subtree — correct, and the source of the nondeterministic execution order that makes fork-join results order-sensitive if the combine is not associative (Parallel Reduce).
- • All workers become thieves at once at the end of a phase: every deque is empty, every worker scans, and the cost is a burst of pure overhead just before completion.
- • Guaranteed: every task executes exactly once, given a correct deque protocol.
- • Guaranteed: no worker sits idle while any deque anywhere holds a task it could steal — asymptotically good load balance without central coordination.
- • NOT guaranteed: any particular execution order. The order tasks complete in varies run to run, which matters if your combine step is order-sensitive.
- • NOT guaranteed: locality. A stolen task runs on a core whose caches know nothing about it, and the runtime will not tell you it happened.
- • NOT guaranteed: that stealing is cheap. It costs a CAS plus a cold cache; for tiny tasks that exceeds the task itself.
- • NOT guaranteed: fairness in any latency sense. LIFO means the oldest task on a busy worker's deque may wait a long time; this is a throughput scheduler, not a latency scheduler.
- • Fast path: near zero. Owner-only access to the bottom end is the entire point.
- • Slow path: thieves contend on victims' top indices via CAS. Randomised victim selection spreads it; sequential scanning concentrates every thief on worker 0.
- • Cache-line contention on the deque indices themselves, since owner and thieves write adjacent metadata — a classic False Sharing: Different Variables, Same Cache Line site, which is why real implementations pad them.
- • End-of-phase convergence: all workers idle simultaneously and all hunt, producing a short burst of maximum contention at exactly the moment there is no work.
- • Duplicate task execution from a naive last-element protocol — data corruption, double frees, or in-place algorithms silently producing wrong output.
- • Index crossing leaving the deque in an inconsistent state so subsequent steals read stale or freed slots.
- • Livelock-adjacent thrashing where thieves spend more time hunting than working, with high CPU and no progress (Livelock).
- • Starvation of a deep task on a busy worker's deque under LIFO ordering — throughput is fine, that task's latency is not.
- • Locality collapse on NUMA hardware where stolen tasks repeatedly access memory attached to another socket.
- • Pool deadlock if a task blocks on a lock or I/O: the worker cannot steal while blocked, so a handful of blocking tasks can idle the whole pool (Blocking the Event Loop is the async analogue of the same mistake).
- • Recursive divide-and-conquer where subtask sizes cannot be predicted — the case static partitioning handles worst.
- • CPU-bound task graphs with many small-to-medium independent tasks and a fork-join shape.
- • Workloads whose imbalance varies by input, so no static split is right for all inputs.
- • Runtimes multiplexing very large numbers of lightweight tasks over few threads, where a central queue would be the bottleneck (A Task Is Not a Thread).
- • When tasks are tiny: steal cost and cache misses exceed task cost, and a sequential cutoff is the actual fix.
- • When tasks block on I/O or locks — the worker is occupied but not working, and stealing cannot rebalance around it.
- • When locality dominates, such as streaming over a large array where migration destroys prefetching gains.
- • When you need deterministic execution order or per-task latency bounds; this scheduler optimises neither.
- • When the workload is already uniform — a static split has better locality and no steal overhead at all.
- • Steal count and steal success rate. High attempts with low successes means thieves are converging on the same victims or there is genuinely no work.
- • Ratio of steal attempts to completed tasks — the direct thrashing signal, and the one that says your tasks are too small.
- • Per-worker completed-task counts. A flat distribution means balancing works; a skewed one means tasks are too coarse to split.
- • Cache miss rate attributed to just-stolen tasks versus locally-created ones, where the profiler supports it.
- • Time from the last useful task to pool quiesce — the end-of-phase hunting burst.
- • Task duration histogram: if the median task is microseconds, the cutoff is wrong regardless of what the scheduler reports.
- • The scheduler is now nondeterministic in execution order, so reproducing a bug requires recording the schedule rather than the input (Deterministic Replay: Making the Schedule Reproducible).
- • Correctness of the deque protocol is genuinely hard — memory ordering on the indices matters, and this is one of the few places writing it yourself is unjustifiable.
- • The decomposition needs a tuned cutoff constant, which is a workload-and-hardware-dependent number with the same problems as pool sizing.
- • Blocking inside a task becomes a scheduling hazard rather than a local slowdown, so task bodies acquire a "must not block" rule that is easy to violate.
- • A single shared queue, when tasks are coarse and few — far simpler, and the lock is not hot if hand-offs are rare.
- • Static partitioning, when subtask cost is uniform and predictable: best locality, zero scheduling overhead, no protocol to get wrong.
- • Guided or chunked self-scheduling, where workers claim decreasing-size chunks from a shared counter — most of the balance for much less machinery.
- • Coarser tasks with a central queue, when the imbalance is mild; often the whole problem disappears at a different granularity.
Work stealing between deques
Own work → popped from the HEAD of my deque (LIFO: hottest in cache)
Stolen → taken from the TAIL of a victim's deque (oldest, biggest sub-task)
Two ends → the owner and the thief rarely touch the same slot, so the
common case is uncontended and needs no lock at all.Thread pool: utilization and queue
capacity = workers / service = 8 / 50 ms = 160.0 req/s ρ = arrivals / capacity = 120 / 160.0 = 0.750 Little L = λ × W → 0.120/ms × 59.8 ms = 7.2 in flight engine status = healthy
compare_exchange in a loop — retries, and the pointer that lied
do {
old = counter.load(); # 1 read
next = old + 1; # compute off to the side
} while (!counter.compare_exchange(old, next)); # swap only if unchanged| # | T1 — pop() via CAS | T2 — another thread | State |
|---|---|---|---|
| 1 | old ← head (= A) | · | head=A stack=A→B→C |
| 2 | · | pop() → A | head=B stack=B→C |
| 3 | · | pop() → B | head=C stack=C |
| 4 | · | push(A) | head=A stack=A→C |
| 5 | CAS(head, A, B) → SUCCESS | · | head=B stack=B→ freed ✕ head now points at B, which was popped and freed. Node C has vanished from the stack and T1 returned a node it never observed being on top. |
| 6 | return A to the caller | · | head=B stack=corrupt |
What people believe, and what is true
Work stealing means workers grab from a shared queue when idle.
The queues are per-worker and mostly private; that privacy is the entire performance argument. A shared queue is the design work stealing exists to avoid.
The owner and the thief never touch the same end, so no synchronization is needed.
They collide at exactly one element, and that boundary case carries the whole exactly-once invariant.
More, smaller tasks give the scheduler more balancing opportunities, so they are better.
Past a threshold the per-task overhead and stolen-cache misses exceed the work. Every fork-join decomposition needs a sequential cutoff.
Go deeper
Overview
Each worker has its own to-do list and works from its own end. When a worker runs out, it takes an item from the other end of somebody else's list.
Practical
Use the runtime's implementation, never block inside a task, and put a sequential cutoff in the decomposition so tasks stay big enough to be worth scheduling.
Advanced
LIFO-local/FIFO-steal is a locality decision, not an arbitrary one; randomised victim selection prevents thief convergence; padding the indices prevents false sharing between owner and thieves.
Internals
The owner speculatively decrements bottom, then compares against top; on a crossing it resolves with a CAS. The index writes need release/acquire ordering, which is where architecture-specific memory models enter.