14.AQS的前世，从1990年的论文说起

Posted on by hackdl

大家好，我是王有志。关注王有志，一起聊技术，聊游戏，聊在外漂泊的生活。
鸽了这么久怪不好意思的，因此送一本《多处理器编程的艺术》，快点击此处参加吧。另外欢迎大家加入“共同富裕的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版TASLock和TTASLock，供大家参考。

基于数组的自旋锁

前面的设计中，自旋锁的性能问题是由多个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 lock;

  ThreadLocal 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版MCSLock，供大家参考，代码有详细的注释。

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 tail;

  ThreadLocal myPred;

  ThreadLocal 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版CLHLock，供大家参考，代码有详细的注释。

单线程场景

在单线程场景中，完成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~~

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: