Michael–Scott 无锁队列

形式陈述

Michael–Scott队列用单链节点、一个哨兵头和CAS实现并发FIFO 队列。Head指向不再属于抽象队列的哨兵；Head.next起的值依次构成队列。Tail用于定位链尾，允许短暂落后，但不能随意倒退。

本页采用SC原子读写/CAS。节点value在发布后不变，next为原子指针；基础伪代码假设节点存储不释放、地址不复用。稍后再加入安全回收，不能把下列裸指针读直接与立即free拼接。

初始化一个节点d，d.next=null，Head=Tail=d。

text

enqueue(v):
  q = freshNode(value=v, next=null)
  repeat:
    t = Tail
    n = t.next
    if Tail != t: continue
    if n != null:
      CAS(Tail, t, n)                 // 帮忙修复尾指针
    else if CAS(t.next, null, q):
      CAS(Tail, t, q)                 // 尽力推进，失败也不撤销入队
      return

dequeue():
  repeat:
    h = Head
    t = Tail
    n = h.next
    if Head != h: continue
    if n == null: return EMPTY
    if h == t:
      CAS(Tail, t, n)
      continue
    v = n.value
    if CAS(Head, h, n):
      retire(h)                      // 基础模型只记退休，不立即释放
      return v

CAS返回成功/失败。一个节点最多链接一次；next从null变成后继后不再改写。出队移动Head，后继节点成为新哨兵，其旧value留在存储中但不再属于队列内容。

直觉

入队最关键的一步是把新节点接到链上。Tail只是帮助后续请求找到末端的路标；路标可以晚一点更新，因为其他线程看见它落后时能代劳。

这种帮助机制让一个已经完成关键链接、随后暂停的线程不垄断后续操作。别人不必等待它回来声明成功，就能继续入队或出队。

新节点已经接入链而Tail仍指旧节点；后来的线程推进Tail，出队则把Head移到新哨兵

例子与边界

入队者暂停在尾指针更新之前

初始只有哨兵d，队列为空。A入队α，B入队β，C出队。

步骤	事件	Head	Tail	从Head起的物理链
1	A成功CAS(d.next,null,u)，u.value=α，随后暂停	d	d	d→u
2	B读Tail=d及d.next=u，帮助CAS(Tail,d,u)	d	u	d→u
3	B成功把v链接到u.next，v.value=β	d	u	d→u→v
4	B把Tail推进到v并返回	d	v	d→u→v
5	C读取u.value=α，成功CAS(Head,d,u)	u	v	u→v
6	A恢复，尝试CAS(Tail,d,u)失败，但正常返回	u	v	u→v

抽象队列在第1步已经含α，第3步变成[α,β]，第5步出队α后剩[β]。第6步不能把Tail硬写回u；CAS失败正避免覆盖别人更晚的进展。

A尚未返回不妨碍它的入队已经对C可见，这完全符合线性化：操作只需在调用与返回之间某一点生效，甚至可以由别人的执行完成后续整理。

线性化点与空判断

成功enqueue在把q从null接入前驱next的CAS处生效
成功dequeue在Head从旧哨兵h改成n的CAS处生效
返回EMPTY可放在读到h.next=null的那次观察处，前提是后续Head==h验证成功

空判断的验证不能省略。一个过时Head快照的next与当前队列状态未必属于同一观察。基础模型中Head不会回到已离开的旧节点，所以验证成功保证两次Head读取之间它未换过；若入队恰在读null之后发生，空出队仍可排在那次入队之前。

h==t本身不表示空。第1步之后Head=Tail=d，但d.next=u，队列已经有α。出队者必须看到next非空、先帮助Tail，再尝试移动Head，避免把Tail留到Head之后。

哪些结构事实不会变

链从Head起保持单向无环顺序；已发布节点的value不变；next一旦非空就固定。Tail的成功更新只向后继前进。正常可达状态下Tail在Head所在链上，位于真正链尾或落后一个节点：再一次末尾链接前，操作先把Tail追到当前尾部。

这些事实解释了失败CAS的意义。链接失败表示已有线程把该null改成后继；移动Head失败表示已有出队者先推进；修Tail失败表示路标已被别人推进。重新读取即可，不必撤销已经完成的链接。

两个hazard槽各自保护什么

若允许释放旧哨兵，必须使用安全回收协议。出队至少要覆盖h的字段访问与Head比较，以及n.value的读取。只保护h不够：别的线程可以先把h摘为旧哨兵，再把n摘为下一轮旧哨兵并释放n，虽然h因保护仍未释放。

入队也有同样的生命周期责任：读取t.next之前先发布对t的保护，并复查Tail仍为t；保护持续覆盖后续使用t的CAS，不能在开启回收后保留裸t读取。

一种双槽检查次序是：读h、发布slotH=h、复查Head；成功后读n=h.next，发布slotN=n，再复查Head==h；只有第二次复查成功后才读n.value。整个对应危险使用期间，h和n分别持续留在同一个实际槽中；不能仅以重叠写入把保护迁移到另一个槽。失败则不解引用尚未验证的n，结束本次尝试再重新取快照。

h已被持续保护且不重新插入，因而Head验证不能被h的地址释放复用欺骗。第二次验证成功时，n仍是当前Head的后继，它的保护已经发布；之后即使别的线程出队，也只能退休而不能释放它。终点任务给出完整双槽账本及相反交错。

推论与应用

在基础内存假设下，算法具有lock-free进展：一个线程若反复因快照变化或CAS失败重试，就有其他线程推进了Head、Tail或链尾；Tail帮助不会无限孤立地发生，因为每次前进都由实际链接支持。若竞争停止，一个持续执行的请求在有限步内完成。

这不保证某个指定线程不饿死，也不给固定重试上限。无竞争的一次入队/出队做 $O(1)$ 次原子操作；竞争时单次调用工作可无界。队列内容占线性节点空间，另加一个当前哨兵；退休缓存、hazard扫描和分配器成本必须单独计入。

对实际实现，还需验证弱内存发布、value读取、节点生存期、元素复制/移动与异常规则。把所有共享字段口头称为“原子”，却不提供正确的内存顺序，不能由本页SC证明直接得到正确C++程序。

参考资料

Maged M. Michael and Michael L. Scott, “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” PODC, 1996；作者维护的更正版伪代码
Maged M. Michael, “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”, 2004，§4.1、Figures5–7：不含回收的队列与hazard双槽扩展

形式陈述 ​

入队者暂停在尾指针更新之前 ​

线性化点与空判断 ​

哪些结构事实不会变 ​

两个hazard槽各自保护什么 ​

反向链接

形式陈述

入队者暂停在尾指针更新之前

线性化点与空判断

哪些结构事实不会变

两个hazard槽各自保护什么