a work-stealing scheduler

Picture a row of cashiers, each with their own personal line. If everyone funnels into one shared line, a single contended doorway becomes the bottleneck. If instead each cashier keeps a private line but, when idle, walks over and serves the back of a busy neighbour's line, the load balances itself without a central traffic cop. A work-stealing scheduler runs tasks exactly this way: each worker thread has its own task deque, and an idle worker steals work from a busy worker's deque.

The structure is a per-worker double-ended queue (a deque). A worker pushes and pops its own newly-spawned tasks at one end — its private end — like a stack: last in, first out. This is deliberate. Recently-created tasks are usually the children of what the worker is doing right now, so their data is hot in cache, and LIFO keeps the worker deep in one subtree of work. When a worker's deque runs empty, it picks a random victim and steals from the other end — the tail — taking an older, bigger task that is likely independent. Stealing from the far end also minimises contention with the owner, who is busy at the near end. This is the model behind Tokio, Go's goroutine scheduler, Intel TBB, and the .NET thread pool.

Why this wins: it has almost no central coordination, so it scales to many cores; it is provably efficient for divide-and-conquer (fork-join) workloads; and it self-balances — a worker that finishes early does not idle, it helps. The honest caveats: steals touch another thread's data and so are not free (they cost a synchronised operation and a cache miss), so a good scheduler keeps them rare by stealing big chunks; and if tasks are wildly uneven or a worker blocks instead of yielding, balance suffers. It is a heuristic for throughput, not a guarantee about any single task's latency.