2. ReentrantLock 原理1

ReentrantLock类架构图：

可以看出，ReentrantLock首先实现了Lock接口，其内部采用Sync类实现。Sync类继承自AQS类，同时有两个实现类：NonfairSync、FairSync，分别表示非公平锁、公平锁；

一、非公平锁实现原理

非公平锁：当多个线程竞争不到锁时会进入阻塞队列中排队以等待锁，如果锁空闲，且有新线程来竞争锁。那么新线程不会进入阻塞队列中排队，而是直接去竞争锁（插队行为）
公平锁：不能插队，老实在阻塞队列中等待

1. 加锁成功流程

先从构造器开始看，默认为非公平锁实现

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

其中sync是ReentrantLock类的成员变量，Sync类继承自AQS类

public class ReentrantLock implements Lock, java.io.Serializable {
    private static final long serialVersionUID = 7373984872572414699L;
    /** Synchronizer providing all implementation mechanics */
    private final Sync sync;
//...
}

ReentrantLock类，NonfairSync类中lock()方法实现：

        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

此lock方法是ReentrantLock类中的静态内部类NonfairSync中的方法，当调用ReentrantLock类中的抽象lock方法时，会返回该NonfairSync类中的lock()方法；

加锁成功示意图：

2. 加锁失败流程

下图为加锁失败示例图：

当NonfairSync锁已经被Thread-0占有，并且Thread-0一直不释放锁，那么当Thread-1尝试获取锁时，会执行一系列操作后才决定是否进入阻塞队列：
线程Thread-1执行lock方法尝试获得锁，由于锁已经被Thread-0占有，所以会进入acquire逻辑：

        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

acquire逻辑：

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

是AQS自带的acquire方法，可以看到acquire方法会优先再次tryAcquire一次来获取锁，因为占有锁的线程有可能这时会将锁释放掉。如果还获取不到锁则会进入addWaiter逻辑，构造Node队列：

• 图中黄色三角表示该Node的 waitStatus状态，其中0为默认正常状态
• Node的创建是懒惰的

• 其中第一个Node称为Dummy（哑元）或哨兵，用来占位，并不关联线程

  

其中Node是一个双向链表，头节点为哨兵，并不关联线程，其余节点关联线程。在执行完addWaiter方法后，进入acquireQueued逻辑：

1、acquireQueued会在一个死循环中不断尝试获得锁，失败后进入park阻塞
2、如果当前线程关联的node节点紧邻着head（排第二位），那么再次tryAquire尝试获取锁，当然如果这时state仍为1，失败
3、失败后会进入 shouldParkAfterFailedAcquire逻辑，将前驱node，即head的waitStatus改为-1（节点的waitStatus初始值均==0），方法这次返回false，waitStatus状态设置为-1表示，该节点有职责去唤醒其后继节点，即当前线程有职责去唤醒后继线程，因为线程是调用park陷入阻塞，所以需要其它线程调用unpark方法唤醒。
4、shouldParkAfterFailedAcquire执行完毕回到acquireQueued，再次tryAcquire尝试获取锁，当然如果这时state仍为1，失败
5、当再次进入 shouldParkAfterFailedAcquire时，这时因为其前驱node的waitStatus已经是-1，这次返回true
6、进入parkAndCheckInterrupt，Thread-1 park（灰色表示）

AQS类中的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);
        }
    }

shouldParkAfterFailedAcquire方法会再给当前线程一次获取锁的机会，如果当前线程关联的node节点紧邻着head（排第二位），shouldParkAfterFailedAcquire方法会返回false值并将前驱的waitStatus值设置为-1，由于这种情况下方法返回false值，会再次进入for循环从头执行tryAcquire方法尝试获取锁。如果这次仍获取失败则会进入shouldParkAfterFailedAcquire方法中，发现线程node节点的前驱节点的waitStatus状态已经为-1，则这时候才会真正进入parkAndCheckInterrupt流程，开始阻塞线程。

另外注意，if(p==head && tryAcquire(arg))的设置，表明如果线程对应的节点的前驱并不是头节点，那么该线程会直接进入shouldParkAfterFailedAcquire流程，可能是进入队列的位置靠后，被判定为没有资格再次尝试获取锁，而是直接进入阻塞流程。

