Java并发系列（二）：AQS

type

status

date

slug

summary

1、AQS是什么

上一篇文章介绍了 Java 并发问题的根源，Java 为解决并发问题提供了 volatile 、synchronized 、final 等关键字，但是这些关键字提供的功能比较单薄，远远不能满足并发编程的需求。

并发大神 Doug Lea 为此特地写了个java.util.concurrent （JUC）包，从 JDK1.5 开始引入。这是一个专门为 Java 并发编程而设计的包，为 Java 开发者提供了各种便捷的开箱即用的并发工具。包下的所有类可以分为如下几大类：

locks：显式锁(互斥锁和速写锁)相关

atomic：原子变量类相关，是构建非阻塞算法的基

executor：线程池相关

collections：并发容器相关

tools：同步工具相关，如信号量、闭锁、栅栏等功能

比如我们最常用 Semaphore 信号量、Lock 接口以及接口的实现类 ReentrantLock、ReentrantReadWriteLock 等都来源自这个包。

那么 AQS 又是什么呢？AQS 和上面提到的这个并发包又是什么关系呢？

AQS 的全称为 AbstractQueuedSynchronizer ，这个类在 java.util.concurrent.locks 包下面。

一句话总结，AQS 是用来实现锁或者其他同步器组件的公共基础部分的抽象实现，是整个 JUC 体系的基础。

说的更加通俗易懂一点，比如我们常用的 ReentrantLock、Semaphore 这些并发工具，虽然他们面向开发者的上层用法存在差异，但是在更底层的实现上是存在功能的重叠，比如都需要占用操作系统的共享资源、释放共享资源等。

AQS 把这些通用的功能提炼出来写成一个并发抽象类，屏蔽了底层和操作系统交互等细节。只需要继承 AQS 并实现几个模板方法，就可以实现各种类型的并发工具。Java 开发者自己也可以基于 AQS 实现 ReentrantLock 这类并发工具。

2、一些底层工具

在介绍 AQS 原理之前，先介绍一下和 AQS 相关的一些底层工具。这些底层工具不需要太深入理解，简单了解原理即可。

2.1 Unsafe

Unsafe 是 rt.jar 包下的一个类，类中的方法都是 native 方法，它们使用 JNI 的方式访问本地 C++ 实现库。由此提供了一些绕开 JVM 的更底层功能，可以提高程序效率。

Unsafe 作用可以大致归纳为：

内存管理，包括分配内存、释放内存等。

非常规的对象实例化。

操作类、对象、变量。

自定义超大数组操作。

多线程同步。包括锁机制、CAS 操作等。

线程挂起与恢复。

内存屏障。

Unsafe 类使 Java 语言拥有了类似 C 语言指针一样操作内存空间的能力，这无疑也增加了程序发生相关指针问题的风险。一般不建议开发者自行使用 Unsafe 类。如果要使用的话，一般通过单例模式获取 Unsafe 对象。

2.2 CAS

2.2.1 CAS 是什么

CAS 是 Compare And Swap 的缩写，直译就是比较并交换。CAS 是现代 CPU 广泛支持的一种对内存中的共享数据进行操作的一种特殊指令，这个指令会对内存中的共享数据做原子的读写操作。其作用是让 CPU 比较内存中某个值是否和预期的值相同，如果相同则将这个值更新为新值，不相同则不做更新。

本质上来讲 CAS 是一种无锁的解决方案，也是一种基于乐观锁的操作，可以保证在多线程并发中保障共享资源的原子性操作，相对于 synchronized 或 Lock 来说，是一种轻量级的实现方案。

JUC 包中大量使用了 CAS 机制来实现多线程下数据更新的原子化操作，比如 AtomicInteger、ConcurrentHashMap当中都有 CAS 的应用。但 Java 中并没有直接实现 CAS，而是使用上面提到的 Unsafe 类，通过 JNI 调用 native 方法，借助 C/C++ 调用 CPU 指令来实现的。

例如 AtomicInteger 类的 compareAndSet 方法就调用了 Unsafe 的 compareAndSwapInt 方法

这个 unsafe 方法对应的的 C++ 源码如下：

看到这上面的源码调用了 Atomic::cmpxchg 方法。事实上 Java 的 CAS 操作的最终底层实现，是通过 lock cmpxchg 汇编指令实现的。

