AQS原理与ReentrantLock源码分析

AQS 的全称为 AbstractQueuedSynchronizer，即抽象队列同步器，这个类在java.util.concurrent.locks包下面。

AQS 是一个用来构建锁和同步器的框架，使用 AQS 能简单且高效地构造出大量应用广泛的同步器，比如我们提到的 ReentrantLock，Semaphore，其他的诸如 ReentrantReadWriteLock，SynchronousQueue，FutureTask 等等皆是基于 AQS 的。

AQS 原理

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

CLH(Craig,Landin and Hagersten)队列是一个虚拟的双向队列（虚拟的双向队列即不存在队列实例，仅存在结点之间的关联关系）。AQS 是将每条请求共享资源的线程封装成一个 CLH 锁队列的一个结点（Node）来实现锁的分配。

这个队列是通过CLH队列实现的，从图可以看出，该队列是一个双向队列，有Node结点组成，每个Node结点维护一个prev引用和next引用，这两个引用分别指向自己结点的前驱结点和后继结点，同时AQS还维护两个指针Head和Tail，分别指向队列的头部和尾部。

AQS 使用一个 int 成员变量来表示同步状态，通过内置的 FIFO 队列来完成获取资源线程的排队工作。

AQS 使用 CAS 对该同步状态进行原子操作实现对其值的修改。

private volatile int state; //共享变量，使用volatile修饰保证线程可见性

状态信息通过 protected 类型的 getState，setState，compareAndSetState 进行操作

//返回同步状态的当前值
protected final int getState() {
    return state;
}
//设置同步状态的值
protected final void setState(int newState) {
    state = newState;
}
//原子地（CAS操作）将同步状态值设置为给定值update如果当前同步状态的值等于expect（期望值）
protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

资源共享方式

AQS 定义两种资源共享方式

• 独占模式（Exclusive）：资源是独占的，一次只能一个线程获取。如 ReentrantLock。
  • 又可分为公平锁和非公平锁：
    • 公平锁：按照线程在队列中的排队顺序，先到者先拿到锁
    • 非公平锁：当线程要获取锁时，无视队列顺序直接去抢锁，谁抢到就是谁的
• 共享模式（Share）：同时可以被多个线程获取，具体的资源个数可以通过参数指定。如 CountDownLatch、Semaphore、 CyclicBarrier、ReadWriteLock 。

相对来说，非公平锁会有更好的性能，因为它的吞吐量比较大。当然，非公平锁让获取锁的时间变得更加不确定，可能会导致在阻塞队列中的线程长期处于饥饿状态。

AQS 底层基于模板方法模式

AQS 的设计基于模板方法模式，自定义同步器时需要重写下面几个 AQS 提供的模板方法：

• isHeldExclusively()：该线程是否正在独占资源。只有用到condition才需要去实现它。

• tryAcquire(int)：独占方式。尝试获取资源，成功则返回true，失败则返回false。

• tryRelease(int)：独占方式。尝试释放资源，成功则返回true，失败则返回false。

• tryAcquireShared(int)：共享方式，尝试获取资源。负数表示失败，0表示成功，但没有剩余可用资源，正数表示成功并且有剩余资源。

• tryReleaseShared(int)：共享方式。尝试释放资源，如果释放后允许唤醒后续等待结点返回true，否则返回false。

这些方法虽然都是protected方法，但是它们并没有在AQS具体实现，而是直接抛出异常（这里不使用抽象方法的目的是：避免强迫子类中把所有的抽象方法都实现一遍，减少无用功，这样子类只需要实现自己关心的抽象方法即可，比如 Semaphore 只需要实现 tryAcquire 方法而不用实现其余不需要用到的模版方法）。AQS 类中的其他方法都是 final ，所以无法被其他类使用，只有这几个方法可以被其他类使用。

AQS 源码分析

获取资源

先来看下 AQS 提供的获取资源方法 acquire：

