并发算法中的帮助机制

帮助把操作从“这个线程正在做的私有过程”变成“任何参与者都能辨认和推进的公开任务”。描述符像附有编号的工单：原处理人可以离开，接手者必须知道工单是哪一件、做到哪一步、是否已经完成，以及该回报哪个结果。

与锁不同，helper 不等待原持有者恢复。与盲目重试也不同，helper 不重新制造一份外部效果。安全帮助的关键是把可重复的准备工作与不可重复的抽象提交分开，并让所有人认可同一个提交证据。

用顺序日志帮助一次递增 ​

考虑初值为 $0$ 的 fetch_increment()：一次调用把计数器加一，返回递增前的值。三个进程 $p_0,p_1,p_2$ 各公布唯一请求 $a,b,c$；$p_0$ 公布 $a$ 后暂停。为解释机制，假设有一条已决定前缀唯一的日志，提交协议保证每个请求身份至多入日志一次，每个位置使用一个共识公理库分布式共识Distributed consensus · Consensus problem多个进程在可能故障和通信延迟下对一个值达成一致的任务。实例决定下一请求；这里使用的是共享内存、固定参与者的 wait-free 共识对象，不是直接调用消息传递协议。

若日志的前三个位置决定为 $b,c,a$，则可以逐项执行如下纯状态转移：

$p_1,p_2$ 分别获得结果 $0,1$；某个继续运行的进程把 $a$ 接入日志并确定结果 $2$。$p_0$ 恢复后查到自己的请求已提交，返回 $2$。它虽最早发起，却与其他调用重叠，因此无需排在第一位；第三项的提交仍在它的调用区间内。

共识的作用是让同一位置只有一个后继，描述符状态及日志不变式的作用是让同一请求只出现一次。拥有者和 helper 可分别计算“状态 $2$ 加一得到 $3$”，计算两遍并无害；只有被决定的日志项改变抽象历史，不能让每个计算者都再执行一次底层 fetch_increment()。

为什么先做副作用、再标记完成不安全 ​

一种看似简单的实现是：helper 读到 d.done == false，先递增共享计数器，再执行 CAS(d.done, false, true)。让两个 helper 都读到 false，随后分别递增，最后只有一个 CAS 成功。一次请求已产生两次递增；失败的 CAS 无法撤销先前效果。若赢家在递增后、写入结果前停住，其他人还可能不知道该返回哪个旧值。

修复不能只加一个完成标志。提交协议必须使“哪次状态转移归属哪个请求”可被唯一识别：例如通过共识决定日志后继，或在适当原语和状态表示下原子地安装包含请求身份与结果的状态。内存回收还必须保证旧 helper 不会持有已重用的描述符地址；本页例子假设描述符和日志项在仍可能被访问时不回收。

有帮助仍可能饥饿 ​

若每次日志竞争总优先挑最快进程的新请求，慢请求 $a$ 可以一直公开而从未入选；不断完成的只是 $b_1,b_2,\dots$。这可能提供系统级进展，却没有给 $a$ wait-free 保证。

Herlihy 的通用构造按日志序号轮转优先考察一个进程的公告；该进程有未提交请求时优先帮助它，否则才推进自己的候选。优先规则、公告与已接入链的状态不变式共同给出有限轮次界，不是“偶尔帮别人一次”就足够。原文 §4.1 Theorem 14 给出至多 $n+1$ 次主循环的界；这不等于 $n+1$ 条机器指令，因为一次循环还包含读共享数组、共识和状态处理。对象顺序操作本身也须可在有限步骤内计算。

共识数与 wait-free 层级公理库共识数与 Wait-free 层级Consensus number · Consensus hierarchy · Wait-free hierarchy以对象类型可为多少参与者 Wait-free 地解决共识来分类同步原语的表达能力。中的通用构造用唯一排序解决安全性，用轮转帮助解决请求不会永久落后的进展问题。具备足够强的原语只说明这种构造存在，不能替代具体实现的提交与步骤界证明。

原子快照公理库原子快照Atomic snapshot · Wait-free snapshot · 原子共享内存快照利用带序号的原子寄存器、重复收集与已发布视图，在有限自身步骤内读取共享数组的线性一致快照。提供另一种帮助：更新者把自己已取得的完整视图与新值一起发布，扫描者在合适的版本证据下复用视图。这里没有替别人插入操作日志，仍需证明被复用结果在接收者的调用区间内有效。两类帮助共享的原则是公开足够证据，让一个调用的完成不依赖某个特定进程继续运行。

自测：在递增例子的第三项已经决定后，两个 helper 同时准备把结果 $2$ 写入 $a$ 的结果字段。什么条件下重复发布无害？检查标准：两者依据同一已提交前缀、发布相同结果，结果字段不能再改变抽象计数器，且 $a$ 的身份未被复用。如果其中任何一人又执行实际递增，就已经违反“一次请求一次效果”。