How does ForkJoinPool's work-stealing algorithm work, and what is the role of the per-worker deques?
answer
- Per-worker deque, not one shared queue
- Owner: push/pop HEAD, LIFO (cache-hot, depth-first)
- Thief: steal from TAIL, oldest = biggest chunk
- Opposite ends → rarely the same slot
- Pull model: idle threads steal work to themselves
basics
~20 sEach ForkJoinPool worker owns a double-ended queue (deque) of tasks, pushing and, by default, popping at one end. An idle worker steals from the opposite end of a busy worker's deque, so threads stay busy without a central queue.
solid answer
~50 sForkJoinPool gives every worker thread its own work-stealing deque (double-ended queue). When a task forks subtasks, they are pushed onto the current worker's deque. By default the worker processes its own deque in LIFO order, popping from the top (head): it stays on recently forked, cache-hot subtasks and runs the recursion depth-first. (A pool built with `asyncMode` set to true takes its own tasks FIFO instead, for event-style tasks that are never joined.) When its deque is empty, a worker becomes a thief: it scans other queues from a random start and steals from the base (tail), taking the oldest, largest-grained task. Because owner and thieves work opposite ends, their atomic claims rarely hit the same slot. Idle threads pull work to themselves, so load balances without a central queue. If subtasks block, stealing can't compensate and cores idle.
code
java · 27 lines// Sum a large array via divide-and-conquer on a ForkJoinPool.
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;
final class SumTask extends RecursiveTask<Long> {
private static final int THRESHOLD = 10_000;
private final long[] data; private final int lo, hi;
SumTask(long[] data, int lo, int hi) { this.data = data; this.lo = lo; this.hi = hi; }
@Override protected Long compute() {
if (hi - lo <= THRESHOLD) { // base case: small enough, do it directly
long sum = 0;
for (int i = lo; i < hi; i++) sum += data[i];
return sum;
}
int mid = (lo + hi) >>> 1;
SumTask left = new SumTask(data, lo, mid);
SumTask right = new SumTask(data, mid, hi);
left.fork(); // push left onto THIS worker's deque (stealable)
long rightResult = right.compute(); // compute right inline (no extra task overhead)
long leftResult = left.join(); // wait for left (maybe stolen by another worker)
return leftResult + rightResult;
}
}
// Usage: ForkJoinPool.commonPool().invoke(new SumTask(data, 0, data.length));go deeper
Can state that each worker has its own queue and idle workers steal tasks from others so no thread sits idle while work remains.
Knows the queue is a double-ended deque, the owner uses one end and thieves the other, and stealing balances load without a central queue.
Explains LIFO-own-end vs FIFO-steal-end and why (cache locality, depth-first bounding, stealing the biggest chunk), and that opposite-end access plus CAS keeps contention low.
Reasons about the push-vs-pull scheduling inversion, scalability vs a single-queue pool, randomised victim selection, and the failure mode when tasks block; relates it to sizing and to alternatives for blocking workloads.
## The data structure: a per-worker deque A **deque** ("deck", double-ended queue) is a queue you can add to and remove from at *both* ends. In ForkJoinPool, **every worker thread owns one deque** holding the tasks it has forked. There is no single shared queue that all threads fight over — that decentralisation is the whole point. Two ends matter (the JDK source calls them `top` and `base`): - **Head / top** — the owner's end. The owner **pushes** newly forked subtasks here and, by default, **pops** from here (LIFO, last-in-first-out). - **Tail / base** — the thieves' end. Idle workers **steal** from here. ## How a worker runs its own work (LIFO, head) When `compute()` calls `fork()`, the subtask is pushed onto the **head** of the current worker's deque. When the worker needs more work, it **pops from the head** — the most recently forked task. Why LIFO for yourself? - **Cache locality:** the most recent subtask shares data with what you just touched, so it's likely still in CPU cache. - **Depth-first traversal:** popping the newest task drives the recursion down to base cases quickly, which keeps the deque small and memory bounded rather than fanning out breadth-first. LIFO is the default, which the Javadoc calls the "locally stack-based mode". A pool constructed with `asyncMode = true` takes its own tasks **FIFO** instead, which suits event-style tasks that are never joined, at the cost of more contention among task producers and consumers, since the owner then takes from the end thieves use. The JDK's virtual-thread scheduler is such a FIFO-mode pool, distinct from the common pool, which runs in LIFO mode. ## How stealing works (FIFO, tail) When a worker's own deque is **empty**, it doesn't sleep — it tries to **steal**. It picks another worker (the **victim**, chosen with some randomisation to spread contention) and takes a task from the victim's **tail** — the *oldest* task the victim pushed. Why steal the oldest/biggest task? The oldest task sits highest in the recursion tree, so it represents the **largest remaining chunk** of work — not yet split into tiny pieces. Stealing one big task gives the thief plenty to do (and more subtasks to later be stolen from *it*), minimising how often threads have to steal again. ## Why opposite ends = low contention The owner works the **head**; thieves work the **tail**. Because they operate on opposite ends, they almost never touch the same slot. In JDK 25 and 27 the arbitration sits on the array slots themselves: - a thief claims the slot at the tail with an atomic **compare-and-swap (CAS)**, a hardware instruction that updates a value only if it still holds an expected value, so threads coordinate without a lock; - the owner's pop clears the slot at the head with an atomic exchange (`getAndSet`), so when the two meet on a nearly empty deque exactly one of them gets the last task. Most contention therefore comes from thieves competing for the same victim, and a thief that keeps losing moves on to another queue. ## Push vs pull: the key inversion A classic thread pool **pushes** work from a central queue out to workers — that central queue becomes a contention hotspot as core counts rise. Work stealing **inverts** this: work stays local to the worker that created it, and **idle threads pull work to themselves**. Balancing is demand-driven and happens only when a thread actually goes idle, so there's no coordinator and no global bottleneck. This is what lets Fork/Join scale across many cores on irregular, recursively-generated workloads where you can't predict task counts up front. ## Assumptions and failure modes Work stealing balances load **only if there are stealable tasks and workers don't block**: - If subtasks **block** (I/O, locks, sleeps), each blocked worker stops running tasks. It uses no CPU, but the pool does not replace a worker blocked on plain I/O, so fewer workers run than the pool's parallelism (sized to cores by default) while queued tasks wait. - If you **don't split finely enough**, there's nothing to steal and some cores idle; split **too** finely and per-task overhead dominates. Choosing a sensible threshold (or letting parallel streams choose) matters. ## Mental model Picture each worker with a personal stack of work. In the default mode you grab from the top of *your own* stack (fresh, cache-hot). When your stack is empty, you reach over and grab from the *bottom* of a neighbour's stack — the big, old job they haven't gotten to. Everyone stays busy; nobody fights over one shared pile.
- Why does the owner use LIFO on its own end but thieves take FIFO from the other end?LIFO keeps the owner on freshly forked, cache-hot subtasks and drives depth-first recursion (bounding deque size). The thief takes the oldest task from the far end because it's the largest, least-split chunk — one steal yields lots of work and minimises future steals, and using the opposite end avoids contending with the owner.
- What happens to throughput if your compute() tasks frequently block on I/O?Each blocked worker stops running tasks. It uses no CPU, but the pool does not replace a worker blocked on plain I/O, so fewer workers run than there are cores while queued tasks wait. With parallelism at the core count, a handful of blocked tasks can starve the pool. Move blocking work to a separate executor or virtual threads, or wrap an occasional wait in a ManagedBlocker.
- Saying there is one shared task queue — each worker has its own deque
- Claiming workers steal the newest task — they steal the oldest/biggest from the tail
- Saying a default pool's worker runs its own deque FIFO — it's LIFO unless asyncMode is set
- Thinking stealing requires a global lock — opposite-end access + CAS keeps it mostly contention-free
- Assuming work stealing fixes load imbalance even when tasks block — it can't reclaim a blocked worker
- ForkJoinPool work-stealing deques
- Java 1.7
The slot arbitration described (CAS on the stolen slot, an atomic exchange on the owner's pop) is the JDK 27 implementation and the same at JDK 25 LTS; the LIFO default and the asyncMode FIFO option are the public contract.
context
- ForkJoinPool (Java SE 27 & JDK 27)docs.oracle.com
- ForkJoinPool.java at jdk-27-gagithub.com
- ForkJoinPool.java at jdk-27-gagithub.com