Java并发篇(6)深入剖析AbstractQueuedSynchronizer

写在前面:这一篇主要深入剖析AQS的组成结构及同步状态的操作,

AQS大纲体系

将会从两个方向讲解AQS:

  1. AQS的内部结构及加锁解锁的节点操作
  2. AQS的同步状态操作

AQS的内部组成结构

Node节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static final class Node {
// 该节点线程以共享模式等待锁
static final Node SHARED = new Node();
// 该节点线程以独占模式等待锁
static final Node EXCLUSIVE = null;
// 该线程已经取消等待锁
static final int CANCELLED = 1;
// 线程释放同步状态或者被取消后,将会通知后继节点线程
static final int SIGNAL = -1;
// 节点在等待队列中,节点线程等待被唤醒
static final int CONDITION = -2;
// 下一次共享式同步状态将会无条件传播下去, 在共享模式下才会使用
static final int PROPAGATE = -3;
// 节点在队列中的状态
volatile int waitStatus;
// 节点线程的前驱节点指针
volatile Node prev;
// 节点线程的后继节点指针
volatile Node next;
// 节点线程
volatile Thread thread;
// 等待队列的后继节点
Node nextWaiter;
}

Node节点组成的结构是一个双向队列

Node节点的可选状态

状态 含义
CANCELLED = 1 该线程已经取消等待锁
SIGNAL = -1 线程释放同步状态或者被取消后,将会通知后继节点线程
CONDITION = -2 节点在等待队列中,节点线程等待被唤醒
PROPAGATE = -3 下一次共享式同步状态将会无条件传播下去, 在共享模式下才会使用

Node节点的属性

属性 含义
int waitStatus 节点在队列中的状态
Node prev 节点线程的前驱节点指针
Node next 节点线程的后继节点指针
Thread thread 节点线程
Node nextWaiter 同步队列的后继等待线程节点

