序
在上一篇关于Java对象的文章总结之后，我在文末有提到过有机会再去复习总结一下关于AQS的知识，现在刚好机会来了，想着趁着周末再去看看AQS源码，理解和记录一下分析过程，以便之后回顾。
在Java的java.util.concurrent包下有一个名叫AbstractQueuedSynchronizer的抽象类，它其实就是AQS的实现，AQS我们一般叫它抽象队列同步器，它是除了Java自带的sychronized之外的另外一种锁同步机制，是Java并发包的基础工具类，是实现ReentrantLock、Condition、CountDownLatch、Semaphore以及FutureTask等类的基础类。
本文以及可能后续的几篇文章都会从源码入手，分析其执行流程，了解其中实现原理，最后再通过自问自答的方式对整篇文章进行总结，所以如果你觉得自己已经深入了解了AQS源码以及原理，也可以直接跳过正文直接到总结部分看一看这些问题。
本篇文章将会从分析ReentrantLock的公平锁源码入手，分析AQS的整个工作流程。
回顾
在我们日常开发中，或多或少使用过ReentrantLock这个类，经常使用的方式可能是类似下面的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class Test {
private static Lock lock = new ReentrantLock(true);
public static void main(String[] args) {
}
void test() {
//同时只允许一个线程进来（获取到锁）
lock.lock();
try {
//这里同时只会有一个线程进来，其他线程都会在lock.lock()方法上阻塞
//dosomthing()
} finally {
//一个线程执行完成之后会释放锁
lock.unlock();
}
}
}
|
我们使用lock.lock()进行加锁，而使用lock.unlock()进行解锁，保证代码执行的线程安全，简单进入ReentrantLock类的lock()方法中，可以看到在该方法的内部是委托了Sync类的lock()方法来管理锁，而进一步查看发现Sync类是继承了AbstractQueuedSynchronizer类来管理锁的。
1
2
3
|
abstract static class Sync extends AbstractQueuedSynchronizer {
}
|
抽象类Sync是有两个实现类，分别为FairSync和NonfairSync，从名称上来看，这两个类其实对应的就是公平锁和非公平锁的具体实现，在ReentrantLock的构造方法中可以设置采用公平锁还是非公平锁。
1
2
3
|
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
|
由于本文主要分析公平锁的源码，所以我们可以直接看FairSync类的实现。
前情提要
在看FairSync类之前，我们需要先知道两个类中的属性，一个是AbstractQueuedSynchronizer（下文简称AQS）类中的属性，另外一个是Node类中的属性。
AQS结构
我们先来看看AQS中有哪些属性，如果能够知道这些属性的含义，那我们就能够对AQS的实现有了个大概了解。
1
2
3
4
5
6
7
8
9
10
11
12
|
//头结点，可以把它当成当前持有锁的线程，链表的头结点
private transient volatile Node head;
//尾结点，每一个结点进入队列之后，都会被插入到队列尾部，这里其实就是链表尾结点
private transient volatile Node tail;
//当前锁状态，从volatile关键字就可以知道，这个字段是全局共享的，0表示没有被占有，大于0表示有线程持有锁
//这个值可以大于1，因为存在冲入锁
private volatile int state;
//当前持有独占锁的线程，注意没有volatile关键字修饰，所以一般只需要当前线程知道即可，
//那么很明显重入锁的时候可以用来判断当前线程是否已经拥有了锁
private transient Thread exclusiveOwnerThread;
|
这样看下来其实AQS的实现还是挺简单的，毕竟只有四个属性。
AQS的同步队列原理图如下所示，其中head结点是不包含在同步队列中的，所以被单独拿了出来，至于为何需要单独拿出来，后面的分析中会给出原因。
Node结构
每一个线程在进入队列的时候都会被包装成一个Node实例，通过这些实例之间的关系构成一条链表，老规矩还是看看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
25
|
static final class Node {
//节点在共享模式下
static final Node SHARED = new Node();
//节点在独占模式下
static final Node EXCLUSIVE = null;
//下面四个常量是给waitStatus用的
//当前线程取消了锁的争抢
static final int CANCELLED = 1;
//表示当前结点的后继结点需要被唤醒
static final int SIGNAL = -1;
//和Condition类有关，后面分析到Condition的时候可以再讲述，这里忽略
static final int CONDITION = -2;
//同样这里忽略
static final int PROPAGATE = -3;
//取值范围为0以及上面的四个值，0不代表任何状态，简单来说大于0表示线程取消了锁等待
volatile int waitStatus;
//当前结点的前驱结点
volatile Node prev;
//后继结点
volatile Node next;
//当前线程
volatile Thread thread;
//条件队列中会使用到，在condition或者共享锁的时候会详细介绍
Node nextWaiter;
}
|
从上面分析，我们知道Node结点中主要就是线程节点的模式、节点的状态以及节点的前驱、后继节点，需要在心里有个大概了解。
ReentrantLock源码分析
我们继续分析源码，上面说到ReentrantLock的lock()方法主要是委托Sync类的lock()方法实现，而Sync类有两个子类分别为FairSync和NonfairSync，所以这里仅仅分析公平锁对应的FairSync类。
加锁
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
static final class FairSync extends Sync {
private static final long serialVersionUID = -3000897897090466540L;
// 争锁
final void lock() {
acquire(1);
}
//来自父类AbstractQueuedSynchronizer的方法，后续遇到类似的会采取同样的方式进行
//我们看到如果tryAcquire(arg)返回true那么会直接结束，否则会继续执行后续方法，
//后续方法中会先对当前线程进行封装成一个Node结点，然后将节点放到队列尾部
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
//当前线程没有获取到锁，封装当前线程为Node节点，放到同步队列尾部
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
//设置当前线程为中断状态
selfInterrupt();
}
//尝试直接获取锁，返回值是boolean类型，表示获取锁成功与否
protected final boolean tryAcquire(int acquires) {
//当前线程
final Thread current = Thread.currentThread();
//获取同步队列中的state字段值，即锁状态值，为0表示没有线程获取锁，大于0表示有线程持有锁
int c = getState();
if (c == 0) {//state为0表示此时没有线程持有锁
//因为是公平锁，所以即使当前没有线程持有锁，也会先看看同步队列中是否有节点等待
if (!hasQueuedPredecessors() &&//如果没有节点等待
//尝试获取锁，cas方式，原子性，如果失败说明同时存在一个线程稍微早一丢丢来获取到了锁
compareAndSetState(0, acquires)) {
//如果获取锁成功，将同步队列中的持有线程设置为当前线程，
//exclusiveOwnerThread字段非线程可见
setExclusiveOwnerThread(current);
//从这里我们也能看到，第一个线程来的时候，是会返回true的，同时该线程
//既没有入队，也没有更改head或者tail的相关操作
return true;
}
}
//进入到这个分支，要么c>0要么c<0，大于0时说明是重入锁，需要看一下当前线程是否持有锁
else if (current == getExclusiveOwnerThread()) {
//冲入的话需要state+1
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
//如果是进入到这里，说明根本没有获取到锁，那么就需要回到上一层的判断条件中继续分析
//if (!tryAcquire(arg) &&
//acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
//selfInterrupt();
return false;
}
/**
* 假设tryAcquire(arg)方法返回的是false，那么代码将会执行
* acquireQueued(addWaiter(Node.EXCLUSIVE), arg))方法，所以需要先去看看
* addWaiter(Node.EXCLUSIVE), arg)方法
**/
//该方法会将当前线程包装成一个Node节点，并放到队列尾部
private Node addWaiter(Node mode) {
//将当前线程包装成一个Node节点
Node node = new Node(Thread.currentThread(), mode);
// Try the fast path of enq; backup to full enq on failure
//当前队列的尾部结点，也是当前节点的前驱结点
Node pred = tail;
if (pred != null) {
//队列尾部结点不为空，设置当前结点前驱结点为队列尾部结点
node.prev = pred;
//cas，设置当前结点为新的尾部结点，如果成功，tail==node，当前节点为新的队尾节点
if (compareAndSetTail(pred, node)) {
//设置原队尾节点后继节点指向当前节点，这步完成说明当前节点已经是新的队尾节点
pred.next = node;
return node;
}
}
//到这里说明设置当前节点的为队尾节点失败，那么要么pred==null，要么cas设置节点失败
//但是这个方法能够返回，要求就是当前节点必须为新的队尾节点，那么enq方法所做的肯定是
//自旋式的设置当前节点为新的队尾节点
enq(node);
return node;
}
//自旋设置当前节点为新的队尾节点（自旋入队）
//这里自旋的思路就是，如果一次竞争不到，那么就再竞争几次
private Node enq(final Node node) {
for (;;) {
Node t = tail;
//尾节点为空
if (t == null) { // Must initialize
//初始化head节点，队列中没有节点
if (compareAndSetHead(new Node()))
//设置好之后，这里就有了head，但是tail还是为null
//所以需要设置一下tail节点，将tail指向head
//这里仅仅设置了tail并没有返回，所以下一次循环的时候就会走到另外一个else分支
tail = head;
} else {
//下面的逻辑和addWaiter方法中是一样的
//这里的基本思路就是在无限的循环中，总有一次会成功将当前线程对应的节点设置为队尾节点
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
/**
* 分析完addWaiter方法之后，再次回到上面的代码
* if (!tryAcquire(arg) &&
* acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
* selfInterrupt();
* 接下来就来分析acquireQueued(node)方法了，该方法的入参是当前线程对应的节点和arg（这里是1）
**/
//从正常情况来看，如果acquireQueued(addWaiter(Node.EXCLUSIVE), arg))返回true，那么方法结束
//所以这里一般会返回false，而这里会发生什么呢？让我们来理一理
//一个线程没有获取到锁，然后被放到了同步队列的尾部，那还缺少什么？没错，缺少线程挂起和被唤醒
//所以这个方法中肯定存在线程挂起和被唤醒，那么我们去看看它的实现方式
final boolean acquireQueued(final Node node, int arg) {
//返回值，正常情况是返回false
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
//获取节点node的前驱结点
final Node p = node.predecessor();
//p==head说明当前结点是第一个结点，因为它的前驱结点是head
//我们在上面也说过，同步队列是不包含head的，head后面的结点才是同步队列
//因为当前结点是同步队列的第一个结点，而head结点可能是刚刚初始化的结点，
//即head结点不属于任何一个线程，所以此时可以尝试去获取一下
//tryAcquire(arg)方法上面已经分析过了，忘记了可以往上翻一下
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
//到这里说明要么当前结点不是队列的第一个结点，或者尝试获取锁失败，
//下面两个方法我们拎出来再分析
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
//只能是抛出异常，因为上面是在一个死循环中，只有抛出异常才有可能进行cancle
if (failed)
cancelAcquire(node);
}
}
//从方法名我们就能知道该方法的作用，方法名说的是获取锁失败后尝试挂起当前线程，
//返回true表示可以挂起，false表示不能
//该方法有两个参数，第一个参数是当前线程对应结点的前驱结点，第二个参数是当前线程对应结点
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
//前驱结点的状态
int ws = pred.waitStatus;
//状态值为-1表示前驱结点会通知当前结点，那么当前结点可以被挂起（return true）
if (ws == Node.SIGNAL)
/*
* This node has already set status asking a release
* to signal it, so it can safely park.
*/
return true;
//状态值大于0，说明前驱结点取消了排队，所以如果当前结点挂起那么将不会被唤醒，
//因此需要重新找一个状态为-1的前驱结点，以便后续唤醒当前结点
if (ws > 0) {
/*
* Predecessor was cancelled. Skip over predecessors and
* indicate retry.
*/
do {//这里会从当前结点的前驱结点开始依次往前找，直到找到一个结点状态值小于等于0
//注意这里是找到一个结点值<=0，所以前驱结点状态等于0也是满足条件的，但是最终
//该方法返回的是false，然后经过上层的for循环再到这个方法内部，前驱结点状态改为-1
node.prev = pred = pred.prev;
// pred = pred.prev;
// node.prev = pred;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
/*
* waitStatus must be 0 or PROPAGATE. Indicate that we
* need a signal, but don't park yet. Caller will need to
* retry to make sure it cannot acquire before parking.
*/
//到这个分支意味着当前结点的前驱结点状态不等于1和-1，那么就可能是0，-2，-3
//在前面分析中没有看到设置结点状态的地方，所以结点默认状态为0
//所以这里使用cas的话当前结点状态就会变为-1
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
//该方法返回false，那就会再走一次acquireQueued()方法的for循环，最终会从第一个
//if分支中返回true
return false;
}
/**
* if (shouldParkAfterFailedAcquire(p, node) &&
* parkAndCheckInterrupt())
* interrupted = true;
* 执行完shouldParkAfterFailedAcquire(p, node)返回true之后，就会执行
* parkAndCheckInterrupt()方法，该方法很简单，就是挂起当前线程
* 然后当线程被唤醒的时候，继续从当前位置执行，返回中断状态之后重新设置中断状态
**/
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
}
|
解锁
分析完加锁之后，接下来肯定是解锁操作了，一般来说如果线程没有获取到锁，在被添加到同步队列之后，最终都会被LockSupport.park(this)方法挂起，然后等待被唤醒，所以我们继续看看解锁操作之后是如何唤醒线程的。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
//唤醒操作我们来猜一猜它的原理，应该就是对条件队列的state字段减1，然后当前线程让出锁
//最后唤醒当前线程对应结点的后继结点，那么当前结点会不会被回收？然后是如何唤醒的？还是要继续往下看
public void unlock() {
sync.release(1);
}
public final boolean release(int arg) {
//如果解锁成功，会执行if语句内部的代码，主要的是unparkSuccessor()方法
//看方法名称应该是唤醒后继结点
//还是先看tryRelease方法
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 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) {
//锁释放成功，将当前锁拥有者改为null
free = true;
setExclusiveOwnerThread(null);
}
setState(c);
return free;
}
//唤醒头结点的后继结点，注意后继结点可能已经取消
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)//如果状态小于0，那么更改状态为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.
*/
//获取当前结点的下一符合条件的结点（状态值小于等于0的结点为符合条件的结点），以便唤醒这个结点
Node s = node.next;
//注意这里如果不满足条件，说明结点s不为空，且状态值小于等于0
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);
}
//唤醒线程之后，线程会从LockSupport.park(this)后面继续执行
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
|
到此，关于公平锁下面的ReentrantLock的加锁和解锁操作对应的源码分析已经完全结束了，剩下的如果还存在疑问可以仔细分析分析源码考虑考虑，毕竟Doug Lea的源码中针对很多的条件语句的判断进行的精简，往往一个语句可能在不同的两次循环下起到的效果不同，分析起来可能比较绕，需要多读和思考。
总结
加锁和解锁的源码分析下来，主要变化的由以下几点：
- 锁的状态值，如果要知道锁是否被其他线程占有了，只需要看
state的值是否大于0即可，线程在获取锁的时候会尝试将锁的状态值加1，如果获取锁成功，那么state值也会加1，而如果是锁冲入的话，也是在当前state值基础上加1；解锁操作其实就是一个反向的过程，一个线程释放锁的时候会将锁的状态值减1，直到staet值为0，表示没有线程占有锁。
- 线程的挂起使用
LockSupport.park()来实现，唤醒用LockSupport.unpark()来实现。
- 当存在多个线程去争抢锁的时候，没有获取到锁的线程会进入同步队列中，同步队列是一个用双向链表来实现的先进先出队列，每一个没有获取到锁的线程都会被放到队列尾部，当前一个线程释放锁的时候，会通过前一个线程对应的状态值来判断后继结点是否要被唤醒，一般来说每一个线程结点进入队列的时候都会将当前结点的前驱结点设置为
-1，但是会存在程序运行中间线程取消等待的状态，此时前驱结点状态会发生改变。
问题
分析完了源码，那我们就需要趁热打铁回顾回顾一下，看看下面的问题能否回答上来：
-
第一个线程进入到tryAcquire(arg)方法的时候进行了怎样的操作?
-
我们知道acquireQueued(Node node)方法是在当前线程获取锁失败之后才会去执行的，按道理线程获取锁已经失败了，为什么还要在该方法内部再次尝试获取一下锁?
1
2
3
4
5
6
|
if (p == head && tryAcquire(arg)) {//这里可以再次获取一下锁
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
|
-
shouldParkAfterFailedAcquire()方法return false为什么不直接挂起?
-
unparkSuccessor方法中唤醒线程时为何是从后往前找到最后一个满足条件的结点，而不是从前往后找第一个满足条件的结点?
回答
-
第一个线程进入该方法时，由于没有设置任何前驱结点和状态值，甚至此时队列中的head结点和tail结点都没有初始化，仅仅是进行了尝试获取锁的操作，如果获取成功的话，设置了一下当前锁对应的线程，然后直接返回了，可以看以下代码：
1
2
3
4
5
6
7
8
|
if (c == 0) {
if (!hasQueuedPredecessors() &&
compareAndSetState(0, acquires)) {
//第一个线程直接获取锁成功
setExclusiveOwnerThread(current);
return true;
}
}
|
-
因为在addWaiter()方法中有对head结点进行初始化，此时head结点并不属于任何结点，所以在acquireQueued()方法内部遇到当前结点是队列中的第一个结点时，因为此时head结点可能不是任何线程结点的缘故，那么锁就有可能不被任何线程持有，所以可以尝试获取一下锁。
-
线程挂起的条件是当前线程对应的结点的前驱结点状态已经被修改成-1了，也就是前驱结点肯定能够通知当前结点了，这样当前线程才能安心地去“休息”，然而很明显，在``shouldParkAfterFailedAcquire()方法内部返回false的时候，当前线程对应结点的前驱结点可能并没有被设置为-1`，就是发生在以下代码块中：
1
2
3
|
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
|
在这个代码块中，我们可以看到while循环退出条件是当前结点前驱结点状态值小于等于0，而当前驱结点状态值等于0的时候是无法唤醒当前结点的，因此返回false的时候不能直接挂起当前线程。
-
这要从addWaiter()方法说起，我们来看看addWaiter()方法：
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);
// Try the fast path of enq; backup to full enq on failure
Node pred = tail;
if (pred != null) {
//1.维护前驱结点
node.prev = pred;
//2.使用cas设置当前结点为尾结点
if (compareAndSetTail(pred, node)) {
//3.维护后继结点
pred.next = node;
return node;
}
}
enq(node);
return node;
}
|
我们能够看到，在向队列中添加结点时，如果执行到了if分支，代码中是先设置当前结点的前驱结点的，然后设置成功之后再去设置前驱结点的后继结点为当前结点，所以会存在一个时间差，即存在某一时刻，从后往前可以找到当前结点，但是从前往后找不到，因此需要从后往前遍历寻找。
注意在enq()方法内部还存在着一个类似设置结点的自旋，所以即使这里设置尾结点失败也不会有问题。
