并发算法 #04：无锁队列（Michael-Scott Queue）

Michael-Scott 无锁队列通过 CAS 操作替代互斥锁实现线程安全的 FIFO 队列，被 Java ConcurrentLinkedQueue、Disruptor 等高性能框架广泛采用，在高并发场景下显著降低锁竞争开销。

相关文章：CAS 与 ABA 问题 · Disruptor（无锁环形缓冲） · RCU（Read-Copy-Update）

目录

问题背景

有锁队列的瓶颈

传统 mutex 队列在多线程下存在以下问题：

• 单点竞争：所有 enqueue/dequeue 争抢同一把锁，高并发时 99% 时间消耗在锁等待

• 优先级反转：低优先级线程持锁时，高优先级线程被阻塞

• 死锁风险：锁嵌套、异常路径忘记释放锁

• 内核切换代价：mutex 竞争触发 futex 系统调用，上下文切换耗时 1~10 μs

  futex（Fast Userspace muTEX） 是 Linux 的混合锁机制：无竞争时完全在用户态用 CAS 完成，有竞争时才陷入内核让线程睡眠，把系统调用的代价只摊在真正争抢的少数情况。

  加锁：CAS(futex_word, 0→1) 成功 → 直接返回（0次系统调用）✅
         CAS 失败 → futex(FUTEX_WAIT) 陷入内核，线程睡眠 ← 产生上下文切换
  释放：CAS(futex_word, 1→0)，若有等待者 → futex(FUTEX_WAKE) 唤醒
  

  Java 的 synchronized / ReentrantLock 无竞争时走 CAS 零开销，有竞争时 LockSupport.park() 最终调用 futex，产生 1~10 μs 的上下文切换代价——这正是无锁队列要避免的。

CAS 为何能替代锁

CAS（Compare-And-Swap）是硬件原子指令：CAS(addr, expected, newVal) —— 仅当 *addr == expected 时写入 newVal，返回是否成功。

关键性质：

• 无锁（lock-free）：至少一个线程总能在有限步骤内完成操作
• 硬件支持：x86 CMPXCHG，ARM LDREX/STREX，无系统调用
• 失败时自旋重试，无阻塞，适合低竞争场景

Michael-Scott Queue 的贡献

1996 年 Maged Michael 和 Michael Scott 发表论文，提出：

• dummy head node：head 始终指向哨兵节点（非必要，是简化算法的设计选择，见下文）
• 两步 enqueue：先 CAS tail.next（步骤 7），再推进 tail（步骤 8）；两步之间可被 OS 抢占，步骤 9 让其他线程协助推进，保证系统整体不因单个线程被抢占而阻塞
• tail 滞后容忍：tail 最多落后 1 个节点，不阻止正确性

核心数据结构

Node<T>:
    value:    T                    // 存储的数据（dummy node 的 value 为 null）
    next:     AtomicReference<Node<T>>  // volatile，指向下一个节点，初始为 null

Queue<T>:
    head:     AtomicReference<Node<T>>  // 始终指向 dummy（哨兵）节点
    tail:     AtomicReference<Node<T>>  // 指向最后一个节点，可能滞后 1 步

初始状态：

dummy = new Node(null, null)
head  = AtomicRef → dummy
tail  = AtomicRef → dummy

head ──► [dummy | next=null] ◄── tail

字段语义：

• head.get().next 是队列第一个真实元素（若为 null 则队列为空）
• tail.get() 是最后一个节点，但在并发窗口内可能是倒数第二个

为什么需要哨兵节点（设计选择，而非必须）

哨兵节点不是正确性的必要条件，而是用一个常驻节点换掉对「空队列」的所有特判。

去掉哨兵后的问题：空队列状态变为 head = null, tail = null，此时入队需要同时设置 head 和 tail，但这是两步 CAS，不是原子操作：

T1 入队 A（空队列）：
  CAS(head, null, A)  ← 第一步成功
  // T1 被 OS 抢占，此时 head=A，tail=null → 不一致中间状态
  CAS(tail, null, A)  ← 第二步尚未执行

T2 此时 dequeue：
  head != null → 准备读值
  tail == null → 逻辑混乱

同样，出队最后一个元素时也需同时将 head 和 tail 置 null，同样面临两步 CAS 的原子性问题。

有哨兵后，这两个特殊情况彻底消失：

代价：多占一个节点的内存（前一个出队的节点复用为新哨兵，通过 GC 回收旧哨兵）。

