大家好，我是王有志。关注 王有志 ，一起聊技术，聊游戏，聊在外漂泊的生活。 鸽了这么久怪不好意思的，因此送一本《多处理器编程的艺术》，快点击 此处 参加吧。另外欢迎大家加入“ 共同富裕的Java人 ”互助群.

今天的主题是 AbstractQueuedSynchronizer ，即AQS 。 作为 java.util.concurrent 的基础，AQS在工作中的重要性是毋庸置疑的。通常在面试中也会有两道“必考”题等着你 。

• 原理相关： AQS是什么？它是怎样实现的?

• 设计相关： 如何使用AQS实现Mutex?

原理相关的问题几乎会出现在每场Java面试中 ，是面试中的“明枪”，是必须要准备的内容；而设计相关的问题更多的是对技术深度的考察，算是“暗箭”，要尤为谨慎的去应对.

我和很多小伙伴交流关于AQS的问题时发现，大部分都只是为了应付面试而“背”了AQS的实现过程。为了全面地理解AQS的设计，今天我们会从1990年T.E.Anderson引入排队的思想萌芽开始，到Mellor-Crummey和Scott提出的MCS锁，以及Craig，Landin和Hagersten设计的CLH锁.

AQS的内容整体规划了4个部分:

今天我们一起学习前两个部分，了解AQS的前世.

Tips ：本文基于Java 11完成，与Java 8存在部分差异，请注意区分源码之间的差异.

AQS是什么？

通常我们按照类名将 AbstractQueuedSynchronizer 翻译为 抽象队列同步器 。单从类名来看，我们就已经可以得到3个重要信息:

• Abstract： 抽象类 ，通常无法直接使用； 。

• Queued： 队列 ，借助队列实现功能； 。

• Synchronizer： 同步器 ，用于控制并发.

源码中的注释也对AQS做了全面的概括:

Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. 。

提供了依赖于FIFO等待队列用于实现阻塞锁和同步器（信号量，事件等）的框架。 这段描述恰好印证了我们通过类名得到的信息，我们来看Java中有哪些AQS的实现:

可以看到，JUC中有大量的同步工具内部都是通过继承AQS来实现的，而这也正是Doug Lea对AQS的期望： 成为大部分同步工具的基础组件.

Tips ：至少在Java 8中， FutureTask 已经不再依赖AQS实现了（未考证具体版本）.

接着我们来看注释中提到的“rely on first-in-first-out (FIFO) wait queues”，这句话指出AQS依赖了FIFO的等待队列。那么这个队列是什么？我们可以在注释中找到答案:

The wait queue is a variant of a "CLH" (Craig, Landin, and Hagersten) lock queue. CLH locks are normally used for spinlocks. 。

AQS中使用的等待队列时CLH队列的变种 。那么CLH队列是什么呢？AQS做了哪些改变呢?

AQS的前世

AQS明确揭示了它使用CLH队列的变种，因此我从CLH队列的相关论文入手:

• Craig于1993年发表的《Building FIFO and priority-queueing spin locks from atomic swap》 。

• Landin和Hagersten于1994年发表的《Efficient Software Synchronization on Large Cache Coherent Multiprocessors》 。

这两篇文章都引用了T.E.Anderson于1990年发表的的《The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors》，因此我们以这篇文章中提出的 基于数组的自旋锁设计 作为切入点.

Tips :

• 《Efficient Software Synchronization on Large Cache Coherent Multiprocessors》的作者有3个人~~ 。

• Landin和Hagersten的《Efficient Software Synchronization on Large Cache Coherent Multiprocessors》中引用了Craig的《Building FIFO and priority-queueing spin locks from atomic swap》，Craig率先提出了CLH锁的结构，不知道为什么学术界以他们3人进行命名； 。

• 由于论文是很多年前收集的，现在去查找原始网站较为困难，只能提供下载链接了，对不起各位祖师爷~~ 。

  • T.E.Anderson The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors 1990 。

  • Mellor Crummey，Scott Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors 1991 。

  • Craig Building FIFO and priority-queueing spin locks from atomic swap 1993 。

  • Landin， Hagersten Efficient Software Synchronization on Large Cache Coherent Multiprocessors 1994 。

  • Doug Lea The java.util.concurrent Synchronizer Framework 2004 。

• 《 多处理器编程的艺术 》中第7章详细讨论了队列锁的设计，包括基于数组的设计，MCS锁，CLH锁.

基于 数组 的自旋锁

1990年T.E.Anderson发表了《The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors》，文章讨论了基于CPU原子指令自旋锁的性能瓶颈，并提出了基于数组的自旋锁设计.

基于原子指令的自旋锁

