前言
ReentrantLock关系类图：
ReentrabtLock实现了LOCK接口，Lock接口中定义了lock与unlock相关操作，并且还存在newCondition方法，表示生成一个条件。
1
| public class ReentrantLock implements Lock, java.io.Serializable
|
ReentrantLock总共有三个内部类，并且三个内部类是紧密相关的，下面先看三个类的关系。
说明: ReentrantLock类内部总共存在Sync、NonfairSync、FairSync三个类，NonfairSync与FairSync类继承自Sync类，Sync类继承自AbstractQueuedSynchronizer抽象类。
一、非公平锁实现原理
1.1 示例
代码示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import lombok.extern.slf4j.Slf4j;
import java.util.concurrent.locks.ReentrantLock;
import static com.lilinchao.concurrent.utils.Sleeper.sleep;
@Slf4j(topic = "c.ReentrantLockUnfairLock")
public class ReentrantLockUnfairLock {
public static void main(String[] args) {
ReentrantLock lock = new ReentrantLock();
for (int i = 0; i < 10; i++){
final int num = i;
new Thread(() -> {
lock.lock();
try {
log.debug("线程 {} 获取到锁",num);
sleep(1);
} finally {
lock.unlock();
log.debug("线程 {} 释放锁成功",num);
}
}).start();
}
}
}
|
运行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
| 20:42:23.238 [Thread-0] DEBUG c.ReentrantLockUnfairLock - 线程 0 获取到锁
20:42:24.244 [Thread-1] DEBUG c.ReentrantLockUnfairLock - 线程 1 获取到锁
20:42:24.244 [Thread-0] DEBUG c.ReentrantLockUnfairLock - 线程 0 释放锁成功
20:42:25.244 [Thread-1] DEBUG c.ReentrantLockUnfairLock - 线程 1 释放锁成功
20:42:25.244 [Thread-2] DEBUG c.ReentrantLockUnfairLock - 线程 2 获取到锁
20:42:26.245 [Thread-2] DEBUG c.ReentrantLockUnfairLock - 线程 2 释放锁成功
20:42:26.245 [Thread-4] DEBUG c.ReentrantLockUnfairLock - 线程 4 获取到锁
20:42:27.246 [Thread-4] DEBUG c.ReentrantLockUnfairLock - 线程 4 释放锁成功
20:42:27.246 [Thread-3] DEBUG c.ReentrantLockUnfairLock - 线程 3 获取到锁
20:42:28.247 [Thread-3] DEBUG c.ReentrantLockUnfairLock - 线程 3 释放锁成功
20:42:28.247 [Thread-5] DEBUG c.ReentrantLockUnfairLock - 线程 5 获取到锁
20:42:29.248 [Thread-5] DEBUG c.ReentrantLockUnfairLock - 线程 5 释放锁成功
...............
|
结果说明
- 默认构造函数创建的是非公平锁
- 从运行结果可以看出，线程4优先于线程3获取到锁
1.2 加锁原理
1. 构造函数创建锁对象
1
2
3
| public ReentrantLock() {
sync = new NonfairSync();
}
|
- 默认构造函数，创建了NonfairSync,非公平锁同步器，它是继承自AQS。
2. 第一个线程加锁时，不存在竞争
1
2
3
4
5
6
7
8
9
|
final void lock() {
if (compareAndSetState(0, 1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}
|
- cas修改state从0到1，获取锁
- 设置锁对象的线程为当前线程
3. 第二个线程申请加锁时，出现锁竞争
Thread-1 执行，CAS 尝试将 state 由 0 改为 1，结果失败（第一次），进入 acquire 逻辑
1
2
3
4
5
6
7
8
|
public final void acquire(int arg) {
if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
|
调用tryAcquire方法尝试获取锁，这里由子类NonfairSync实现。
如果tryAcquire获取锁失败，通过addWaiter方法将当前线程封装成节点，入队
acquireQueued方法会将当前线程阻塞
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
protected final boolean tryAcquire(int acquires) {
return nonfairTryAcquire(acquires);
}
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)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
|
- 正是这个方法体现了非公平锁，在nonfairTryAcquire如果发现state=0,无锁的情况，它会忽略队列中等待的线程，优先获取一次锁，相当于”插队”。
4. 第二个线程tryAcquire申请锁失败，通过执行addWaiter方法加入到队列中
- 图中黄色三角表示该 Node 的 waitStatus 状态，其中 0 为默认正常状态
- Node 的创建是懒惰的，其中第一个 Node 称为 Dummy（哑元）或哨兵，用来占位，并不关联线程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
private Node addWaiter(Node mode) {
Node node = new Node(Thread.currentThread(), mode);
Node pred = tail;
if (pred != null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) {
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
|
5. 第二个线程加入队列后，现在要做的是想办法阻塞线程，不让它执行，就看acquireQueued的了
- 图中黄色三角表示该 Node 的 waitStatus 状态，0 为默认正常状态， 但是-1状态表示它肩负唤醒下一个节点的线程。
- 灰色表示线程阻塞了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| 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())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
|
- acquireQueued 会在一个自旋中不断尝试获得锁，失败后进入 park 阻塞
- 如果当前线程是在 head 节点后,也就是第一个节点，又会直接多一次机会 tryAcquire 尝试获取锁，如果还是被占用，会返回失败
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
return true;
if (ws > 0) {
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
|
- shouldParkAfterFailedAcquire发现前驱节点等待状态是-1， 返回true,表示需要阻塞。
- shouldParkAfterFailedAcquire发现前驱节点等待状态大于0，说明是无效节点，会进行清理。
- shouldParkAfterFailedAcquire发现前驱节点等待状态等于0，将前驱 node 的 waitStatus 改为 -1，返回 false。
1
2
3
4
5
6
| private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
|
- 通过不断自旋尝试获取锁，最终前驱节点的等待状态为-1的时候，进行阻塞当前线程。
- 通过调用LockSupport.park()方法进行阻塞。
6. 多个线程尝试获取锁，竞争失败后，最终形成下面的图形
1.3 释放锁原理
1. 第一个线程通过调用unlock方法释放锁
1
2
3
| public void unlock() {
sync.release(1);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
unparkSuccessor(h);
return true;
}
return false;
}
|
- 进入 tryRelease，设置 exclusiveOwnerThread 为 null，state = 0
- 当前队列不为 null，并且 head 的 waitStatus = -1，进入 unparkSuccessor, 唤醒阻塞的线程
2. 线程一通过调用tryRelease方法释放锁，该类的实现是在子类中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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;
}
|
3. 唤醒队列中第一个线程Thread1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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);
}
|
- 从后往前找到队列中距离 head 最近的一个没取消的 Node，unpark 恢复其运行，本例中即为 Thread-1
- thread1活了，开始重新去获取锁，也就是前面acquireQueued中的流程
为什么这里查找唤醒的节点是从后往前，而不是从前往后呢？
enq 方法中，节点是尾插法，首先赋值的是尾节点的前驱节点，此时前驱节点的 next 并没有指向尾节点，从前遍历会丢失尾节点。
4. Thread1恢复执行流程
- 唤醒的Thread-1 线程会从 park 位置开始执行，如果加锁成功（没有竞争），设置了exclusiveOwnerThread为Thread-1， state=1
- head 指向刚刚 Thread-1 所在的 Node，该 Node 会清空 Thread
- 原本的 head 因为从链表断开，而可被垃圾回收
5. 另一种可能，突然来了Thread-4来竞争，体现非公平锁
如果这时有其它线程来竞争锁，例如这时有 Thread-4 来了并抢占了锁，很有可能抢占成功。
- Thread-4 被设置为 exclusiveOwnerThread，state = 1
- Thread-1 再次进入 acquireQueued 流程，获取锁失败，重新进入 park 阻塞
二、可重入原理
同一个线程, 锁重入, 会对state进行自增；释放锁的时候, state进行自减。当state自减为0的时候，此时线程才会将锁释放成功, 才会进一步去唤醒其他线程来竞争锁。
三、可打断原理
在此模式下，即使它被打断，仍会驻留在 AQS 队列中，并将打断信号存储在一个interrupt变量中。
一直要等到获得锁后方能得知自己被打断了,并且调用selfInterrupt方法打断自己。
此模式下即使线程在等待队列中等待，一旦被打断，就会立刻抛出打断异常。
四、公平锁实现原理
公平锁是如何实现的：
- 简而言之，公平与非公平的区别在于，公平锁中的tryAcquire方法被重写了
- 新来的线程即便得知了锁的state为0，也要先判断等待队列中是否还有线程等待，只有当队列没有线程等待时，才获得锁。
五、条件变量实现原理
每个条件变量其实就对应着一个等待队列，其实现类是 ConditionObject
5.1 await 流程
1. 线程0（Thread-0）一开始获取锁，exclusiveOwnerThread字段是Thread-0, 如下图中的深蓝色节点
2. Thread-0调用await方法，Thread-0封装成Node进入ConditionObject的队列，因为此时只有一个节点，所有firstWaiter和lastWaiter都指向Thread-0，会释放锁资源，NofairSync中的state会变成0，同时exclusiveOwnerThread设置为null
3. 线程1（Thread-1）被唤醒，重新获取锁，如下图的深蓝色节点所示
4. Thread-0被park阻塞，如下图灰色节点所示
5.2 signal过程
1. 假设 Thread-1 要来唤醒 Thread-0
2. 进入 ConditionObject 的 doSignal 流程，取得等待队列中第一个 Node，即 Thread-0 所在 Node
3. 执行 transferForSignal 流程，将该 Node 加入 AQS 队列尾部，将 Thread-0 的 waitStatus 改为 0，Thread-3 的 waitStatus 改为 -1