shouldParkAfterFailedAcquire源码：

    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL)
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park.
             */
            return true;
        if (ws > 0) {
            /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            /*
             * waitStatus must be 0 or PROPAGATE.  Indicate that we
             * need a signal, but don't park yet.  Caller will need to
             * retry to make sure it cannot acquire before parking.
             */
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }

parkAndCheckInterrupt方法源码：

    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

调用park方法将该线程阻塞住，并且返回当前线程的打断标记

ReentrantLock加锁流程图：

3. 解锁竞争成功流程

当有多个线程竞争锁失败后，会变成如下示意图：

解锁时，Thread-0释放锁，进入tryRelease流程，如果成功：

• 设置exclusiveOwnerThread为null
• state = 0

ReentrantLock类的unlock方法源码：

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

调用同步器对象的release方法，release释放锁方法源码：

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

调用release会首先调用tryRelease方法去尝试释放锁，tryRelease方法源码：

        protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }

tryRelease方法由AQS的实现类完成，这里即由Sync类来重写tryRelease方法（实际是NotFairSync与FairSync类重写方法）
tryRelease方法可以简单理解为：锁拥有者置为null，state值置为0，表示锁释放。

当tryRelease执行完毕后，锁释放完成，继续在release方法中向下执行：

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

接下来的操作实际上是在唤醒节点，如果头节点不空/当前队列不为空，并且头节点的waitStatus!=0，表示头节点需要唤醒之后的节点所绑定的线程，进入unparkSuccessor流程，找到队列中离head最近的一个Node（没取消的），unpark恢复其运行，本例中即为Thread-1.

unparkSuccessor方法源码：

   private void unparkSuccessor(Node node) {
        /*
         * If status is negative (i.e., possibly needing signal) try
         * to clear in anticipation of signalling.  It is OK if this
         * fails or if status is changed by waiting thread.
         */
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);
        /*
         * Thread to unpark is held in successor, which is normally
         * just the next node.  But if cancelled or apparently null,
         * traverse backwards from tail to find the actual
         * non-cancelled successor.
         */
        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);
    }

大概内容为：调用LockSupport.unpark()方法唤醒阻塞线程，使其能够竞争锁。

唤醒Thread-1后，回到Thread-1的acquireQueued流程

Thread-1线程在acquireQueued方法的parkAndCheckInterrupt（）方法中调用park方法阻塞。当线程被唤醒时，会从parkAndCheckInterrupt位置恢复执行，再执行for循环，此时当前节点是其头节点的后继节点，所以会进入tryAcquire流程并成功获取到锁，state=1并且exclusiveOwnerThread设置为本线程。
接着会将本节点设置为头节点（不关联线程），原来的头节点置空。

                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }

解锁成功并唤醒后继节点的示意图：

4. 解锁竞争失败流程

如果锁已经空闲，Node队列中的第一个线程Thread-1被唤醒，在acquireQueued方法中再次循环并执行tryAcquire方法。但此时其它线程插队（非公平）率先获取了锁，线程只能继续进入shouldParkAfterFailedAcquire流程中，再次被阻塞住。

二、可重入原理

可重入定义：某线程获得锁后，可以再次获得该锁，即自己不会被自己阻塞住。
实现原理：重入几次state值则自增几次

以NonfairSync类中的nonfairTryAcquire、tryRelease方法讲解：

        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                // state++
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
        protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }

nonfairTryAcquire，acquires默认传入1。进入方法后，首先查看state值。如果state=0代表锁空闲，那么CAS尝试获取锁，获取成功返回true，方法结束。如果state=1表示锁已被占用，这时通过判断 current == getExclusiveOwnerThread()，来验证占用锁的线程是不是当前线程，如果是则state++，自增的次数代表重入次数。

释放时，传入tryRelease方法，releases值默认为1。进入方法，首先获取（state-1），表示重入次数，c==0才释放成功，否则每次调用tryRelase只是令state值减一，并没有真正释放锁。

三、可打断原理