第一种设计（SPIN ON TEST-AND-SET），即 TASLock ，使用CPU提供的原子指令test-and-set尝试更新锁标识:

初始化锁标识为CLEAR，获取锁时尝试更新锁标识为BUSY，更新成功则获取到锁，释放时将锁标识更新为CLEAR.

设计非常简单，竞争并不激烈的场景下性能也是完全没问题，但是一旦CPU的核心数增多，问题就出现了:

• 持有者在释放锁时要和其它正在自旋的竞争者争夺锁标识内存的 独占 访问权限，因为test-and-set是原子写操作； 。

• 在使用总线的体系结构中，无论test-and-set指令是否成功，它都会消耗一次总线事务，会使总线变得拥堵.

因此提出了第二种设计（SPIN ON READ），即 TTASLock ，加入test指令，避免频繁的:

该设计中，在执行test-and-set指令前，先进行锁标识状态的判断，处于BUSY状态，直接进入自旋逻辑（或运算的短路特性），跳过test-and-set指令的执行.

额外一次读取操作，避免了频繁的test-and-set指令造成的内存争抢，也减少了总线事务 ，竞争者只需要自旋在自己的缓存上即可，只有锁标识发生改变时，才会执行test-and-set指令.

这种设计依旧有些性能问题无法解决:

• 如果频繁锁标识频繁的发生改变，CPU的缓存会频繁的失效，重新读取； 。

• 持有者释放锁时，会导致所有CPU的缓存失效，必须重新在内存或总线中竞争.

T.E.Anderson对两种设计进行了测试，计算了在不同数量的CPU上执行了100万次操作的耗时，执行等待锁，执行临界区，释放锁和延迟一段时间.

可以看到SPIN ON READ的设计随着CPU数量的增多性能确实得到了改善，但距离理想的性能曲线仍有着不小的差距.

除了这两种设计外，T.E.Anderson还考虑了在自旋逻辑中引入延迟来减少冲突:

此时需要考虑设置合理的延迟时间，选择合适的退避（backoff）算法来减少竞争.

Tips ： Java版TA S Lock 和 T T A S Lock ，供大家参考.

基于 数组 的自旋锁

前面的设计中，自旋锁的性能问题是由多个CPU同时争抢内存访问权限产生的，那么让它们按顺序排队是不是就解决了这个问题？T.E.Anderson引入了队列的设计:

初始化 。

• 创建长度为CPU数量P的数组flags[P] 。

• flags[0]标识为HAS_LOCK（拥有锁），其余标记为MUST_WAIT（等待锁） 。

• 初始化queueLast为0， 标识当前队列位置 。

加锁 。

• CPU通过ReadAndIncrement指令读取queueLast后保存为自己的myPlace 。

  • ReadAndIncrement指令，先读取，后自增

• CPU判断自己的flags[myPlace mod P]上的标记来决定持有锁或进入自旋 。

  • 取模操作让数组变成了头尾相连的“环状”数组

解锁 。

• 将当前CPU在队列中的位置flags[myPlace]更新为MUST_WAIT 。

• 将flags[(myPlace + 1) mod P]更新为HAS_LOCK，标识下一个CPU获取锁 。

每个CPU只访问自己的锁标识（myPlace），避免了争抢内存访问的权限，另外锁会直接释放给队列中的下一个CPU，避免了通过竞争获取，减少了从释放锁到获取锁的时间.

当然缺点也很明显，仅从伪代码的行数上也能看出来， 基于队列的自旋锁设计更复杂，当竞争并不激烈时，它的性能会更差 。T.E.Anderson也给出了他的测试结果:

很明显，在竞争激烈的场景中，引入队列后的自旋锁性能更加优秀，并没有过多的额外开销.

Tips :

• T.E.Anderson的论文就介绍到这里，除了对自旋锁的讨论，文章中还讨论了在自旋锁引入退避算法和静态延迟（static delays）的优劣，就留给大家自行阅读了； 。

• Java版TEALock ，供大家参考（名字是我自己起的~）.

MCS锁的设计

基于数组的自旋锁是排队思想的实现 ，T.E.Anderson的论文发表后，又涌现出了许多使用排队思想锁，例如：Mellor-Crummey和Scott于1991年在论文《Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors》中提出的MCS锁，也是基于排队思想实现，只不过在数据结构上选择了 单向链表 .

描述MCS锁的初始化与加解锁的原理，我使用经过“本地化”的Java实现版本的MCS锁:

