本文是AQS与CLH相关论文学习系列第二篇。 系列其他文章链接如下
AQS与CLH相关论文学习系列（一）- 排队式自旋锁思想启蒙
AQS与CLH相关论文学习系列（三）- CLH 锁
AQS与CLH相关论文学习系列（四）- AQS的设计思路
本文在第一篇 AQS与CLH相关论文学习系列（一）- 排队式自旋锁思想启蒙的基础上进一步学习首个提出的基于链表结构排队式自旋锁： MCS 锁
参考文章 Algorithms for Scalable Synchronization onSharedMemory Multiprocessor 在 Anderson 论文之后， 首个基于链表的排队式自旋锁 Ticket 锁
在 Anderson 90 年发布的论文发布之后， Mellor-Crummey 和 Scott 紧随其后在 91 年发布的论文中【参考文章2】中提到了另一种有趣而简单的锁， 也是排队的思想。
类似饭店排队叫号， 每一个试图进入饭店的人， 首先获取一个属于自己的编号， 当有位置空闲出来后， 饭店当前可服务的编号会增加， 等到你的编号和叫到的编号相等时， 代表你可以接受服务， 也就是获取了锁 。
伪代码如下：
小提示 伪代码方法声明method( varName : type), 等价于于 java 语法的 method(Class var)^someType 代表someType类型的指针something^ 代表指针something所指向的变量& 代表获取该变量的内存地址, 也就是指针。&L->next_ticket 表示的是获取next_ticket 的地址， 不是 L 的地址：= 表示赋值这个算法的问题还是会涉及到内存争抢， 因为需要自旋监控公共的 counter, 尽管是读操作， 但是当 counter 变动频繁时， CPU 缓存能发挥作用的时间也很短。
该算法的特点之一是可以通过自己活得的 my_ticket 值与 now_serving 之前的差值， 据此信息可以进行一定的延迟等待， 减少内存的争抢访问。 就像饭店排队一样，通过自己拿到的号和当前叫号牌上显示的号差值， 推算一下自己要不要在这里持续等待是一个道理。不过这个算法治标不治本，又引入了争抢激烈时， 退避延时该如何取舍的问题， 因此笔者不作过多展开， 感兴趣的同学可自行阅读论文。
MCS 锁Mellor-Crummey 和 Scott 在总结了前人提出的各种各种自旋锁后， 提出了自己设计的基于链表的排队式自旋锁。
笔者认为， 其实就是受到基于数组的排队式自旋锁启发后的一种改良，核心思想和基于数组的排队没有太大区别， 只是数据结构变化带来的一种空间消耗上的进步。如作者本人所说， MCS 锁主要有如下优点，其中前 3 个优点是 Anderson 提出的数组自旋锁也具备的， 第 4 点作者宣称是 MCS 锁独有的优点
保证锁的 FIFO 先入先出获取顺序，可以避免饥饿式等待问题自旋在局部标识变量上， 避免共享内存的频繁访问争抢每个锁的创建只需要 O（1） 的空间开销无论 CPU 架构是否采用一致性缓存架构（coherent cache）, 该算法每次获取锁都只会产生 O(1) 常量级别的内存通信开销。但笔者并不理解为什么基于数组排队的自旋锁没有第 4 个优点， 论文作者也提到了， 其实第 4 个优点是第2个优点的产物。而第2点是 MCS 锁和基于数组排队自旋锁都具备的特性
伪代码如下：
小提示 ^someType 代表某种类型的指针somePointer^ =x 代表somePointer 指针所指向的位置修改为 x& 代表获取该变量的内存地址, 也就是指针。：= 表示赋值首先描述一下这个锁设计的整体思想， 便于理解：
每一个进程都对应于一个链表中的结点， 在伪代码中， 该结点类型为 qnode, 每一个 qnode 中有两个变量， 一个后继指针 next, 用于指向队列中的下一个结点， 一个 Boolean 标识符locked， 代表锁是否已经被前驱结点获取， true 代表锁已经被前驱结点获取， 当前进程需要自旋等待， false 代表当前进程可以结束等待。
具体看 MCS 锁的三个核心操作
锁的初始化操作：
新建一个 lock 类型的指针 L, 使每个需要获取锁的进程都能访问到 L 。加锁操作（入队）：
为本进程初始化一个 qnode， 指针 I 指向这个 qnode ( 初始化 qnode 这个操作伪代码中没有体现）让 I 所指的 qnode 的后继指针 next 指向 nil(null)建立临时变量指针 predecessor， 利用原子指令 fetch_and_store(L,I) , 让 predecessor 指向原本的队尾结点， 然后将 L 所指内存的值更新为 I。 其实就是将新的 qnode 结点插入队尾， predecessor 记录当前结点的前驱， L 最终指向新的队尾。 伪代码采用类似 C 语言的风格， L 变量是一个二级指针。fetch_and_store( L, I) 这条原子性指令的语义是将 地址A 指向的内存区域值取出来， 并且更新为 I。这里二级指针的作用是让多个需要访问锁的进程共享一块内存， 这块内存中保存着队尾指针， L 保存的是这块共享内存的地址， 每个进程只需要持有 L 的副本， 即可共同读写队列的队尾指针。 如果 predecessor 所指 qnode 为空 代表队列为空 ， 则可以直接从 acquire_lock 方法返回 ，代表已经获取了锁。 如果 predecessor 所指 qnode 不为空 代表锁已经被前驱结点占据， 则需要将执行 I->locked := true , 将当前结点中的 locked 值置为 true, 代表锁已经被前驱结点获取， 当前进程需要等待。前驱结点的 next 指针指向当前结点在当前 qnode 结点 locked 值未被更新为 false 前， 自旋等待。解锁操作（出队）：
如果当前结点的后继指针 next 指向结点非空 则直接将后继 qnode 中的 locked 置为 false， 代表后继结点可以获取锁 如果当前结点的后继指针 next 指向结点非空 则首先尝试执行原子指令 compare_and_swap(L,I,nil) , 即将队尾指置空， 如果成功， 则可以直接返回。 如果失败则说明突然有新的 qnode 入队， 此时需要先自旋判断当前节点的 next 指针是否已经被更新， 只有在next 被更新完毕后， 才能继续执行 I->next->lockd:=false上述算法中， 最富有技巧性的部分有两点：
acquire_lock 操作中， 是先执行 I->locked := true, 再执行 predecessor->>next:=I , 这两行代码的顺序绝对不能调换， 因为要确保当前结点不会错过前驱结点的释放锁操作， 如果这两行代码调换了顺序，则可能发生在 predecessor->>next:=I 执行后， I->locked := true 执行前，前驱结点对应进程执行完毕了 release_lock 操作， 将当前结点的 locked 标志置为了 false, 随后当前结点对应进程又将 locked 置为了 false,进入自旋， 则永远无法退出循环。release_lock 操作中， compare_and_swap(L,I,nil) 执行失败后的自旋 repeat while I->next = nil 必不可少， 因为 compare_and_swap(L,I,nil) 执行失败， 只能说明有其他进程抢先执行了 acquire_lock 操作中的 fetch_and_store( L, I)， 但是肯能 predecessor->>next:=I 还尚未执行完毕， 所以正在释放锁的进程必须自旋等待直到它的 next 指针被更新后， 再完成后继结点的 locked 标识更新。 MCS 锁的证明笔者在阅读 MCS 锁论文中，发现作者提到了 MCS 锁的证明思路， 这种证明思路，在其他锁的设计论文中并未提到。主要思路如下
即先假设 acuire_lock 操作和 release_lock 操作整体都是原子性的（除了 acquire_lock 进入自旋等待状态后的部分非原子）。 基于这种假设证明锁的互斥性， 无死锁性后， 再证明将一些操作保留语义正确性的基础上， 可以转化到算法描述的非原子步骤， 即完成了整个算法的正确性证明。
这种非常正式的理论证明很难得，但是MCS lock 作者因证明过程较为冗长， 将其放入了论文的如下参考文献 Technical Report 的附录中，笔者简单尝试， 并未搜索获取到， 这里仅作记录， 如有同学能够获取到， 希望评论分享