CLH (Craig, Landin, and Hagersten)

一、基本概念

AQS 内部维护着一个 FIFO 的队列，即 CLH 队列。AQS 的同步机制就是依靠 CLH 队列实现的。CLH 队列是 FIFO 的双端双向队列，实现公平锁。头节点是一个获取同步状态成功的节点。线程通过 AQS 获取锁失败，就会将线程封装成一个 Node 节点，插入队列尾。当有线程释放锁时，后唤醒头节点的 next 节点（第二个节点）尝试占用锁。

为啥 AQS 内部要维护一个双向队列，而不是单向队列？

答：空间换时间，为了节约出队的时间，特别是高并发下会有频繁的入队出队操作。

假如你的队列是单向的如：Head -> N1 -> N2 -> Tail。出队的时候你要获取 N1 很简单，Head.next 就行了，入队你就麻烦了，你要遍历整个链表到 N2，然后 N2.next = N3; N3.next = Tail。入队的复杂度就是 O(n)，而且 Tail 也失去他的意义。相反双向链表出队和入队都是 O(1) 时间复杂度。

二、队列结构

这里是基于 CAS（保证线程的安全）来设置尾节点的。

三、Node 对象

CLH 队列由 Node 对象组成，Node 是 AQS 中的内部类。

static final class Node {
    // 节点分为两种模式： 共享式和独占式
    // 共享式
    static final Node SHARED = new Node();
    // 独占式
    static final Node EXCLUSIVE = null;

    // 等待线程超时或者被中断、需要从同步队列中取消等待（也就是放弃资源的竞争），此状态不会在改变
    static final int CANCELLED = 1;
    // 后继节点会处于等待状态，当前节点线程如果释放同步状态或者被取消则会通知后继节点线程，使后继节点线程的得以运行
    static final int SIGNAL = -1;
    // 节点在等待队列中，线程在等待在 Condition 上，其他线程对 Condition 调用 singnal() 方法后，该节点加入到同步队列中
    static final int CONDITION = -2;
    // 表示下一次共享式获取同步状态的时会被无条件的传播下去
    static final int PROPAGATE = -3;

    // 等待状态
    volatile int waitStatus;

    // 前驱节点
    volatile Node prev;

    // 后继节点
    volatile Node next;

    // 获取同步状态的线程
    volatile Thread thread;

    // 链接下一个等待状态
    Node nextWaiter;
    
    // 下面一些方法就不贴了
}

四、入列操作

如上图了解了同步队列的结构， 我们在分析其入列操作在简单不过。无非就是将 tail 指向新节点，新节点的 prev 指向队列中最后一节点（旧的 tail 节点），原队列中最后一节点的 next 节点指向新节点以此来建立联系，来张图帮助大家理解。

源码我们可以通过 AQS 中的以下两个方法来了解下：

4.1 addWaiter 方法

private Node addWaiter(Node mode) {
  // 以给定的模式来构建节点， mode 有两种模式 
  // 共享式 SHARED， 独占式 EXCLUSIVE;
  Node node = new Node(Thread.currentThread(), mode);
    // 尝试快速将该节点加入到队列的尾部
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    // 如果快速加入失败，则通过 enq 方式入列
    enq(node);
    return node;
}

先通过 addWaiter(Node node) 方法尝试快速将该节点设置尾成尾节点，设置失败走 enq(final Node node) 方法。

4.2 enq 方法

private Node enq(final Node node) {
// CAS自旋，直到加入队尾成功        
for (;;) {
    Node t = tail;
    if (t == null) { 
        // 如果队列为空，则必须先初始化 CLH 队列，新建一个空节点标识作为 Header 节点,并将 tail 指向它
        if (compareAndSetHead(new Node()))
            tail = head;
        } else {
            // 正常流程，加入队列尾部
            node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                return t;
            }
        }
    }
}

通过“自旋”也就是死循环的方式来保证该节点能顺利的加入到队列尾部，只有加入成功才会退出循环，否则会一直循序直到成功。

上述两个方法都是通过 compareAndSetHead(new Node()) 方法来设置尾节点，以保证节点的添加的原子性。

五、出列操作

同步队列（CLH）遵循 FIFO，首节点是获取同步状态的节点，首节点的线程释放同步状态后，将会唤醒它的后继节点（next），而后继节点将会在获取同步状态成功时将自己设置为首节点，这个过程非常简单。如下图

设置首节点是通过获取同步状态成功的线程来完成的（获取同步状态是通过 CAS 来完成），只能有一个线程能够获取到同步状态，因此设置头节点的操作并不需要 CAS 来保证，只需要将首节点设置为其原首节点的后继节点并断开原首节点的 next（等待 GC 回收）应用即可。

参考链接

• J.U.C|同步队列（CLH）
• JUC之AQS中的CLH队列