使用ReentrantLock演示由Node节点组成的双向队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class AQSTest {

private static ReentrantLock lock = new ReentrantLock(true);

public static void main(String[] args) {
for (int i = 0; i < 5; i++) {
Thread thread = new Thread(() -> {
lock.lock();
try {
Thread.sleep(10000);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}, "thread-" + (i + 1));
thread.start();
}
}

}

lock.unlock()处打断点,可以看到下图的结果

看到thread-2 thread-3 thread-4 thread-5依次排队,当前正在占用锁的线程是thread-1

AQS同步队列的头节点与尾节点

还有两个重要的成员变量

  1. head:同步队列的头节点
  2. tail:同步队列的尾节点

所以,AQS中由Node组成的同步队列结构如下图所示:

两个更新队列的方法:

  1. 节点成功获取锁从队列中去除头节点的方法:setHead(Node update)

  2. 线程无法获取锁时添加节点至同步队列中的方法:compareAndSetTail(Node expect, Node update)

同步状态 State

1
2
3
4
/**
* The synchronization state.
*/
private volatile int state;

同步状态被volatile修饰,具有内存可见性。

三个重要的更新同步状态的方法:

方法名 含义
protected final void setState(int newState) 设置新的同步状态,具有volatile写的内存语义
protected final int getState() 获取最新的同步状态,具有volatile读的内存语义
protected final boolean compareAndSetState(int expect, int update) 利用CAS更新同步状态,保证线程安全

可以通过设置state的初始值来自定义实现共享锁和排它锁。图片来源:从ReentrantLock实现看AQS的原理

AQS的内部组成结构小总结

  1. 最明显的是Node节点,它代表着一个等待线程节点
  2. AQS中的同步队列是一个双向队列
  3. AQS同步器中含有头节点head和尾节点tail,指向同步队列的头部和尾部
  4. State状态是实现各种锁(共享锁、排它锁、可重入锁、读写锁······)的关键成员变量
  5. 任何同步组件都可以通过AQS来自定义实现方式,例如已实现好的非常常用的有:
    • ReentrantLock:可重入锁、排它锁
    • ReadWriteLock:读写锁、读锁共享、写锁盘它
    • CountDownLatch:计数器,共享锁
    • CyclerBarrier:栅栏,共享锁

AQS同步状态的获取与释放

独占式同步状态获取与释放

获取与释放锁的执行流程图

源码解析

acquire()获取

流程3步走:

  1. 尝试获取同步状态,获取失败进入第2步
  2. 加入同步队列
  3. 不断轮询同步状态,直到前驱节点是头节点时才会请求获取同步状态
1
2
3
4
5
6
public final void acquire(int arg) {
// 尝试同步状态获取,如果获取不成功则加入独占式同步队列当中
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}

tryAcquire(arg)尝试获取同步状态,具体获取的方式由子类去决定,获取失败会调用addWaiter(Node.EXCLUSIVE)加入等待队列当中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private Node addWaiter(Node mode) {
// 创建节点线程
Node node = new Node(Thread.currentThread(), mode);
// 尝试在尾部添加节点
Node pred = tail;
if (pred != null) {
node.prev = pred;
// CAS添加尾部节点
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
// 该节点为第一个入队节点
enq(node);
return node;
}

compareAndSetTail(pred, node)保证添加尾节点的线程安全性。

调用enq(Node node)方法说明该节点是第一个入队节点,该方法初始化队列,在初始化前再次判断尾节点是否为空以防有其它等待线程节点已经初始化同步队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private Node enq(final Node node) {
// CAS操作
for (;;) {
Node t = tail;
// Double Check,以防在调用该方法时已经有节点初始化队列了
if (t == null) { // Must initialize
if (compareAndSetHead(new Node()))
tail = head;
} else {
// 把该节点添加到最后一位
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}

加入队列后调用acquireQueued(addWaiter(Node.EXCLUSIVE), arg)方法不断轮询尝试获取线程状态

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
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;
}
// 判断线程是否应该阻塞,如果是则返回true,阻塞后如果被中断则不会获取同步状态
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}

如果出现等待线程被阻塞后被中断就会导致acquireQueued()返回true,所以acquire()方法中的条件为true,线程被中断,线程被唤醒。

1
2
3
4
5
6
public final void acquire(int arg) {
// 尝试同步状态获取,如果获取不成功则加入独占式同步队列当中
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
release()释放

相比获取,释放的过程要简单不少

1
2
3
4
5
6
7
8
9
10
11
public final boolean release(int arg) {
// 尝试释放同步状态
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
// 唤醒头节点线程
unparkSuccessor(h);
return true;
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
// 唤醒后面的节点线程
Node s = node.next;
// 如果后继节点线程被取消了,waitStatus状态为1,则从后往前遍历所有节点线程,找到一个没有取消的节点线程唤醒
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);
}

还记得waitStatus的状态值吗?只有CANCELLED = 1是大于0的,即:

  1. 判断后继节点的等待状态是否大于0,如果不是则马上唤醒,如果是则进行第二步
  2. tail开始往前遍历节点线程,直至找到一个线程的waitStatus <= 0,唤醒该线程。

独占式同步状态获取与释放总结

  1. 获取的流程要清楚,分3步走:获取同步状态、进入同步队列、轮询同步状态
  2. 释放的流程要清楚:头节点释放同步状态,唤醒后继节点线程,如果后继节点线程取消同步请求则从尾指针一直往前遍历直至找到一个没有取消的节点线程

超时等待独占式同步状态获取与释放

获取与释放锁的执行流程图

源码解析

doAcquireNanos(int, long)
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
34
35
36
37
38
private boolean doAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {
if (nanosTimeout <= 0L)
return false;
// 设置超时时间
final long deadline = System.nanoTime() + nanosTimeout;
// 添加节点线程到同步队列
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 true;
}
// 计算剩余超时时间
nanosTimeout = deadline - System.nanoTime();
// 超时则返回false,获取同步状态失败
if (nanosTimeout <= 0L)
return false;
// 判断线程是否应该等待某个线程的唤醒,如果是则让该线程等待nanosTimeout纳秒
if (shouldParkAfterFailedAcquire(p, node) &&
nanosTimeout > spinForTimeoutThreshold)
LockSupport.parkNanos(this, nanosTimeout);
// 如果线程被中断则抛出异常
if (Thread.interrupted())
throw new InterruptedException();
}
} finally {
if (failed)
cancelAcquire(node);
}
}

在自旋的过程中,只有前驱节点为头节点才可以尝试去获取同步状态,如果超时了那么会返回false表示获取锁状态失败。

超时等待独占式同步状态获取与释放总结

