Work-Stealing Deques and Why the Thief Takes the Oldest Task

A scheduler with one shared ready queue has a contention problem that grows with core count. Every worker that finishes a task takes the queue lock to find the next one, so the queue’s lock is touched once per task per worker, and at high task rates the lock’s cache line becomes the bottleneck rather than the work. The work-stealing scheduler removes the shared structure. Each worker owns a deque of tasks, pushes and pops at one end without coordination, and only touches another worker’s deque when its own is empty.

The arrangement is not symmetric, and the asymmetry is the whole design. A worker executes its own tasks in last-in-first-out order; a thief takes from the opposite end, first-in-first-out. Locality and load balance come from that one decision.

Why LIFO locally and FIFO for thieves

A task that spawns subtasks pushes them onto its own deque and then continues. When it finishes, the most recently pushed subtask is the one whose data is most likely still in cache, because the parent just computed it. Executing LIFO means the worker walks down the tree of spawns depth-first, staying inside a small working set. The stack of the computation and the deque are the same thing, which is why the model is called a spawn-and-sync scheduler: a task that spawns and then waits is exactly a call that pushes its continuation.

A thief takes from the far end, which holds the oldest task. The oldest task is the one whose data has had the most time to be evicted from the owner’s cache, so stealing it costs the owner the least locality. It also tends to be a large task, the root of a subtree rather than a leaf, which means one steal transfers a substantial amount of future work rather than one small unit. Stealing the newest task instead would take work the owner is about to do, which is both a cache loss and a wasted transfer.

The consequence for latency is that a stolen task may be the coarsest available granularity. A scheduler that spawns tasks in a binary tree fashion has a deque whose far end holds the top-level splits, so a steal can move half the remaining work to an idle worker. That is good for throughput and bad for fairness: the thief gets a long-running task while its own short ones wait. Runtimes that care about latency bound the size of a stealable unit, or allow partial stealing by splitting the stolen task.

The deque’s concurrent contract

The deque is accessed by one owner and any number of thieves, and the contract is weaker than a general concurrent deque. The owner may push and pop at the bottom end; thieves may only pop at the top end. There is no concurrent push from thieves, and there is no concurrent pop from the bottom by anyone but the owner. That restriction is what makes a lock-free implementation feasible.

The classic algorithm, due to Chase and Lev, keeps a circular array with two indices: top, which only thieves modify, and bottom, which only the owner modifies. The owner’s push is a store to the array at bottom followed by an increment of bottom. The owner’s pop decrements bottom and reads the slot. A thief reads top, reads bottom, and if the difference is at least two it takes the slot at top and advances top with a compare-and-swap.

The interesting case is when the difference is exactly one: the deque holds a single item, and the owner and a thief may both try to take it. The protocol resolves it by having both perform a compare-and-swap on top. Whichever succeeds takes the item; the other observes the changed top and returns empty. When the owner loses that race, its bottom decrement must be undone, because the item it thought it had popped is gone.

_Bool steal(Deque *q, Task **out) {
    size_t t = atomic_load_explicit(&q->top, memory_order_acquire);
    atomic_thread_fence(memory_order_seq_cst);   /* size must be consistent */
    size_t b = atomic_load_explicit(&q->bottom, memory_order_acquire);
    if (b <= t) return 0;                 /* empty: unsigned, so compare, don't subtract */
    *out = q->buf[t % q->cap];
    /* Only the thief advances top; the CAS decides the last-item race. */
    return atomic_compare_exchange_strong_explicit(
        &q->top, &t, t + 1, memory_order_seq_cst, memory_order_relaxed);
}

The memory orderings are load-bearing. The thief’s read of the slot must happen after its read of bottom and before its CAS on top; if the compiler or the processor reorders the slot read after the CAS, the thief may read a slot the owner has already reused. The fence between the reads of top and bottom is what guarantees that at least one of the two sides in the single-element race sees a consistent deque size, and a deque that omits it is correct only under sequentially consistent hardware. On x86-64 the store buffer makes most of this free, but the compiler will still reorder unless told not to, which is why the atomics are explicit rather than plain loads. On weakly ordered architectures such as ARM, the fences are real instructions.

