“并发访问还要分开结构更新与生命周期。Harris非阻塞有序链表先在待删节点的next字上标记，再让前驱跨过它，避免与插入竞争时丢掉新节点；Hazard Pointer另行判断哪些已摘除节点仍…”
形式陈述
Harris无锁有序链表用“先逻辑删除、再物理摘链”实现并发有序集合。每个节点保存不可变key，以及可由单字CAS原子比较/更新的 (next,mark)。mark=true表示本节点已逻辑删除，不是后继已删除。
设有不删除的−∞、+∞哨兵head、tail，键带有全序、集合无重复键。本页所有共享访问为SC，标记指针可在一个抽象原子字中表示；基础模型不释放或复用节点。实际指针位编码与回收是额外实现责任。
以下给出逐个帮助摘除标记节点的教学版本。findWindow(k)返回一对在本次搜索期间某时刻满足 pred.key<k≤curr.key、相邻且未标记的节点。
text
findWindow(k):
restart:
pred = head
curr = pointer(pred.next)
repeat:
(succ, marked) = curr.next
if marked:
if not CAS(pred.next, (curr,false), (succ,false)):
goto restart
curr = succ
else:
if curr.key >= k: return (pred,curr)
pred = curr
curr = succtail.key=+∞、tail.next的mark固定false，循环不会越过tail。修改操作为
text
add(k):
repeat:
(pred,curr) = findWindow(k)
if curr.key == k: return false
q = freshNode(key=k, next=(curr,false))
if CAS(pred.next, (curr,false), (q,false)): return true
discard unpublished q
remove(k):
repeat:
(pred,curr) = findWindow(k)
if curr.key != k: return false
(succ,marked) = curr.next
if marked: continue
if CAS(curr.next, (succ,false), (succ,true)):
CAS(pred.next, (curr,false), (succ,false))
return true未发布的q可由创建者安全处理；已发布节点即使标记或摘链也不能直接释放。
直觉
直接从前驱跳过一个节点，可能切断别人刚接到该节点后面的新分支。mark先给该节点的next上一个不可逆的逻辑封条：它已经不在集合中，也不再允许插入者把新节点接在它后面。
物理摘链于是成为清理工作，任何搜索者都可帮助完成。移除者若标记成功后暂停，不会让别的线程永久等它更新前驱。
例子与边界
没有标记时怎样丢掉已成功插入的c
设a.key=1、b.key=3、d.key=7，链为a→b→d。错误删除器先读出b.next=d，打算CAS(a.next,b,d)。与此同时插入器要加入键5的c：
- 删除器保存旧后继d后暂停
- 插入器成功CAS(b.next,d,c)，其中c.next=d，返回成功
- 删除器用旧快照成功CAS(a.next,b,d)，返回成功
现在从a看见d，c和b一起被绕过。集合remove(3)却丢掉已经add(5)成功的元素，无法解释为合法的集合顺序历史。
标记与插入争夺同一next
正确删除器先在b.next上作标记CAS。
- 若插入c先成功，b.next已经变为
(c,false)，删除器原来期望(d,false)的CAS失败。它重读后继c，再把(c,false)改为(c,true)；随后摘b时连接a→c，保留插入结果 - 若删除标记先成功，b.next为
(d,true)，插入器要求(d,false)的CAS失败。重新搜索跳过b，随后可以把c接到a与d之间
mark与pointer必须属于同一次CAS比较。先用普通写单独置mark、同时允许别人按裸pointer CAS插入，并不能建立上述排他次序。
一次帮助搜索
假设b已标记，物理链还是a→b→d。搜索键5时找到pred=a、curr=b，读取b.next=(d,true)。它尝试CAS(a.next,(b,false),(d,false))；成功后从d继续，得到窗口(a,d)，随后add(5)可把c接进去。
若a自身已经被别人逻辑删除，则a.next的mark为true，期待 (b,false) 的清理CAS会失败，搜索从head重来。因此不能在一个已删除前驱上“清理成功”后继续把新元素挂到失去共享可达性的链段。
线性化点分为更新与搜索见证
成功add在线接q的CAS处生效，成功remove在curr.next的mark由false变true处生效。物理摘链不会再删除一次同一个集合元素。
contains(k)可调用findWindow后检查curr.key是否为k。contains结果以及add的重复键失败、remove的缺失键失败，均可在线性化于搜索期间满足窗口条件的某个时刻；不必硬指定最后一次key比较为那个时刻，因为窗口返回后仍可被别人修改。
例如搜索曾观察到未标记的键3，随后它被删除，但contains在返回前仍回答true。只要该节点确实在调用区间内某刻属于集合，就符合线性化。成功更新则靠CAS重新验证实际边或标记状态，不能仅依赖此前找到过一个窗口。
推论与应用
正确性使用三个关键不变量：可达未标记键严格有序；mark只从false变true，从不撤销；插入或清理CAS必须比较前驱next的未标记状态。标记以后，节点在抽象集合中消失；物理链可能暂时保留它，但搜索会跳过并尝试清理。
搜索沿键递增推进；若因CAS失败重新开始，相关链边已被其他线程改变。暂停线程不独占清理责任，其他搜索可继续移除标记节点。在无地址复用等基础假设下，这支持无锁进展，但并不保证指定请求在固定步数内完成。
若搜索路径含n个物理节点且无竞争，一次查找/更新为
加入Hazard Pointer时，前驱、当前节点及后继的保护和验证必须与具体搜索版本匹配；只给原论文每个裸指针读取前随手插一条hazard写，不能自动证明安全。尤其从一个已摘除但仍受保护的节点沿旧next前进，未必能直接证明后继仍可保护。本页基础伪代码将回收分离，应用时应采用已经证明的兼容遍历协议。
参考资料
- Timothy L. Harris, “A Pragmatic Implementation of Non-Blocking Linked-Lists”, DISC, 2001, 300–314，§§4–5：标记、search窗口、线性化与进展
- Maged M. Michael, “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”, 2004，§4.3：与回收兼容的逐节点清理遍历；不是对任意Harris遍历机械加hazard