CLH 排队自旋锁 | Codeboy's Blog

形式陈述

CLH锁以隐式前驱链组织自旋请求：每个线程发布自己的等待节点，却轮询前驱节点上的标志。节点只需一个共享原子字段wait；每个线程另保存私有指针mine和pred。

采用SC原子读写与exchange。初始化一个哨兵S，S.wait=false，Tail=S；每个线程准备互不相同的新节点作为mine。

text

acquire():
  mine.wait = true
  pred = exchange(Tail, mine)
  while pred.wait: skip
  return

release():
  mine.wait = false
  mine = pred

acquire与release成对，pred在该次release前保持不变。释放后接管的是前驱节点，而不是立即重用刚刚发布给后继观察的自身节点。所有节点必须在其他线程仍可能轮询时保持有效；本页不涉及超时退出或取消排队。

这是SC算法说明，未给出弱内存语言的完整实现。若使用C++或特定CPU，字段原子性、发布和临界区数据的同步都必须按所选内存模型实现，不能仅靠伪代码中的书写顺序。

直觉

MCS让B盯自己的节点，A负责通知B；CLH让B直接盯A的节点，A只宣布“我结束了”。前驱身份保存在等待者的私有pred中，因此释放者不必寻找或等待后继补一条next边。

这个简化把困难移到了节点复用。A一结束，B可能还没来得及看见A.wait=false；A不能马上又把同一个标志设成true，否则会让B把下一轮请求误当作尚未结束的上一轮。

例子与边界

初始各线程节点为a、b、c，Tail=S。

请求	exchange前Tail	得到的pred	此后轮询
A	S	S	S.wait=false，直接进入
B	a	a	a.wait=true，等待A
C	b	b	b.wait=true，等待B

A释放时写a.wait=false。B观察到false后进入；C还在读b.wait。A把mine改为S，下次获取会把S.wait设为true，再将S排入当前Tail之后。

B释放时写b.wait=false，再把mine改为a。此时a已经完成其上一轮通知，B也已经不再需要轮询它；a可在B下一轮请求中重用。C随后以同样方式接管b。节点随着交接转移使用权，不永远属于创建它的线程。

考虑错误release只写a.wait=false，不执行mine=pred。

于是A等C、C等B、B等A，形成永久等待环。所有字段都是SC原子的，也不能补救这个生存期/代际错误。正确版本让A用S重排队，a保持false直到B不再需要它，避免把两轮通知混在同一个标志里。

每个exchange返回紧邻前驱，并且前驱把其节点设为true之后才发布。除了初始哨兵，每个节点只有在相应请求完成临界区之后才变成false。后继只有观察到这一状态才能进入，所以按队列顺序归纳可得互斥。

节点接管纪律保证“看到false”仍指向本轮前驱完成，而非未来不相关的一轮。相反，若允许超时线程简单从队列消失，后继可能一直等待它的标志；支持超时的CLH需要额外状态和绕行协议，不是删掉while循环即可。

推论与应用

获取发布与释放各需常数次更新，非等待部分为 $O(1)$ 。在缓存一致CC机器上，前驱标志虽位于别的线程节点，等待者可把它缓存在本地；前驱最终清除时产生一次必要失效，因此在通常缓存行隔离假设下为每请求 $O(1)$ RMR。

在没有缓存一致性的DSM模型中，反复读前驱节点可能始终是远程访问，不能直接照搬MCS“轮询自己本地节点”的通信界。额外间接层或不同布局可以改变这一点，但不是本页基本CLH的自动性质。

基本锁共需 $O(p+n)$ 规模的节点/锁状态，常数与MCS不同。release不需像MCS那样等待后继补next，仍不使CLH变成无锁算法：暂停的前驱会阻止后继进入。FIFO也按exchange顺序计，不保证每个已开始调用但还未执行exchange的线程按墙钟先后获得服务。

线程退出时尤须留意节点所有权转移。原本分配在该线程名下的节点，可能已经成为另一个线程的mine或pred；只有整个协议不再引用它时才能释放其内存。节点短、代码短，都不意味着资源生命周期可以省略。

参考资料

Michael L. Scott维护的可扩展同步算法伪代码，CLH部分及CC/DSM说明
Travis S. Craig, Building FIFO and Priority-Queuing Spin Locks from Atomic Swap, University of Washington Technical Report 93-02-02, 1993
Peter S. Magnusson, Anders Landin, Erik Hagersten, “Queue Locks on Cache Coherent Multiprocessors,” IPPS, 1994