AQS目录
AQS简介
FIFO队列
NODE节点
独占模式
共享模式
ConditionObject
AQS简介
AQS是Concurrent包核心之一，全称是AbstractQueuedSynchronizer。ReetrantLock，Semaphore,CountDownLatch都有一个内部类Sync继承AQS。
AQS的核心是通过一个共享变量state来同步状态，变量的状态由子类维护，state=0时则说明没有任何线程占有共享资源的锁，当state=1时则说明有一个线程正在使用该共享资源，其他线程必须加入同步队列等待。AQS做的是线程阻塞队列的维护和线程的阻塞和唤醒，其中共享变量的修改都是通过CAS(v,e,n)无锁操作完成。
AQS的主要方法是acquire()和release(),这两个方法一般会被子类封装成lock()和unlock()。
AQS通过内部类Node构建FIFO同步队列完成线程获取锁的排队工作，同时利用内部类ConditionObject构建等待队列，当condition调用await后，线程会加入等待队列，而当condition调用signal后，线程将从等待队列移入同步队列进行锁的竞争。
AQS:
transient volatile Node head;//同步队列队头（不存储实际信息，空信息节点）
transient volatile Node tail;//同步队列队尾
volatile int state;//0代表未占用FIFO队列
NODE节点
Node节点数据结构：node节点是访问同步代码的线程的封装。
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;//线程再condition等待队列等待某一条件
static final int PROPAGATE = -3;//后序线程节点会传播唤醒操作，共享模式起作用
volatile int waitStatus;//上述四种之一，代表线程状态
volatile Node prev;//同步队列前驱
volatile Node next;//同步队列后继
volatile Thread thread;//拥有该node的线程
Node nextWaiter;//等待队列的后继节点
}注意有两个队列，一个同步队列（前驱prev后继next都有），一个等待队列（只有后继nextWaiter，只有等待队列的节点的ws才可以是CONDITION,另外等待队列的节点的ws只可能是CANCELLED或CONDITION）
独占模式
独占模式获取锁：
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}尝试获取锁，如果获取成功，acquire执行完毕，当前线程获取到锁。否则加入同步队列阻塞，等待前驱释放锁再次竞争锁资源。
tryAcquire()是由子类实现，例如ReetrantLock中有公平模式获取锁和非公平模式获取锁。
下面是addWaiter方法：pred指向尾节点，如果尾节点不空，则当前节点的前驱指向尾节点。再cas判断尾节点是不是pred，如果是就把尾节点改为当前节点node，然后pred的后继指向node。以上步骤是尝试快速入队操作，如果失败了才会调用enq(node)。
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) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
}enq（node）
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)) {//如果tail==t，就把tail改为node
t.next = node;
return t;
}
}
}
}addWaiter方法只是入队的操作，没有入队后的真正逻辑操作，而这些操作是acquireQueued完成的，如下：
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;//失败标志
try {
boolean interrupted = false;//acquireQueued过程是否被中断过
for (;;) {
final Node p = node.predecessor();//p为node的前驱
if (p == head && tryAcquire(arg)) {//如果node是老二并且tryAcquire成功
setHead(node);//设置node为头
p.next = null; // help GC
failed = false;
return interrupted;
}
//需不需要挂起当前线程&&挂起该线程
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)//未知错误或异常
cancelAcquire(node);//删除该节点
}
}shouldParkAfterFailedAcquire作用是判断是否要挂起当前线程，有以下三个作用：
- 确定是否需要park;
- 跳过被取消的结点;
- 设置前继的waitStatus为SIGNAL.
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;//node前驱的状态
if (ws == Node.SIGNAL)//前驱是唤醒状态
return true;//返回true直接挂起
if (ws > 0) {//CANCELLED状态
do {//向前找到第一个不是CANCELLED状态的节点，挂在该节点的后面
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;//挂在该节点的后面
} else {//PROPAGATE或0
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);//把前驱改为SIGNAL状态
}
return false;//返回false不能挂起
}parkAndCheckInterrupt执行真正的挂起操作：
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);//挂起当前线程
return Thread.interrupted();//返回线程中断标志，并重置中断标志位为false
}该方法如果返回true，说明曾经中断过，则acquireQueued中interrupted=true.最后会在acquire中selfInterrupt将中断补上，为什么补中断，理由如下：在acquireQueued中，即使线程在阻塞状态被中断唤醒获取到cpu执行权，但是也需要在循环中重新判断，如果前面还有其他的等待线程，根据公平性原则，该线程仍然无法获取到锁资源，也就是说在成功获取锁资源真正执行起来之前，他的中断会被忽略并被清除。
acquire大致流程如下
独占模式释放锁：
public final boolean release(int arg) {
// tryReease由子类实现，通过设置state值来达到同步的效果。
if (tryRelease(arg)) {
Node h = head;
// waitStatus为0说明是初始化的空队列
if (h != null && h.waitStatus != 0)
// 唤醒后续的结点
unparkSuccessor(h);
return true;
}
return false;
}共享模式
共享模式获取锁：
public final void acquireShared(int arg) {
//如果没有许可了则入队等待
if (tryAcquireShared(arg) < 0)
doAcquireShared(arg);
} doAcquireShared和独占模式acquireQueued很像，只有其中setHeadAndPropagate不一样。
private void doAcquireShared(int arg) {
final Node node = addWaiter(Node.SHARED);//以共享的模式入队
boolean failed = true;//失败标志
try {
boolean interrupted = false;//中途是否被中断过
for (;;) {
final Node p = node.predecessor();//p是node的前驱
if (p == head) {
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);
}
}setHeadAndPropagate源码如下：
private void setHeadAndPropagate(Node node, int propagate) {
Node h = head; // Record old head for check below
setHead(node);
if (propagate > 0 || h == null || h.waitStatus < 0) {
Node s = node.next;
// 后继结是共享模式或者s == null
// 如果后继是独占模式，那么即使剩下的许可大于0也不会继续往后传递唤醒操作
// 即使后面有的结点是共享模式。
if (s == null || s.isShared())
// 唤醒后继结点
doReleaseShared();
}
}共享模式释放锁：
public final boolean releaseShared(int arg) {
if (tryReleaseShared(arg)) {
doReleaseShared();
return true;
}
return false;
}private void doReleaseShared() {
for (;;) {
Node h = head;
// 队列不为空且有后继结点
if (h != null && h != tail) {
int ws = h.waitStatus;
// 不管是共享还是独占只有结点状态为SIGNAL才尝试唤醒后继结点
if (ws == Node.SIGNAL) {
// 将waitStatus设置为0
if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
continue; // loop to recheck cases
unparkSuccessor(h);// 唤醒后继结点
// 如果状态为0则更新状态为PROPAGATE，更新失败则重试
} else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
continue; // loop on failed CAS
}
if (h == head) // loop if head changed
break;
}
}ConditionObject
ConditionObject是AQS中定义的内部类，实现了Condition接口，ConditionObject是基于Lock实现的，在其内部通过链表来维护等待队列。Contidion必须在lock的同步控制块中使用，调用Condition的singnal方法并不代表线程可以马上执行，线程的执行始终都需要根据同步状态（即线程是否占有锁）。
为什么Condition必须在lock的同步控制块中使用？即为什么在使用Condition之前要获取锁。
ConditionObject对象是通过显式锁中的lock.newCondition(）方法生成的,可以看出此时必须占有锁资源，这也是为什么Condition必须在lock的同步控制块中使用的原因。
当condition调用await后，线程会加入等待队列，而当condition调用signal后，线程将从等待队列移入同步队列进行锁的竞争。
ConditionObject中定义的变量：
private transient Node firstWaiter;//等待队列头节点
private transient Node lastWaiter;//等待队列的尾节点await方法如下：
public final void await() throws InterruptedException {
if (Thread.interrupted())
throw new InterruptedException();
Node node = addConditionWaiter();//加入等待队列
//上面提到condition必须在同步块中使用，故当前线程获取了锁，在加入等待队列后需要将此锁释放
int savedState = fullyRelease(node);
int interruptMode = 0;
//isOnSyncQueue判断node是不是同步队列的节点
//线程调用signal或signalAll时,会从firstWaiter节点开始，将节点依次从等待队列中移除，并通过enq方法重新添加到同步队列中
//因此当其他线程调用signal或者signalAll方法时，该线程可能从条件（等待）队列中移除，并重新加入到同步队列中
//1. 如果没有加入到同步队列，则阻塞当前线程，同时调用checkInterruptWhileWaiting检测当前线程在等待过程中是否发生中断，设置interruptMode表示中断状态。
//2. 如果isOnSyncQueue方法判断出当前线程已经处于同步队列中了，则跳出while循环
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();//从队列中删除ws是CANCELLED的节点
if (interruptMode != 0)
reportInterruptAfterWait(interruptMode);
}
addConditionWaiter方法如下：
private Node addConditionWaiter() {
Node t = lastWaiter;
// 如果最后一个节点的ws是CANCELLED的话
if (t != null && t.waitStatus != Node.CONDITION) {
unlinkCancelledWaiters();//从队列中删除ws是CANCELLED的节点
t = lastWaiter;//t重新赋值为尾节点
}
Node node = new Node(Thread.currentThread(), Node.CONDITION);//当前线程节点
if (t == null)//如果等待队列为空
firstWaiter = node;//头节点赋值为node
else
t.nextWaiter = node;//尾节点的后继赋值为node
lastWaiter = node;//尾节点重新赋值为node
return node;//返回当前线程节点
}fullyRelease方法如下：
final int fullyRelease(Node node) {
boolean failed = true;//释放锁资源失败的标志
try {
int savedState = getState();//返回state的值，独占模式是1，共享模式大于等于1（重入）
if (release(savedState)) {//如果释放成功了
failed = false;//失败标志置false
return savedState;
} else {
throw new IllegalMonitorStateException();
}
} finally {
if (failed)//如果释放失败了，把node的ws改为CACELLED
node.waitStatus = Node.CANCELLED;
}
}signal方法如下：
public final void signal() {
if (!isHeldExclusively())
throw new IllegalMonitorStateException();
Node first = firstWaiter;
if (first != null)
doSignal(first);
}
//删除等待队列头节点
private void doSignal(Node first) {
do {
if ( (firstWaiter = first.nextWaiter) == null)
lastWaiter = null;
first.nextWaiter = null;
} while (!transferForSignal(first) &&
(first = firstWaiter) != null);
}
//更新节点状态，并通过enq方法，将节点重新加入同步队列中
final boolean transferForSignal(Node node) {
if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
return false;
Node p = enq(node);
int ws = p.waitStatus;
if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
LockSupport.unpark(node.thread);
return true;
}
signal方法的核心其实是doSignal和transferForSignal方法，doSignal的主要作用就是将条件（等待）队列中的头节点firstWaiter从队列中移除，transferForSignal方法的主要作用就是将doSignal方法中移除的firstWaiter节点通过enq方法重新添加到同步队列中，从这里也可以看出为什么会在await方法中调用isOnSyncQueue方法判断节点是否处于同步队列中了。
