11、ReentrantLock原理

从上面这张类图中我们可以看出这个ReentrantLock实现了Lock接口，其内部也维护了一个继承于AQS的Sync同步器，不过这个Sync同步器却是被声明为抽象的，其底下还有两个子类NonfairSync跟FairSync，也就是非公平锁以及公平锁（ReentrantLock同时支持非公平锁与公平锁）；
我们先来看看非公平锁的实现，毕竟非公平锁用的比较多。

非公平锁实现原理

成功加锁

• 先从构造器开始看，ReentrantLock的无参构造默认为非公平锁实现

public ReentrantLock() {
     sync = new NonfairSync();
}

我们就从非公平锁的加锁, 解锁流程开始分析;

    final void lock() {
            if (compareAndSetState(0, 1))
                //获取锁成功，将当前线程设置为持有锁线程
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

从源码的实现中可以发现，其内部调用 compareAndSetState 方法去尝试改变state状态，在没有竞争时当前线程Thread-0成为锁的持有者；如下所示：

加锁失败

• 当第一个竞争出现时，查看源码的NonfairSync的lock方法，我们发现它还是会执行lock方法，但是之前compareAndSetState方法已经将state改变为1了，所以这个竞争者并不能成功获取锁，跳转到else分支执行 acquire （1）方法。
• acquire （1）方法里面调用tryAcquire ，tryAcquire 方法逻辑就是重新尝试获取锁，若果在尝试期间锁被之前的线程释放掉，就能获取锁，但是由于有其他线程获取到了锁，这时 state 已经是1，故这次的重试结果仍然失败 ，失败后tryAcquire 方法返回false，取反后为正

接下来首先进入 acquire方法的addWaiter 逻辑，构造 Node 队列节点 (双向链表实现)

• 下图中黄色三角表示该 Node 的waitStatus状态，其中 0 为默认正常状态
• Node 的创建是懒加载的
• 第一次创建Node节点会创建两个，其中第一个 Node 称为 Dummy（哑元）或哨兵，用来占位，并不关联线程

Node对象创建好后将其放在双向队列中（双向队列中好像又有一个双向链表），然后 当前线程进入 acquire方法的 acquireQueued 方法逻辑

• acquireQueued 会在一个死循环中不断尝试获得锁，失败后进入 park 阻塞

  final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                //获取node节点的前驱节点
                final Node p = node.predecessor();
  //检查前驱节点是否是队头节点，是的话说明node节点是第二位节点，此时它有机会继续去尝试执行tryAcquire方法获取锁
                if (p == head && tryAcquire(arg)) {
                    更新头节点
                    setHead(node);
                    p.next = null; //原来的头节点断开方便GC回收
                    failed = false;
                    return interrupted;
                }
                //是否应该阻塞
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())//阻塞
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

• 如果node自己是紧邻着 队头节点head（也就是说node排队列中第二位），那么再次 执行tryAcquire 尝试获取锁，若是这时锁被释放，那么这个线程就能获取到锁，我们这里这时演示不释放锁即 state 仍为 1，所以最后的尝试失败了。

• 然后进入 shouldParkAfterFailedAcquire 方法的逻辑，从这个方法名字就可以看出来这个方法是在尝试获取锁再次失败的情况下是否应该阻塞，该方法返回真就阻塞了，将前驱 node，即 head 的 waitStatus 改为 -1，如果返回 false ，继续做下次循环尝试获取锁；

这个节点的waitStatus 为-1表示该节点有责任唤醒其后继节点；

• shouldParkAfterFailedAcquire 执行完毕回到 循环又开始，acquireQueued ，再次 tryAcquire 尝试获取锁，当然这时 state 仍为 1，失败
• 当再次进入 shouldParkAfterFailedAcquire 时，这时因为其前驱 node 的 waitStatus 已经是 -1，这次返回 true
• 进入parkAndCheckInterrupt， 将当前线程Thread-1 park阻塞住（灰色表示已经阻塞）

表示将该线程阻塞；

以上就是非公平锁加锁失败时的一个大致过程，可以看出它在加锁失败时仍然会进行好几次加锁的尝试，大概第四次失败就会进入阻塞；

