AQS---抽象队列同步器、CLH锁队列

什么是 AQS

AbstractQueuedSynchronizer，一个抽象类，用来构建锁和同步器，定义了资源获取和释放的通用流程，ReentrantLock、Semaphore 皆是基于 AQS 实现的。

核心思想

线程请求的共享资源已被占用，那么该请求线程进入 AQS 的 CLH 队列进行等待，否则把请求线程设置为有效的工作线程，并将共享资源设置为占用状态，即该线程占用了共享资源。

AQS 的 CLH 锁队列

自旋锁即线程不断对一个原子变量 CAS 来尝试获取锁，若多线程同时竞争同一个原子变量，可能造成某个线程的 CAS 操作长时间失败，从而导致 “饥饿"问题 ，而 CLH 锁对自旋锁进行了改进，通过引入一个单向队列来让线程排队确保公平性，避免饥饿。

AQS 在 CLH 锁的基础上进一步优化，形成了其内部的 CLH 队列变体，优化点如下：

自旋+阻塞：普通的 CLH 锁使用纯自旋等待锁释放，大量自旋会占用 CPU 资源，AQS 的 CLH 锁则会短暂自旋，失败后进入阻塞状态，等待被唤醒，减少 CPU 占用。

双向队列 ：普通的 CLH 锁是单向的，节点只知道前驱节点的状态，而当某个节点释放锁时，需要通过队列唤醒后续节点。AQS 将队列改为 双向队列 ，新增了 next 指针，使得节点不仅知道前驱节点，也可以直接唤醒后继节点，从而简化了队列操作，提高了唤醒效率。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    /**
     * Head of the wait queue, lazily initialized.  Except for
     * initialization, it is modified only via method setHead.  Note:
     * If head exists, its waitStatus is guaranteed not to be
     * CANCELLED.
     */
    private transient volatile Node head;

    /**
     * Tail of the wait queue, lazily initialized.  Modified only via
     * method enq to add new wait node.
     */
    private transient volatile Node tail;

    /**
     * The synchronization state.
     */
    private volatile int state;

Node 节点各个状态含义

为什么 state 要用volatile 修饰

使用 volatile 修饰 state 不是为了利用 volatile 的内存可见性，因为 state 本来就只会被持有线程写入，只会被队列中该线程的后驱节点对应的线程读，而且后者会轮询读取。因此，可见性问题不会影响锁的正确性。

但要实现一个可以在多线程程序中正确执行的锁，还需要解决重排序问题 。
在《Java 并发编程实战》一书对于重排序问题是这么描述的：在没有同步的情况下，编译器、处理器以及运行时等都可能对操作的执行顺序进行一些意想不到的调整。在缺乏足够同步的多线程程序中，要想对内存操作的执行顺序进行判断，几乎无法得到正确的结论。对于 Java synchronized 关键字提供的内置锁(又叫监视器) ，Java 内存模型规范中有一条 Happens-Before（先行发生）规则：“一个监视器锁上的解锁应该发生在该监视器锁的后续锁定之前"也就是后面的锁在锁定之前得知道前面的锁有没有解锁，而自定义互斥锁就需要自己保证这一规则的成立，因此上述代码通过 volatile 的 Happens-Before（先行发生）规则来解决重排序问题。JMM 的 Happens-Before（先行发生）规则有一条针对 volatile 关键字的规则：“volatile 变量的写操作发生在该变量的后续读之前”。

AQS 的独占和共享

Exclusive（独占，如ReentrantLock）和Share（共享，如Semaphore/CountDownLatch）。

一般来说，自定义同步器的共享方式要么是独占，要么是共享，他们也只需实现tryAcquire-tryRelease、tryAcquireShared-tryReleaseShared中的一种即可。但 AQS 也支持自定义同步器同时实现独占和共享两种方式，如ReentrantReadWriteLock。

acquire()和 release()

acquire()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10



public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

tryAcquire() ：尝试获取锁（模板方法），AQS 不提供具体实现，由子类实现。
acquireQueued() ：对线程进行阻塞、唤醒，并调用 tryAcquire() 方法让队列中的线程尝试获取锁。
addWaiter() ：如果获取锁失败，会将当前线程封装为 Node 节点加入到 AQS 的 CLH 变体队列中等待获取锁。

release()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15



public final boolean release(int arg) {
    // 1、尝试释放锁
    if (tryRelease(arg)) {
        Node h = head;
        // 2、唤醒后继节点
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

tryRelease() 方法尝试释放锁，该方法为模板方法，由自定义同步器实现。
如果 tryRelease() 返回 true ，表明线程已经没有重入次数了，锁已经被完全释放，因此需要唤醒后继节点。

以 ReentrantLock 讲解 AQS 原理

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

假设线程 T1 先获取到锁，线程 T2 排队等待获取锁。但是在线程 T2 进入队列之前，需要初始化 AQS 的 CLH 锁队列。head 节点在初始化后状态为 0 。AQS 内部初始化后的队列如下

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

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

此时，假设线程 T1 释放锁，会唤醒后继节点 T2 。线程 T2 被唤醒后获取到锁，并且会从等待队列中退出（不是移除，因为 T2 还要当 head）。