Obstruction-free 进展

形式陈述 ​

一个并发对象公理库并发对象Concurrent object可被多个线程并发调用并以顺序规格解释操作效果的共享对象。实现称为 obstruction-free，若任意参与者 $p$ 的 pending 操作从任意可达状态开始，只要 $p$ 此后获得足够长、没有其他参与者执行该对象步骤的连续区间，该操作就在有限个自身步骤内完成。这项性质也称 solo-termination：竞争一旦最终消失，独自运行的调用不会被协议内部永久卡住。

“足够长的独占区间”是执行条件，不是算法保证会发生的事实。标准异步可容许执行公理库可容许执行Admissible execution满足给定调度、公平性和故障模型约束的执行。可以让多个线程永远交错，因此 obstruction-free 对持续竞争的历史不承诺任何全局完成；所有操作可能反复撤销对方工作，形成活锁公理库活锁Livelock · 活跃锁参与者持续响应并改变状态，却在无限执行中不再产生规格所要求完成事件的进展失败。。短暂几步无竞争也未必足够，定义要求区间长到覆盖该实现从当前状态完成所需的有限路径。

在标准确定性共享内存模型下，进展层级为

$$\text{wait-free}\Rightarrow \text{lock-free}\Rightarrow \text{obstruction-free}.$$

第一项要求每个正确调用不受他人速度影响地完成；第二项要求持续有系统步骤时总有调用完成；第三项只要求最终独占者完成。若算法 lock-free，而某线程从某时刻起独占执行，系统级“总有调用完成”只能由它的 pending 调用实现，所以得到后一个蕴含。反向均不成立。

obstruction-free 与“代码里没有锁”也不是同义词。定义关心操作在独占区间内是否终止；实现是否使用某种内部标志、版本或事务描述并不直接决定性质。安全性同样正交：一个总能独自返回错误结果的算法可以 obstruction-free，却不满足对象的顺序规格。

直觉 ​

这项保证像一条单车道施工规则：只要其他车辆最终让出道路足够久，你一定能开过；规则并不保证交通管理员会真的给你清场。它排除了“没有竞争仍因等待别人而卡住”的实现，却允许竞争者彼此持续干扰。

obstruction-free 因而适合乐观算法的自然底线。算法先假定冲突短暂，用版本检查发现干扰就回滚；稀疏竞争时路径短而简单，激烈竞争时则需要额外的退避或仲裁策略提供更强的系统进展。

例子与边界 ​

乐观事务读取一组版本，在私有缓冲区计算更新，提交时验证读集未被修改并原子发布；验证失败便回滚重试。若事务最终独占对象步骤，某次验证会稳定通过并提交，所以核心算法可 obstruction-free。若两个事务持续同时验证、互相使版本失效并回滚，执行仍满足基本算法规则，却可能永远无人提交；obstruction-free 本身不排除这条历史。

竞争管理器可以在冲突时选择一个事务继续、让其他事务指数退避，或按时间戳保留优先者。若管理器保证持续竞争中仍不断有事务完成，组合系统可能达到lock-free公理库无锁进展Lock-free progress · Lock-freedom系统整体保证在有限步内有某个操作完成，而不保证指定线程。；若进一步保证每个正确事务都有限完成，才可能达到wait-free公理库Wait-free 进展Wait-free progress · Wait-freedom · 无等待进展每个正确参与者的每次操作都在有限个自身步骤内完成的个体级非阻塞保证。。提升来自完整组合的仲裁性质，不能倒过来写成原事务对象天然拥有更强保证。

一个线程只获得短促、反复被打断的无竞争片段，不能据此要求完成；定义中的独占后缀必须足够长。反过来，mutex 保护的操作即使当前没有竞争，也可能因先前持锁线程已经暂停而无法独自完成，所以普通阻塞锁不因“此刻只有一个线程在跑”就成为 obstruction-free。

推论与应用 ​

验证 obstruction-free 时，可以固定其他参与者状态，从任意可达配置出发，只运行目标线程，并证明有限步后返回。这个证明比全调度下的 lock-free 论证局部，却仍必须覆盖回滚元数据、版本清理与内存回收；若 solo 路径等待另一个线程发布记录，性质就在该组件边界上失效。

工程上应把基础对象保证与竞争管理策略分别标注。退避能降低同相重试概率，却不必然给出确定性进展；公平仲裁能改善个体结果，却可能增加元数据与协调成本。选择 obstruction-free 作为合同，意味着调用方接受持续竞争时需要外部机制，而不是把“通常会成功”包装成更强承诺。

参考资料

• Maurice Herlihy, Victor Luchangco, and Mark Moir, “Obstruction-Free Synchronization: Double-Ended Queues as an Example,” ICDCS 2003, pp. 522–529。
• Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, rev. 1st ed., Morgan Kaufmann, 2012，Ch. 3。
• Rachid Guerraoui and Michał Kapałka, Principles of Transactional Memory, Morgan & Claypool, 2010。