工作窃取调度

本地执行与窃取协议 ​

系统有 $P$ 个 workers，每个维护一个双端队列公理库双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。。Worker 产生新可执行子任务时压入本地 bottom；有本地工作时从 bottom 弹出，形成深度优先、缓存友好的 LIFO 执行。队列空时，它均匀随机选择另一个 worker，从受害者 top 窃取最老任务。

Owner 与 thieves 操作不同端，降低常见竞争；较老任务通常位于递归树较高处，窃取它往往带走一棵较大的子计算，从而产生粗粒度并行。这个直觉不替代并发 deque 的线性化证明。

Fork–join 状态轨迹 ​

Worker 0 执行分治任务 solve(A)，产生左右两个子任务。它把右任务压到 bottom，继续执行左任务；Worker 1 空闲，随机选中 Worker 0，从 top 取走较老的右任务。两者随后在各自子树重复分裂。

若 Worker 0 很快完成左子树，它从 bottom 继续拿自己最近产生的 continuation；Worker 1 完成右子树后，父任务的 join 只有在两侧结果都到达时才 ready。偷走任务改变的是处理器归属，不改变 computation DAG 的依赖边。

当只有根到某个叶的一条链 ready 时，其他 worker 可能连续失败窃取；这段不可并行时间正由 span 支付，而不是假设所有处理器始终忙碌。

Fully strict computation ​

经典分析针对 fully strict fork–join computation：每个 spawned task 的结果只在其直接父任务中同步，依赖关系正确嵌套；任务完成后回到其祖先 continuation。固定一次展开后得到 work $T_1$、span $T_{\mathrm{\infty }}$ 的 DAG。

任意跨任务 future、非嵌套同步或长期共享阻塞会形成非严格 DAG，经典势函数与空间界不自动适用。可以有扩展调度器处理这些依赖，但必须引用对应定理。

期望时间保证 ​

在单位成本任务、理想共享内存、随机受害者独立均匀选择和 fully strict 等条件下，经典 randomized work stealing 满足

$$\mathbb{E}[T_P]le\frac{T_1}{P}+O(T_{\mathrm{\infty }}).$$

期望主要对调度器的随机受害者选择取；若应用算法也随机，应先固定其生成的 DAG 应用条件界，再用全期望合并。

分析还给出成功与失败 steal 尝试总量的期望 $O(P{T}_{\mathrm{\infty }})$ 量级。除以 $P$ 后，调度开销贡献 $O(T_{\mathrm{\infty }})$；总工作项由所有 worker 分摊为 $T_1/P$。这与集中式贪心调度公理库Brent 调度定理Brent scheduling theorem · Brent's theorem · work-depth scheduling principle把 work 为 W、depth 为 D 的单位任务 DAG 贪心映射到 P 个处理器，得到 W/P+D 级时间上界。的确定上界形状相似，保证类型却是随机、去中心化的期望界。

随机量词与对手 ​

受害者选择必须在适用集合上近似均匀且不被一个能预知随机位的调度对手操纵。若每个空闲 worker 总偏向同一热点 victim，冲突会增加且其他队列可能长期无人访问。

期望界不表示每次运行都接近均值。需要尾界时要陈述失败概率、任务 DAG 条件和随机独立性；把 benchmark 的平均运行时间称作理论高概率界是不成立的。

Deque 并发状态 ​

Owner pushBottom/popBottom 多为单线程快速路径，thief stealTop 需要原子竞争 top 索引。只剩一个任务时，owner 与 thief 可能同时尝试取走，必须由 compare-and-swap 让恰一方成功；否则会重复执行或丢任务。

环形数组扩容时，旧缓冲不能在仍有 thief 读取时立即释放；需要垃圾回收、epoch 或保留策略。ABA、内存序和 false sharing 属于实现正确性与性能边界，不包含在抽象 $T_1,T_{\mathrm{\infty }}$ 定理里。

空间与局部性 ​

深度优先的 owner 路径让未执行 siblings 留在 deque，常保持良好栈空间与缓存局部性。Fully strict 计算可证明总空间受 $P$ 倍串行空间一类界控制；具体常数依栈帧与 deque 表示，不能只从时间式推得。

Work-first 原则把大部分调度开销放到 steal 慢路径，使无窃取执行接近串行程序。任务过细时，即使渐近 work/span 好，spawn 与原子操作仍可能吞掉收益，需要 cutoff 合并小任务。

系统边界 ​

阻塞 I/O 会让持有关键 continuation 的 worker 睡眠；NUMA 上跨节点偷取带来数据迁移；任务有亲和性或不可迁移状态时，随机 victim 假设也不合适。实践可采用层级窃取、亲和提示或资源感知策略，但需重新评估保证。

工作窃取平衡 ready tasks，不解决算法本身 work 过大、span 过长或内存带宽饱和。只有把调度器界与Work–Depth 分析公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。、任务粒度和硬件成本一起报告，才形成完整性能结论。

参考资料

• Robert Blumofe, Charles Leiserson, Scheduling Multithreaded Computations by Work Stealing, Journal of the ACM, 1999.
• David Chase, Yossi Lev, Dynamic Circular Work-Stealing Deque, SPAA, 2005.
• Matteo Frigo, Charles Leiserson, Keith Randall, The Implementation of the Cilk-5 Multithreaded Language, PLDI, 1998.