获取的步骤:

  1. 尝试获取同步状态,获取成功则马上返回,获取失败则进行第二步
  2. 添加节点线程加入同步队列,并计算超时时间
  3. 如果前驱节点为头节点或者线程被中断则唤醒尝试获取同步状态,如果获取失败则进行第四步
  4. 重新计算超时时间,如果超时则返回false,否则重新执行第3步

共享式同步状态获取与释放

源码解析

acquireShared()共享获取
1
2
3
4
5
public final void acquireShared(int arg) {
// 如果返回小于0代表获取共享锁失败,加入到同步队列当中
if (tryAcquireShared(arg) < 0)
doAcquireShared(arg);
}

doAcquireShared(arg)把线程添加到同步队列当中

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
private void doAcquireShared(int arg) {
// 创建线程节点
final Node node = addWaiter(Node.SHARED);
boolean failed = true;
try {
boolean interrupted = false;
// 死循环监测头节点是否为前驱节点,如果是则尝试获取共享状态
for (;;) {
// 获取前驱节点
final Node p = node.predecessor();
// 如果是头节点则尝试获取同步状态
if (p == head) {
// 获取成功则返回大于等于0的数字
int r = tryAcquireShared(arg);
if (r >= 0) {
setHeadAndPropagate(node, r);
p.next = null; // help GC
if (interrupted)
selfInterrupt();
failed = false;
return;
}
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}

共享式获取同步状态和独占式的区别:

  1. 独占式同步状态的State只要不为0且不是由当前线程获取的同步状态,其它线程进入同步队列中等待
  2. 共享式同步状态State只要满足小于最大可分配线程的数目,那么请求线程都可以获取共享式锁

关于小于等于最大可分配线程的数目说明:

1
2
3
4
5
public final void acquireShared(int arg) {
// 如果返回小于0代表获取共享锁失败,加入到同步队列当中
if (tryAcquireShared(arg) < 0)
doAcquireShared(arg);
}

tryAcquireShared(arg)源码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
protected int tryAcquireShared(int acquires) {
for (;;) {
if (hasQueuedPredecessors())
return -1;
// 获取同步状态已分配的线程数目
int available = getState();
// 是否有空闲的同步状态
int remaining = available - acquires;
// 如果小于0则代表没有空闲数目,返回一个负数
// 如果CAS操作更新成功,那么返回一个非负数,代表该线程获取同步状态成功
if (remaining < 0 ||
compareAndSetState(available, remaining))
return remaining;
}
}

代码中已经做了必要的注释,不再详细说明。

releaseShared()共享释放
1
2
3
4
5
6
7
8
public final boolean releaseShared(int arg) {
// 尝试释放同步状态
if (tryReleaseShared(arg)) {
doReleaseShared();
return true;
}
return false;
}

Semaphore为例,tryReleaseShared()源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
protected final boolean tryReleaseShared(int releases) {
// 死循环一直尝试释放同步状态
for (;;) {
// 获取当前同步状态值
int current = getState();
// 计算出释放后的同步状态值
int next = current + releases;
if (next < current) // overflow
throw new Error("Maximum permit count exceeded");
// CAS更新同步状态值,直到更新成功才返回true
if (compareAndSetState(current, next))
return true;
}
}

共享式同步状态获取与释放总结

  1. 共享式与独占式的区别在于State状态值,独占式的State如果大于0则其它线程必须进入同步队列,共享式的State只有小于0,其它线程才必须进入同步队列中等待。

完结撒花

今天学习了AQS内部非常重要的三种同步状态,分析了它们的源码,当然,在面试中肯定不需要背出这些源码,但是起码要知道这三种状态的执行过程以及它们的区别,还有AQS内部的组成元素及数据结构,下面留下几个问题给大家复习,最重要的还是要理解,每种同步状态都有一个小总结,大家如果觉得知识量很大,可以多点去看总结,总结是最精髓的部分,最后,所有的同步组件都是基于AQS去实现的,理解清楚AQS的实现原理,可以对日后理解其它同步组件和自定义实现同步组件打下扎实的根基。

  1. 独占式同步状态、共享式同步状态、超市等待独占式同步状态之间的异同是什么?
  2. 三种同步状态的获取和释放流程是什么?
  3. AQS内部的结构由什么元素组成?数据结构是怎样的?

巨人的肩膀:

从ReentrantLock的实现看AQS的原理及应用

深入理解AbstractQueuedSynchronizer(AQS)

《Java并发编程的艺术》

0%