• 所有 next 字段必须是 volatile/原子引用，保证可见性

Enqueue 算法

完整伪代码

ENQUEUE(queue, value):
    node = new Node(value, null)        // 1. 创建新节点，next 初始化为 null

    loop forever:                        // 2. 自旋直到成功
        t    = queue.tail.get()          // 3. 读取当前 tail（快照）
        next = t.next.get()              // 4. 读取 tail 的 next（快照）

        if t == queue.tail.get():        // 5. 【性能优化，非正确性必要】若 tail 已被推进，
                                         //    说明 next 快照已过期，提前重试省掉一次必败的 CAS
            if next == null:             // 6. tail 确实是最后一个节点
                if CAS(t.next, null, node):  // 7. 尝试将 node 接到 tail.next
                    CAS(queue.tail, t, node) // 8. 尝试推进 tail（允许失败！）
                    return               //    返回，enqueue 完成
                // else: 第 7 步 CAS 失败 → 有其他线程抢先，循环重试
            else:                        // 9. tail 滞后了（next != null）
                CAS(queue.tail, t, next) //    帮助推进 tail，然后循环重试

关键要点

Dequeue 算法

完整伪代码

DEQUEUE(queue) → value | EMPTY:
    loop forever:                            // 自旋直到成功或确认为空
        h    = queue.head.get()              // 1. 读取 head（dummy 节点的快照）
        t    = queue.tail.get()              // 2. 读取 tail 快照
        next = h.next.get()                  // 3. 读取 dummy.next（第一个真实节点）

        if h == queue.head.get():            // 4. 【性能优化】head 已变则 next 快照过期，提前重试
            if h == t:                       // 5. head == tail，队列可能为空
                if next == null:             //    6. 确认为空（next 为 null）
                    return EMPTY             //       返回空
                else:                        //    7. tail 滞后了（next != null）
                    CAS(queue.tail, t, next) //       帮助推进 tail
                    // 继续循环，不返回 EMPTY
            else:                            // 8. head != tail，队列非空
                value = next.value           //    9. 读取第一个真实节点的值
                if CAS(queue.head, h, next): //    10. 尝试将 next 设为新的 dummy
                    return value             //        成功！返回 value
                // else: CAS 失败，其他线程抢先出队，循环重试

关键要点

Tail 滞后设计

为什么允许 tail 滞后 1 个节点？

如果要求 tail 始终最新，enqueue 必须原子地完成"接入 + 推进"两步，但两步 CAS 无法原子化。

设计选择：将 enqueue 拆分为两步：

1. CAS(tail.next, null, node) — 决定性步骤，成功即入队
2. CAS(queue.tail, t, node) — 辅助步骤，可失败，由后续线程补推

滞后的最大值：tail 最多落后 1 个节点（因为步骤 1 成功后，tail.next 立即指向 node，任何发现 tail.next != null 的线程都会推进 tail）。

好处：

• 提高并发性：多个线程可以同时尝试步骤 1，只有一个成功，其余循环重试，但无人被阻塞
• 失败成本低：步骤 8 失败不需要回滚，只是让别人来收尾

示意：

正常状态：
  head → [D] → [A] → [B] → [C] ← tail
  
tail 滞后（enqueue C 完成步骤 7 但未完成步骤 8）：
  head → [D] → [A] → [B] ← tail
                       ↓
                      [C]   ← tail.next != null，任何线程会推进 tail

ABA 问题

什么是 ABA？

CAS 只检查值是否等于 expected，无法感知"值变成 B 又变回 A"的中间过程。

MS Queue 中的 ABA 场景

场景（无 GC 的 C/C++ 实现，节点内存可复用）：

初始状态：head → [D] → [A] → [B]
                         ↑
              线程1 读取 h = D, next = A

线程1 暂停...

线程2：dequeue A（CAS head: D→A 成功）
线程2：dequeue B（CAS head: A→B 成功）
线程3：enqueue 新节点，内存分配器复用了 A 的地址，
        新 node 地址 == &A（但内容已不同）
线程2：enqueue 这个"新 A"，CAS head.next = &A

此时：head → [B] → [new_A_at_same_address]

线程1 恢复：CAS(head, D, A) 
            D 的地址已不等于当前 head，但如果线程1 
            持有的是 h.next = A 的地址...（具体取决于实现）

Java 中的解决方案

