Work Stealing | Concurrency Roadmap

Language-specific mechanics: Concurrency Language Manual →

The problem: who picks up a forked task?

Fork-join and map-reduce both quietly assumed away a real question: when a task is "forked," which core actually executes it, and how does that assignment happen without becoming a bottleneck itself? The naive answer — one shared, global queue that every worker pulls from — has an obvious problem you've already seen elsewhere on this roadmap: a single shared queue means every push and pop needs to be synchronized against every worker, and that lock becomes exactly the kind of high-contention critical section the Locks & Mutual Exclusion topic warned about. With dozens of workers rapidly forking small tasks, a central queue's lock can become the single biggest bottleneck in the whole system — the parallelism you gained from fork-join gets eaten by contention on the structure that's supposed to distribute it.

Work stealing is the scheduling algorithm that avoids this, and it's what powers essentially every production fork-join runtime: Cilk (where the idea originated), Java's ForkJoinPool, .NET's Task Parallel Library, and Rust's Tokio all use some variant of it.

The core idea

Instead of one shared queue, every worker gets its own double-ended queue (deque) of tasks:

When a worker forks a new task, it pushes the task onto its own deque, at the bottom.
When a worker needs its next task, it pops from the bottom of its own deque — LIFO (last-in-first-out).
When a worker runs out of tasks in its own deque (it's empty), it becomes a thief: it picks another worker at random (the "victim") and steals a task from the top of the victim's deque — FIFO (first-in-first-out) relative to that deque.

The critical property that makes this efficient: a worker operating on its own deque (pushing/popping the bottom) almost never needs to synchronize with anyone, because thieves only ever touch the top. Contention only happens in the rare case where the deque has shrunk down to its last one or two tasks and a thief and the owner reach for the same end at nearly the same time — everywhere else, owner and thieves are working on physically different parts of the structure with no interference. This is a direct, practical instance of "minimize the scope and duration of contention" from the Locks topic, applied at the data-structure level instead of the critical-section level.

Why LIFO for the owner, FIFO for thieves — this is the interview question

This asymmetry is not an arbitrary implementation detail; it's the whole point, and it's the single most commonly tested "why" in this subtopic:

Why the owner uses LIFO (bottom): in a recursive fork-join computation, the most recently forked task is almost always the smallest, most cache-hot piece of work — it was just created from data the worker was just touching. Continuing to work on the most recent task keeps the worker's cache warm and matches the natural depth-first structure of the recursion (finish the deepest, most recent subtask before backing out to combine).

Why thieves use FIFO (top, the opposite end): the oldest task sitting in a deque is, by the nature of recursive splitting, typically the largest remaining chunk of work — it's the one that hasn't been subdivided further yet because the owner has been busy working on newer, smaller pieces closer to the bottom. Stealing the oldest/largest task means:

A single successful steal transfers a large amount of work, so a thief doesn't need to steal often — steals are the "expensive," synchronized operation, so minimizing how many are needed matters.
The stolen task, being large, will itself usually get forked further by the thief, generating fresh work for other idle workers too — stealing propagates parallelism outward instead of just moving one small unit of work.
Operating from opposite ends means the owner's hot path (bottom) and the thief's cold path (top) essentially never collide except when the deque is nearly empty.

Contrast this with a naive shared FIFO queue, where the "next" task handed to any worker (including the owner itself) is essentially arbitrary with respect to cache locality — work stealing's LIFO-own/FIFO-steal split is specifically designed to keep the common case (owner continuing its own recursion) cheap and cache-friendly, while making the rare case (an idle worker needing to steal) still effective when it does happen.

Correctness: this is a genuinely hard concurrent data structure

A production-quality work-stealing deque is one of the harder concurrent data structures to get right, which is exactly why this subtopic's difficulty is high even though the scheduling idea is simple to state. The reference implementations here use plain locks around every operation specifically to make the push/pop/steal semantics unambiguous — but that's not what real runtimes ship:

Real runtimes use lock-free deques. The owner's push/pop on its own end and a thief's steal on the opposite end need as little synchronization overhead as possible, since the owner's operations vastly outnumber steals. The Chase-Lev dynamic circular work-stealing deque (see Resources) is the algorithm most production fork-join runtimes descend from, using atomic compare-and-swap on the deque's indices rather than a mutex.
This is exactly where Memory Models & Atomics stops being optional. A lock-free deque's correctness depends entirely on getting happens-before relationships and atomic operations right — a naive volatile-everywhere approach or an incorrectly-ordered compare-and-swap reintroduces the exact ABA-style and visibility bugs that subtopic covered, now hidden inside your scheduler.
Multiple simultaneous steal attempts on the same victim must be resolved safely — two thieves racing for the last task must not both succeed, which is a compare-and-swap-shaped problem (see Compare-and-Swap & the ABA Problem), not something a plain read-then-write can get right.
Naive implementations have hit real production bugs from exactly this difficulty — e.g. the documented "convoying" problem in early Cilk, where a blocking lock on steal attempts made most idle thieves queue up waiting on the first busy worker rather than fanning out. The fix (non-blocking try_lock, retry against a different random victim on failure) is a small but instructive lesson in how blocking synchronization and load-balancing interact.

If you're asked to implement a full lock-free work-stealing deque in an interview, that's expert-level territory — most senior-level interviews stop at "explain why LIFO-own/FIFO-steal works" and reasoning about correctness at a locks-based level, which is what this subtopic's reference implementations demonstrate.

Work stealing vs. a shared thread-pool queue

	Central queue (e.g. a naive `ThreadPoolExecutor`-style design)	Work stealing
Structure	One shared queue, all workers push/pop from it	One deque per worker
Owner's common-case cost	Lock contention on every enqueue/dequeue, from every worker	Near zero — no synchronization needed most of the time
Idle-worker cost	Just dequeue (already contends with everyone else)	Random victim selection + a steal, only when genuinely idle
Best suited for	Independent, roughly-uniform tasks with no fork/recursion structure (see Thread Pools & Executors)	Recursive, fork/join-shaped computations with widely varying subtask sizes
Load balancing	Automatic by construction (shared queue), but at a contention cost	Automatic via stealing, at the cost of scheduler complexity

This is also why ForkJoinPool and a general-purpose ThreadPoolExecutor are different tools in Java's standard library rather than one configurable class: a plain thread pool's shared-queue design is the right choice for independent, similarly-sized tasks (the Thread Pools & Executors topic's use case), while work stealing specifically earns its complexity when tasks are recursively generated and wildly uneven in size — exactly the shape fork-join and map-reduce produce.

Pitfalls and interview gotchas

Reversing which end is LIFO and which is FIFO. The single most common mistake when explaining this out loud — the owner's own end is LIFO (cache locality), the steal end is FIFO (largest/oldest tasks, fewer steals needed). Getting this backwards undermines the entire justification for the design.
Thinking work stealing eliminates contention entirely. It minimizes it to the (rare) case of a nearly-empty deque touched by both owner and thief at once — it doesn't make concurrent access a non-issue, which is why a real implementation still needs careful lock-free design or correct locking.
Assuming random victim selection is a weakness. It's a deliberate, provably-good choice — Blumofe & Leiserson's original analysis (see Resources) shows randomized victim selection achieves expected running time within a constant factor of optimal, with no worker needing global knowledge of the others' queues.
Forgetting this is what's running underneath higher-level APIs. Calling list.parallelStream() in Java or spawning tasks under Cilk means you're using a work-stealing scheduler whether you think about it or not — this subtopic is what lets you reason about why those APIs behave the way they do under load.

Closing the topic

Work stealing closes the loop on Parallel Algorithm Patterns: Fork-Join gave you the recursive split/combine shape and the sequential-fallback threshold; Map-Reduce specialized that shape to data with an associative combine; Work Stealing is the scheduling mechanism that assigns forked tasks (or map chunks) to cores efficiently, at scale, without a central bottleneck — leaning directly on the memory-model and atomics guarantees from earlier in the roadmap to make its deques safe. The next topic, Classic Concurrency Interview Patterns, moves back to composing these ideas into the end-to-end problems interviewers actually ask.

Real fork-join runtimes (Java's ForkJoinPool, Cilk) use lock-free, cache-optimized deques — see the Chase-Lev deque in Resources. This version uses ordinary locks to keep the push/pop/steal semantics clear without the lock-free machinery.

type WorkStealingDeque struct {
    mu    sync.Mutex
    deque []any // bottom = high index
}

func (d *WorkStealingDeque) PushBottom(task any) {
    d.mu.Lock()
    defer d.mu.Unlock()
    d.deque = append(d.deque, task)
}

func (d *WorkStealingDeque) PopBottom() any {
    d.mu.Lock()
    defer d.mu.Unlock()
    n := len(d.deque)
    if n == 0 {
        return nil
    }
    t := d.deque[n-1]
    d.deque = d.deque[:n-1]
    return t
}

// A thief goroutine calls this on someone ELSE's deque.
func (d *WorkStealingDeque) Steal() any {
    d.mu.Lock()
    defer d.mu.Unlock()
    if len(d.deque) == 0 {
        return nil
    }
    t := d.deque[0]
    d.deque = d.deque[1:]
    return t
}

Application code almost never writes this. Go's scheduler already work-steals: each P has a local runqueue (owner pushes/pops one end; idle Ps steal from the other). That's why a burst of go f() load-balances without a userland deque. The snippet exists to make LIFO-own / FIFO-steal concrete — same teaching aid as the Java version, not an API you import.

Further Resources (Optional)

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.