• 若果此时再次有多个线程经历上述过程竞争失败的过程，就会变成这个样子

竞争成功

Thread-0 执行完代码后调用unlock方法里的release方法释放锁

   public void unlock() {
        sync.release(1);
    }

进入tryRelease(使用ctrl+alt+b查看tryRelease方法的具体ReentrantLock实现)流程，如果成功，将互斥锁的持有者exclusiveOwnerThread 置为 null，state = 0 。

下面是释放锁的大致流程：unlock调用release方法

 public final boolean release(int arg) {
     //tryRelease尝试释放锁，这里假设重入次数为1，tryRelease方法返回true
        if (tryRelease(arg)) {
            Node h = head;
            //队头节点不为空，且waitStatus在之前赋值为-1
            if (h != null && h.waitStatus != 0)
                //唤醒后继节点
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

tryRelease

    //不管是公平锁还是非公平锁都是调用同一个tryRelease方法
    protected final boolean tryRelease(int releases) {
            //在可重入的情况下，state可能大于1
            int c = getState() - releases; //每释放一次锁state就减1
            if (Thread.currentThread() != getExclusiveOwnerThread())
                //当前线程不是锁的持有者不能进入到该线程
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
 //c为0的话说明所有重入的锁都释放完成，free为true表示释放锁成功
                free = true
                    //将线程持有者置空
                setExclusiveOwnerThread(null);
            }
        //重新设置state状态
            setState(c);
            return free; //若果这个free不是true说明此时重入锁还没有完全解锁
        }

设置 exclusiveOwnerThread 为 null，state = 0 成功后唤醒后继节点

unlock方法里的release方法方法中，如果当前队列不为 null，并且 head 的 waitStatus = -1，就会进入 unparkSuccessor 流程：

    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);
    }

unparkSuccessor方法中会找到队列中离 head 最近的一个 Node（没取消的线程，这里默认都是没取消的），这里的这个Node节点s绑定的是Thread-1 。

这是没有人来跟他竞争的情况下加锁成功，然后unpark 唤醒Thread-1 恢复其运行，回到 Thread-1 阻塞的位置继续执行, 会继续执行 acquireQueued方法剩下的流程 。
在新的一轮循环中设置 （acquireQueued 方法中）exclusiveOwnerThread 为 Thread-1，state = 1 。
然后head 指向刚刚 Thread-1 所在的 Node，该 Node 清空 Thread原本的 head 因为从链表断开，而可被垃圾回收。
但是！！！如果这时候有其它线程来竞争（非公平的体现），例如这时有 Thread-4 来了

如果不巧又被 Thread-4 占了先

1. Thread-4 被设置为 exclusiveOwnerThread，state = 1
2. Thread-1 再次进入 acquireQueued 流程，获取锁失败，重新进入 park 阻塞

这是竞争失败的一种情况。

可重入原理

• 同一个线程,锁重入, 会对**state**进行自增. 释放锁的时候, state进行自减; 当state自减为0的时候. 此时线程才会将**锁**释放成功, 才会进一步去唤醒**其他线程**来竞争锁

ReentrantLock是支持锁重入的，那它是怎么保证这个可重入呢？我们还是以非公平锁为例来看它获取锁和释放锁的相关代码。

源码

static final class NonfairSync extends Sync {
    // ...
    // Sync 继承过来的方法, 方便阅读, 放在此处
    final boolean nonfairTryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState(); //获取锁的状态
        if (c == 0) {//如果state是说明还没有其他线程能够获取到锁
            //没有其他线程拿到该锁意味着当前线程就可以尝试使用CAS操作获取锁
            if (compareAndSetState(0, acquires)) {
                //将持有锁的线程设置为当前线程
                setExclusiveOwnerThread(current);
                //获取锁成功返回true
                return true;
            }
        }
        // 如果已经获得了锁, 线程还是当前线程, 表示发生了锁重入
        else if (current == getExclusiveOwnerThread()) {
            // 锁重入了就会让state自增，重入几次自增几次
            int nextc = c + acquires;
            if (nextc < 0) // overflow
                throw new Error("Maximum lock count exceeded");
            setState(nextc);//重新设置state状态
            return true;
        }
        return false;
    }
    // Sync 继承过来的方法, 方便阅读, 放在此处
    protected final boolean tryRelease(int releases) {
        //每次传递的releases都是1，这样就相当于state--
        int c = getState() - releases;
        if (Thread.currentThread() != getExclusiveOwnerThread())
            throw new IllegalMonitorStateException();
        boolean free = false;
        // 支持锁重入, 只有 state 减为 0, 才释放成功
        if (c == 0) {
            free = true;
            setExclusiveOwnerThread(null);
        }
        setState(c);
        return free;
    }
}