LockSupport.park()方法：当前线程调用park方法会被挂起，可以被interrupt方法打断，打断后线程可以正常执行，相当于是正常运行的线程被interrupt，只是将打断标记置为TRUE。当前线程如果打断标记为假，则park方法生效，如果打断标记为真再调用park方法，则线程会一直执行无法停下。注意挂起状态可认为是暂时被淘汰出内存的状态，和阻塞状态要区分开。
注意：与sleep、join、wait方法不同，park方法调用后线程尽管依旧进入【WAITING】状态，但被打断时不会抛异常而终止线程。而是会继续执行，只是将打断标记置为True。

1. 不可打断模式

这里的不可打断是指，当线程由于获取不到锁而阻塞住时，此阻塞状态不会被打断，会一直阻塞下去。
在此模式下，即使线程被打断，仍会驻留在AQS队列中，等获得锁后方能继续运行（是继续运行！只是打断标记被设置为true）

//Sync 继承自 AQS
    static final class NonfairSync extends Sync {
        // ...
        private final boolean parkAndCheckInterrupt() {
        // 如果打断标记已经是true，则park会失效
        LockSupport.park(this);
        // interrupted会清除打断标记
        return Thread.interrupted();
    }
        //Sync 继承自 AQS
    static final class NonfairSync extends Sync {
        // ...
        private final boolean parkAndCheckInterrupt() {
        // 如果打断标记已经是true，则park会失效
        LockSupport.park(this);
        // interrupted会清除打断标记
        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; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }
    }

详细流程：线程执行到parkAndCheckInterrupt方法时，调用LockSupport.park会进入阻塞状态，如果此时有外部线程打断当前线程。由于park本身的特性，打断后会继续向下执行（并不会抛出打断异常），return Thread.interrupt()，返回是否被打断，如果被打断则返回True。需要注意的是，调用此方法会清空线程的打断标记，为了下次park时能park成功，如果打断标记为真，park无法停下。
回到acquireQueued方法中，interrupted=true，表示’当前阻塞线程确实被打断过’，但并不会做其它操作。这时还是会执行for循环，并尝试去获取锁。如果锁还是获取不到，那么线程依旧会进入shouldParkAfterFailedAcquire等流程…..并可能继续被阻塞住，那么本次打断无效（不可打断模式）。若tryAcquire过程中获取到锁，这时才会将 interrupted=true 返回给上层方法，即acquire方法。

acquire方法中，获取到锁后从acquireQueued方法中退出，并且方法返回真，开始执行if块中内容：selfInterrupt()，重新产生一次中断。当然此次中断没什么意义，因为线程处于运行状态中的中断，实际只是将打断标记设为真。

 public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            // 如果打断状态为true
            selfInterrupt();
    }
static void selfInterrupt() {
        // 重新产生一次中断
        Thread.currentThread().interrupt();
}

这里有一个小细节，如果某一阻塞线程在Node队列中是第一个节点（不考虑头节点），那么在被打断后执行for循环，该线程会获得一次执行tryAcquire方法的机会，如果此时恰好锁被释放掉，那么本次打断有可能使得该线程直接获得锁的。而如果该阻塞线程在Node队列中不是第一个节点，那么该线程完全被无效打断，会直接驻留进AQS队列中。

2. 可打断模式

与不可打断模式类似，只是在unpark线程后，线程从parkAndCheckInterrupt方法执行完毕退出，直接抛出打断异常：throw new InterruptedException()，这样即使线程调用lock()方法被阻塞住，也可以直接抛出打断异常并退出线程。

    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) &&
                    parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

四、公平锁原理

ReentrantLock锁中，公平锁与非公平锁的差别，体现在tryAcquire这一步。观看源码可知：AQS中的acquire方法，首先执行tryAcquire方法，而tryAcquire方法需要被子类重写，对于公平锁实现来说，tryAcquire的实现需要考虑AQS队列；对于非公平锁实现（默认）来说，在这一步直接CAS获取锁。而不管是公平锁实现还是非公平锁实现，如果tryAcquire失败，均要执行addwaiter-acquireQueued等流程，内容基本类似，竞争失败的线程要进入AQS队列中等待。所以tryAcquire后，并不能体现公平/非公平

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

1、非公平锁的实现，reentrantLock默认是非公平锁实现，NonfairSync类中的nonfairTryAcquire方法继承自Sync类。实现方式为：对于一个线程，如果state=0，即锁空闲，直接CAS获取锁，不去检查AQS队列中的阻塞线程，属于”插队行为”。

        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                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;
        }

2、公平锁的实现，当tryAcquire时，会考虑AQS队列中阻塞线程的情况。如果有阻塞线程则直接tryAcquire失败，开始执行addwaiter等流程；如果AQS队列中确实已经没有阻塞线程，这时此线程才会执行cas操作来获取锁。

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

五、条件变量原理

每个条件变量对应着一个等待队列，其实现类是ConditionObject

Await 流程

开始Thread-0持有锁，调用await，进入ConditionObject的 addConditionWaiter流程：创建新的Node状态为-2（Node.CONDITION），关联Thread-0，加入等待队列尾部.。注意await()是ConditionObject类的方法。

await方法源码：

        public final void await() throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int 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);
        }

addConditionWaiter方法创建新的node节点，并将node节点插入到ConditionObject的等待队列中：

调用await方法后，Thread-0释放锁，开始执行释放锁流程，fullRelease方法。因为可能出现锁重入情况，那么在Thread-0拥有锁时，state值可能不止等于1，所以需要fullRealse将重入锁完全释放掉。

fullRelease方法源码：

    final int fullyRelease(Node node) {
        boolean failed = true;
        try {
            int savedState = getState();
            if (release(savedState)) {
                failed = false;
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            if (failed)
                node.waitStatus = Node.CANCELLED;
        }
    }

可以看出方法中，首先获取savedState值，接着执行release方法，开始唤醒流程（与前文总结过的锁释放流程一致）

fullRelease后，处于ConditionObject队列中的Node节点，要调用park方法阻塞住，等待条件满足后由signal（）执行unpark方法唤醒。

Signal 流程

当前场景为，Thread-0执行await方法进入条件变量队列中等待，且节点状态waitStatue=-2. Thread-1占有锁，并由Thread-1执行signal方法唤醒Thread-0.

signal方法源码：

        public final void signal() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignal(first);
        }

调用signal方法的前提条件是，调用signal方法的线程要先获得锁。所以isHeldExclusively()方法用来判断线程是否为锁拥有者，不是拥有者却调用signal方法会抛出IllegalMonitorStateException异常。接着获取ConditionObject中等待队列的第一个节点（线程）尝试进行唤醒，所以这里可以看出signal方法并不是真正的“随即唤醒”。如果队列中头节点==null，表示await队列中无待唤醒节点，方法结束。

doSignal方法源码：

        private void doSignal(Node first) {
            do {
                if ( (firstWaiter = first.nextWaiter) == null)
                    lastWaiter = null;
                first.nextWaiter = null;
            } while (!transferForSignal(first) &&
                     (first = firstWaiter) != null);
        }

首先对队列作链表处理操作，如果待唤醒节点(first节点)的下一节点为空，说明此节点是await队列中唯一待唤醒节点，做队列置空操作。
设置完队列节点信息后，执行transferForSignal方法尝试唤醒节点，如果唤醒节点成功则do-while循环终止，否则继续下次循环，只要await队列中仍有待唤醒节点。这里唤醒节点失败的情况有很多，如节点在await等待队列中等够时间自动唤醒；或者被其它线程调用interrrupt方法打断；

transferForSignal方法源码：

    final boolean transferForSignal(Node node) {
        /*
         * If cannot change waitStatus, the node has been cancelled.
         */
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
        /*
         * Splice onto queue and try to set waitStatus of predecessor to
         * indicate that thread is (probably) waiting. If cancelled or
         * attempt to set waitStatus fails, wake up to resync (in which
         * case the waitStatus can be transiently and harmlessly wrong).
         */
        Node p = enq(node);
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }

首先cas操作尝试从Node.CONDITION（-2）改成0，如果节点当前状态已经不再处于await状态，则waitstatus！=Node.CONDITION，Node.CONDITION状态表明节点处于await队列中。
如果成功改为0，表示节点被成功唤醒，下一步需要争夺锁，于是执行enq流程，进入AQS队列中，并将node节点放入队列尾部。成功放入尾部后，获取其前驱节点，将其waitStatus改为-1，表明其有义务唤醒后继节点。最后，调用LockSupport.unpark()方法，将该线程阻塞住，等待锁释放。