Work-Stealing Scheduler: Parallel Task Load Balancing

Scheduler Setup

Worker cores 5

Total tasks 70

Mean task time 550 ms

Live Stats

0 / 70 tasks done

Throughput

0.0 /s

Steals so far

Load imbalance (σ)

0.00

Idle cores

How it works

Each of the N worker cores owns a private deque (double-ended queue) of pending tasks. A worker always pops its own next task from the bottom of its own deque — cheap, uncontended, no locking needed since only the owner touches that end.

while true:
  if myDeque not empty:
    task = myDeque.popBottom()      // LIFO, cache-friendly
  else:
    victim = randomOtherCore()
    if victim.deque not empty:
      task = victim.deque.popTop()  // FIFO steal, rare & random
    else:
      idle
  run(task)

When a core drains its own deque it becomes a thief: it picks a victim uniformly at random and steals from the opposite end of that victim's deque (the oldest task), which minimises contention with the victim's own owner-side pops. This is the algorithm behind Cilk, Intel TBB, Java's ForkJoinPool, Rayon and Go's runtime scheduler.

Worker cores — how many parallel deques share the task pool; more cores finish faster but idle more often near the end, when only a few tasks remain.
Total tasks — the work pool, split round-robin across cores at the start (visible as uneven stack heights).
Mean task time — each task's real duration is drawn as 0.4×–1.6× this mean, so cores finish their queues at different moments and start stealing.
Stealing OFF — cores that empty their own deque simply go idle, even while a neighbour still has a tall stack — this is what work stealing exists to prevent.

Blumofe & Leiserson's classic result: random-victim work stealing achieves an expected running time of T₁/P + O(T∞) on P cores, where T₁ is the total work and T∞ the critical-path length — near-optimal without any central scheduler.

All tasks complete

Queued task Running task Idle core

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.