非公平锁中它最终调的是这个 nonfairTryAcquire 方法，传过来一个整形参数就是个 1。首先去用if判断这个state状态是不是0。如果是 0 的话，那就说明还没有别人获得锁，没有别人获得锁，自己就调用 compareAndSetState 方法从 0 试图把它改成1。

那如果成功，就返回真，然后 setExclusiveOwnerThread 方法把这个 owner 线程设为我当前线程。这是相当于第一次从 0 变验证1，这是首次获得锁。

那如果是同一个线程，下次又调用到这个 nonfairTryAcquire 了，那会怎么样呢？

这时候既然等于 0 这个条件不成立了，那else if 再做一个判断，就看当前线程是不是等于这个 owner 线程。

如果是当前线程就是 owner 线程，就是我自己，那说明这时候发生了锁重入，即让state 状态++。
刚开始自己已经把它改成 1 了，表示占用了锁，第二次又在这个基础上再加1，那就表示我重入了两次。
释放锁的时候会怎做？它会调用这个 tryRelease 方法， 就会把这个 state 去减去你的 releases参数且为1。那每次去减1，比如说你这个state现在是2，那我就 2 减1，那就得到了这个 c是1 。
但是 c是1 的情况下，应不应该把这个 state 置为 0 ，让他所有的这个这个 owner 也是设为 null呢？不应该。
注意，它应该返回一个 false 返回一个 false 。也就是它有个 free 变量等于 false
最后这个条件不成立，他就返回的是 false， 就表示只是让那个锁重入的计数减 1 了，我没有真正把这个锁释放掉。
直到你比如说这个 state 是 1 了，你再减1，等于 0 了。

这个条件成立了，那它就会把这个 free 这个变量设为 true 设为处，然后这回才是把这个 owner thread 设为。那然后返回处表示我真正true。
释放成功了以后，这个返回的true会用于去判断是不是要接下来去唤醒那些阻塞的线程。因为只有你在真正把锁释放成完了再去唤醒其他它线程才有意义，不然的话你还处于重入状态中，你这个状态还是 1 你就去唤醒其他线程，那其他线程也竞争不到锁就白唤醒了，这就是这个唤醒。
其实总结一点，其实就是加锁时重入它就让这个状状态自增。然后解锁时让这个状态自检减为零，真正解开。

可打断原理

不可打断模式

先来看一下ReentrantLock 的不可打断模式，因为它默认情况下是不可打断的。

那什么叫不可打断呢？我们来看一下它的源码分析（后面附带源码）。我们都知道线程它在没办法立刻获得锁时，它就会进入这个 acquireQueued 的方法的循环内不断地去尝试。如果尝试仍不成功，它会进入这个 park 方法进入一个等待。

但是我们也知道进入 park 阻塞的这个线程，它可以被其他的线程调用他的 interrupt 方法可以唤醒，且返回一个布尔值，表示你这个是否被打断过。不过这个 interrupt 的这个方法它除了返回这个是否被打断过这个布尔值以外，它还会清除打断标记。意思是你下次如果这个线程再 park 的时候，他还可以 park 住。

在此模式下，即使它这个线程被打断了，由于是无限循环的缘故，该线程跑不出循环，仍会驻留在AQS队列中，只有在执行tryAcquire方法获得锁后才能return跳出死循环继续往下运行（是继续运行 ! 只是打断标记被设置为true)

也就是说其他线程打断该线程时，他不能立刻的去响应这个打断，他必须等到他自己获得锁以后才能知道有其他线程打断他了，这个就叫做不可打断模式。