public final void acquire(int arg) {
    //尝试获得许可， arg为许可的个数。对于重入锁来说，每次请求1个。
    if (!tryAcquire(arg) &&
    // 如果tryAcquire 失败，则先使用addWaiter()将当前线程加入同步等待队列
    // 然后继续尝试获得锁
    acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
    selfInterrupt();
}

进入一步看一下tryAcquire()函数。该函数的作用是尝试获得一个许可（资源）。对于 AbstractQueuedSynchronizer 来说，这是一个未实现的抽象函数，默认直接抛出异常。具体实现在子类中。在重入锁，读写锁，信号量等实现中， 都有各自的实现。

如果tryAcquire()成功，则acquire()直接返回成功。如果获取资源失败，就通过 addWaiter(Node.EXCLUSIVE) 方法把这个线程加入同步等待队列中。其中传入的参数代表要插入的Node是独占式的。

private Node addWaiter(Node mode) {
    // 生成该线程对应的Node节点
    Node node = new Node(Thread.currentThread(), mode);
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        // 使用CAS尝试将节点插入等待队列尾部 
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 如果等待队列为空或者上述CAS失败，再自旋CAS插入
    enq(node);
    return node;
}

由于AQS中会存在多个线程同时争夺资源的情况，因此肯定会出现多个线程同时插入节点的操作，在这里是通过CAS自旋的方式保证了操作的线程安全性。

将 Node 节点加入等待队列尾部后，处于等待队列的节点是从头结点一个一个去获取资源，具体实现在方法 acquireQueued 中：

// 以独占的方式不间断地获取已在队列中的线程。
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        // 自旋获取锁
        for (;;) {
            // 获取前驱节点
            final Node p = node.predecessor();
            // 检测当前节点的前驱节点是否为head
            // 也就是说只有等待队列的第二个节点才能获取资源，因为第一个节点已经在运行了，请求锁已成功
            if (p == head && tryAcquire(arg)) {
                // 请求锁成功，会将自己设置为头结点
                setHead(node);
                p.next = null; // help GC
                failed = false; // 标记请求成功
                return interrupted;
            }
            // 获取锁失败，判断是否要阻塞，直到被unpark
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true; //阻塞中断
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

所以结点进入等待队列后，是调用park使它进入阻塞状态的。只有头结点的线程是处于活跃状态的。

释放资源

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            // 从队列中唤醒一个等待中的线程（遇到CANCEL节点直接跳过）
            unparkSuccessor(h);
        return true;
    }
    return false;
}

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);
    // 得到头结点的后继结点head.next
    Node s = node.next;
    // 如果这个后继结点为空或者状态大于0（节点被取消）
    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;
    }
    // 如果后继结点不为空，unpark唤醒
    if (s != null)
        LockSupport.unpark(s.thread);
}

以 ReentrantLock 为例

ReentrantLock 默认采用非公平锁，因为考虑获得更好的性能，通过 boolean 来决定是否用公平锁（传入 true 用公平锁）。

/** Synchronizer providing all implementation mechanics */
private final Sync sync;
public ReentrantLock() {
    // 默认非公平锁
    sync = new NonfairSync();
}
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

非公平锁在调用 lock() 后，首先就会调用 CAS 进行一次抢锁，如果这个时候恰巧锁没有被占用，那么直接就获取到锁返回了。

static final class NonfairSync extends Sync {
    final void lock() {
        // CAS抢锁
        if (compareAndSetState(0, 1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
            acquire(1);
    }

非公平锁在 CAS 失败后，和公平锁一样都会调用 AQS 的模板方法 acquire 方法。

static final class FairSync extends Sync {
    final void lock() {
        acquire(1);
    }

获取资源的入口是acquire(int arg)方法。arg是要获取的资源的个数，在独占模式下始终为1。我们先来看看这个方法的逻辑：

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

然后模板方法会调用使用者（自定义同步器）重写的方法 tryAcquire 尝试去获取资源， 如果发现锁这个时候被释放了（state == 0），非公平锁会直接 CAS 抢锁，但是公平锁会判断等待队列是否有线程处于等待状态，如果有则不去抢锁，按顺序排到后面。

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        // if (!hasQueuedPredecessors() && compareAndSetState(0, acquires)) { 公平锁实现
        // 公平锁会判断是否有排在自己前面且在等待的线程，而非公平锁继续直接CAS抢锁
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) { //如果获得锁的是当前线程，则可重入
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

获取资源流程图

state 初始化为 0，表示未锁定状态。A 线程 lock() 时，会调用 tryAcquire()独占该锁并将 state+1。此后，其他线程再 tryAcquire()时就会失败，直到 A 线程 unlock()到 state=0（即释放锁）为止，其它线程才有机会获取该锁。当然，释放锁之前，A 线程自己是可以重复获取此锁的（state 会累加），这就是可重入的概念。但要注意，获取多少次就要释放多少次，这样才能保证 state 是能回到零态的。

参考资料

11 AQS · 深入浅出Java多线程 (redspider.group)