How do work-stealing schedulers (like Go's or Java's ForkJoinPool) balance load across threads?

#The problem with a single shared queue

The naive way to distribute work across a pool of threads is one global queue: every worker pulls the next task from the same place. This is simple and correct, but it does not scale, because every pull and every push must synchronize against that one queue — as core count grows, contention on the queue's lock (or the CAS retries on a lock-free implementation) grows with it, and at high core counts the threads spend more time fighting over the queue than doing the work it hands out. It also has poor cache behavior: a task picked up by whichever thread happens to win the queue lock has no relationship to which thread produced it, so there is no locality to exploit.

Work-stealing schedulers — the design behind Java's ForkJoinPool, Go's goroutine scheduler, .NET's thread pool, and Rust's rayon and Tokio — solve this by giving every worker thread its own local queue (usually a double-ended queue, or deque) and making the common case require no synchronization with any other thread at all.

#How the local deque is used

Each worker treats its own deque as a stack for its own purposes: when it creates new sub-tasks (say, splitting a divide-and-conquer computation in half), it pushes them onto one end of its own deque, and when it looks for its next unit of work, it pops from that same end. Because only the owning thread ever touches that end, push and pop are effectively single-threaded operations requiring no locking — the fast path is as cheap as an ordinary stack.

The deque only becomes a point of contention when a different thread's local queue runs dry. An idle worker becomes a thief: instead of sitting idle, it picks another worker at random as a "victim" and tries to steal a task from the opposite end of that victim's deque. This two-ends design is deliberate, not incidental:

• The owner works LIFO on its own end, which tends to pop the most recently created, finest-grained sub-tasks first — the ones still hot in cache and closest to the bottom of a recursive split.
• Thieves steal FIFO from the other end, which tends to grab the oldest, coarsest-grained tasks — typically the largest remaining chunks of work in a divide-and-conquer tree. Stealing a big chunk amortizes the cost of the steal (and any resulting cache migration) over more actual work, instead of paying synchronization overhead for a tiny task.
• Operating on opposite ends also minimizes collisions between the owner's fast local pops and a thief's occasional steal — the two operations only need to coordinate at all when the deque has shrunk down to its last one or two items.

#Go's scheduler: the GMP model

Go's runtime scheduler names the same idea with different letters: Goroutines are the units of work, Machine threads are real OS threads, and Processors are logical execution contexts — there are GOMAXPROCS of them, and each holds a local run queue of up to 256 runnable goroutines. A goroutine only runs while attached to an M that is attached to a P; when a P's local run queue empties, its M looks, in order, at the global run queue, then the network poller for goroutines unblocked by completed I/O, and finally at another P chosen at random, stealing roughly half of that P's local queue in one shot (not just one goroutine, which amortizes the steal's cost, mirroring the "steal the big remaining chunk" idea from ForkJoinPool). Randomizing the victim avoids every idle P hammering the same busy P at once, and moving half the queue rather than one item means a steal does not need to happen again immediately.

#Java's ForkJoinPool

ForkJoinPool is Java's dedicated home for divide-and-conquer parallelism (RecursiveTask/RecursiveAction, and the engine underneath parallel streams). Each ForkJoinWorkerThread owns a work-stealing deque; calling fork() on a subtask pushes it to the calling thread's own deque, and calling join() on a subtask that has not completed lets the calling thread go help — either by executing that specific task if no one else has grabbed it, or by stealing other pending work — rather than simply blocking, which is what makes fork/join so much better than a plain ExecutorService for recursive splitting: the thread that is "waiting" is itself a candidate thief.

The broader lesson for backend engineers: any time your workload's tasks have unpredictable or highly variable duration — a recursive parallel sort, a batch job that fans out per-record work of wildly different cost, a request handler that forks off sub-computations — a work-stealing pool will keep every core productive far better than a fixed-partition or single-shared-queue design, at the cost of a scheduler that is meaningfully more complex to implement (which is exactly why you reach for ForkJoinPool, rayon, or Go's built-in scheduler instead of writing one yourself).