Hazard Pointer 安全回收

摘链说明“新的访问者不应再从结构入口拿到这个节点”，却不说明“先前的访问者已经不用它”。Hazard槽就是访问者公开的一张暂借单。节点摘链后进入退休区，只有所有暂借单都不再列出它，才可考虑释放。

但暂借单必须在读者确认仍能合法取得节点时已经生效。先拿一个裸指针，过很久再补登记，可能遇到别人早已检查过名单并释放内存的情况。复查源指针把这个竞态变成重试，而不是一次悬空读取。

读到地址后暂停的窗口 ​

初始Head=a，T1的hazard为空。T2用CAS公理库比较并交换Compare-and-swap · CAS原子地比较内存值并在相等时写入新值、同时返回比较结果的读改写原语。摘除旧头，之后再判断何时可以释放。

第4步发布的地址值不会令已释放内存复活。安全来自第5步失败后没有发生解引用。若删掉复查，T1就可能在第6步读取已释放的a。

另一种交错是T1先发布a、再复查成功，随后T2摘除并扫描。只要T1还未完成所有危险使用，它的槽一直保存a，扫描就必须保留a。T1清空槽后，下一次扫描才可能释放。

退休批次必须先于扫描固定 ​

设回收者先读到读者的slot=null；随后读者发布a并复查共享入口仍为a，开始合法使用；另一个线程这时才摘除并退休a。若把这个新退休节点塞进已经开始的候选批次，旧扫描没有a，便可能在读者仍使用时将它释放。正确协议只评估扫描开始前就已退休的候选，新增退休项等下一次扫描。

为什么扫描不必是全体槽的原子快照 ​

关键不变量是：每个将要危险使用节点a的读者，必须从a仍可合法取得的某一时刻起，到最后使用结束，连续保持同一个实际hazard槽指向a。

候选节点在扫描前已经退休，此后新的读者无法重新取得同一个已退休实例。若一个旧读者在扫描结束时仍可能危险使用a，保护它的那个固定实际槽必覆盖整个相关扫描期间，扫描该槽时就应看到a。逐槽读可能来自不同时间，但不能把一个连续存在的保护全都漏掉。这个论证依赖完整的发布、可达性验证和持续保护条件，而不是“最终大概会看见写入”。

“任何时刻总有某个槽保护a”仍然太弱，单遍扫描可能在槽之间追丢一个移动的保护。设初始槽1=a、槽2=null，发生以下交错：

1. 回收者先扫描槽2，读到null
2. 读者把a写入槽2，此刻两个槽都保护a
3. 读者清空槽1，此刻槽2仍保护a
4. 回收者再扫描槽1，读到null，形成的集合却完全没有a

读者始终保留至少一份保护，扫描仍可能释放a。因此本页协议要求整个危险使用期间持续保留同一个实际槽，不能仅靠“先填新槽、再清旧槽”的重叠迁移。交换线程私有的槽角色名称不改变实际槽内容，可以保持这条纪律；真正迁移保护则需要额外验证或扫描协议。

地址复用与逻辑ABA ​

在首次读取到发布复查之间，地址a可能已经释放并重新分配给另一个节点。若复查最终又读到a，本协议尚未读取旧内容，后续保护针对的是当前可达节点；算法必须在验证成功之后才收集依赖该节点的字段。

成功保护期间，受保护节点不能被释放并换成另一实例，从而阻止很多由回收引起的地址ABA。但如果某个结构允许一个仍然存活的同一节点被摘下又插回，或逻辑状态自行回到原值，hazard并不自动证明所有旧快照仍有效。操作自身的线性化公理库线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。和状态不变量仍要另证。

一个保护尝试有常数次原子读写，源指针若持续改变，重试次数可能无界。因此不能把回收扫描可在有限步完成，误写为“每个调用protect的对象操作都是wait-free”。对象进展还依赖其自己的重试、帮助与分配协议。

设退休批次含r个节点。扫描H个槽建立地址哈希集合，再检查r个退休地址，期望时间为 $O(H+r)$；使用排序可给出确定性 $O(H\log (H+1)+r\log (H+1))$ 界。若每个线程在积累至少 $2H+1$ 个退休节点时扫描，则最多H个不同地址被该次hazard集合命中，至少一半批次可回收，扫描成本可期望摊还到每个被处理节点的常数量级。分配器/free的额外代价不包括在内。

暂停线程可以长期保护至多K个地址，但这些地址仍不能释放。各线程私有批次和正在扫描的列表也占空间；在固定线程数、固定阈值和规定扫描策略下才有相应缓存上界，不能把“单线程只有K个槽”直接当成整个程序只多占K个节点。

Michael–Scott队列公理库Michael–Scott 无锁队列Michael–Scott queue · MS queue用哨兵链和可帮助的尾指针修复实现无锁FIFO，并将关键链接、出队与安全回收分别定位。的出队通常需要同时保护旧Head和下一个节点：保护旧哨兵并不自动保护将要读取data的后继。本单元终点给出具体双槽发布/复查轨迹，将结构线性化与安全释放分开审核。