Work Stealing: Per-Processor Deques and Why Thieves Take the Oldest Task

Brent’s bound says a greedy schedule is within a factor of two of optimal, but it says nothing about how to be greedy without a central structure every processor must consult. A global ready queue satisfies greediness and fails on contention: with P processors, each task removal is a contended atomic operation on one cache line, and once many processors contend for it the queue itself becomes the bottleneck. Work stealing avoids the shared structure by giving each processor a private deque and letting idle processors take work from others only when they have none of their own.

The deque protocol

Each worker owns a double-ended queue of tasks. Three operations are permitted:

• push(task) and pop() at the same end, called the bottom, used by the owner. These are the operations on the hot path and they are not synchronised against other owners, because only the owner touches that end.
• steal() at the opposite end, the top, used by any other worker. Stealing takes the oldest task in the deque, the one pushed earliest and therefore the one closest to the root of the computation.

The asymmetry is the whole design. The owner works depth-first on the newest tasks, which are the children of what it just split; those children typically touch the same data the parent touched, so the owner stays warm in cache. A thief takes the oldest task, which is the largest remaining piece of the computation, so a single steal moves a lot of work and steals are rare. Both effects push in the same direction: locality for the owner, few and large transfers for the thief.

Push and pop at the bottom need no atomic operation between the owner and itself, and a steal needs only one atomic operation on the top. The result is that the common case, owner push followed by owner pop, is a plain array index update on a line the worker already owns.

#include <atomic>
#include <cstddef>
#include <functional>
#include <vector>

using Task = std::function<void()>;

// Lock-free deque, conceptually: bottom is owner-only, top is CAS-arbitrated.
struct Deque {
    std::atomic<size_t> top{0};      // thieves CAS this
    std::atomic<size_t> bottom{0};   // owner writes this
    std::vector<Task> buf = std::vector<Task>(1024);

    bool push(Task t) {              // owner only, no contention
        size_t b = bottom.load(std::memory_order_relaxed);
        if (b - top.load(std::memory_order_acquire) >= buf.size())
            return false;            // full; the caller grows buf and retries
        buf[b] = t;
        std::atomic_thread_fence(std::memory_order_release);
        bottom.store(b + 1, std::memory_order_relaxed);
        return true;
    }

    bool steal(Task& out) {          // any worker
        size_t t = top.load(std::memory_order_acquire);
        size_t b = bottom.load(std::memory_order_acquire);
        if (t >= b) return false;    // empty, or the owner is mid-pop
        if (!top.compare_exchange_strong(t, t + 1,
                std::memory_order_acq_rel))
            return false;            // lost the race, try another victim
        out = buf[t];
        return true;
    }
};

The subtle case is a deque holding one element, where owner pop and thief steal race for the same slot. The protocol resolves it by having the owner CAS top before taking the element; if the CAS fails, the thief won and the owner’s pop returns empty. A steal that observes top >= bottom may be seeing a deque the owner is in the middle of popping, so a failed steal is a normal outcome, not an error.

What the scheduler does

A worker loop has four steps. Pop from the local deque and run the task. If the local deque is empty, pick a victim — at random, or round-robin over the other workers — and attempt one steal. If the steal fails, repeat with another victim; after enough failures, the worker may need to park, which is the point where a runtime interacts with the operating system scheduler.

Random victim selection is not cosmetic. It makes the probability of two thieves choosing the same victim small, and it makes the analysis work: with uniform random choice, the expected number of steal attempts needed to keep all processors busy is bounded, and the expected running time is O(W/P + D) for a computation with work W and span D on P processors. The bound holds for fully strict computations, where a task may only synchronise with its parent, which is exactly the shape fork-join produces.

The O(W/P + D) bound has the same two terms as Brent’s, so work stealing is asymptotically optimal in expectation. Its practical advantage over a central queue is that the W/P term has a much smaller constant: steal attempts are the only shared-memory operations, and they occur at a rate proportional to the number of idle-to-busy transitions rather than to the number of tasks.

Contention, and where it moves to

Removing the central queue does not remove contention; it relocates it. Three places remain.

The victim’s deque top. Every steal from a given worker serialises on that worker’s top atomic. If one worker holds most of the remaining work, thieves queue on its cache line. Random victim selection spreads this, and the “largest task first” property of stealing from the top means the situation resolves quickly once a steal succeeds.

Memory reclamation. A deque grows, and a grow copies live entries while thieves may be reading them. The usual solution is a grow that publishes the new array through an atomic pointer and defers freeing the old one until no thief can still be reading it, which requires a grace-period mechanism. That is the same problem as safe memory reclamation in lock-free data structures, and it is only solvable under an assumption about which orderings the hardware actually preserves — the subject of the memory-model article.

The join and sync path. A worker that finishes a task and finds its continuation not ready must either help run other tasks or block. Blocking a worker whose child is still running is how a fork-join computation deadlocks if the pool has exactly P threads and all P block on children; the standard fix is that a blocked worker steals instead of sleeping, so it does useful work while waiting. Runtimes that do not do this need more threads than processors.

A fourth, subtler cost is migration. A stolen task runs on a different core from its parent, so the data the parent just wrote is in another core’s cache. The steal granularity determines whether that cost is amortised: stealing a task that runs for microseconds is mostly cache-miss; stealing one that runs for milliseconds amortises the migration. This is the granularity trade-off seen from the scheduler’s side, and it is why runtimes expose a minimum task size rather than letting every recursion level become a task.

The alternatives and what they cost

Three other policies are worth naming because they clarify what work stealing gives up.

A shared pool with per-worker queues plus a global overflow queue. Every worker may take any task, so balance is excellent and locality is poor, since a task’s data is usually written by a different worker. This suits irregular workloads where locality is unpredictable anyway, and the overflow queue becomes a contention point when the per-worker queues are not large enough to buffer a burst of spawning.

Static partitioning: assign each worker a contiguous range computed in advance. Zero scheduling overhead and the best possible locality, but balance depends entirely on the input. Fine for uniform work per element, catastrophic for a workload where one range contains the expensive cases — the merge-path partitioning approach exists precisely to compute a balanced split without sampling every element.

Master-worker with a central queue. Simple and correct, and the contention is proportional to the number of task completions, which is fatal for fine-grained tasks. It survives in coarse-grained systems where a task is seconds long and the queue is touched a few thousand times.

Work stealing sits between these: nearly static locality on the owner’s side, dynamic balance through steals, and shared-memory traffic proportional to imbalance rather than to work. Its weakness is the tail. When only a few large tasks remain, thieves converge on their owners and the last phase is dominated by a handful of steals and the cache misses they cause. Runtimes mitigate this by splitting large tasks eagerly when they are stolen rather than handing the whole thing over, which converts one long steal into two medium tasks.

Reading a trace

A scheduler trace shows the shape directly: total busy time across all workers equals W plus overhead, wall time is T_P, and utilisation is W/(P·T_P). A run with utilisation near 1 until a final phase where it collapses to 1/P is a span problem, and no scheduler will fix it. A run with utilisation low throughout and many failed steals is a granularity problem, with tasks too small to amortise the steal. The two look similar in a summary and are distinguishable only by the distribution of task durations, which is why runtimes expose per-worker counters for steals, failed steals, and task counts.