Work-Stealing Schedulers: How Modern Runtimes Balance Concurrent Tasks

When you spawn thousands of goroutines, fire off async Rust tasks, or parallelize a data pipeline with Rayon, something has to decide which CPU core runs what. That something is the scheduler, and the dominant design in modern runtimes—work stealing—is worth understanding. It explains a lot about why these runtimes perform the way they do, and where their limits are.

The Problem With Simpler Approaches

The naive solution to spreading work across N threads is a single shared queue. Every thread pulls the next task off the queue when it’s free. This is easy to reason about but terrible under load: every enqueue and dequeue requires a lock or an atomic operation on shared state, and with dozens of threads all hammering the same queue, contention becomes the bottleneck. Throughput plateaus exactly when you need it most.

The opposite extreme—one queue per thread, filled at submission time—eliminates contention but trades it for imbalance. If thread 0 gets assigned ten long tasks and threads 1–7 get nothing, seven cores sit idle while one runs hot. Static partitioning only works when you know the workload distribution in advance, which you almost never do.

Work stealing splits the difference. Each thread has its own local deque (double-ended queue) and operates on it without coordination. Stealing only happens when a thread would otherwise go idle, and it targets a peer thread rather than a global structure. Contention is rare by design because it only occurs during imbalance, which is exactly when you want threads to be doing something other than spinning.

How Stealing Actually Works

Each worker thread maintains a deque of pending tasks. The owning thread pushes new tasks onto the bottom and pops work from the bottom as well—LIFO for local execution. This is the hot path and it requires no synchronization because only the owner touches the bottom.

When a thread exhausts its local deque, it picks a victim thread at random and attempts to steal from the top of that thread’s deque—the oldest, most deeply queued tasks. The steal requires a compare-and-swap, but it’s infrequent enough that this cost is acceptable. The asymmetry (owner works bottom, thieves steal top) is intentional: it keeps recently spawned tasks local and warm in cache while exposing older work to redistribution.

The LIFO local ordering also improves cache behavior. A task that just spawned a child task is likely to still have relevant data in L1 or L2 cache. Executing that child immediately—before the parent’s data evicts—is better than deferring it. This is the opposite of a fair FIFO scheduler and the right call for performance.

What Real Runtimes Do With This

Go’s runtime uses a layered version of this model. Each OS thread has a local run queue capped at 256 goroutines. New goroutines go into the local queue first, then overflow to a global queue. When a local queue drains, the thread checks the global queue, then steals from peer threads. Go also multiplexes goroutines onto a smaller pool of OS threads (the M:N model), which means blocking syscalls require additional bookkeeping to avoid starving the scheduler.

Tokio, Rust’s async runtime, uses a similar work-stealing design across its worker threads. Because Tokio tasks are async—they yield at await points rather than blocking—the scheduler doesn’t need the M:N threading complexity Go requires. Rayon, used for data parallelism, applies the same pattern but targets CPU-bound fork-join workloads rather than I/O concurrency.

Where It Falls Short

Work stealing is not free. The random victim selection means stealing threads traverse cache lines belonging to other cores, producing cross-core cache traffic at exactly the moment the system is under load. Systems with Non-Uniform Memory Access (NUMA) topologies can see stealing across NUMA nodes incur significant latency penalties—some runtimes add NUMA-aware scheduling layers on top of basic work stealing to constrain which threads steal from which.

There’s also a subtler problem: unfairness. Long-running tasks that never yield can starve the work they displaced. Most runtimes that target I/O workloads rely on cooperative yielding at await points; truly CPU-bound tasks that run without yielding can disrupt scheduler fairness assumptions.

Why It Matters for Application Design

Understanding work stealing clarifies some common runtime behaviors. Spawning many small tasks generally performs well because the scheduler can spread them efficiently. A single long-running blocking call on one thread can stall that thread’s local queue until the runtime detects the block and compensates. Keeping tasks reasonably fine-grained and ensuring blocking I/O goes through the runtime’s async mechanisms—rather than raw blocking syscalls—lets the work-stealing layer do what it was designed to do.

The algorithm is old—it traces back to research from the 1990s—but its fit with modern multicore hardware has made it the default choice for any runtime that takes throughput seriously.