lock 指令：前面有介绍过，可以禁用指令重排序，并保证后面指令执行的原子性。

cmpxchg 指令：真正实现比较并交换操作的指令。虽然 cmpxchg 看起来只有一条指令，但在多核 CPU 下单独使用仍然不具有原子性，因为 cmpxchg 作为复杂指令同时带有读写操作，在执行时会被分解为一条条的更小的微码。一般来说只有单一的 load、stroe 等指令是真正原子性的。所以 cmpxchg 指令必须搭配 lock 指令一起使用才能保证原子性。

2.2.2 CAS 的问题

CAS 虽然实现了比较并交换的原子性，且性能高效，但也不是完美的。目前 CAS 存在下面三个问题（面试常问！）：

ABA问题

循环时间长，开销大

只能保证一个共享变量的原子操作

1）ABA问题

ABA 问题出现的基本流程：

进程 P1 在共享变量中读到值为A。

P1 被抢占了，进程 P2 执行。

P2 把共享变量里的值从 A 改成了B，再改回到 A，此时被 P1 抢占。

P1 回来看到共享变量里的值没有被改变，于是继续执行。

虽然 P1 以为变量值没有改变，继续执行了，但是这个会引发一些潜在的问题。ABA 问题最容易发生在 lock free 的算法中。因为 CAS 判断的是指针的地址。如果这个地址被重用了，问题就很大了（地址被重用是很经常发生的，一个内存分配后释放了，再分配，很有可能还是原来的地址）。

ABA 问题的解决思路就是使用版本号：在变量前面追加上版本号，每次变量更新的时候把版本号加 1，那么 A->B->A 就会变成 1A->2B->3A。

另外，从 Java 1.5 开始，JDK 的 Atomic 包里提供了一个类 AtomicStampedReference 来解决 ABA 问题。这个类的 compareAndSet 方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志（类似于版本号），如果全部相等，才以原子方式将该引用和该标志的值设置为给定的更新值。

2）循环时间长，开销大

在 Unsafe 的实现中使用了自旋锁的机制。当预期值和主内存中的值不等时，就会循环进行 CAS 操作(do while循环同时将期望值更新为最新的)。如果长时间都不成功的话，那么会造成 CPU 极大的开销。如果 JVM 能支持处理器提供的 pause 指令那么效率会有一定的提升。

3）只能保证一个共享变量的原子操作

当对一个共享变量执行操作时，我们可以使用 CAS 的方式来保证原子操作。但如果存在多个共享变量，或一整个代码块的逻辑需要保证线程安全，CAS 就无法保证原子性操作了。

解决办法是采用加锁方式（悲观锁）保证原子性，或者有一个取巧的办法，把多个共享变量合并成一个共享变量进行CAS操作。从 Java 1.5 开始，JDK 提供了 AtomicReference 类来保证引用对象之间的原子性，可以把多个变量放在一个对象里来进行 CAS 操作。

2.3 CLH锁

在介绍 CLH 锁之前我们先来看下什么叫自旋锁。自旋锁是指没有抢到锁的线程会一直自旋等待锁的释放，处于 busy-waiting 的状态，此时等待锁的线程不会进入休眠状态，而是一直忙等待浪费 CPU 周期。

下面是自旋锁的 Java 实现。

可以看出在获取锁时，线程会对一个原子变量循环执行 compareAndSet 方法，直到该方法返回成功时即为成功获取锁。这种方式实现简单，同时避免了操作系统进程调度和线程上下文切换的开销，但是存在两个缺点：

锁饥饿问题。在锁竞争激烈的情况下，可能存在一个线程一直被其他线程”插队“而一直获取不到锁的情况。

性能问题。在竞争激烈的情况下，锁状态变更会导致多个 CPU 的高速缓存的频繁同步，从而拖慢 CPU 效率。所以在实际的多处理上运行的自旋锁在锁竞争激烈时性能较差。

CLH 锁是对自旋锁的一种改进，有效的解决了以上的两个缺点。CLH 锁就是一个基于链表（队列）非线程饥饿的自旋公平锁。由于是 Craig、Landin 和 Hagersten三人的发明，因此命名为 CLH 锁。CLH 锁的原理是：

