ReentrantLock CLH队列出队入队流程

前言：学习了ReentrantLock各个方法，但是对这个锁的一个完整流程还是有点懵，所以总结一下ReentrantLock CLH队列出队入队流程

前言：虽然学习了ReentrantLock的源码，但是对方法的调用流程还是没有直观的感受，所以作图模拟一下 CLH队列出队入队流程

初始化

入队

public final void acquire(int arg) {
    //尝试获取锁
    if (!tryAcquire(arg) &&
        //获取不到,则进入等待队列，返回是否中断
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        //如果返回中断，则调用当前线程的interrupt()方法
        selfInterrupt();
}

然后t1线程调用acquire方法，但是尝试获取锁失败，然后入队，addWaiter方法这里略，具体可以看我AQS源码学习一篇，CLH队列此时如下，需要注意两点，1、图中s指Node类的 waitStatus属性，这里便于我作图，2、虽然构造方法没有指定waitStatus值，但是java类int属性在没有指定时默认值为0

然后t2线程也尝试获取资源失败并入队

自旋状态

入队后，t1线程、t2线程会执行acquireQueued方法开始自旋，如下

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

t1线程结点前驱结点为head，所以先执行tryAcquire方法尝试获取资源，而t2线程结点发现不是head结点，就会直接调用shouldParkAfterFailedAcquire方法检测是否需要从自旋状态到堵塞状态

自旋时成功获取资源

如果t1线程获取资源成功，调用setHead方法

private void setHead(Node node) {
    head = node;
    node.thread = null;
    node.prev = null;
}

原先的head结点会被GC，t1线程设置为新的head，当然结点属性被设为null（但是结点不为空）

自旋到堵塞

t1获取锁失败，会执行shouldParkAfterFailedAcquire，t2的前驱结点因为不是head，所以直接执行该方法，关于这个方法，WS>0大于0的情况，这里不考虑，因为ws>0,说明结点状态为CANCELLED即取消状态，一般出现在异常或者线程中途不再需要获取该资源等情况

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
        return true;
    if (ws > 0) {
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

不考虑WS>0大于0，那结点状态变化过程一般为：0 ——> -1 ——> 堵塞 ——>其他线程执行release释放资源，如果前驱结点是head，该节点状态设为0，然后进行新的循环

也就是说第一个线程结点一般自旋两次，两次都失败就会堵塞，第二、第三等更后面的结点一般自旋一次就会因为前驱结点已堵塞而堵塞，最后整个CLH队列均堵塞，

PS：我这里的第一个线程结点指head结点后面那个结点，head结点是哨兵结点，用于构建CLH队列，但是其本身没有实际意义

虽然不同线程执行顺序是随机的，但是我们能确定3点，

CLH队列只有第一个线程结点能尝试获取锁
结点自旋次数有限，尝试获取资源失败一定次数（0、1、2次）就会被堵塞
前驱结点为-1（SIGNAL）状态，后面的结点会直接堵塞

这个设定是合理，因为尝试获取资源失败就说明锁已经被其他线程获取了，那么自旋就没有意思，只是浪费资源，不如堵塞。

但是CLH队列第一个线程结点被堵塞了，此时锁又被释放了怎么办，毕竟只有第一个线程结点能尝试获取锁?不用担心，有堵塞（park）就有唤醒！(unpark)

堵塞到自旋

唤醒机制（unpark）。

当资源（锁）被释放时，release方法会调用unparkSuccessor方法，将第一个结点状态重新设为0并unpark，然后结点就会继续自旋获取资源，如果获取锁成功就会被出队，如果获取锁失败，那就只能再次堵塞，因为这说明锁已被其他线程获取，一般只会出现在非公平模式下，公平模式下肯定是CLH队列中第一个结点获取到锁的优先级最高

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}
private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next;
    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)
        LockSupport.unpark(s.thread);
}