The array is circular and finite. When the owner’s push finds bottom - top equal to the capacity, it must grow the array. Growth is the delicate part of the algorithm: the owner allocates a larger array, copies the live entries, and publishes the new array pointer. A thief that read the old pointer before the swap continues to use the old array, so the old array must remain valid until every thief that might hold a reference has finished. Implementations solve this with an epoch or reference-counting scheme, or by making the array pointer a tagged pointer that thieves re-read and retry. Getting this wrong produces a use-after-free that appears only under contention, which is the worst kind of bug to diagnose.

Idle workers and the cost of looking

A worker with an empty deque must find work. The obvious approach is to scan every other deque in turn, which costs O(P) per attempt and produces a burst of cache-line traffic on all P deques. The refined approach is to maintain a list of workers that are likely to have work, updated when a worker pushes a task onto an empty deque, and to pick a victim at random from that list. Random selection has a useful property: two idle workers are unlikely to choose the same victim at the same time, so the contention on any one deque stays low.

The frequency of stealing attempts matters too. A worker that spins looking for work burns a core and competes with useful work for memory bandwidth. A worker that sleeps must be woken, and the wakeup costs a syscall plus a scheduling latency. Runtimes usually spin briefly, then yield, then park, and the park is where a wakeup notification is needed. That ladder is the same economics as a spinlock’s adaptive behaviour, applied to the scheduler itself.

There is a degenerate case worth naming: one worker with a long task and every other worker idle. Stealing cannot help, because the deque holds no separate items. The computation is serial by construction, and the runtime’s only recourse is to let the idle workers park. This is why parallel runtimes ask the program to express parallelism in units, and why a loop with no spawn points runs on one core regardless of the machine.

Granularity and the overhead floor

Every spawn and join has a cost: a push, a possible steal, a synchronisation at the join, and the memory traffic between. If the task’s work is smaller than that cost, the parallel version is slower than the serial one. The ratio is not a constant: it depends on the deque’s contention, the cache behaviour of the stolen task, and the join’s fence, but the shape of the trade is fixed. Runtimes therefore ask for a grain size, either explicitly or by cutting loops into chunks, and the useful grain is the smallest chunk for which the overhead is amortised.

The overhead is also why the deque is per-worker rather than per-task. A deque per task would need a deque allocation per spawn, and the allocator would become the bottleneck. A per-worker deque allocated once and grown as needed turns the common push into an array store.

A subtler point is that the deque’s own memory is a cache line shared by the owner and any thief currently stealing. A steal writes top, which invalidates the line in the owner’s cache; the owner’s next push touches the same line and takes it back. Under heavy stealing, the deque’s cache line ping-pongs between cores, and the cost is a coherence transaction per steal. Padding the deque’s control variables to separate cache lines, or keeping top and bottom far enough apart, reduces that traffic at the cost of memory.

What the model does not provide

Work stealing balances load, not priority. A stolen task runs at the thief’s priority, and a high-priority task on a busy worker’s deque waits behind everything the worker has pushed since. Runtimes that need priority either partition workers by priority class or keep a separate queue for high-priority work, and the second reintroduces the shared structure the design was meant to avoid.

It also does not bound the latency of a task that is never stolen. If a worker’s deque holds a task and the worker keeps pushing more, the old task waits for the worker to unwind. LIFO execution means the oldest tasks are the last to run locally, and a thief only takes them when it has nothing else. A long-running system can therefore starve the bottom of a deque, which is the same shape of problem as an unbounded ready queue and is addressed by the fairness mechanisms discussed in fairness and tail latency in task schedulers.

The final limitation is that the algorithm assumes the tasks are independent and that the join graph is a tree. A computation with a cyclic dependency, or one that waits on an external event, does not fit the spawn-and-join model and must be integrated with a blocking mechanism, the interaction that makes blocking calls inside an asynchronous runtime a scheduler concern rather than a library one.