MCS锁的 初始化

                        
                          public class MCSLock {

  AtomicReference<QNode> lock;
  
  ThreadLocal<QNode> myNode;
  
  public MCSLock() {
    this.lock = new AtomicReference<>(null);
    this.myNode = ThreadLocal.withInitial(QNode::new);
  }
  
  private static class QNode {
    private boolean locked;
    private QNode next;
  }
}

                        
                      

• 声明单向链表的节点QNode，locked表示 锁是否被前驱节点获取 ； 。

• 创建QNode节点lock，表示当前锁的位置，实际上也是链表的尾节点.

MCS锁的 加锁

                        
                          public void lock() {
  QNode I = this.myNode.get();
  QNode predecessor = this.lock.getAndSet(I);
  if (predecessor != null) {
    I.locked = true;
    predecessor.next = I;
    while (I.locked) {
      System.out.println("自旋，可以加入退避算法");
    }
  }
}

                        
                      

• 为每个线程初始化QNode，命名为 I ； 。

• 通过 原子指令 获取 I 的前驱节点lock命名为predecessor，并将 I 设置为lock（取出当前lock，并设置新的lock）； 。

  • 当 predecessor == null 时，表示队列为空，可以直接返回，代表获取到锁； 。

  • 当 predecessor != null 时，表示前驱节点已经获取到锁； 。

    • 更新locked，表示锁已经被前驱节点获取； 。

    • 更新predecessor的后继节点为 I ，否则predecessor无法唤醒 I ； 。

    • I 进入自旋逻辑.

MCS锁的 解锁

                        
                          public void unlock() {
  QNode I = this.I.get();
  if (I.next == null) {
    if (lock.compareAndSet(I, null)) {
      return;
    }
    
    while (I.next == null) {
      System.out.println("自旋");
    }
  }
  
  I.next.locked = false;
  I.next = null;
}

                        
                      

• 获取当前线程的QNode命名为 I ； 。

• 如果 I.next == null ，队列中无其它节点，即不存在锁竞争的场景； 。

  • 尝试通过CAS更新lock为null，保证下次加锁时 predecessor == null ，成功则直接返回； 。

  • 如果失败，表示此时有线程开始竞争锁，此时进入自旋，保证竞争者成功执行 predecessor.next = I ； 。

• 如果 I.next != null ，队列中有其他节点，锁存在竞争； 。

  • 更新后继节点的locked标识，使其跳出自旋； 。

  • 更新自己的后继节点指针，断开联系.

MCS锁的逻辑并不复杂，不过有些细节设计的非常巧妙，提个问题供大家思考下：加锁过程中 I.locked = true 和 predecessor.next = I 的顺序可以调整吗?

MCS锁的整体设计思路到这里就结束了，Mellor-Crummey和Scott给出了MCS锁的4个优点:

• FIFO保证了公平性，避免了锁饥饿； 。

• 自旋标识是线程自身的变量，避免了共享内存的访问冲突； 。

• 每个锁的创建只需要极短的时间（requires a small constant amount of space per lock）； 。

• 无论是否采用一致性缓存架构, 每次获取锁只需要$ O(1)$ 级别的通信开销.

除此之外，相较于T.E.Anderson的设计， MCS锁在内存空间上是按需分配，并不需要初始化固定长度数组，避免了内存浪费 .

Tips :

• 本文只简单的介绍MCS锁的原理，想要深入学习的可以阅读以下内容:

  • 《 Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors 》 。

  • 《多处理器编程的艺术》第7章 。

• Java版 MCS Lock ，供大家参考，代码有详细的注释.

CLH锁的设计

1993年Craig发表了《Building FIFO and priority-queueing spin locks from atomic swap》，文章中描述了另一种基于排队思想的队列锁，即CLH 锁（我觉得称为Craig Lock更合适）的雏形，它和MCS锁很相似，但有一些差异:

• CLH旋转在队列前驱节点的锁标识上； 。

• CLH锁使用了一种“隐式”的链表结果.

我们带着这两个差异来看CLH的锁的设计，原文使用Pascal风格的伪代码，这里我们使用《多处理器编程的艺术》中提供的Java版本，与论文中的差异较大，重点理解实现思路即可.

CLH锁的 初始化

                        
                          public class CLHLock {
  
  AtomicReference<Node> tail;
  
  ThreadLocal<Node> myPred;
  
  ThreadLocal<Node> myNode;
  
  public CLHLock() {
    this.tail = new AtomicReference<>(new Node());
    this.myNode = ThreadLocal.withInitial(Node::new);
    this.myPred = new ThreadLocal<>();
  }
  
  private static class Node {
    private volatile boolean locked = false;
  }
}

                        
                      

Craig的设计中，请求锁的队列节点有两种状态，在实现中可以使用布尔变量代替:

• PENDING，表示获取到锁或者等待获取锁，可以使用true； 。

