AQS

引用：JavaGuide

1. 什么是AQS？

AQS，全称AbstractQueuedSynchronizer，是Java中的一个抽象类，是Java并发包中提供的构建锁和同步器的基本框架。像ReentrantLock，CountDownLatch，Semaphore等类都使用到AQS完成线程间同步

2. CLH锁

AQS是基于CLH锁进一步优化实现的，那什么是CLH锁呢？

CLH 锁对自旋锁进行了改进，是基于单链表的自旋锁。在多线程场景下，会将请求获取锁的线程组织成一个单向队列，每个等待的线程会通过自旋访问前一个线程节点的状态，前一个节点释放锁之后，当前节点才可以获取锁。CLH 锁的队列结构如下图所示。

CLH 锁的队列结构

3. AQS的核心思想

首先是它有一个volatile修饰的int型变量state，在ReentrantLock里它表示锁被获取的次数，在Semaphore里它表示剩余的许可数量。一般我们通过cas操作来修改这个变量，cas成功表示获取锁成功，否则失败。

同时，AQS维护了一个基于CLH锁优化实现的FIFO等待队列，以下称之为CLH变体队列，CLH变体队列与原队列的区别如下：

由自旋优化为 自旋 + 阻塞 ：自旋操作的性能很高，但大量的自旋操作比较占用 CPU 资源，因此在 CLH 变体队列中会先通过自旋尝试获取锁，如果失败再进行阻塞等待
由 单向队列 优化为 双向队列 ：在 CLH 变体队列中，会对等待的线程进行阻塞操作，当队列前边的线程释放锁之后，需要对后边的线程进行唤醒，因此增加了 next 指针，成为了双向队列

AQS 将每条请求共享资源的线程封装成一个 CLH 变体队列的一个结点（Node）来实现锁的分配。当线程获取锁失败时，就会把线程引用包装成一个结点放到队列里去。当持有锁的线程释放资源时，会调用release方法，在释放锁之后会把队列里的第一个结点唤醒，被唤醒的线程会去尝试获取锁。

CLH 变体队列结构

AQS 定义两种资源共享方式：Exclusive（独占，只有一个线程能获得锁，如ReentrantLock）和Share（共享，允许多个线程同时获得锁资源，如Semaphore/CountDownLatch）。

4. Node节点WaitStatus状态

AQS 中的 waitStatus 状态类似于 状态机 ，通过不同状态来表明 Node 节点的不同含义，并且根据不同操作，来控制状态之间的流转。

Node 节点状态	值	含义
`CANCELLED`	1	表示线程已经取消获取锁。线程在等待获取资源时被中断、等待资源超时会更新为该状态。（排队时突然不需要锁了）
`SIGNAL`	-1	表示后继节点需要当前节点唤醒。在当前线程节点释放锁之后，需要对后继节点进行唤醒。
`CONDITION`	-2	表示节点在等待 Condition。当其他线程调用了 Condition 的 `signal()` 方法后，节点会从等待队列转移到同步队列中等待获取资源。
`PROPAGATE`	-3	用于共享模式。在共享模式下，可能会出现线程在队列中无法被唤醒的情况，因此引入了 `PROPAGATE` 状态来解决这个问题。
	0	加入队列的新节点的初始状态。

4. 以ReentrantLock为例图解AQS工作流程（资源独占）

假设总共有 3 个线程尝试获取锁，线程分别为 T1 、 T2 和 T3 。

此时，假设线程 T1 先获取到锁，线程 T2 排队等待获取锁。在线程 T2 进入队列之前，需要对 AQS 内部队列进行初始化。head 节点（虚拟头节点）在初始化后状态为 0 。AQS 内部初始化后的队列如下图：

此时，线程 T2 尝试获取锁。由于线程 T1 持有锁，因此线程 T2 会进入队列中等待获取锁。同时会将前继节点（ head 节点）的状态由 0 更新为 SIGNAL ，表示需要对 head 节点的后继节点进行唤醒。此时，AQS 内部队列如下图所示：

此时，线程 T3 尝试获取锁。由于线程 T1 持有锁，因此线程 T3 会进入队列中等待获取锁。同时会将前继节点（线程 T2 节点）的状态由 0 更新为 SIGNAL ，表示线程 T2 节点需要对后继节点进行唤醒。此时，AQS 内部队列如下图所示：

此时，假设线程 T1 释放锁，会唤醒后继节点 T2 。线程 T2 被唤醒后获取到锁，并且会从等待队列中退出。

这里线程 T2 节点退出等待队列并不是直接从队列移除，而是令线程 T2 节点成为新的 head 节点，以此来退出资源获取的等待。此时 AQS 内部队列如下所示：

此时，假设线程 T2 释放锁，会唤醒后继节点 T3 。线程 T3 获取到锁之后，同样也退出等待队列，即将线程 T3 节点变为 head 节点来退出资源获取的等待。此时 AQS 内部队列如下所示：

5. 公平锁与非公平锁

上面给出的就是一个公平锁的流程：一个新的线程来到想要竞争锁，

如果此时锁不空闲，就到队列中去排队等待
如果此时有线程释放了锁，也得老老实实去队列中排队，等待前面的人用完了锁之后自己才能获得锁

而非公平锁则有一些不同，当一个新线程来到想要竞争锁，

如果此时锁不空闲，也得老老实实排队等待
如果此时有线程释放了锁，这个新线程是有机会通过CAS操作直接插队获取到这个锁的
- 如果成功获得，那就不用排队了
- 否则，还是得排队

6. 为什么AQS要用双向链表?

没有竞争到锁的线程会加入到队列中，线程阻塞等待的前提是：当前线程所在的节点的前置节点是正常状态（waitStatus = SIGNAL）。这是为了避免队列中出现异常线程，导致无法唤醒后续线程的情况出现。所以线程阻塞等待之前需要判断它的前置节点状态是否正常，如果使用单向链表，那就只能从头遍历，效率很低
处于队列中阻塞等待的线程允许被外部线程通过interrupt()方法去触发唤醒的，这时节点的状态waitStatus需要修改为CANCELLED，标记为CANCELLED的线程就不需要参与锁的竞争了，但它仍会处于队列中，为了方便移除它，可以选用双向链表
线程在加入到队列之后，会尝试通过CAS+自旋去获取锁，但我们知道，只有队列中的第一个线程能优先得到锁，后面的线程去尝试获取锁只会浪费资源，于是在线程尝试CAS+自旋获取锁之前，会判断这个线程的前置节点是不是队列的头节点，如果是，说明这个线程是队列中的第一个线程，则可以尝试CAS+自旋获取锁；否则直接阻塞等待即可。所以，这个判断前置节点是否是头节点的操作，使用双向链表效率会更高

7. AQS唤醒节点时，为什么是从队列后面往前去找的？

// AQS：这里的入参 node 为队列的头节点（虚拟头节点）
private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    // 1、将头节点的状态进行清除，为后续的唤醒做准备。
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next;
    // 2、如果后继节点异常，则需要从 tail 向前遍历，找到正常状态的节点进行唤醒。
    if (s == null || s.waitStatus > 0) {
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    if (s != null)
        // 3、唤醒后继节点
        LockSupport.unpark(s.thread);
}