Why one shared queue is not enough
The previous guide built a thread pool: a fixed crew of worker threads, all pulling work items off a single shared task queue. That design is correct and it is a fine place to start. But picture eight workers all reaching into one queue protected by a single lock. Every time any thread wants a task, it must take that lock; eight cores end up taking turns at one door. The queue head becomes a bottleneck, and worse, the cache line holding it ping-pongs between cores — a textbook case of contention on a hot line. The more cores you add, the more they fight over the same handle, and throughput stops scaling.
The first instinct is to give each worker its own private queue, so threads stop colliding. That removes the contention beautifully — but it creates a new problem just as fatal. Tasks rarely arrive in eight perfectly equal piles. One worker may be handed a thousand items while another sits on three. Now seven cores finish early and go to sleep while the eighth grinds through its mountain alone. You have traded a contention problem for a load-imbalance problem: idle threads next to a swamped one, the very thing a thread pool exists to prevent.
A work-stealing scheduler resolves the tension with a single deceptively simple rule. Keep the per-worker private queues — so the common, uncontended case stays fast — but when a worker empties its own queue, instead of going to sleep it walks over to a random other worker and steals a task from the far end of that victim's queue. Most of the time everyone works out of their own queue with no synchronization at all; stealing only happens at the moment imbalance appears, and it happens automatically, with no central coordinator deciding who needs help.
The deque: push and pop one end, steal from the other
The whole trick rests on the shape of the per-worker queue. It is not a plain FIFO queue but a double-ended queue, a deque, with two ends that play different roles. The owner thread pushes new tasks onto one end (call it the bottom) and pops its next task off that same end — so for the owner it behaves like a stack, last-in-first-out. A thief, by contrast, reaches in at the opposite end (the top) and takes the oldest task there. The owner and the thieves touch opposite ends, which is the geometric heart of why this is cheap.
worker's own deque TOP BOTTOM | | v v [ t0 ][ t1 ][ t2 ][ t3 ][ t4 ][ t5 ][ t6 ] ^ ^ | | thieves steal here owner push/pop here (oldest task) (newest task, LIFO)
Why have the owner work LIFO while thieves work FIFO? It is not an arbitrary choice — it falls straight out of how recursive parallel work behaves. When a task splits into subtasks, the newest subtask the owner just created is the one whose data is still hot in cache, so popping it next gives the best locality. Meanwhile the oldest task at the far end is usually the root of a large, not-yet-expanded chunk of work — exactly the fat piece worth the cost of a steal. So the deque hands each side what suits it: warm, fine-grained work to the owner; big, coarse-grained work to the thief.
There is a real subtlety hiding in that picture, and it would be dishonest to wave it away. When the deque has many tasks, owner and thief touch different ends and never interfere — so those operations need no lock at all, just a couple of atomic reads and writes. But when the deque shrinks to a single task, both ends are the same task, and the owner's pop can race a thief's steal for that last item. Handling that one boundary case correctly — usually with a compare-and-swap on the shared index, the same primitive from the earlier lock-free guide — is the entire delicate part of a real work-stealing deque. The famous Chase–Lev deque, published in 2005, is the standard answer.
A worker's life: run, steal, sleep
Put the pieces together and a single worker thread's main loop becomes almost embarrassingly simple. It is the same outer loop you saw in guide 1, with one new branch bolted on: before giving up and sleeping, try to steal. That one branch is the difference between a pool that wastes idle cores and one that keeps every core busy until the work genuinely runs out.
- Pop a task from the bottom of your own deque (LIFO, no lock in the common case). If you got one, run it and loop. Running it may push fresh subtasks onto your own deque — that is how parallel work spreads.
- If your deque is empty, pick another worker at random and try to steal one task from the top of its deque. Random choice matters: it spreads the steal attempts evenly and avoids a thundering herd all raiding the same victim.
- If that steal fails (the victim was also empty or a rival thief beat you to it), try another random victim. Spinning through a few victims is normal and cheap.
- If repeated steals all come up empty, the system is genuinely out of work. Now — and only now — park the thread to sleep so it stops burning a core, to be woken when new tasks arrive.
Fork-join: the workload work-stealing was born for
Work-stealing shines brightest on fork-join parallelism, where a problem splits recursively into independent subproblems and the answers join back. Think of a parallel sum over a million-element array: fork it into two halves, fork each half again, keep splitting until each chunk is small enough to handle directly, then add the partial sums back up the tree. Each fork is just a `push` onto the worker's own deque; each subtask runs and, if still too big, forks further. The tree of work materializes on the deques as the computation runs, no global plan required.
Now watch the load balancing happen for free. The worker that started the sum forks the array and immediately dives into one half (LIFO — newest, hottest task first), leaving the other half sitting at the bottom of its deque. An idle worker on another core steals that other half from the top, forks it, and dives in. Within a few steals, all eight cores are busy on disjoint slices of the array, each working locally, stealing again only when its own slice is exhausted. Nobody computed a schedule; the imbalance simply drained itself away through random steals. This is the celebrated result behind Cilk and Java's ForkJoinPool: with P processors, work-stealing comes provably close to a perfect P-times speedup on well-structured fork-join work.
Where it lives, and where it doesn't
You have almost certainly run a work-stealing scheduler without knowing it. It is the engine inside Intel's TBB, Java's ForkJoinPool and parallel streams, the .NET Task Parallel Library, Apple's Grand Central Dispatch, Rust's Rayon, and the async executors in Go and Tokio. In the async runtimes especially, this is what we meant in guide 1 by an executor distributing tasks across worker threads — and it is one common implementation of M:N scheduling, where many lightweight tasks are multiplexed onto a small fixed set of OS threads. Work-stealing is the mechanism that keeps those few OS threads evenly loaded as the many tasks come and go.
Be honest about the limits, though, because work-stealing is not free magic. It wins overwhelmingly when tasks are independent and short-ish, so a stolen task can run to completion without blocking. It does not automatically solve everything. If your tasks call a blocking system call — a slow read(), a lock wait — the stealing thread is stuck inside that task and cannot go help elsewhere, which is exactly the don't block the executor hazard the async guides keep returning to. And if tasks have dependencies (B must wait for A), the scheduler cannot run them in parallel no matter how cleverly it steals; that is a property of your problem, not a knob the scheduler can turn.
Hold the shape of the idea. Give each worker a private deque so the common case needs no synchronization; let an idle worker steal the oldest, fattest task from a random busy peer so load balances itself with no central planner; and let the owner work newest-first for cache warmth while thieves take oldest-first for big chunks. That single structure is why a thread pool can keep eight or sixty-four cores genuinely busy on irregular work. The next guide picks up the thread this one left dangling — what happens when a task can't finish right now because it's waiting on something — and that is where futures, promises, and async/await enter the story.