A team runs their whole workload on a work-stealing thread pool and sees poor CPU utilization and erratic tail latency. What properties of a workload make a work-stealing scheduler perform badly, and what would you change?

## What the scheduler assumes Work stealing is a throughput-optimizing scheduler for a specific workload shape: **many short, CPU-bound, non-blocking tasks, generated recursively, whose individual completion order does not matter.** Every failure mode below is a violation of one of those assumptions. ## Failure mode 1 — tasks that block A worker that blocks (network call, disk, a lock, waiting on a queue) is a worker not executing tasks. Two things follow. First, the pool loses parallelism silently: with W workers and B blocked, you have W−B running, and utilization drops with no obvious error. Second, the blocked worker's deque may still hold runnable tasks, and those are reachable only through the steal path — if the pool has no other idle workers, they are effectively stranded. The pathological case is a task that blocks *waiting for another task in the same pool*: all workers can end up blocked on work that only they could execute, which is a scheduler-level deadlock. Remedies, in order of preference: keep blocking work out of the compute pool and give it its own pool sized for waiting rather than for cores; make the operation non-blocking (async completion) so the worker returns to the scheduler; or use the runtime's managed-blocking hook, which tells the scheduler to spin up a compensating worker for the duration so parallelism is preserved. ## Failure mode 2 — granularity too fine Every task costs something: allocation, a push, a pop, and its share of failed steal attempts and cache traffic. If the task body is comparable to that fixed cost, you have built an expensive way to do nothing. The symptom is that parallel is *slower* than serial, and profiles show scheduler internals near the top. Fix by batching: process a range of items per task, and give recursive splitting a **sequential cutoff** — below N items, just do it in a loop. A useful heuristic is to size tasks so the body is at least a few microseconds, well above the cost of one push/pop pair, and to aim for a few times more tasks than workers rather than millions. ## Failure mode 3 — granularity too coarse The opposite error: 8 workers, 10 tasks, one of which takes ten times as long. Once the short tasks are done, the deques are empty, so there is nothing to steal, and 7 workers idle while 1 finishes. Work stealing can only rebalance work that has been *expressed as stealable tasks*; it cannot subdivide a running task. This is the source of most "we parallelized it and got 2x on 16 cores" results with skewed data. Fix by expressing more parallelism: split recursively so that near the root there are large stealable subtrees, split by cost estimate rather than by item count when items are non-uniform, and avoid pre-partitioning statically into exactly W chunks — that reintroduces the imbalance the scheduler was supposed to absorb. ## Failure mode 4 — steal contention and thrash When many workers are simultaneously out of work, they hammer the steal path: random victims, failed compare-and-swaps, cache lines bouncing. Symptoms are high CPU with low useful throughput, and steal-attempt counters far exceeding successful steals. Mature runtimes mitigate with backoff, spin-then-park, and re-scanning heuristics, but the root cause is usually failure mode 3 (not enough stealable work) or an over-sized pool for the available parallelism. ## Failure mode 5 — fairness and tail latency The local LIFO order is deliberately unfair. A task pushed early can sit at the bottom of a busy worker's deque while that worker keeps generating and consuming newer tasks, and nothing bounds how long it waits unless a thief happens to pick that victim. For a batch computation that is irrelevant — only the finish time of the whole thing matters. For independent user requests it is exactly wrong: you get erratic p99 with no head-of-line discipline, and completion order unrelated to arrival order. The structural fix is **workload isolation**: serve latency-sensitive independent requests from a fair FIFO executor, run recursive CPU-bound computations on the work-stealing pool, and give blocking work its own pool. Sharing one pool across classes couples their tails: a burst of one class occupies workers and inflates the other's latency. Note that many production work-stealing runtimes already treat externally submitted tasks FIFO while keeping internally forked tasks LIFO, precisely because these two workloads want different disciplines. ## How to diagnose rather than guess Instrument before changing anything: per-worker busy vs idle time, deque depth over time, steal attempts vs successful steals, count of blocked/compensating workers, and task duration distribution. That data distinguishes "nothing to steal" (idle workers, empty deques) from "too much stealing" (high attempts, tiny tasks) from "blocked pool" (workers alive but not running tasks) — three problems whose fixes are unrelated and whose symptoms all look like "the pool is slow".