首先有一个尾节点指针，通过这个尾结点指针来构建等待线程的逻辑队列，保证先请求的线程先获得锁，避免了饥饿问题。

每一个等待锁的线程封装成队列的一个节点，每个节点自己的前驱节点某个变量上自旋等待，等待前驱节点解锁之后即可去获取锁。这样当一个线程释放它的锁时，只能使其后续线程的高速缓存失效，缩小了影响范围，从而减少了 CPU 的开销。

如上图所示，当前线程只要判断前一线程的locked状态如果是true，那么则说明前一线程要么拿到了锁，要么也处于自旋等待状态，所以自己也要自旋等待。而尾指针tailNode总是指向最后一个线程的CLHNode节点。

对 CLH 锁有了一个概念后，那么我们为什么要学习 CLH 锁呢？因为 AQS 是 JUC 的核心，而 CLH 锁又是 AQS 的基础。AQS 其实就是用了变种的 CLH 锁。

3、AQS原理

AQS 整体可以分为三个部分：

state 变量：同步状态

CLH 同步队列：双向链表，用于存储获取锁失败的线程。

ConditionObject 等待队列：单向链表，用于存储被阻塞在某个 Condition 上的线程。

整体结构可以用下面的图来表示：

AQS 核心思想是：如果被请求的共享资源空闲，则将当前请求资源的线程设置为有效的工作线程，并且将共享资源设置为锁定状态。如果被请求的共享资源被占用，那么就需要一套线程阻塞等待以及被唤醒时锁分配的机制，这个机制 AQS 是基于 CLH 锁实现的。

3.1 state 同步变量

state 是一个 volatile 修饰的 int 类型的变量，是 AQS 的核心变量。所有通过 AQS 实现功能的类都是通过修改 state 的状态来操作线程的同步状态。state 可以通过 protected 类型的getState()、setState()和compareAndSetState() 进行操作，这几个方法都是 final 修饰的，在子类中无法被重写。

3.2 CLH 同步队列

上面提到的 CLH 队列是一个单向链表，而 AQS 使用的是 CLH 的变种——虚拟的双向队列（虚拟的意思是说不存在队列实例，每个节点通过保存前一个节点的引用来形成链表关系）。AQS 使用内部类 Node 类来表示 CLH 队列。

如上面代码所示，AQS 还有两个特殊的 Node 结点：head 和 tail ，分别指向 CLH 同步队列的头 Node 和尾 Node。head 节点是虚节点（哨兵节点），不保存除 waitStatus 的其他信息。整体结构如下：

设置尾节点的过程

当线程获取同步状态失败时，会加入到同步队列的尾部。在加入尾节点时，通过 CAS 机制，调用 compareAndSetTail() 保证线程安全。

设置首节点的过程

设置首节点是没有线程安全问题的。因为释放同步状态时，只会唤醒后继节点，后继节点获取到同步状态时，就会将自己设置为首节点，并断开与原首节点的引用。

3.3 ConditionObject 同步队列

只有同步队列还不够，当某个线程执行 wait() 方法，如果本来就已经获取到同步锁，这时候就需要让出同步锁；如果本来在同步队列里面，这时候就要退出同步队列。在让出同步锁或者退出同步队列之后，这个线程节点需要找一个地方存起来，等待后续唤醒后再进入锁资源竞争。

AQS 内的数据结构 ConditionObject ，就是用来存储这些等待状态的 Node 结点。ConditionObject 复用了 Node 的数据结构，不过是一个单向链表。

看到 ConditionObject 实现了 Condition 接口。Condition 接口类似于等待条件的作用，提供了类似 Object 的监视器方法，与 Lock 配合可以实现等待/通知模式。每个 Condition 对应一个 ConditionObject 等待队列，所以一个 AQS 虽然只存在一个 CLH 同步队列，但是可能存在多个 ConditionObject 等待队列。

ConditionObject 里面还提供了 signal 和 signalAll 方法。signal 方法唤醒 firstWaiter 节点，加入同步队列的尾部；signalAll 则唤醒等待队列的所有节点，加入同步队列（慎用！）。

4、AQS实战

4.1 AQS的模板方法

