(一)、非公平锁实现原理
1、加锁解锁流程
先从构造器开始看，默认为非公平锁实现
public ReentrantLock() {
sync = new NonfairSync();
}NonfairSync 继承自 AQS
没有竞争时
加锁流程
- 构造器构造，默认构造非公平锁
- (无竞争，第一个线程尝试加锁时)加锁，luck()，
final void lock() { // 首先用 cas 尝试（仅尝试一次）将 state 从 0 改为 1, 如果成功表示获得了独占锁 if (compareAndSetState(0, 1)) setExclusiveOwnerThread(Thread.currentThread()); else // 如果尝试失败，进入 ㈠ acquire(1); }首先尝试将锁的state改为1，如果修改成功，则将拥有锁的线程修改位为当前线程
- 当第一个竞争线程出现时，竞争线程尝试加锁，无法将state由0改为1，竞争线程进入方法acquire(1);
// ㈠ AQS 继承过来的方法, 方便阅读, 放在此处 public final void acquire(int arg) { // ㈡ tryAcquire if ( !tryAcquire(arg) && // 当 tryAcquire 返回为 false 时, 先调用 addWaiter ㈣, 接着 acquireQueued ㈤ acquireQueued(addWaiter(Node.EXCLUSIVE), arg) ) { selfInterrupt(); } } - 线程进入tryAcquire(arg)方法，再次尝试加锁，如果成功 !(tryAcquire(arg)) = false，退出流程，加锁成功
- 再次加锁失败!(tryAcquire(arg)) = true，进入 acquireQueued(addWaiter(Node.EXCLUSIVE), arg)方法
- 先执行addWaiter(Node.EXCLUSIVE)方法，该方法是构造 Node 队列，在第一个竞争线程执行该方法时，除了创造关联本线程的节点，还会创造一个哑元节点(该节点就是列表的head节点，NonfairSync中的head也指向该节点)，默认初始状态都为0，形成双向列表，返回值时关联竞争线程的那个Node节点
- 执行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）为 head setHead(node); // 上一个节点 help GC p.next = null; failed = false; // 返回中断标记 false return interrupted; } if ( // 判断是否应当 park, 进入 ㈦ shouldParkAfterFailedAcquire(p, node) && // park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧ parkAndCheckInterrupt() ) { interrupted = true; } } } finally { if (failed) cancelAcquire(node); } } -
进入到for(;;)循环，找出当前节点的前驱节点定义为p，此时p就是哑元节点，此时 p == head，再次尝试获取锁(如果当前节点是排在第二位的节点，就可以尝试再次加锁)，如果尝试加锁成功
-
尝试加锁失败，执行
if( // 判断是否应当 park, 进入 ㈦ shouldParkAfterFailedAcquire(p,node)&& // park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧ parkAndCheckInterrupt() ){ interrupted=true; } -
执行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.SIGNAL compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false; } -
由于pred(p)的状态=0，所以进入compareAndSetWaitStatus(pred, ws, Node.SIGNAL)，该方法时将pred(p)的状态改为-1，结束方法，返回false
-
回到之前的代码，进行下一次循环，再次执行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）为 head setHead(node); // 上一个节点 help GC p.next = null; failed = false; // 返回中断标记 false return interrupted; } if ( // 判断是否应当 park, 进入 ㈦ shouldParkAfterFailedAcquire(p, node) && // park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧ parkAndCheckInterrupt() ) { interrupted = true; } } } finally { if (failed) cancelAcquire(node); } } -
再次进入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.SIGNAL compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false; } -
进入parkAndCheckInterrupt()方法，当前线程进入阻塞状态
// 阻塞当前线程 private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); }
-
多个线程竞争失败后，
-
此时，Thread-0执行完成，释放锁，调用ReentrantLock中的
public void unlock() { sync.release(1); } -
进入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 的情况下面再说)
-
执行到
AbstractQueuedSynchronizer.Node h = head; if (h != null && h.waitStatus != 0) unparkSuccessor(h); -
此时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); } -
s(Thread-1)线程回到
// 阻塞当前线程 private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); }继续执行
-
返回到
// 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）为 head setHead(node); // 上一个节点 help GC p.next = null; failed = false; // 返回中断标记 false return 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)
-
如果刚才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) // 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);
return free;
}
}
- 当一个线程第一次获得锁时，进入代码
if (c == 0) { if (compareAndSetState(0, acquires)) { setExclusiveOwnerThread(current); return true; } }把锁的state设置为1，把拥有锁的线程设置为当前线程，返回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; }让state++，返回true
- 当锁重入后释放锁时，进入
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 被唤醒, 返回打断状态为 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() {
// 重新产生一次中断
Thread.currentThread().interrupt();
}
}- 被打断后，进入方法，return true，但是Thread.interrupted()会重置打断标记为false
// 阻塞当前线程 private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); } -
回退到
if ( shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt() ) { // 如果是因为 interrupt 被唤醒, 返回打断状态为 true interrupted = true; }置interrupted = true
-
接着循环，接着进入到
// 阻塞当前线程 private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); }进入阻塞状态，但再次被唤醒之后器其返回值仍然时true
-
直到该线程获得所之后，执行
if (p == head && tryAcquire(arg)) { setHead(node); p.next = null; failed = false; // 还是需要获得锁后, 才能返回打断状态 return interrupted; }返回true
-
回退到
public final void acquire(int arg) { if ( !tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg) ) { // 如果打断状态为 true selfInterrupt(); } } 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 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()
);
}
}在获取锁时，要限先执行方法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);
}- 先进入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; else t.nextWaiter = node; lastWaiter = node; return node; }
- 执行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的后继节点
- 返回到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);
}- 执行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
