Explain the internal working of the ForkJoinPool work-stealing algorithm?

Each worker thread in a ForkJoinPool owns its own double-ended queue (deque) of tasks rather than pulling from one shared queue.

flowchart TB
  W1[Worker 1 deque] -->|push/pop from head| W1
  W2[Worker 2 deque] -->|push/pop from head| W2
  W2 -.steal from tail.-> W1
  W3[Idle Worker 3] -.steal from tail.-> W2

When a worker forks a subtask, it pushes it onto the head of its own deque and continues working; when it needs a result, it pops from its own head too, which favors recently created, cache-warm tasks (LIFO order for the owner).

When a worker's own deque is empty, instead of sitting idle, it becomes a thief: it picks another worker at random and steals a task from the tail of that worker's deque, i.e. the oldest, typically largest, task, opposite the end the owner works from. Stealing from the tail rather than the head minimizes contention between the owner and the thief, since they're operating on opposite ends of the same structure.

This design keeps all worker threads busy without any central coordinator or shared task queue as a bottleneck, and it naturally load-balances an uneven recursive split, since idle workers actively seek out work rather than waiting for it to be assigned. It's the mechanism that lets RecursiveTask/RecursiveAction workloads, and parallel streams built on the common pool, scale close to linearly with core count for well-balanced divide-and-conquer problems.