题干与适用场景
请实现一个固定 N 个 worker 的调度器。公开 API 为 submit(task)、shutdown() 和 awaitTermination()。每个 worker 有自己的 deque：所有者从本端 LIFO 取任务；空闲 worker 从其他 worker 的另一端 FIFO 窃取。任务可以产生新任务，但关闭后不得接收新任务。
本题允许先用互斥锁实现正确基线，再说明如何替换为 Chase–Lev 一类无锁 deque。要求不得丢任务、不得执行两次、任务异常不能杀死整个调度器，并要处理队列为空、没有可偷目标、关闭竞态和 worker 阻塞。
面试官考察点
强回答会明确“所有权端”和“窃取端”的并发边界，而不是只说“用线程池”。本地 LIFO 保留缓存局部性和深度优先行为，远端 FIFO 让窃取者拿到较老、通常更大的工作块。面试官还会检查你是否把任务提交、停止接收、排空队列和 worker 退出拆成状态机，以及是否能证明每个任务只被认领一次。
回答前需要澄清的问题
- 任务是否允许阻塞 I/O？若允许，需要独立 I/O 池或可计数的阻塞补偿；仅增加窃取次数不能解决线程被占满。
submit是否返回 future？若返回，需要传播任务异常和取消语义；本题先返回 future，但取消只保证尚未开始的任务不会执行。- 是否要求无锁和无界队列？没有的话先做加锁 deque；只有在竞争成为瓶颈且内存回收模型明确时才升级。
- shutdown 是立即停止还是优雅排空？本文采用优雅排空：停止接收新任务，已提交任务完成后退出。
30 秒回答框架
我为每个 worker 分配一个 deque，并规定所有者在一端 LIFO 操作，窃取者在另一端 FIFO 操作。先用每个 deque 的锁建立正确基线：submit 选择队列并唤醒 worker，worker 先取本地任务，空了再随机或轮询目标窃取。任务被成功移出队列后才执行，因此不会重复认领。shutdown 进入停止接收状态，计数归零且所有队列为空后退出。测试覆盖并发 submit、窃取竞态、任务生成任务、异常、关闭和无任务空转。
分步骤深入解答
先定义状态：accepting、draining、terminated。提交在 accepting 时把任务放入负载较低的 deque，原子增加 outstanding 计数并唤醒一个 worker；draining 只允许已有任务继续产生子任务，是否允许子任务取决于题目契约，本文允许由已运行任务产生，但在计数归零前保持 draining。
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; }
}
}
}示例代码把计数和 deque 操作写成单线程伪代码；真正实现必须让 submit、outstanding、关闭条件和唤醒机制使用同一套同步协议。为了避免“检查为空后马上有任务”的丢唤醒，通常用条件变量、信号量或事件计数，而不是裸 sleep。
加锁基线的正确性不变量是：任务只在从某个 deque 成功移除后才执行；同一时刻只有一个操作能移除该任务；outstanding 等于已入队但尚未完成的任务数。若任务在执行中产生子任务，应先登记子任务再减少父任务计数，避免计数短暂归零触发错误退出。
调度公平性来自目标选择和批量窃取策略。完全随机可能长期偏斜，固定轮询又可能在热点队列上产生同步；可以记录连续失败次数、随机起点和窃取批量。轻量、均匀任务适合窃取单个或小批量；递归产生的大任务更适合从远端拿较大的旧任务。
无锁升级不是默认答案。Oracle 的 ForkJoinPool 采用 work-stealing，并提供 steal count 等观测；Chase–Lev 类 deque 需要原子索引、内存序和安全回收。若没有明确的单 owner/多 thief 假设、扩容和回收方案，手写“无锁”比加锁基线更容易产生重复执行或 use-after-free。
复杂度：本地 push/pop 期望 O(1)，一次窃取为 O(1) 或 O(batch)，选择 V 个目标的朴素扫描为 O(V)。空间为 O(T + N)，T 是未完成任务数，N 是 worker 数。阻塞 I/O 会破坏“worker 空闲即可窃取”的假设，应隔离阻塞任务或限制其并发。
高质量示范回答
我会先交付加锁正确版本，再讨论无锁优化。每个 worker 有独立 deque，所有者从 bottom 做 LIFO，窃取者从 top 做 FIFO；两个方向分别由 owner lock 和 steal lock 保护。任务只有在成功 pop/steal 后才进入执行阶段，所以认领是唯一线性化点。
提交状态和关闭状态分开处理。shutdown 先禁止新提交，再等待 outstanding 归零；运行中的任务产生子任务时，要么在 draining 期间明确允许并计数，要么直接拒绝并让任务处理错误。worker 取不到任务时使用条件变量或信号量等待，避免忙等和丢唤醒。任务异常记录到 future/监控，不传播到 worker 主循环。
最后我会用并发屏障同时提交大量短任务和少量长任务，验证每个任务恰好执行一次、窃取确实发生、队列最终归零。再注入任务生成子任务、worker 在 steal 时关闭、阻塞任务、异常任务和重复 shutdown。只有在锁竞争和指标证明必要时，才替换为带明确内存序与回收方案的 Chase–Lev deque。
常见错误
- 只用一个全局队列 → 所有 worker 在同一把锁上排队 → 先实现 per-worker deque，再让窃取承担不均衡。
- 先查看队列非空再单独 pop → 检查与移除之间会被其他 thief 插入竞态 → 把成功移除作为一个原子操作。
shutdown看到队列暂时为空就退出 → 运行中的父任务可能马上生成子任务 → 用 outstanding 和明确 draining 状态判断。- 任务异常直接逃出 worker 主循环 → 一个坏任务减少有效并行度 → 把异常封装到 future 并继续调度。
- 盲目手写无锁 deque → 忽略内存序、扩容和回收 → 先用锁验证语义，再按成熟算法和测量升级。
- 用固定单一 victim → 热点队列持续被争抢 → 随机起点、失败退避和批量窃取结合监控调整。
追问及应对
如何避免阻塞任务拖死所有 worker？
如何证明关闭不会丢掉子任务？
什么时候批量窃取优于单任务窃取？
阻塞 I/O 应进入独立池，或用可计数的 managed blocking 机制补充 worker；否则窃取只能搬运等待中的任务。关闭证明依赖状态机和计数不变量：停止新根任务、子任务登记先于父任务完成、只有 draining 且 outstanding 为零才终止。批量窃取适合任务生成密集且单任务成本较高的场景，可摊薄同步成本；任务很小或队列短时，批量搬运会增加缓存和公平性代价。