// Sync 继承自 AQS
static final class NonfairSync extends Sync {
    // ...
    private final boolean parkAndCheckInterrupt() {
        // 如果打断标记已经是 true, 则 park 会失效
        // 被park阻塞的线程, 可以被别的线程调用它的interrupt方法打断该park阻塞
        LockSupport.park(this);
        // interrupted 会清除打断标记; 下次park仍然可以阻塞
        return Thread.interrupted();
    }
    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;
                    failed = false;
                    // 还是需要获得锁后, 才能返回打断状态
                    return interrupted;
                }
                if (
                        shouldParkAfterFailedAcquire(p, node) &&
                                parkAndCheckInterrupt()
                ) {
                    // 如果是因为 interrupt 被唤醒, 返回打断状态为 true
                    interrupted = true;
                }
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }
    public final void acquire(int arg) {
        if (
                !tryAcquire(arg) &&
                        acquireQueued(addWaiter(Node.EXCLUSIVE), arg)
        ) {
            // 如果打断状态标记为 true
            selfInterrupt();
        }
    }
    static void selfInterrupt() {
        // 重新产生一次中断，这时候线程是如果正常运行的状态，那么不是出于sleep等状态，interrupt方法就不会报错
        Thread.currentThread().interrupt();
    }
}
}

可打断模式

与之对应的，我们再来看一下可打断模式，就是当你调用这个acquireInterruptibly这个方法的时候，就表示我去获得锁时可以被打断。

那调这个方法跟刚才有什么不一样的？我们继续来看。

 public final void acquireInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
         //若果线程没有获取到锁
        if (!tryAcquire(arg))
            //执行该方法
            doAcquireInterruptibly(arg);
    }

这个方法里面也是一个类似的死循环。

private void doAcquireInterruptibly(int arg)
        throws InterruptedException {
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    //没有获取到锁就在这里阻塞住，当某个线程调用了该线程的Interrupted方法就会将该线程从park阻塞中唤醒，继续向下运行
                    parkAndCheckInterrupt())
                    //直接抛出异常跳出死循环，这里就是跟不可打断模式的区别
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

公平锁实现原理

非公平锁

非公平锁，它最后会调这个nonfairTryAcquire 这个方法来获取锁。

获取锁的时候他如果是发现这个状态是0，也就是没人占这个锁，他就直接上去 compareAndSetState 去抢这个锁了，他根本不会去检查 KR 4 那个等待队列。

      final boolean nonfairTryAcquire(int acquires) {
           final Thread current = Thread.currentThread();
           int c = getState();
           if (c == 0) { //c==0表示还没有获取锁
//尝试去获取锁，这里就体现了非公平性：直接就尝试获取锁了，根本不管AQS队列中是否有等待的线程
               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;
       }

公平锁

与非公平锁主要区别在于tryAcquire方法的实现

    static final class FairSync extends Sync {
            //    ......  看注释也解释的很明白
        /**
         * Fair version of tryAcquire.  Don't grant access unless
         * recursive call or no waiters or is first.
         */
        protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                //检查前驱节点
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
    }

他发现 C 如果等于0，也就是还没有别人占这个锁，那他会在compareAndSetState 之前会做一件事情，这个条件如果不成立，他才会去调用 compareAndSetState 去竞争这个锁。

但如果这个条件成立了，就相当于这个队列中有其他的这个线程正在等待，则后面的 compareAndSetState 方法就不会执行了。

if中的这个方法翻译过来叫是不是有一个队列中有一个前任的或者叫前驱的节点，具体的这个实现我们大概看一下

T是尾部，H是头部，如果头不等于尾，这两个引用值不相等，就表示队列中有节点。
这个队列中其实优先级最高的是那个老二节点，老大是一个占位用的，里面没有关联线程，老二是会关联线程，所以他这个检查方法是这样，如果队列中有元素，但是没有老二或者队列中老二这个线程不是你当前线程，这说你说明你当前线程还没有获取锁的资格，因此他就会返回true，表示你这个有其他的这个前任，优先级比你高的这个线程在队列等着，所以取反之后就不会往下去执行这个竞争锁了。

条件变量实现原理

每个条件变量其实就对应着一个等待队列（跟AQS相似的队列、底层是双向链表），其实现类是 **ConditionObject** 。

学习条件变量的原理主要是看两个方法的流程

await 流程

开始时Thread-0 持有锁，是锁的持有者，然后conditionObject对象调用 await方法，

进入 ConditionObject 的 addConditionWaiter 流程 创建新的 Node 状态为 -2（Node.CONDITION），关联 Thread-0，加入等待队列尾部（第一次插入头部） 。

接下来进入 AQS 的 fullyRelease 流程，释放同步器上的所有的锁 (因为可能线程发生可重入, 锁有很多层)

之前调用release方法的时候大都是传一个1，这里的release方法直接传递获取到的state，释放掉了所有的重入锁，同时在这个release方法中还会去唤醒后继节点
unparkSuccessor(h); —> unpark唤醒 AQS 队列中的下一个节点，去竞争锁，假设没有其他竞争线程，那么 竞争成功 。

而Thread-0 进入while循环执行 LockSupport.park(this); —> Thread-0 将自己 park 阻塞住

对应源码

   public final void await() throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
       //这个方法将线程加入到条件变量对应的双向链表中（没有占位的空节点），返回一个新的Node
            Node node = addConditionWaiter();
       //释放该节点绑定的线程上所有的锁，不管重入不重入都释放掉
            long savedState = fullyRelease(node);
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) // clean up if cancelled
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
        }
