Coding interview: Implement a work-stealing scheduler

Prompt and context

Implement a scheduler with a fixed N workers. Its public API is submit(task), shutdown(), and awaitTermination(). Each worker owns a deque: the owner takes local work in LIFO order, while an idle worker steals from the opposite end in FIFO order. Tasks may create more tasks, but new root submissions are rejected after shutdown begins.

You may start with a mutex-protected correctness baseline and then explain how a Chase–Lev-style lock-free deque would replace it. The scheduler must not lose or execute a task twice. A task failure must not kill the worker loop. Cover empty queues, no steal victim, shutdown races, and blocking workers.

What the interviewer is testing

A strong answer names the concurrency boundary between owner operations and steals instead of merely saying “use a thread pool.” Local LIFO preserves locality and depth-first behavior; remote FIFO gives a thief older, often larger work. The interviewer also checks whether submission, stopping acceptance, draining, and worker exit form an explicit state machine, and whether you can identify the linearization point that makes task claiming unique.

Clarifying questions

1. Can tasks block on I/O? If yes, use a separate I/O pool or counted blocking compensation; more stealing cannot help when every worker is blocked.
2. Does submit return a future? If yes, define exception propagation and cancellation; this answer returns a future, while cancellation only guarantees that work not yet claimed will not run.
3. Must the deque be lock-free and unbounded? If not, implement the locked deque first and upgrade only when contention and reclamation requirements are proven.
4. Is shutdown immediate or graceful? This answer is graceful: reject new roots, drain accepted work, then exit.

30-second answer

I give every worker a deque and use LIFO at the owner end and FIFO at the steal end. I first build a locked baseline: submit selects a queue and wakes a worker; a worker pops local work, then steals from other queues when empty. A task is executed only after one operation successfully removes it, so it cannot be claimed twice. Shutdown stops new submissions, and workers exit only when the scheduler is draining, outstanding work is zero, and all queues are empty. Tests cover concurrent submit, steal races, child-task creation, exceptions, shutdown, and idle waiting.

Step-by-step deep dive

Define states accepting, draining, and terminated. During accepting, submit puts work on a lightly loaded deque, increments an outstanding counter atomically, and wakes a worker. During draining, whether running tasks may create children is part of the contract; this version allows children and keeps draining until the count reaches zero.

type Task = () => void;

class WorkStealingScheduler {
  private readonly queues: Array<Deque<Task>>;
  private accepting = true;
  private outstanding = 0;

  submit(task: Task): void {
    if (!this.accepting) throw new Error("scheduler is shutting down");
    const queue = this.chooseQueue();
    queue.pushBottom(task);
    this.outstanding += 1;
    this.wakeOneWorker();
  }

  run(workerId: number): void {
    while (true) {
      const task = this.queues[workerId].popBottom()
        ?? this.stealFromOtherQueues(workerId);
      if (!task) {
        if (!this.accepting && this.outstanding === 0) return;
        this.parkBriefly();
        continue;
      }
      try { task(); } finally { this.outstanding -= 1; }
    }
  }
}

The snippet is intentionally single-threaded pseudocode for the state transitions. A real implementation must use one synchronization protocol for submit, outstanding, shutdown, and wakeups. To avoid the lost-wakeup race where a task arrives just after an empty check, use a condition variable, semaphore, or counted event rather than raw sleep.

The locked baseline preserves three invariants: a task runs only after successful removal from a deque; no two operations can remove the same task; and outstanding equals accepted but unfinished work. When a running task creates children, register the children before decrementing the parent, or a transient zero can trigger premature termination.

Fairness depends on victim selection and steal batch size. Pure randomness can be skewed for a long time; fixed round-robin can synchronize many thieves on one hot queue. Use randomized starts, failed-steal backoff, and bounded batches. Tiny uniform tasks favor single or small steals; recursive workloads often benefit from taking an older, larger chunk.

Lock-free is an optimization, not the default answer. Oracle’s ForkJoinPool uses work stealing and exposes steal counts for tuning. A Chase–Lev deque additionally needs atomic indices, memory ordering, growth, and safe reclamation. Without an explicit single-owner/multiple-thief model and a reclamation plan, hand-written “lock-free” code is more likely to duplicate work or use freed storage than the locked baseline.

Expected local push/pop cost is O(1); a steal is O(1) or O(batch), while scanning V victims naively costs O(V). Space is O(T + N), where T is unfinished work and N is worker count. Blocking I/O invalidates the assumption that an idle worker can always steal, so isolate blocking work or cap it.

High-quality sample answer

I would deliver a locked correct version first and then discuss a lock-free upgrade. Each worker has a private deque; the owner uses LIFO at the bottom and thieves use FIFO at the top, with separate owner and steal synchronization. A task enters execution only after a successful pop or steal, which is its claiming linearization point.

Submission and shutdown are separate concerns. Shutdown rejects new roots, then waits for outstanding work to reach zero. If running tasks can create children, the draining contract must explicitly allow and count them; otherwise reject them and let the task handle the error. Workers wait on a condition variable or semaphore rather than spin, and task exceptions are captured in futures and metrics instead of escaping the worker loop.

I would release simultaneous short and long tasks with a barrier, assert exactly-once execution and actual steals, and verify that queues drain. Then I would inject child creation, shutdown during a steal, blocking work, task exceptions, and repeated shutdown calls. Only if contention and measurements justify it would I replace the baseline with a Chase–Lev deque whose memory ordering and reclamation are specified.

Common mistakes

• One global queue → every worker contends on one lock → use per-worker deques and let stealing handle imbalance.
• Check non-empty and pop separately → another thief changes the queue between operations → make successful removal the atomic claim.
• Exit when queues look empty during shutdown → a running parent can create children immediately afterward → use the draining state and outstanding invariant.
• Let a task exception escape the worker loop → one bad task reduces parallelism → capture it in a future and continue scheduling.
• Hand-write lock-free code without memory or reclamation rules → duplicate work or use-after-free → validate the locked semantics first and follow a proven algorithm.
• Always steal from one victim → a hot queue stays contended → combine randomized starts, backoff, and bounded batches with metrics.

Follow-up questions and answers

How do you prevent blocking work from stalling every worker?

How do you prove shutdown cannot lose child tasks?

When is batch stealing better than single-task stealing?

Blocking I/O belongs in a separate pool or a counted managed-blocking mechanism; stealing only moves waiting work. The shutdown proof uses the state machine and counter invariant: stop new roots, register children before completing parents, and terminate only in draining with zero outstanding work. Batch stealing helps when task creation is dense and each synchronization is expensive; for tiny queues or tiny tasks, movement and fairness costs can outweigh the savings.