上面有提到 AQS 是一个抽象类，在内部封装了绝大部分操作共享资源的逻辑。Java 开发者不需要去了解这些底层逻辑是怎么实现的，只需要实现 AQS 类，并实现 AQS 提供的几个钩子方法。这是这是模板方法设计模式很经典的一个运用。

什么是钩子方法呢？钩子方法是一种被声明在抽象类中的方法，一般使用 protected 关键字修饰，它可以是空方法（由子类实现），也可以是默认实现的方法。模板设计模式通过钩子方法控制固定步骤的实现。

AQS 需要开发者重写的几个常用的钩子方法有：

可以看出这些钩子方法还分为独占模式和共享模式两种模式。

独享模式：只能有一个线程占有锁资源。其他竞争资源的线程，在竞争失败后都会进入到等待队列等待锁释放。这种情况下如果是不可重入锁，state 的值只能为 0 或 1；如果是可重入锁，state的值可以为 0、1 或者大于 1（持有锁的线程重入 state 会累加1）。

共享模式：允许多个线程同时获取锁，并发访问共享资源。这种情况下 state 的值表示可以同时持有锁的线程数。

共享模式下可以只实现共享模式的模板方法（例如CountDownLatch），独占模式下可以只实现独占模式的模板方法（例如ReentrantLock），也支持两种都实现，两种模式都使用（例如ReentrantReadWriteLock）。

两种模式允许开发者重写的完整的模板方法列表如下：

独占模式方法	共享模式方法
tryAcquire(int arg)	tryAcquireShared(int arg)
tryAcquireNanos(int aro long nanosTimeout)	tryAcquireSharedNanos(int arg, long nanosTimeout)
acquire(int arg)	acquireShared(int arg)
acquire Queued(final Node node, int arq)	doAcquireShared(int arg)
acquirelnterruptibly(int arg)	acquireSharedlnterruptibly(int arg)
doAcquirelnterruptibly(int arg)	doAcquireSharedlnterruptibly(int arg)
doAcquireNanos(int arg, long nanosTimeout)	doAcquireSharedNanos(int arg, long nanosTimeout)
release(int arg)	releaseShared (int arg)
tryRelease(int arg)	tryReleaseShared (int arg)
/	doReleaseShared()

除了最后一个属于共享锁的 doReleaseShared() 方法没有对应外，其他的模板方法，独占锁和共享锁都是一一对应的。除了上面提到的模板方法之外，AQS 类中的其他方法都是 final ，所以无法被其他类重写。

4.2 使用AQS自定义锁

上面是 AQS 的一些底层原理，看起来可能有点云里雾里，结合实战会对整体有更清晰的理解。下面使用 AQS 自定义不可重入的独占锁和可重入的独占锁，两者步骤都是相同的。

定义一个类实现 Lock 接口，这个类代表锁类。

在该类里面定义一个静态内部类继承 AQS，并实现tryAcquire、tryRelease、isHeldExclusively方法，在实现的时候需要调用 AQS 的其他 final 方法。

在该类里面定义一个上面的内部类类型的变量，使用该变量具体实现 Lock 接口定义的方法，例如 lock 、tryLock 、unlock 等方法。

使用这个锁类对外提供加锁解锁等功能。

由此可见，我们的锁类并没有直接实现 AQS，而是在内部类里面实现了 AQS，再在lock 、unlock 等方法的实现里面调用内部类（即 AQS）的方法。

4.2.1 不可重入的独占锁

锁代码实现如下：

测试代码如下，创建一个固定 5 个线程的线程池，同时提交 5 个任务。

输出结果如下，由此可见同一时间只有一个线程获取到锁资源，在执行任务，其他线程都在等待锁资源的释放，然后竞争抢到锁资源后才能执行任务。

4.2.2 可重入的独占锁

和上面的步骤一致，Lock 接口的方法实现不需要修改，只需要修改继承 AQS 的内部类的 tryAcquire 、 tryRelease 等方法的实现即可。代码实现如下：

测试代码如下，和上面类似，为了让打印结果更加清晰，这里创建只包含 2 个线程的线程池，同时提交 2 个任务。每个线程获取三次锁资源，并释放三次锁资源。

输出结果如下，从打印结果可以看到实现了锁的可重入功能，每个线程都能获取三次锁，并释放三次锁。