How Work-Stealing Deques Reduce Scheduler Contention

20 Oct 2026 concurrencyalgorithms

A work-stealing deque is a double-ended queue of tasks: the worker that owns it adds and removes tasks from one end, while idle workers take tasks from the other end. This gives a parallel runtime a mostly local, low-contention way to distribute work.

The problem: one shared queue

A parallel runtime breaks a larger job into smaller tasks—units of work that can run independently—and assigns those tasks to worker threads. A straightforward design uses one shared queue:

1. Workers take a task from the queue.
2. They execute it.
3. They add newly created tasks back to the queue.

This is easy to understand, but every worker must coordinate on the same data structure. A lock around the queue makes correctness simple, yet it also makes the lock a bottleneck. When many workers finish tasks at roughly the same time, they wait to acquire it. Replacing the lock with atomic operations—updates that hardware performs as one indivisible action—can reduce blocking, but many workers may still repeatedly compete for the same memory locations.

A work-stealing design spreads that coordination out. Each worker normally operates on its own deque, so the common path does not require all workers to touch one shared queue.

One deque, two roles

Imagine a worker's deque with tasks arranged from top to bottom:

 top                         bottom
  |                            |
  v                            v
 [older task] [task] [new task]

The owner worker uses the bottom end for both operations:

• Push: add a newly created task at the bottom.
• Pop: take its next task from the bottom.

An idle worker, called a thief, uses the opposite end:

• Steal: take a task from the top.

The owner therefore follows a last-in, first-out pattern for its own work. If a task creates child tasks, the owner tends to execute the newest child first. This often keeps related work close in the processor's cache and supports a depth-first execution pattern.

Thieves generally take the oldest available task. They do not need to preserve the owner's exact order; they need to find useful independent work. Taking from the far end also avoids interfering with the owner's usual push and pop operations.

The key arrangement is not merely “a queue per thread.” It is one owner at one end and many possible thieves at the other.

What a normal execution looks like

Suppose worker A starts with a task that divides itself into several smaller tasks. A pushes those tasks onto A's deque, then pops work from the bottom as it continues. Most of these operations involve only A and its own deque.

Worker B may finish its current task and find its deque empty. Instead of waiting for a global queue, B chooses another worker—often using a randomized or rotating victim-selection policy—and attempts to steal from that worker's top. If A has several tasks waiting, B removes one and runs it independently.

A busy worker can therefore keep working without stopping to hand tasks to idle workers. An idle worker goes looking for work only when it needs it. This is why the technique is called work stealing: workers normally keep the work they generate, and other workers take tasks only when they have capacity.

Why the two ends reduce contention

Contention occurs when multiple threads frequently need the same mutable state at the same time. In this design, the owner usually updates the bottom index, while thieves compete over the top index. Their ordinary operations are separated rather than all targeting a single queue lock or a single head pointer.

The owner can often update its end with very cheap memory operations. A thief must coordinate with other thieves, because two idle workers might choose the same victim simultaneously. That coordination is usually implemented with compare-and-swap (CAS): hardware changes a value only if it still equals an expected old value. If another thief won first, the losing thief observes the failure and tries another task or victim.

There is one important race. If the deque contains only one task, the owner popping from the bottom and a thief stealing from the top are both trying to claim the same item. The implementation must use an atomic claim operation or equivalent synchronization so that exactly one worker receives it. The other worker treats the operation as unsuccessful.

Many production implementations also use an array as the deque's storage, with top and bottom counters that wrap around it. When the array fills, the owner can grow it. The exact algorithm varies—for example, the Chase–Lev deque is a well-known bounded-contention design—but the ownership rule remains the same.

Why this helps parallel runtimes

The arrangement improves several parts of scheduling at once:

• Common operations stay local. A worker pushing and popping its own tasks usually does not contend with every other worker.
• Load balancing is demand-driven. Idle workers obtain work from busy workers instead of requiring a central dispatcher to predict how to distribute it.
• Locality is preserved. The owner tends to continue with recently created tasks, which may reuse data already in cache.
• Parallelism remains available. Older tasks at the opposite end can be stolen while the owner follows its local chain of work.
• Coordination is limited to real competition. Atomic conflict is concentrated on steals and the rare one-item race, rather than imposed on every task operation.

This does not make contention disappear. Many thieves can target the same busy worker, task creation may still be expensive, and memory-ordering rules are subtle. A runtime also needs policies for choosing victims and deciding when to stop looking for work.

Still, the deque changes the dominant case from “all workers serialize through one scheduler queue” to “workers operate independently, and occasional thieves rebalance the system.” When a stack trace, profiler, or configuration option mentions a worker pool, a scheduler deque, or stealing, this owner-versus-thieves arrangement is usually the mechanism behind it.