private Node addConditionWaiter() {
            Node t = lastWaiter;
            // If lastWaiter is cancelled, clean out.
            if (t != null && t.waitStatus != Node.CONDITION) {
                unlinkCancelledWaiters();
                t = lastWaiter;
            }
            //创建一个新的Node节点
            Node node = new Node(Thread.currentThread(), Node.CONDITION);
            //将该节点添加到条件变量维护的双向链表中
            if (t == null)
                firstWaiter = node;
            else
                t.nextWaiter = node;
            lastWaiter = node;
            return node;
        }
    final long fullyRelease(Node node) {
        boolean failed = true;
        try {
            long savedState = getState();
//之前调用release方法的时候大都是传一个1，这里直接传递获取到的state，释放掉了所有的重入锁，同时在这个release方法中还会去唤醒后继节点
            if (release(savedState)) {
                failed = false;
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            if (failed)
                node.waitStatus = Node.CANCELLED;
        }
    }

signal 流程

• 现在的场景是Thread-0在条件变量的等待队列中等待，假设 Thread-1 是锁的持有者，它要调用signal 方法来唤醒 Thread-0线程

进入 ConditionObject 的 doSignal 流程，取得等待队列中第一个 Node，即 Thread-0 所在 Node

执行 transferForSignal 流程，将该 Node 加入 AQS 队列尾部，将 Thread-0 的 waitStatus 改为 0，Thread-3 的waitStatus 改为 -1 , 改为-1就有责任去唤醒自己的后继节点

Thread-1 释放锁，进入 unlock 流程，略

    public final void signal() {
        // 如果没有持有锁，会抛出异常 --> 这里的意思是Thread-1要持有锁, 才可以去条件变量中调用该方法去唤醒等待的线程
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
        //拿到条件变量等待队链表中的队头元素，也就是说总是调队首的
            Node first = firstWaiter;
            if (first != null)
                //进入 ConditionObject 的 doSignal 流程，取得等待队列中第一个 Node，即 Thread-0 所在 Node
                doSignal(first);
        }
//这个方法要做的事情无非就是将传进来的节点从双向队列中断开
     private void doSignal(Node first) {
            do {
                //如果有下一节点，先保存它的引用
                if ( (firstWaiter = first.nextWaiter) == null)
                    lastWaiter = null;
                //将它的下一指针设置为null， 
                first.nextWaiter = null;
                //transferForSignal方法会将条件等待队列中被唤醒的线程转移到竞争锁的AQS等待队列中，转移成功返回真，取反是false，结束循环
            } while (!transferForSignal(first) &&
                     //转移失败就尝试去唤醒下一个节点，转移失败的原因可能是该线程取消竞争锁
                     (first = firstWaiter) != null);
        }
  final boolean transferForSignal(Node node) {
     //尝试将节点的CONDITION-2状态改变为0
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
        //这个方法就是将节点添加到了AQS等待队列的尾部
        Node p = enq(node);//成功了返回其前驱节点
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }