Wait-free 进展

形式陈述 ​

一个并发对象公理库并发对象Concurrent object可被多个线程并发调用并以顺序规格解释操作效果的共享对象。实现称为 wait-free，若对任意可容许执行、任意正确参与者 $p$ 及其调用 $op$，只要 $p$ 在调用后持续取得自身对象步骤，$op$ 就在有限个 $p$ 的步骤内返回。完成所需步骤数不能依赖其他参与者继续运行、释放资源或以某种速度配合；其他线程可以暂停、崩溃或任意快地干扰，$p$ 仍须完成。

量词中的“自身步骤”把进展与现实时间分开。操作系统可以暂停 $p$ 一小时，这不反驳 wait-free，因为暂停期间它没有取得步骤；一旦持续执行，算法不能让它无限重试。参与者数量、可用原子原语、内存容量和故障类型都是模型参数，改变它们可能改变实现是否满足定义。

文献中“有界 wait-free”常强调存在统一函数 $B(n,op)$，使每个操作在至多 $B$ 个自身步骤内完成；较弱的口头表述只要求每个具体调用有限完成。有限状态、固定参与者的标准算法通常给出显式上界。无论采用哪种约定，都应说明界依赖线程数、对象大小还是输入规模，不能把一次测得的平均延迟当成步复杂度证明。

wait-free 蕴含lock-free公理库无锁进展Lock-free progress · Lock-freedom系统整体保证在有限步内有某个操作完成，而不保证指定线程。：若每个持续取步骤的 pending 调用都能有限完成，那么系统持续执行对象步骤时必然不断有操作完成。逆命题不成立，因为系统级完成可以永远由其他线程贡献。两种进展条件都只讨论终止；对象返回值是否满足线性一致性公理库线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。或其他安全规格仍需独立证明。

帮助机制与 wait-free 并不矛盾。线程可以公开自己的操作描述，其他线程在更新共享状态时顺手替它完成；只要每个调用无论竞争怎样都在有限自身步骤内确认完成，这种协作反而是许多 wait-free 构造突破无限重试的关键。

直觉 ​

lock-free 像承诺“队伍一直有人办完业务”，wait-free 则给每位持续走到窗口前的顾客一张有限流程单：无论旁边的人多快、是否离场，这位顾客执行完有限步骤就会结束。它不承诺现实秒数，却不允许同一个人永远被抢先。

这种保证昂贵之处在于算法不能把完成希望寄托在某个特定同伴上。等待锁持有者、等待全体线程响应或使用可能无限失败的 CAS 循环，都需要额外结构才能提升为 wait-free；常见代价是复制操作描述、帮助其他请求或维护更多版本。

例子与边界 ​

在固定 $n$ 个线程的单写寄存器数组中，每个线程只写自己的槽位，一次写可在常数步内完成，不受其他线程停顿影响，是最小的 wait-free 操作。要得到原子的 snapshot，单次逐槽扫描并不充分，因为更新可穿插在扫描中形成从未同时存在的组合；经典 wait-free snapshot 算法使用带序号的重复 collect 与帮助信息，在检测到持续更新时采用更新者已经发布的完整视图，从而同时给出一致快照和有限步骤界。

CAS 计数器采用 read; CAS(old, old+1); retry。每次 CAS 失败都说明某个竞争者修改了值，所以系统可能一直完成递增，满足 lock-free；恶意调度却可让线程 $p$ 每次将要 CAS 时都被别人抢先，$p$ 的调用无限重试，因而不 wait-free。给重试次数设任意经验阈值后返回失败，只在接口允许失败结果时才算操作完成，不能悄悄改变原规格来声称 wait-free。

等待一把 mutex 的操作也不是 wait-free。持锁线程暂停后，等待者执行再多自身检查都无法完成。robust lock 能处理某些持有者故障，公平锁能排除某些插队，它们仍以其他线程释放或恢复为前提，与“独立于他人速度”的量词不同。

推论与应用 ​

wait-free 是非阻塞进展层级中强而清晰的个体保证，适合实时控制路径、故障隔离和共享内存可计算性研究。Herlihy 的共识层级用“对象类型能为多少进程 wait-free 地解决共识”衡量同步能力；这里比较的是可实现性，不是硬件指令吞吐排名。

完整系统的端到端性质取决于所有组成部分。核心数据结构即使 wait-free，动态内存分配、内存回收或回调若会阻塞，公开操作就未必 wait-free。证明必须覆盖调用路径实际依赖的组件，并明确调度公平公理库饥饿与公平性Starvation and fairness · 调度公平性 · 无饥饿用调度与服务选择的公平假设刻画持续请求者是否可能永久得不到完成机会。只要求调用线程自身持续取步骤，而非让算法借公平性掩盖无限内部重试。

参考资料

• Maurice Herlihy, “Wait-Free Synchronization,” ACM Transactions on Programming Languages and Systems 13(1), 1991, pp. 124–149。
• Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, rev. 1st ed., Morgan Kaufmann, 2012，Chs. 3, 4, 5。
• Afek et al., “Atomic Snapshots of Shared Memory,” Journal of the ACM 40(4), 1993, pp. 873–890。