并发编程——详解 AQS CLH 锁

1. 从 acquire 方法开始 —— 获取
2. 为什么 AQS 需要一个虚拟 head 节点
3. reelase 方法如何释放锁
4. 总结

前言

AQS 是 JUC 中的核心，其中封装了资源的获取和释放，在我们之前的 并发编程之 AQS 源码剖析 文章中，我们已经从 ReentranLock 那里分析了锁的获取和释放。但我有必要再次解释 AQS 的核心 CLH 锁。

这里引用一下别人对于 CLH 的解释：

CLH CLH(Craig, Landin, and Hagersten locks): 是一个自旋锁，能确保无饥饿性，提供先来先服务的公平性。

CLH锁也是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，它不断轮询前驱的状态，如果发现前驱释放了锁就结束自旋。

Java AQS 的设计对 CLH 锁进行了优化或者说变体。

我们还是从代码开始说起吧。

1. 从 acquire 方法开始 —— 获取

acquire 方法是获取锁的常用方法。代码如下：

public final void acquireQueued(int arg) {
    // 当 tryAcquire 返回 true 就说明获取到锁了，直接结束。
    // 反之，返回 false 的话，就需要执行后面的方法。
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

只要子类的 tryAcquire 方法返回 false，那么就说明获取锁事变，就需要将自己加入队列。

private Node addWaiter(Node mode) {
    // 创建一个独占类型的节点
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    Node pred = tail;
    // 如果 tail 节点不是 null，就将新节点的 pred 节点设置为 tail 节点。
    // 并且将新节点设置成 tail 节点。
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 如果 tail 节点是  null，或者 CAS 设置 tail 失败。
    // 在 enq 方法中处理
    enq(node);
    return node;
}

将自己加入了尾部，并更新了 tail 节点。

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        // 如果 tail 是 null，就创建一个虚拟节点，同时指向 head 和 tail，称为 初始化。
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {// 如果不是 null
            // 和 上个方法逻辑一样，将新节点追加到 tail 节点后面，并更新队列的 tail 为新节点。
            // 只不过这里是死循环的，失败了还可以再来 。
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

enq 方法的逻辑是什么呢？当 tail 是 null（没有初始化队列），就需要初始化队列了。CAS 设置 tail 失败，也会走这里，需要在 enq 方法中循环设置 tail。直到成功。

注意：这里会创建一个虚拟节点。

2. 为什么 AQS 需要一个虚拟 head 节点

为什么要创建一个虚拟节点呢？

事情要从 Node 类的 waitStatus 变量说起，简称 ws。每个节点都有一个 ws 变量，用于这个节点状态的一些标志。初始状态是 0。如果被取消了，节点就是 1，那么他就会被 AQS 清理。

还有一个重要的状态：SIGNAL —— -1，表示：当当前节点释放锁的时候，需要唤醒下一个节点。

所有，每个节点在休眠前，都需要将前置节点的 ws 设置成 SIGNAL。否则自己永远无法被唤醒。

而为什么需要这么一个 ws 呢？—— 防止重复操作。假设，当一个节点已经被释放了，而此时另一个线程不知道，再次释放。这时候就错误了。

所以，需要一个变量来保证这个节点的状态。而且修改这个节点，必须通过 CAS 操作保证线程安全。

So，回到我们之前的问题：为什么要创建一个虚拟节点呢？

每个节点都必须设置前置节点的 ws 状态为 SIGNAL，所以必须要一个前置节点，而这个前置节点，实际上就是当前持有锁的节点。

问题在于有个边界问题：第一个节点怎么办？他是没有前置节点的。

那就创建一个假的。

这就是为什么要创建一个虚拟节点的原因。

总结下来就是：每个节点都需要设置前置节点的 ws 状态（这个状态为是为了保证数据一致性），而第一个节点是没有前置节点的，所以需要创建一个虚拟节点。

回到我们的 acquireQueued 方法证实一下：

// 这里返回的节点是新创建的节点，arg 是请求的数量
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            // 找上一个节点
            final Node p = node.predecessor();
            // 如果上一个节点是 head ，就尝试获取锁
            // 如果 获取成功，就将当前节点设置为 head，注意 head 节点是永远不会唤醒的。
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            // 在获取锁失败后，就需要阻塞了。
            // shouldParkAfterFailedAcquire ---> 检查上一个节点的状态，如果是 SIGNAL 就阻塞，否则就改成 SIGNAL。
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

这个方法有 2 个逻辑：

1. 如何将自己挂起？
2. 被唤醒之后做什么？

先回答第二个问题： 被唤醒之后做什么？

尝试拿锁，成功之后，将自己设置为 head，断开和 next 的连接。

再看第二个问题：如何将自己挂起？

注意：挂起自己之前，需要将前置节点的 ws 状态设置成 SIGNAL，告诉他：你释放锁的时候记得唤醒我。

具体逻辑在 shouldParkAfterFailedAcquire 方法中：

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    //  如果他的上一个节点的 ws 是 SIGNAL，他就需要阻塞。
    if (ws == Node.SIGNAL)
        // 阻塞
        return true;
    // 前任被取消。 跳过前任并重试。
    if (ws > 0) {
        do {
            // 将前任的前任 赋值给 当前的前任
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        // 将前任的前任的 next 赋值为 当前节点
        pred.next = node;
    } else { 
        // 如果没有取消 || 0 || CONDITION || PROPAGATE，那么就将前任的 ws 设置成 SIGNAL.
        // 为什么必须是 SIGNAL 呢？
        // 答：希望自己的上一个节点在释放锁的时候，通知自己（让自己获取锁）
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    // 重来
    return false;
}

该方法的主要逻辑就是将前置节点的状态修改成 SIGNAL。其中如果前置节点被取消了，就跳过他。

那么肯定，在前置节点释放锁的时候，肯定会唤醒这个节点。看看释放的逻辑吧。

3. reelase 方法如何释放锁

先来一波代码:

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        // 所有的节点在将自己挂起之前，都会将前置节点设置成 SIGNAL，希望前置节点释放的时候，唤醒自己。
        // 如果前置节点是 0 ，说明前置节点已经释放过了。不能重复释放了，后面将会看到释放后会将 ws 修改成0.
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

从这个方法的判断就可以看出，head 必须不等于 0。为什么呢？当一个节点尝试挂起自己之前，都会将前置节点设置成 SIGNAL -1，就算是第一个加入队列的节点，在获取锁失败后，也会将虚拟节点设置的 ws 设置成 SIGNAL。

而这个判断也是防止多线程重复释放。

那么肯定，在释放锁之后，肯定会将 ws 状态设置成 0。防止重复操作。

代码如下：

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        // 将 head 节点的 ws 改成 0，清除信号。表示，他已经释放过了。不能重复释放。
        compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next;
    // 如果 next 是 null，或者 next 被取消了。就从 tail 开始向上找节点。
    if (s == null || s.waitStatus > 0) {
        s = null;
        // 从尾部开始，向前寻找未被取消的节点，直到这个节点是 null，或者是 head。
        // 也就是说，如果 head 的 next 是 null，那么就从尾部开始寻找，直到不是 null 为止，找到这个 head 就不管了。
        // 如果是 head 的 next 不是 null，但是被取消了，那这个节点也会被略过。
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    // 唤醒 head.next 这个节点。
    // 通常这个节点是 head 的 next。
    // 但如果 head.next 被取消了，就会从尾部开始找。
    if (s != null)
        LockSupport.unpark(s.thread);
}

如果 ws 小于 0，我们假设是 SIGNAL，就修改成 0. 证实了我们的想法。

如果他的 next 是 null，说明 next 取消了，那么就从尾部开始向上寻找（不从尾部也没办法）。当然找的过程中，也跳过了失效的节点。

最后，唤醒他。

唤醒之后的逻辑是什么样子的还记得吗？

复习一下：拿锁，设置自己为 head，断开前任 head 和自己的连接。

4. 总结

AQS 使用的 CLH 锁，需要一个虚拟 head 节点，这个节点的作用是防止重复释放锁。当第一个进入队列的节点没有前置节点的时候，就会创建一个虚拟的。

来一幅图尝试解释 AQS 吧：

1. 新增节点时

   
   image.png

2. 更新 tail

image.png

3. 唤醒节点时，之前的 head 取消了

image.png