方案 1：带版本号的 AtomicReference（AtomicStampedReference）

// 每次 CAS 同时更新版本号，ABA 时版本号不同
AtomicStampedReference<Node<T>> head = new AtomicStampedReference<>(dummy, 0);

// dequeue 中：
int[] stampHolder = new int[1];
Node<T> h = head.get(stampHolder);        // 同时读取值和版本号
int stamp = stampHolder[0];
// ...
head.compareAndSet(h, next, stamp, stamp + 1);  // 版本号递增

方案 2：Hazard Pointer（C/C++ 中）

• 每个线程声明当前正在使用的节点指针（hazard pointer）
• 内存回收前检查所有 hazard pointer，被引用的节点不能释放
• 消除内存复用，从根本上避免 ABA

方案 3：Java GC 自动防护

Java 的垃圾回收保证：只要有引用指向对象，对象不会被回收和复用。因此 ConcurrentLinkedQueue 的 Java 实现无需 stamp，GC 天然解决了 ABA。

执行追踪：3 线程并发 Enqueue

初始状态：

head → [D|next=null] ← tail

时间线（T1 enqueue "X"，T2 enqueue "Y"，T3 enqueue "Z"）：

时刻  线程  操作                              队列状态
──────────────────────────────────────────────────────────────
t1    T1   t = tail → D; next = D.next → null     head→[D]←tail
t2    T2   t = tail → D; next = D.next → null     head→[D]←tail
t3    T3   t = tail → D; next = D.next → null     head→[D]←tail
            (三线程同时读到相同的 t 和 next)

t4    T1   CAS(D.next, null, NodeX) → 成功！      [D]→[X]
t5    T2   CAS(D.next, null, NodeY) → 失败！      （D.next 已不是 null）
t6    T3   CAS(D.next, null, NodeZ) → 失败！      （D.next 已不是 null）

t7    T1   CAS(tail, D, NodeX) → 成功！           head→[D]→[X]←tail

t8    T2   重新循环：
           t = tail → X; next = X.next → null
           CAS(X.next, null, NodeY) → 成功！      [D]→[X]→[Y]
t9    T3   重新循环：
           t = tail → X; next = X.next → (Y 刚被接入，但 tail 未更新)
           next = X.next → NodeY（tail 滞后！）
           CAS(tail, X, NodeY) → T3 帮助推进 tail  head→[D]→[X]→[Y]←tail

t10   T2   CAS(tail, X, NodeY) → 失败（T3 已推进）
           步骤7已在 t8 成功，步骤8失败无所谓，T2 执行 return ✅
           T2 的 enqueue 完成，退出

t11   T3   重新循环：
           t = tail → Y（已更新）; next = Y.next → null
           CAS(Y.next, null, NodeZ) → 成功！      [D]→[X]→[Y]→[Z]
t12   T3   CAS(tail, Y, NodeZ) → 成功！           head→[D]→[X]→[Y]→[Z]←tail
──────────────────────────────────────────────────────────────

最终队列：head→[D]→[X]→[Y]→[Z]←tail
出队顺序：X, Y, Z（FIFO 保持）

观察：

• CAS 竞争导致 T2、T3 各自旋重试 1~2 次
• T3 在 t9 帮助推进了 T2 遗留的滞后 tail
• 所有线程最终都完成了自己的 enqueue，没有任何线程被阻塞

正确性：线性化点（Linearization Point）

线性化点是并发理论中用来证明并发数据结构正确性的核心概念：在操作的整个执行区间内，存在一个精确的时刻，在这一刻操作"原子地生效"——之前不可见，之后对所有线程可见。

为什么需要线性化点

并发操作有持续时间，中间可以被其他线程打断：

T1 的 enqueue：  [────────────────────]
T2 的 enqueue：       [────────────────────]
T3 的 dequeue：              [───────────────]

线性化点允许把并发操作"压扁"到时间轴上的某个点，等价为某种合法的顺序执行：

实际执行（有交叠）：
  T1 enqueue X：[─────★─────]
  T2 enqueue Y：     [─────★─────]
  T3 dequeue：              [─────★─────]

等价的顺序执行（按线性化点★排列）：
  T1 enqueue X → T2 enqueue Y → T3 dequeue X

只要每个操作都能找到线性化点，整个结构就满足线性一致性（Linearizability）——证明了并发行为等价于某种合法的顺序执行。

MS 队列各操作的线性化点

