ReentrantLock 原理

(一)、非公平锁实现原理

1、加锁解锁流程

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

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

NonfairSync 继承自 AQS

没有竞争时

加锁流程

1. 构造器构造，默认构造非公平锁
2. (无竞争，第一个线程尝试加锁时)加锁，luck()，

   final void lock() {// 首先用 cas 尝试（仅尝试一次）将 state 从 0 改为 1, 如果成功表示获得了独占锁if (compareAndSetState(0, 1))setExclusiveOwnerThread(Thread.currentThread());else// 如果尝试失败，进入 ㈠acquire(1);
   }

   首先尝试将锁的state改为1，如果修改成功，则将拥有锁的线程修改位为当前线程

3. 当第一个竞争线程出现时，竞争线程尝试加锁，无法将state由0改为1，竞争线程进入方法acquire(1);

   // ㈠ AQS 继承过来的方法, 方便阅读, 放在此处
   public final void acquire(int arg) {// ㈡ tryAcquireif (!tryAcquire(arg) &&// 当 tryAcquire 返回为 false 时, 先调用 addWaiter ㈣, 接着 acquireQueued ㈤acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {selfInterrupt();}
   }

4. 线程进入tryAcquire(arg)方法，再次尝试加锁，如果成功 !(tryAcquire(arg)) = false，退出流程，加锁成功
5. 再次加锁失败!(tryAcquire(arg)) = true，进入  acquireQueued(addWaiter(Node.EXCLUSIVE), arg)方法
6. 先执行addWaiter(Node.EXCLUSIVE)方法，该方法是构造 Node 队列，在第一个竞争线程执行该方法时，除了创造关联本线程的节点，还会创造一个哑元节点(该节点就是列表的head节点，NonfairSync中的head也指向该节点)，默认初始状态都为0，形成双向列表，返回值时关联竞争线程的那个Node节点
7. 执行acquireQueued(addWaiter(Node.EXCLUSIVE), arg)方法，

   // AQS 继承过来的方法, 方便阅读, 放在此处
   final boolean acquireQueued(final Node node, int arg) {boolean failed = true;try {boolean interrupted = false;for (; ; ) {final Node p = node.predecessor();// 上一个节点是 head, 表示轮到自己（当前线程对应的 node）了, 尝试获取if (p == head && tryAcquire(arg)) {// 获取成功, 设置自己（当前线程对应的 node）为 headsetHead(node);// 上一个节点 help GCp.next = null;failed = false;// 返回中断标记 falsereturn interrupted;}if (// 判断是否应当 park, 进入 ㈦shouldParkAfterFailedAcquire(p, node) &&// park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧parkAndCheckInterrupt()) {interrupted = true;}}} finally {if (failed)cancelAcquire(node);}
   }

8. 进入到for(;;)循环，找出当前节点的前驱节点定义为p，此时p就是哑元节点，此时                 p == head，再次尝试获取锁(如果当前节点是排在第二位的节点，就可以尝试再次加锁)，如果尝试加锁成功

9. 尝试加锁失败，执行

   if(// 判断是否应当 park, 进入 ㈦shouldParkAfterFailedAcquire(p,node)&&// park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧parkAndCheckInterrupt()){interrupted=true;
   }

10. 执行shouldParkAfterFailedAcquire(p,node)方法

    //  AQS 继承过来的方法, 方便阅读, 放在此处
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {// 获取上一个节点的状态int ws = pred.waitStatus;if (ws == Node.SIGNAL) { //Node.SIGNAL = -1// 上一个节点都在阻塞, 那么自己也阻塞好了return true;}// > 0 表示取消状态if (ws > 0) {// 上一个节点取消, 那么重构删除前面所有取消的节点, 返回到外层循环重试do {node.prev = pred = pred.prev;} while (pred.waitStatus > 0);pred.next = node;} else {// 这次还没有阻塞// 但下次如果重试不成功, 则需要阻塞，这时需要设置上一个节点状态为 Node.SIGNALcompareAndSetWaitStatus(pred, ws, Node.SIGNAL);}return false;
    }

11. 由于pred(p)的状态=0，所以进入compareAndSetWaitStatus(pred, ws, Node.SIGNAL)，该方法时将pred(p)的状态改为-1，结束方法，返回false

12. 回到之前的代码，进行下一次循环，再次执行if (p == head && tryAcquire(arg))，再次尝试加锁，如果成功，...... ,失败，进入

    if(// 判断是否应当 park, 进入 ㈦shouldParkAfterFailedAcquire(p,node)&&// park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧parkAndCheckInterrupt()){interrupted=true;
    }

    // AQS 继承过来的方法, 方便阅读, 放在此处
    final boolean acquireQueued(final Node node, int arg) {boolean failed = true;try {boolean interrupted = false;for (; ; ) {final Node p = node.predecessor();// 上一个节点是 head, 表示轮到自己（当前线程对应的 node）了, 尝试获取if (p == head && tryAcquire(arg)) {// 获取成功, 设置自己（当前线程对应的 node）为 headsetHead(node);// 上一个节点 help GCp.next = null;failed = false;// 返回中断标记 falsereturn interrupted;}if (// 判断是否应当 park, 进入 ㈦shouldParkAfterFailedAcquire(p, node) &&// park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧parkAndCheckInterrupt()) {interrupted = true;}}} finally {if (failed)cancelAcquire(node);}
    }

13. 再次进入shouldParkAfterFailedAcquire(p,node)，此时prep(p) = -1，返回true

    //  AQS 继承过来的方法, 方便阅读, 放在此处
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {// 获取上一个节点的状态int ws = pred.waitStatus;if (ws == Node.SIGNAL) { //Node.SIGNAL = -1// 上一个节点都在阻塞, 那么自己也阻塞好了return true;}// > 0 表示取消状态if (ws > 0) {// 上一个节点取消, 那么重构删除前面所有取消的节点, 返回到外层循环重试do {node.prev = pred = pred.prev;} while (pred.waitStatus > 0);pred.next = node;} else {// 这次还没有阻塞// 但下次如果重试不成功, 则需要阻塞，这时需要设置上一个节点状态为 Node.SIGNALcompareAndSetWaitStatus(pred, ws, Node.SIGNAL);}return false;
    }

14. 进入parkAndCheckInterrupt()方法，当前线程进入阻塞状态

    // 阻塞当前线程
    private final boolean parkAndCheckInterrupt() {LockSupport.park(this);return Thread.interrupted();
    }

    

15. 多个线程竞争失败后，

16. 此时，Thread-0执行完成，释放锁，调用ReentrantLock中的

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

17. 进入sync.release(1)方法，

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

    在tryRelease(arg)方法中，设置 exclusiveOwnerThread 为 null，state = 0，返回true(返回false 的情况下面再说)

18. 执行到

    AbstractQueuedSynchronizer.Node h = head;
    if (h != null && h.waitStatus != 0)unparkSuccessor(h);

19. 此时h = head 不等于null，且h的状态!=0 (等于-1)，进入unparkSuccessor(h)方法，唤醒后继节点，此时node (h) 的状态=-1，h的后继节(s)点 != null，执行                                               if (s != null)   LockSupport.unpark(s.thread); 唤醒s线程，s线程开始竞争锁

    private void unparkSuccessor(AbstractQueuedSynchronizer.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.*/AbstractQueuedSynchronizer.Node s = node.next;if (s == null || s.waitStatus > 0) {s = null;for (AbstractQueuedSynchronizer.Node t = tail; t != null && t != node; t = t.prev)if (t.waitStatus <= 0)s = t;}if (s != null)LockSupport.unpark(s.thread);
    }

20. s(Thread-1)线程回到

    // 阻塞当前线程
    private final boolean parkAndCheckInterrupt() {LockSupport.park(this);return Thread.interrupted();
    }

    继续执行

21. 返回到

    // AQS 继承过来的方法, 方便阅读, 放在此处
    final boolean acquireQueued(final Node node, int arg) {boolean failed = true;try {boolean interrupted = false;for (; ; ) {final Node p = node.predecessor();// 上一个节点是 head, 表示轮到自己（当前线程对应的 node）了, 尝试获取if (p == head && tryAcquire(arg)) {// 获取成功, 设置自己（当前线程对应的 node）为 headsetHead(node);// 上一个节点 help GCp.next = null;failed = false;// 返回中断标记 falsereturn interrupted;}if (// 判断是否应当 park, 进入 ㈦shouldParkAfterFailedAcquire(p, node) &&// park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧parkAndCheckInterrupt()) {interrupted = true;}}} finally {if (failed)cancelAcquire(node);}
    }

    继续进行for循环，此时if (p == head && tryAcquire(arg)) ，在次尝试加锁，此时如果加锁成功，执行以下代码

    setHead(node);
    // 上一个节点 help GC
    p.next = null;
    failed = false;
    // 返回中断标记 false
    return interrupted;

    将关联s线程(刚才关联Thread-1线程的节点)的节点设置为头节点(删除之前的头节点，将此节点关联的线程改为null)

22. 如果刚才thread-1线程唤醒后，新出现了一个线程与之竞争，且thread-1线程竞争失败，在次进入parkAndCheckInterrupt()，进入阻塞状态

2、可重入原理

ReentrantLock的非公平获取锁的源码

protected final boolean tryAcquire(int acquires) {return nonfairTryAcquire(acquires);
}

static final class NonfairSync extends Sync {// ...// Sync 继承过来的方法, 方便阅读, 放在此处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) // overflowthrow new Error("Maximum lock count exceeded");setState(nextc);return true;}return false;}// Sync 继承过来的方法, 方便阅读, 放在此处protected final boolean tryRelease(int releases) {// 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;}
}

1. 当一个线程第一次获得锁时，进入代码

   if (c == 0) {if (compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current);return true;}
   }

   把锁的state设置为1，把拥有锁的线程设置为当前线程，返回true

2. 当一个线程多次获得锁时(锁重入)，进入代码

   else if (current == getExclusiveOwnerThread()) {// state++int nextc = c + acquires;if (nextc < 0) // overflowthrow new Error("Maximum lock count exceeded");setState(nextc);return true;
   }
   

   让state++，返回true

3. 当锁重入后释放锁时，进入

       protected final boolean tryRelease(int releases) {// 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;}

   让state--，如果state != 0 返回false，如果=0，设置当前拥有锁的线程为null，返回true

3、可打断原理

(1)、不可打断(默认)

在此模式下，即使它被打断，仍会驻留在 AQS 队列中，一直要等到获得锁后方能得知自己被打断了

// 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;failed = false;// 还是需要获得锁后, 才能返回打断状态return interrupted;}if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt()) {// 如果是因为 interrupt 被唤醒, 返回打断状态为 trueinterrupted = true;}}} finally {if (failed)cancelAcquire(node);}}public final void acquire(int arg) {if (!tryAcquire(arg) &&acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {// 如果打断状态为 trueselfInterrupt();}}static void selfInterrupt() {// 重新产生一次中断Thread.currentThread().interrupt();}
}

1. 被打断后，进入方法，return true，但是Thread.interrupted()会重置打断标记为false

   // 阻塞当前线程
   private final boolean parkAndCheckInterrupt() {LockSupport.park(this);return Thread.interrupted();
   }

2. 回退到

   if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt()) {// 如果是因为 interrupt 被唤醒, 返回打断状态为 trueinterrupted = true;
   }

   置interrupted = true

3. 接着循环，接着进入到

   // 阻塞当前线程
   private final boolean parkAndCheckInterrupt() {LockSupport.park(this);return Thread.interrupted();
   }

   进入阻塞状态，但再次被唤醒之后器其返回值仍然时true

4. 直到该线程获得所之后，执行

   if (p == head && tryAcquire(arg)) {setHead(node);p.next = null;failed = false;// 还是需要获得锁后, 才能返回打断状态return interrupted;
   }

   返回true

5. 回退到

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

   acquireQueued(addWaiter(Node.EXCLUSIVE), arg)返回值时true，执行selfInterrupted()，打断当前进程

在不可打断模式下，只要任务在AQS队列中，就不能打断

(2)、可打断

// ㈠ 可打断的获取锁流程
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 GCfailed = false;return;}if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt()) {// 在 park 过程中如果被 interrupt 会进入此// 这时候抛出异常, 而不会再次进入 for (;;)throw new InterruptedException();}}} finally {if (failed)cancelAcquire(node);}
}

打断后直接抛出异常

(二)、公平锁实现原理

static final class FairSync extends Sync {private static final long serialVersionUID = -3000897897090466540L;final void lock() {acquire(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final void acquire(int arg) {if (!tryAcquire(arg) &&acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {selfInterrupt();}}// 与非公平锁主要区别在于 tryAcquire 方法的实现protected final boolean tryAcquire(int acquires) {final Thread current = Thread.currentThread();int c = getState();if (c == 0) {// 先检查 AQS 队列中是否有前驱节点, 没有才去竞争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;}// ㈠ AQS 继承过来的方法, 方便阅读, 放在此处public final boolean hasQueuedPredecessors() {Node t = tail;Node h = head;Node s;// h != t 时表示队列中有 Nodereturn h != t &&(// (s = h.next) == null 表示队列中没有老二(s = h.next) == null || // 或者队列中老二线程不是此线程s.thread != Thread.currentThread());}
}

在获取锁时，要限先执行方法hasQueuedPredecessors()，该方法当队列中

没有第二位(没有老二是因为这时候另一个线程在初始化这个队列，刚好head被创建出来了但是没有设置next)

或者

第二位节点不是当前节点时，返回true，取反为false，无法获取锁，返回false

(三)、条件变量实现原理

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

1、await流程

// 等待 - 直到被唤醒或打断
public final void await() throws InterruptedException {if (Thread.interrupted()) {throw new InterruptedException();}// 添加一个 Node 至等待队列, 见 ㈠Node node = addConditionWaiter();// 释放节点持有的锁int savedState = fullyRelease(node);int interruptMode = 0;// 如果该节点还没有转移至 AQS 队列, 阻塞while (!isOnSyncQueue(node)) {// park 阻塞LockSupport.park(this); // 如果被打断, 退出等待队列if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)break;}// 退出等待队列后, 还需要获得 AQS 队列的锁if (acquireQueued(node, savedState) && interruptMode != THROW_IE)interruptMode = REINTERRUPT;// 所有已取消的 Node 从队列链表删除, 见 ㈡if (node.nextWaiter != null)unlinkCancelledWaiters();// 应用打断模式, 见 ㈤if (interruptMode != 0)reportInterruptAfterWait(interruptMode);
}

1. 先进入addConditionWaiter()方法，创建一个顶的node节点，将其挂到ConditionObject中，将其状态置为-2，返回这个节点

   // 添加一个 Node 至等待队列
   private Node addConditionWaiter() {Node t = lastWaiter;// 所有已取消的 Node 从队列链表删除, 见 ㈡if (t != null && t.waitStatus != Node.CONDITION) {unlinkCancelledWaiters();t = lastWaiter;}// 创建一个关联当前线程的新 Node, 添加至队列尾部Node node = new Node(Thread.currentThread(), Node.CONDITION);if (t == null)firstWaiter = node;elset.nextWaiter = node;lastWaiter = node;return node;
   }

   
2. 执行int savedState = fullyRelease(node)，

   final int fullyRelease(AbstractQueuedSynchronizer.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 = AbstractQueuedSynchronizer.Node.CANCELLED;}
   }

   进入release(savedState)

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

   进入tryRelease(arg)中，将state置为0，将拥有锁的线程设置为null

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

   返回

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

   唤醒head的后继节点

3. 返回到await，进入while循环，阻塞当前线程

   // 等待 - 直到被唤醒或打断
   public final void await() throws InterruptedException {if (Thread.interrupted()) {throw new InterruptedException();}// 添加一个 Node 至等待队列, 见 ㈠Node node = addConditionWaiter();// 释放节点持有的锁int savedState = fullyRelease(node);int interruptMode = 0;// 如果该节点还没有转移至 AQS 队列, 阻塞while (!isOnSyncQueue(node)) {// park 阻塞LockSupport.park(this); // 如果被打断, 退出等待队列if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)break;}// 退出等待队列后, 还需要获得 AQS 队列的锁if (acquireQueued(node, savedState) && interruptMode != THROW_IE)interruptMode = REINTERRUPT;// 所有已取消的 Node 从队列链表删除, 见 ㈡if (node.nextWaiter != null)unlinkCancelledWaiters();// 应用打断模式, 见 ㈤if (interruptMode != 0)reportInterruptAfterWait(interruptMode);
   }

2、signal流程

让Thread-1线程唤醒Thread-0线程

public final void signal() {if (!isHeldExclusively())  //判断当前线程是否是拥有锁的线程throw new IllegalMonitorStateException();AbstractQueuedSynchronizer.Node first = firstWaiter; //获取队首的节点if (first != null)doSignal(first);
}

1. 执行doSignal(first)方法

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

   将当前的节点从ConditionObject的队列中断开执行transferForSignal(first)方法

   final boolean transferForSignal(AbstractQueuedSynchronizer.Node node) {if (!compareAndSetWaitStatus(node, AbstractQueuedSynchronizer.Node.CONDITION, 0))return false;AbstractQueuedSynchronizer.Node p = enq(node);int ws = p.waitStatus;if (ws > 0 || !compareAndSetWaitStatus(p, ws, AbstractQueuedSynchronizer.Node.SIGNAL))LockSupport.unpark(node.thread);return true;
   }

   先将当前节点的状态设置为0，进入enq(node)方法，将node挂在到阻塞队列末尾，返回node的前驱节点(Thread-3)记为p，将p的状态设置为-1，然后返回true