剑指JUC原理-14.ReentrantLock原理（上）:https://developer.aliyun.com/article/1413648
进入 shouldParkAfterFailedAcquire 逻辑，将前驱 node，即 head 的 waitStatus 改为 -1，这次返回 false
改成-1后，就有责任唤醒后继的节点
shouldParkAfterFailedAcquire 执行完毕回到 acquireQueued （因为是一个死循环），再次 tryAcquire 尝试获取锁，当然这时state 仍为 1，失败
当再次进入 shouldParkAfterFailedAcquire 时，这时因为其前驱 node 的 waitStatus 已经是 -1，这次返回true
进入 parkAndCheckInterrupt， Thread-1 park（灰色表示）
private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); }
再次有多个线程经历上述过程竞争失败，变成这个样子
解锁流程
Thread-0 释放锁，进入 tryRelease 流程，如果成功
- 设置 exclusiveOwnerThread 为 null
- state = 0
public void unlock() { sync.release(1); }
public final boolean release(int arg) { if (tryRelease(arg)) { Node h = head; if (h != null && h.waitStatus != 0) // 判断 head不为空 且不等于0 // 唤醒下一个节点 unparkSuccessor(h); 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; // 设置为 null setExclusiveOwnerThread(null); } // 设置 为 0 setState(c); return free; }
当前队列不为 null，并且 head 的 waitStatus = -1，进入 unparkSuccessor 流程
找到队列中离 head 最近的一个 Node（没取消的），unpark 恢复其运行，本例中即为 Thread-1
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) // 底层调用 unpark 恢复运行了 LockSupport.unpark(s.thread); }
回到 Thread-1 的 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); } } private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); }
之前在这里阻塞着呢，一被唤醒，就又进入循环了，进入循环后，又去执行 p == head && tryAcquire(arg)
setHead(node); p.next = null; // help GC failed = false; return interrupted;
- exclusiveOwnerThread 为 Thread-1，state = 1
- head 指向刚刚 Thread-1 所在的 Node，该 Node 清空 Thread
- 原本的 head 因为从链表断开，而可被垃圾回收
如果这时候有其它线程来竞争（非公平的体现），例如这时有 Thread-4 来了
如果不巧又被 Thread-4 占了先
- Thread-4 被设置为 exclusiveOwnerThread，state = 1
- Thread-1 再次进入 acquireQueued 流程，获取锁失败，重新进入 park 阻塞
final boolean acquireQueued(final Node node, int arg) { boolean failed = true; try { boolean interrupted = false; for (;;) { final Node p = node.predecessor(); // 循环过来，没竞争过，被thread4占先了！！！ 返回false，又和之前一样的流程了 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); } }
可重入原理
static final class NonfairSync extends Sync { // ... // Sync 继承过来的方法, 方便阅读, 放在此处 final boolean nonfairTryAcquire(int acquires) { final Thread current = Thread.currentThread(); int c = getState(); // 首先先获取锁的流程 // 先查看状态是否为 0，如果还没有获得锁，从0试图将其改成1 。如果成功，将其改为真 if (c == 0) { if (compareAndSetState(0, acquires)) { setExclusiveOwnerThread(current); return true; } } // 如果已经获得了锁, 线程还是当前线程, 表示发生了锁重入 else if (current == getExclusiveOwnerThread()) { // state++ // 锁重入时，实际上是对 state做了一个累加 int nextc = c + acquires; if (nextc < 0) // overflow throw 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); // 返回true，才会去唤醒其他的线程 return free; } }
可打断原理
不可打断模式
在此模式下，即使它被打断，仍会驻留在 AQS 队列中，一直要等到获得锁后方能得知自己被打断了
// Sync 继承自 AQS static final class NonfairSync extends Sync { // ... private final boolean parkAndCheckInterrupt() { // 如果打断标记已经是 true, 则 park 会失效 LockSupport.park(this); // interrupted 会清除打断标记 // 清除了打断标记，以后线程还是能park住 // 下次再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; // 只是设置为 true，并没有做任何的处理，所以还是会再次进入循环，如果获得不了锁，还是会进入这个阻塞，再次设置上park。 // 而这个打断标记与 Thread.interrupted(); 所控制的打断标记并不是一个东西，由于之前 返回true，并清除了打断标记，所以是可以park的。 } } } finally { if (failed) cancelAcquire(node); } } public final void acquire(int arg) { if ( !tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg) ) { // 如果打断状态为 true selfInterrupt(); } } static void selfInterrupt() { // 重新产生一次中断 Thread.currentThread().interrupt(); } }
可打断模式
static final class NonfairSync extends Sync { 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()) { // 在 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 时表示队列中有 Node return h != t && ( // (s = h.next) == null 表示队列中还有没有老二 (s = h.next) == null || // 或者队列中老二线程不是此线程 s.thread != Thread.currentThread() ); } }
条件变量实现原理
每个条件变量其实就对应着一个等待队列，其实现类是 ConditionObject
await 流程
开始 Thread-0 持有锁，调用 await，进入 ConditionObject 的 addConditionWaiter 流程
创建新的 Node 状态为 -2（Node.CONDITION），关联 Thread-0，加入等待队列尾部
public final void await() throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); // 将线程加入到我们条件变量中去，并且将新的node状态设置为 -2 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); } private Node addConditionWaiter() { Node t = lastWaiter; // If lastWaiter is cancelled, clean out. if (t != null && t.waitStatus != Node.CONDITION) { unlinkCancelledWaiters(); t = lastWaiter; } Node node = new Node(Thread.currentThread(), Node.CONDITION); if (t == null) firstWaiter = node; else t.nextWaiter = node; lastWaiter = node; return node; } static final int CONDITION = -2;
接下来进入 AQS 的 fullyRelease(是有可能发生锁重入) 流程，释放同步器上的锁
final int fullyRelease(Node node) { boolean failed = true; try { int savedState = getState(); // release方法默认一次 -1 if (release(savedState)) { failed = false; return savedState; } else { throw new IllegalMonitorStateException(); } } finally { if (failed) node.waitStatus = Node.CANCELLED; } }
unpark AQS 队列中的下一个节点，竞争锁，假设没有其他竞争线程，那么 Thread-1 竞争成功
public final boolean release(int arg) { if (tryRelease(arg)) { Node h = head; if (h != null && h.waitStatus != 0) unparkSuccessor(h); return true; } return false; }
park 阻塞 Thread-0
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)) { // 此时就park住了 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); }
signal 流程
假设 Thread-1 要来唤醒 Thread-0
public final void signal() { // 首先检查当前变量是否持有独占锁 if (!isHeldExclusively()) throw new IllegalMonitorStateException(); // 也不是随机调用，总是调队首 Node first = firstWaiter; if (first != null) doSignal(first); }
进入 ConditionObject 的 doSignal 流程，取得等待队列中第一个 Node，即 Thread-0 所在 Node
private void doSignal(Node first) { do { if ( (firstWaiter = first.nextWaiter) == null) lastWaiter = null; first.nextWaiter = null; } while (!transferForSignal(first) && (first = firstWaiter) != null); // 如果转移为 真，就不会进行循环了，如果转移失败，就看看还有没有下一个节点。 }
执行 transferForSignal 流程，将该 Node 加入 AQS 队列尾部，将 Thread-0 的 waitStatus 改为 0，Thread-3 的waitStatus 改为 -1
final boolean transferForSignal(Node node) { /* * If cannot change waitStatus, the node has been cancelled. */ // 将状态改为0 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; }
Thread-1 释放锁，进入 unlock 流程，略
