Work stealing and task scheduling

In a Chase–Lev-style deque, one owner pushes and pops tasks at the bottom, while thieves try to remove tasks at the top. The asymmetric interface keeps common local operations cheap. When several items remain, the owner and a thief usually operate at different ends. When exactly one remains, both ends refer to the same task, so a coordinated atomic decision must ensure that only one participant claims it. Returning the same task twice can corrupt results even if the deque never crashes.

A growing circular array introduces another lifetime problem: a thief may still hold an older backing-array pointer while the owner resizes. Correct resizing must preserve accessible entries and retain old storage until no thief can use it. Memory ordering is part of the algorithm, especially around the last-item race and publication of the backing array. Translating sequential pseudocode into arbitrary relaxed C++ atomics is unsafe; use an implementation justified for the target language memory model.

Represent a fixed computation as a directed acyclic graph of tasks. Total work T1 is its execution time on one ideal processor, and span T∞ is the length of its longest dependency path in the same cost units. With P identical processors, total work alone needs at least T1 divided by P time; no scheduler can execute a dependency chain faster than its span. The larger quantity is a lower bound, even before accounting for task creation, cache misses, synchronization, or interference.

Randomized work-stealing analysis gives an expected work-plus-span bound for a specified scheduler and fully strict computations. That theorem is not an equality for a particular run, and its hidden constants are not measured scheduling overhead. Arbitrary blocking tasks, external I/O, resource constraints, and general dependency graphs need their own analysis. Increasing the processor count beyond the computation’s average parallelism leaves a substantial span bottleneck; changing the dependency structure may matter more than choosing a different victim-selection policy.

Uniform random victim selection spreads idle workers across potential sources of tasks. For intuition, suppose each attempt independently succeeds with a fixed probability p. Then the count of successes in n attempts is binomial, and the chance of finding nothing is the probability of zero successes. Actual attempts can be dependent because deques change, workers collide, and successful steals change the future distribution. The simple model therefore cannot establish a production scheduler’s fairness, tail latency, or speedup.

In the probability lab, first predict how zero successes changes when p rises from one quarter to one half while n stays fixed. Then increase the trial count and inspect the exact binomial bars. These controls represent an explicitly independent, fixed-probability toy experiment, not a trace of workers manipulating deques. For real scheduling, also choose task grain carefully: very small tasks amplify enqueue, steal, and wakeup costs, while very large tasks can leave idle workers unable to share a long running task.