本文正在参与「金石方案」

咱们好，我是王有志。关注王有志，一同聊技能，聊游戏，聊在外流浪的生活。鸽了这么久怪不好意思的，因而送一本《多处理器编程的艺术》，快点击此处参与吧。别的欢迎咱们参加“共同富裕的Java人”互助群。

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

原理相关：AQS是什么？它是怎样完结的？
规划相关：如何运用AQS完结Mutex？

原理相关的问题几乎会呈现在每场Java面试中，是面试中的“明枪”，是有必要要预备的内容；而规划相关的问题更多的是对技能深度的调查，算是“暗箭”，要尤为谨慎的去应对。

为了全面地了解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<QNode> lock;
  ThreadLocal<QNode> I;
  public MCSLock() {
    this.lock = new AtomicReference<>(null);
    this.I = 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.I.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<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版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~~

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

AQS是什么？

AQS的宿世

根据数组的自旋锁

根据原子指令的自旋锁

根据数组的自旋锁

MCS锁的规划

MCS锁的初始化

MCS锁的加锁

MCS锁的解锁

CLH锁的规划

CLH锁的初始化

CLH锁的加锁

CLH锁的解锁

单线程场景

多线程场景

CLH锁和MCS锁的比照

结语

作者信息

推广

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

AQS是什么？

AQS的宿世

根据数组的自旋锁

根据原子指令的自旋锁

根据数组的自旋锁

MCS锁的规划

MCS锁的初始化

MCS锁的加锁

MCS锁的解锁

CLH锁的规划

CLH锁的初始化

CLH锁的加锁

CLH锁的解锁

单线程场景

多线程场景

CLH锁和MCS锁的比照

结语

相关文章

211 毕业就入职 30 人的小公司是什么体验

『白板推导系列笔记』4.线性分类

仅9天拿下CVPR竞赛冠军，家里的狗狗都改了作息

如何构建企业内的 TiDB 自运维体系

作者信息

推广