算法与数据结构 / 并发数据结构 · 从 CAS 到无锁队列与内存回收 / Michael-Scott 队列 待审核 3 / 6
MPMC 无锁队列 · 帮助机制

Michael-Scott 队列

高频交易里的无锁环形队列 讲的是单生产者单消费者：容量固定，两个 counter 各归一方独占，没有任何一次 CAS。生产者与消费者都可以有多个时，counter 不再有唯一的主人，队列也就必须换一个形状。Michael-Scott 队列是这个形状的标准答案，java.util.concurrent.ConcurrentLinkedQueue 与 Go runtime 的若干队列都是它的变体。

1 · dummy 节点与两个指针

结构是一条单向链表，Head 指向一个不携带数据的 dummy 节点，Tail 指向最后一个节点或它的前一个。真正的第一个元素在 Head.next 上。

dummy 节点省不掉。若 Head 直接指向第一个元素，队列空时 Head 与 Tail 都是 NIL，入队要同时改两个指针；队列只剩一个元素时出队同样要同时改两个。一次 CAS 只能原子地改一个字，两个指针没法一起改。dummy 节点把这两种边界情形合并成常规情形：链表永不为空，Head == Tail 就是队列空。

一次 enqueue 要改两处：把新节点挂到 t.next 上，再把 Tail 推到新节点。两处各一次 CAS，中间必然存在一个窗口。

2 · enqueue 的两次 CAS 与中间状态

读 t = Tail，读 nx = t.next；若 nx != NIL 说明 Tail 落后，处理后重来；否则 CAS(t.next, NIL, node)，成功则 CAS(Tail, t, node)

链接必须用 CAS 而不是普通写。两个线程可能读到同一个 t，谁的 CAS(t.next, NIL, node) 换成功谁就入队成功，另一个发现 t.next 已非 NIL，退回去重读。

第二次 CAS 允许失败。Tail 落后时任何线程都可以替它推进，所以等到原主来推 Tail 的时候，可能已经有人代劳了。这一次失败不是错误，只表示这件事已经被别人做过。

图 2-1 · Michael-Scott 队列的单步交错器。左右两栏是两个线程的程序计数器与局部变量，中间是共享内存与节点堆，下方是已走过的交错序列。可切换操作集，也可一键复现「节点已链上、Tail 尚未推进」那个中间状态。

穷举两个 enqueue 的全部交错共 702 条，全部可线性化。换成一个线程做 enqueue 加 dequeue、另一个做 enqueue，交错数涨到 90178，同样一条反例都没有。

3 · 帮助推进 Tail

「见到 Tail 落后就替它 CAS(Tail, t, nx)」这条分支不是优化，而是 lock-free 的前提。

设某线程刚做完 CAS(t.next, NIL, node) 就被抢占。此刻链表已经包含新节点，而 Tail 指向它的前一个。若别的 enqueue 线程只会「发现 Tail 落后就重来」，它每一轮都读到同一个落后的 Tail、发现 nx != NIL、重来，全局没有任何线程在推进。

图 3-1 · 冻结 T1 于入队的某一步之后，教科书版与去掉帮助的版本各自能否让 T2 跑完。可调冻结位置，也可把对照线程换成 dequeue。

实测：把 T1 冻结在链接之后，教科书版里 T2 再走 8 步就完成，去掉帮助的版本跑满 4000 步一次也没能推进。不设冻结、直接穷举两个 enqueue 的交错，教科书版 702 条全部在有限步内收敛，去掉帮助的版本在 60 步预算下枚举出 3822 条，其中 500 条到预算耗尽仍未跑完。

注 · 上面这个对照实验最初做不出来。把 enqueue 的帮助削掉之后，用一个 dequeue 线程当对照，T2 照样 9 步跑完 —— 因为 dequeue 自己那段 h == t 且 nx != NIL 的分支做的正是同一件事，替 enqueue 把 Tail 推过去。论文伪代码里这两段隔着大半页，看上去是两条不相干的边界处理。要让 livelock 现形，对照线程必须也是 enqueue。

4 · 用普通写链接节点的后果

把 CAS(t.next, NIL, node) 换成 store(t.next, node)，enqueue 从五步缩到三步，单线程下行为完全相同。

图 4-1 · 普通写链接与 CAS 链接的对照，附全部交错的统计。可一键复现那条六步的最短反例，观察先入队的节点如何从链上消失。

两个 enqueue 的全部交错只有 20 条，其中 18 条不可线性化。最短的反例只要六步：

0 T1: node = alloc(1) → n2; t = load(Tail) → n1
1 T1: store(n1.next, n2)
2 T2: node = alloc(2) → n3; t = load(Tail) → n1
3 T1: store(Tail, n2)
4 T2: store(n1.next, n3)
5 T2: store(Tail, n3)

第 4 步把 n1.next 从 n2 改成 n3，元素 1 连同它的节点一起从链上掉了下去。幸存的两条合法交错，是两个线程完全不重叠的那两条。九成的交错出错，而单元测试若只跑顺序执行，一条都发现不了。

5 · dequeue 与空队列的判别

出队要读三个量：h = Head、t = Tail、nx = h.next。判别分三种情形：

  • h != t：队列非空，CAS(Head, h, nx) 摘掉 dummy，nx 成为新的 dummy，它携带的值就是返回值。
  • h == t 且 nx == NIL：队列真空，返回空。
  • h == t 且 nx != NIL：Tail 落后，替它推进后重来。

值必须在 CAS(Head, ...) 之前读出来。CAS 一旦成功，nx 就成了新的 dummy，别的线程随时可能再把它摘掉并释放。这个顺序约束在带 GC 的语言里无所谓，在 C++ 里读晚一步就是 use-after-free。

三种情形里最容易写错的是第二种与第三种的区分。只看 h == t 就返回空的实现，会在「有人正在入队但 Tail 还没跟上」时谎报空队列。而这个中间状态的存在时间可以是任意长的，因为入队线程可能在两次 CAS 之间被换出去。

6 · 参考文献

  1. Michael, M. M., & Scott, M. L. (1996). Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. Proceedings of the 15th ACM Symposium on Principles of Distributed Computing, 267–275.
  2. Ladan-Mozes, E., & Shavit, N. (2008). An optimistic approach to lock-free FIFO queues. Distributed Computing, 20(5), 323–341. 用双向链表把 enqueue 的两次 CAS 减到一次。
  3. Herlihy, M., & Shavit, N. (2012). The Art of Multiprocessor Programming (Revised ed., Chapter 10). Morgan Kaufmann. 第 10 章逐行讲解 MS 队列，含线性化点的选取论证。
  4. OpenJDK. java.util.concurrent.ConcurrentLinkedQueue 源码注释。Doug Lea 在其中记下了与论文的两处偏离：允许 Tail 落后不止一格以摊薄 CAS 次数，以及自链接节点用作已出队标记。