线性化点均为单条 CAS 指令或单次内存读，在硬件层面是原子的——这正是无锁算法正确性的根基。

异常与边界场景

场景 1：步骤 7 完成后线程被 OS 抢占（步骤 8 尚未执行）

这是"协助推进"存在的主要原因：步骤 7 和步骤 8 是两条独立的 CAS，两者之间没有原子保证，OS 可以在任意字节码边界抢占线程。

T1 执行完步骤 7 后时间片耗尽，被 OS 调度出去：

  当前状态：head → [D] → [A] ← tail
                           ↓
                          [B]   （B 已接入 A.next，但 tail 未推进）

T2 此时入队 "C"：
  t = tail → A；next = A.next → B（不为 null！走步骤 9）
  CAS(tail, A, B) → 帮助推进 tail
  循环，正常将 C 接入 B.next，推进 tail 到 C

T1 最终被调度回来：
  CAS(tail, A, B) → 失败（tail 已是 C）
  直接 return ✅（B 已在队列中，任务完成）

结论：T1 被抢占期间，T2 无需等待，独立完成推进
      这正是"无锁"的含义：系统整体进展不依赖任何特定线程

场景 2：步骤 7 执行前线程被抢占

T1 创建 NodeB 后、执行步骤 7 前被抢占

队列状态：完全不受影响（NodeB 尚未接入）
T2/T3 正常入队出队，不受影响

T1 被调度回来后继续执行步骤 7，走正常入队流程

场景 3：Dequeue 时 next 为 null（队列为空）

初始：head → [D|next=null] ← tail

DEQUEUE 执行到步骤 5：h == t（都指向 D）
步骤 6：next = h.next → null
返回 EMPTY

边界：如果在步骤 3 读 next 之后，另一个线程 enqueue 了节点，
       next 仍然是旧快照 null，返回 EMPTY（允许，linearization point 在读 next 时）

场景 4：多消费者竞争同一个节点

状态：head → [D] → [A] → [B]
T1, T2 同时 dequeue

T1: h=D, t=B, next=A; value=A.value（准备 CAS）
T2: h=D, t=B, next=A; value=A.value（准备 CAS）

T1: CAS(head, D, A) → 成功！head 现在指向 A
T2: CAS(head, D, A) → 失败！（head 已变为 A，不等于 D）
T2: 循环重试
T2: h=A, t=B, next=B; value=B.value
T2: CAS(head, A, B) → 成功！

结论：T1 取到 A，T2 取到 B，每个元素只被一个线程消费，FIFO 保持

场景 5：tail 读取与 head 读取不一致（h==t 但实际非空）

状态：head → [D] → [A] ← tail

dequeue 执行：
  h = head → D
  t = tail → A（此时 tail 未滞后）
  next = h.next → A（不为 null）
  h != t，进入步骤 8
  value = A.value
  CAS(head, D, A) → 成功

但如果读 h 和 t 的时序不同：
  h = head → D
  （此时 enqueue B，tail 推进到 B）
  t = tail → B
  next = h.next → A

  h != t，进入步骤 8，value = A.value
  CAS(head, D, A) → 成功

两种情况结果相同（稳定性检查只是减少无效 CAS 的优化，去掉后正确性不受影响）

性能对比：CAS 重试 vs Mutex

CAS 的代价：

• 每次 CAS 失败 = 一次白白的内存读写 + 重新循环
• 极高竞争（N >> CPU核数）时，CAS 重试次数 O(N²)，性能反而不如 mutex
• 缓存行竞争（false sharing）：head 和 tail 应在不同缓存行（64 字节对齐）

Java ConcurrentLinkedQueue 的优化：

• head 和 tail 更新懒惰（HOPS 机制）：积累多个操作再更新，减少 CAS 次数
• 利用 sun.misc.Unsafe 直接操作内存，降低间接寻址开销

适用场景：

• 推荐无锁：生产者消费者数量稳定、任务粒度细、延迟敏感
• 推荐有锁：线程数远超核心数、临界区逻辑复杂、需要条件等待（await/notify）

图示

参考资料

1. Michael, M. M., & Scott, M. L. (1996). Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. PODC '96.
2. Java ConcurrentLinkedQueue 源码
3. [The Art of Multiprocessor Programming — Herlihy & Shavit, Chapter 10]
4. [Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects — Michael 2004]
5. 1024cores.net — Lock-Free Algorithms