Introduction

Your laptop has multiple cores. When you run a parallel program, something has to decide which core runs which piece of work — and doing that badly wastes hardware you already paid for.

The naive answer is to hand out tasks in advance: split the problem into nn equal chunks and give one chunk to each core. But tasks rarely finish at the same time. One core may be done in a millisecond while another is still grinding through its chunk. The idle core just sits there.

Work-stealing fixes this with one elegant rule: whenever a core runs out of tasks, it steals a task from the back of another core's queue. No central coordinator, no global lock — each core manages its own local deque and only reaches out when it has nothing left to do.

The result is near-perfect load balance with almost no overhead. It was formalized by Robert Blumofe and Charles Leiserson in 1999, and it now powers scheduling runtimes from Cilk and Java's ForkJoinPool to Rust's Rayon and Go's goroutine scheduler.

Try It

Each column below is a CPU core with a queue of tasks (colored blocks). Cores drain their queue from the top; when a core goes idle it steals from the bottom of the longest neighbor's queue.

<!-- Work-stealing demo: 4 cores, each with a queue of tasks (top=active, bottom=steal target) -->
<div class="toolbar">
  <button id="btn-start" type="button">Start</button>
  <button id="btn-steal-toggle" type="button" class="ghost">Stealing: ON</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="cores-row" class="cores-row"></div>
<div class="legend-row">
  <span class="legend-item"><span class="legend-dot busy"></span>Busy</span>
  <span class="legend-item"><span class="legend-dot idle"></span>Idle</span>
  <span class="legend-item"><span class="legend-dot stealing"></span>Stealing</span>
</div>
<div id="stats" class="stats"></div>

/* Demo layout for work-stealing scheduler simulation */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.toolbar { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .75rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
/* Core columns, each holding a vertical stack of task blocks */
.cores-row { display: flex; gap: 10px; flex-wrap: wrap; }
.core-col { display: flex; flex-direction: column; align-items: center; gap: 4px; min-width: 60px; }
.core-label { font: 600 11px system-ui; color: #555; text-transform: uppercase; letter-spacing: .04em; }
.core-box { width: 56px; min-height: 160px; border: 2px solid #c0c8d0; border-radius: 8px;
            display: flex; flex-direction: column; align-items: center; justify-content: flex-start;
            padding: 4px; gap: 3px; transition: border-color .2s; }
.core-box.busy { border-color: #2196f3; }
.core-box.idle { border-color: #aaa; }
.core-box.stealing { border-color: #ff9800; background: #fff8f0; }
/* Individual task block — color = origin core, number = remaining ticks */
.task { width: 44px; height: 20px; border-radius: 4px; display: flex; align-items: center;
        justify-content: center; font: 700 10px ui-monospace; color: #fff;
        transition: opacity .15s; }
.task.active { outline: 2px solid #fff; outline-offset: -2px; }
.legend-row { display: flex; gap: 14px; margin-top: .5rem; flex-wrap: wrap; }
.legend-item { display: flex; align-items: center; gap: 5px; font-size: .78rem; color: #555; }
.legend-dot { width: 12px; height: 12px; border-radius: 50%; border: 2px solid; }
.legend-dot.busy { border-color: #2196f3; }
.legend-dot.idle { border-color: #aaa; }
.legend-dot.stealing { border-color: #ff9800; background: #fff8f0; }
.stats { margin-top: .5rem; font-size: .82rem; color: #555; min-height: 1.3em; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Work-stealing scheduler simulation: cores drain their own queue top-to-bottom; idle cores steal from the bottom of the longest neighbor's queue.

// Simulation configuration
const NUM_CORES = 4;
const TASK_COLORS = ['#e63946','#2a9d8f','#e9c46a','#f4a261','#264653','#6a4c93','#43aa8b','#f94144'];
let stealingEnabled = true;
let running = false;
let rafId = null;

// Simulation state: cores array, task counters, steal counter
let cores = [];
let totalTasks = 0;
let completedTasks = 0;
let steals = 0;

function makeTask(id, color, weight) {
  // Create a task: id, display color, total weight (ticks to complete)
  return { id, color, weight, remaining: weight };
}

function initCores() {
  // Initialize cores with uneven task loads to show the imbalance work-stealing fixes
  cores = [];
  totalTasks = 0;
  completedTasks = 0;
  steals = 0;
  const taskId = { v: 0 };
  for (let i = 0; i < NUM_CORES; i++) {
    const queue = [];
    // Skewed initial load: core 0 gets 8 tasks, core 1 gets 6, cores 2-3 get 2 each
    const taskCount = i === 0 ? 8 : i === 1 ? 6 : 2;
    for (let t = 0; t < taskCount; t++) {
      const color = TASK_COLORS[(taskId.v) % TASK_COLORS.length];
      const weight = 3 + Math.floor(Math.random() * 5);
      queue.push(makeTask(taskId.v++, color, weight));
      totalTasks++;
    }
    cores.push({ queue, status: 'idle', active: null });
  }
}

// Render all cores and their task queues to the DOM
function render() {
  const row = document.getElementById('cores-row');
  row.innerHTML = '';
  for (let i = 0; i < cores.length; i++) {
    const c = cores[i];
    const col = document.createElement('div');
    col.className = 'core-col';
    const label = document.createElement('div');
    label.className = 'core-label';
    label.textContent = 'Core ' + (i + 1);
    col.appendChild(label);
    const box = document.createElement('div');
    box.className = 'core-box ' + c.status;
    // Show the currently executing task at the top of each core box
    if (c.active) {
      const el = document.createElement('div');
      el.className = 'task active';
      el.style.background = c.active.color;
      el.textContent = c.active.remaining;
      box.appendChild(el);
    }
    for (const t of c.queue) {
      const el = document.createElement('div');
      el.className = 'task';
      el.style.background = t.color;
      el.textContent = t.remaining;
      box.appendChild(el);
    }
    col.appendChild(box);
    row.appendChild(col);
  }
  updateStats();
}

function updateStats() {
  const done = completedTasks;
  const total = totalTasks;
  const pct = total > 0 ? Math.round((done / total) * 100) : 0;
  let msg = i18nFmt('Tasks: %done% / %total% (%pct%%)', { done, total, pct });
  if (steals > 0) msg += ' ' + i18nFmt('| steals: %steals%', { steals });
  if (done === total && total > 0) msg = 'All tasks complete!';
  document.getElementById('stats').textContent = msg;
}

// Animation tick: advance one scheduling step per interval
let lastTime = 0;
const TICK_MS = 350;
function tick(now) {
  if (now - lastTime < TICK_MS) { rafId = requestAnimationFrame(tick); return; }
  lastTime = now;

  // Step 1: each core advances its active task by one tick, or picks the next from its queue
  let allDone = true;
  for (const c of cores) {
    if (c.active) {
      allDone = false;
      c.active.remaining--;
      if (c.active.remaining <= 0) {
        completedTasks++;
        c.active = null;
        c.status = 'idle';
      } else {
        c.status = 'busy';
      }
    }
    if (!c.active && c.queue.length > 0) {
      allDone = false;
      c.active = c.queue.shift();
      c.status = 'busy';
    }
  }

  // Step 2 (if stealing enabled): idle cores with empty queues steal from the longest neighbor
  if (stealingEnabled) {
    for (const c of cores) {
      if (!c.active && c.queue.length === 0) {
        // Find the neighbor core with the most queued tasks
        let victim = null;
        let maxLen = 1;
        for (const other of cores) {
          if (other !== c && other.queue.length > maxLen) {
            maxLen = other.queue.length;
            victim = other;
          }
        }
        if (victim) {
          // Steal from the bottom of the victim's queue (pop = bottom, mimicking deque steal)
          const stolen = victim.queue.pop();
          c.queue.unshift(stolen);
          c.status = 'stealing';
          steals++;
          allDone = false;
        } else {
          c.status = c.active ? 'busy' : 'idle';
        }
      }
    }
  }

  render();
  if (allDone && completedTasks === totalTasks) {
    running = false;
    document.getElementById('btn-start').disabled = false;
  } else if (running) {
    rafId = requestAnimationFrame(tick);
  }
}

function start() {
  if (running) return;
  running = true;
  document.getElementById('btn-start').disabled = true;
  lastTime = 0;
  rafId = requestAnimationFrame(tick);
}

function reset() {
  running = false;
  if (rafId) cancelAnimationFrame(rafId);
  initCores();
  document.getElementById('btn-start').disabled = false;
  render();
}

function toggleStealing() {
  stealingEnabled = !stealingEnabled;
  const btn = document.getElementById('btn-steal-toggle');
  btn.textContent = stealingEnabled ? 'Stealing: ON' : 'Stealing: OFF';
}

document.getElementById('btn-start').addEventListener('click', start);
document.getElementById('btn-reset').addEventListener('click', reset);
document.getElementById('btn-steal-toggle').addEventListener('click', toggleStealing);

// Initialize and render on load
initCores();
render();
Result
Console

Press Start to run the simulation. Toggle Stealing on/off to see what happens when idle cores just wait instead of stealing. With stealing off, fast cores finish early and sit idle while slow cores are still overwhelmed — the classic imbalance. With stealing on, the load levels out automatically.

The Real Complexity

Work-stealing is not just a good heuristic — it has tight theoretical guarantees.

Any parallel computation can be described by two numbers: work T1T_1 (total instructions if run on one core) and span T∞T_\infty (the length of the longest dependency chain, the minimum time even with infinite cores). The best you can hope for on PP cores is roughly T1/P+T∞T_1/P + T_\infty.

Blumofe and Leiserson proved in 1999 that a randomized work-stealing scheduler achieves expected time T1/P+O(T∞)T_1/P + O(T_\infty) — matching the optimal lower bound up to a small constant. They also showed that the expected number of steal attempts is only O(P⋅T∞)O(P \cdot T_\infty), so most steals never happen and the overhead stays tiny.

The key insight is the deque (double-ended queue): each core pushes and pops its own tasks from the top (cheap, no contention), while a thief steals from the bottom (one compare-and-swap is enough). This separation is what keeps the fast path fast.

Work-stealing sits in the broader landscape of load balancing algorithms. Unlike static partitioning or work-sharing (where a central scheduler pushes tasks), work-stealing is pull-based and decentralized — exactly the properties that make it scale to hundreds of cores without a bottleneck.

Where It Matters

Work-stealing is everywhere modern software runs fast in parallel:

  • Cilk / Cilk Plus: the original academic language (MIT, 1994) built around fork-join parallelism and work-stealing. Its ideas were absorbed into Intel's Threading Building Blocks and OpenCilk.
  • Java ForkJoinPool (Java 7, 2011): the standard pool behind parallelStream() and CompletableFuture. Every Java server that uses parallel streams relies on work-stealing under the hood.
  • Rust Rayon: the data-parallelism library that makes par_iter() as easy to write as iter() — backed by a work-stealing deque pool.
  • Go runtime: Go's goroutine scheduler uses a work-stealing variant to distribute goroutines across OS threads, letting millions of goroutines coexist with low overhead.
  • WebAssembly / browser workers: emerging WASM threading proposals use work-stealing to spread computation across Web Workers.

The common thread: whenever you have irregular parallel workloads — recursive divide-and-conquer, tree traversals, graph searches — static assignment wastes cores, and work-stealing adapts on the fly. It is the practical answer to the scheduling problem for shared-memory parallel machines.

Conclusion

Work-stealing captures something rare in computer science: a simple rule that is also provably near-optimal. An idle core reaches out and takes a task — no central authority, no global coordination, no pre-planned allocation. Yet that one rule guarantees expected running time within a small constant of the theoretical best on PP cores.

The next time your parallel program finishes faster than you expected, there is a good chance a work-stealing scheduler quietly rearranged the work behind the scenes. It is the closest thing to a free lunch that scheduling theory has ever found.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/work-stealing/Content licensed under CC BY-NC 4.0.