• GRANTED，表示释放锁，可以使用false.

另外CLHLock的初始化中， this.tail = new AtomicReference<>(new QNode()) 添加了默认节点，该节点的locked默认为false，这是借鉴了链表处理时常用到技巧虚拟头节点.

CLH锁的 加锁

                        
                          public void lock() {
  Node myNode = this.myNode.get();
  myNode.locked = true;
  Node pred = this.tail.getAndSet(myNode);
  this.myPred.set(pred);
  while(myPred.locked) {
    System.out.println("自旋，可以加入退避算法");
  }
}

                        
                      

实现中巧妙的使用了两个ThreadLocal变量来构建出了逻辑上的链表，和传统意义的单向链表不同， CLH的链表从尾节点开始指向头部 .

另外，CLH锁中的节点只关心自身前驱节点的状态，当前驱节点释放锁的那一刻，节点就知道轮到自己获取锁了.

CLH锁的 解锁

                        
                          public void unlock() {
  Node myNode = this.myNode.get();
  myNode.locked = false;
  this.myNode.set(this.myPred.get());
}

                        
                      

解锁的逻辑也非常简单，只需要更新自身的锁标识即可。但是你可能会疑问 this.myNode.set(this.myPred.get()) 是用来干嘛的？删除会产生什么影响吗?

Tips ： Java版 CLH Lock ，供大家参考，代码有详细的注释.

单线程场景

在单线程场景中，完成CLH锁的初始化后，锁的内部结构是如下:

Tips ：@后表示Node节点的地址.

第一次加锁后状态如下:

这时前驱节点的锁标记为false，表示当前节点可以直接获取锁.

第一次解锁后状态如下:

到目前为止一切都很正常，但是当我们再次加锁时会发现，好像没办法加锁了，我们来逐行代码分析锁的状态。当获取myNode后并更新锁标识，即执行如下代码后:

                        
                          Node myNode = this.myNode.get();
myNode.locked = true;

                        
                      

当获取并更新tail和myPred后，即执行如下代码后:

                        
                          Node pred = this.tail.getAndSet(myNode);
this.myPred.set(pred);

                        
                      

这时候问题出现了， myNode == myPred ，导致永远无法获取锁。 this.myNode.set(this.myPred.get()) 相当于在链表中移除当前节点， 使获取锁的节点的直接前驱节点永远是初始化时锁标识为false的默认节点.

多线程场景

再来考虑多线程的场景，假设有线程t1和线程t2争抢锁，此时t1率先获取到锁:

线程t1释放后再次立即获取是有可能出现的，最典型的情况是如果为自旋逻辑添加了退避算法，当线程t2多次自旋后再次进入自旋逻辑，此时线程t1释放锁后立即尝试获取锁，先更新线程t1的锁标记为true，接着从tail节点中获取前驱节点线程t2，然后再更新tail节点，此时线程t1在线程t2的锁标记上自旋，线程t2在线程t1的锁标记上自旋，凉凉~~ 。

留个思考题，为什么 this.myNode.set(this.myPred.get()) 可以避免这种情况?

CLH锁和MCS锁的对比

首先是代码实现上，CLH锁的实现非常简单，除了自旋的部分其余全是平铺直叙，反观MCS锁，分支，嵌套，从实现难度上来看CLH锁更胜一筹（难点在于逆向思维，让当前节点自旋在直接前驱节点的锁标识上）。另外，CLH锁只在加锁时使用了一次原子指令，而MCS锁的加解锁中都需要使用原子指令，性能上也略胜一筹.

那么CLH锁是全面超越了MCS锁吗？不是的，在 NUMA 架构下，CLH锁的自旋性能非常差。先来看NUMA架构的示意图:

NUMA架构中，每个CPU有自己缓存，访问不同CPU缓存的成本较高，在需要频繁进入自旋的场景中CLH锁自旋的性能较差，而在需要频繁解锁更新其他CPU锁标识的场景中MCS锁的性能较差.

结语

到目前为止，我们一起学习了3种基于排队思想的自旋锁设计，作为AQS的“前世”，理解它们的设计能够帮助我们理解AQS的原理。当然并非只有这3种基于排队思想的自旋锁，还有如RHLock，HCLHLock等，感兴趣的可以自行探索，这里提供论文链接:

• 《 RH Lock：A Scalable Hierarchical Spin Lock 》 。

• 《 A Hierarchical CLH Queue Lock 》 。

---

好了，今天就到这里了，Bye~~ 。

最后此篇关于14.AQS的前世，从1990年的论文说起的文章就讲到这里了,如果你想了解更多关于14.AQS的前世，从1990年的论文说起的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。