> 大家好，我是[王有志](https://flowus.cn/chang/share/fa5ee5c8-bbd8-4a82-a31e-c6be478f44bc)，欢迎和我聊技术，聊漂泊在外的生活。快来加入我们的Java提桶跑路群：[共同富裕的Java人](https://flowus.cn/chang/share/c864e259-7629-42ac-84ea-6c4f509adfa8)。

今天的主题是**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个部分：

![](http://img.blog.itpub.net/blog/2023/07/16/2f40c3892131457b.png?x-oss-process=style/bb)

今天我们一起学习前两个部分，了解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的实现：

![](http://img.blog.itpub.net/blog/2023/07/16/8660be8e60dfd597.png?x-oss-process=style/bb)
可以看到，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](https://flowus.cn/chang/share/466179d4-da50-40c8-b716-9ba667d5fc3c) 1990

- Mellor Crummey，Scott [Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors](https://flowus.cn/chang/share/8dba980c-6e79-485b-ab33-254c2141ea88) 1991

- Craig [Building FIFO and priority-queueing spin locks from atomic swap](https://flowus.cn/chang/share/c0694ea9-80b8-4d58-b1d5-be2ee65b8305) 1993

- Landin， Hagersten [Efficient Software Synchronization on Large Cache Coherent Multiprocessors](https://flowus.cn/chang/share/7db65359-3591-4e45-9631-8d92e39a280d) 1994

- Doug Lea [The java.util.concurrent Synchronizer Framework](https://flowus.cn/chang/share/dedb9468-ba9f-47fb-9050-3f44bf2804d4) 2004

- 《[多处理器编程的艺术](https://book.douban.com/subject/3901836/)》中第7章详细讨论了队列锁的设计，包括基于数组的设计，MCS锁，CLH锁。

# 基于数组的自旋锁

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

## 基于原子指令的自旋锁

第一种设计（SPIN ON TEST-AND-SET），即[TASLock](https://gitee.com/wyz-A2/JavaInterview/blob/master/Concurrence/src/main/java/com/wyz/lock/TASLock.java)，使用CPU提供的原子指令test-and-set尝试更新锁标识：

![](http://img.blog.itpub.net/blog/2023/07/16/9b6b547f66d36590.png?x-oss-process=style/bb)
初始化锁标识为CLEAR，获取锁时尝试更新锁标识为BUSY，更新成功则获取到锁，释放时将锁标识更新为CLEAR。

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

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

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

因此提出了第二种设计（SPIN ON READ），即[TTASLock](https://gitee.com/wyz-A2/JavaInterview/blob/master/Concurrence/src/main/java/com/wyz/lock/TTASLock.java)，加入test指令，避免频繁的：

![](http://img.blog.itpub.net/blog/2023/07/16/bc78b961c2ba4760.png?x-oss-process=style/bb)
该设计中，在执行test-and-set指令前，先进行锁标识状态的判断，处于BUSY状态，直接进入自旋逻辑（或运算的短路特性），跳过test-and-set指令的执行。

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

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

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

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

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

![](http://img.blog.itpub.net/blog/2023/07/16/2b1344c42249210a.png?x-oss-process=style/bb)
可以看到SPIN ON READ的设计随着CPU数量的增多性能确实得到了改善，但距离理想的性能曲线仍有着不小的差距。

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

![](http://img.blog.itpub.net/blog/2023/07/16/43a2b9585d323051.png?x-oss-process=style/bb)
此时需要考虑设置合理的延迟时间，选择合适的退避（backoff）算法来减少竞争。

**Tips**：[Java版TASLock](https://gitee.com/wyz-A2/JavaInterview/blob/master/Concurrence/src/main/java/com/wyz/lock/TASLock.java)和[TTASLock](https://gitee.com/wyz-A2/JavaInterview/blob/master/Concurrence/src/main/java/com/wyz/lock/TTASLock.java)，供大家参考。

## 基于**数组**的自旋锁

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

![](http://img.blog.itpub.net/blog/2023/07/16/71e5f868fc5acab0.png?x-oss-process=style/bb)
**初始化**

- 创建长度为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也给出了他的测试结果：

![](http://img.blog.itpub.net/blog/2023/07/16/3224c85004784291.png?x-oss-process=style/bb)
很明显，在竞争激烈的场景中，引入队列后的自旋锁性能更加优秀，并没有过多的额外开销。

**Tips**：

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

- [Java版TEALock](https://gitee.com/wyz-A2/JavaInterview/blob/master/Concurrence/src/main/java/com/wyz/lock/TEALock.java)，供大家参考（名字是我自己起的~）。

# MCS锁的设计

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

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

## MCS锁的初始化

```Java
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锁的加锁

```Java
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锁的解锁

```Java
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](https://flowus.cn/chang/share/8dba980c-6e79-485b-ab33-254c2141ea88)》

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

- [Java版MCSLock](https://gitee.com/wyz-A2/JavaInterview/blob/master/Concurrence/src/main/java/com/wyz/lock/MCSLock.java)，供大家参考，代码有详细的注释。

# CLH锁的设计

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

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

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

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

## CLH锁的初始化

```Java
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锁的加锁

```Java
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锁的**解锁**

```Java
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](https://gitee.com/wyz-A2/JavaInterview/blob/master/Concurrence/src/main/java/com/wyz/lock/CLHLock.java)，供大家参考，代码有详细的注释。

### 单线程场景

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

![](http://img.blog.itpub.net/blog/2023/07/16/cd93ce6586c71669.png?x-oss-process=style/bb)
**Tips**：@后表示Node节点的地址。

第一次加锁后状态如下：

![](http://img.blog.itpub.net/blog/2023/07/16/9573d7b139a3ab0d.png?x-oss-process=style/bb)
这时前驱节点的锁标记为false，表示当前节点可以直接获取锁。

第一次解锁后状态如下：

![](http://img.blog.itpub.net/blog/2023/07/16/1e296d5000606774.png?x-oss-process=style/bb)
到目前为止一切都很正常，但是当我们再次加锁时会发现，好像没办法加锁了，我们来逐行代码分析锁的状态。当获取myNode后并更新锁标识，即执行如下代码后：

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

![](http://img.blog.itpub.net/blog/2023/07/16/6c68d9e32f5a80f8.png?x-oss-process=style/bb)
当获取并更新tail和myPred后，即执行如下代码后：

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

![](http://img.blog.itpub.net/blog/2023/07/16/2c408b71dde168c8.png?x-oss-process=style/bb)
这时候问题出现了，`myNode == myPred`，导致永远无法获取锁。`this.myNode.set(this.myPred.get())`相当于在链表中移除当前节点，**使获取锁的节点的直接前驱节点永远是初始化时锁标识为false的默认节点**。

### 多线程场景

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

![](http://img.blog.itpub.net/blog/2023/07/16/66fbf5008bff987a.png?x-oss-process=style/bb)

线程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](https://baike.baidu.com/item/NUMA/6906025)架构下，CLH锁的自旋性能非常差。先来看NUMA架构的示意图：

![](http://img.blog.itpub.net/blog/2023/07/16/23595315ab5250d0.png?x-oss-process=style/bb)
NUMA架构中，每个CPU有自己缓存，访问不同CPU缓存的成本较高，在需要频繁进入自旋的场景中CLH锁自旋的性能较差，而在需要频繁解锁更新其他CPU锁标识的场景中MCS锁的性能较差。

# 结语

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

- 《[RH Lock：A Scalable Hierarchical Spin Lock](https://flowus.cn/chang/share/abf4b49c-17ff-4dba-b043-d0d0d28da193)》

- 《[A Hierarchical CLH Queue Lock](https://flowus.cn/chang/share/9df9adcb-c37e-47e0-8f3d-a0777984d027)》

---

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

ITPub博客

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

最新文章