概述
AQS(AbstractQueuedSynchronizer)是一个用于构建锁和同步器的框架,许多同步器都可以通过AQS很容易并且高效地构造出来。不仅ReentrantLock和Semaphore是基于AQS构建的,还包括CountDownLatch、ReentrantReadWriteLock、SynchronousQueue和FutureTask。
AQS解决了在实现同步器时涉及的大量细节问题,例如等待线程采用FIFO队列操作顺序。在不同的同步器中还可以定义一些灵活的标准来判断某个线程是应该通过还是需要等待。基于AQS来构建同步器能带来许多好处。它不仅能极大地减少实现工作,而且也不处理在多个位置上发生的竞争问题(这是在没有使用AQS来构建同步器时的情况)。在 SemaphoreOnLock中,获取许可的操作可能在两个时刻阻塞一一一当锁保护信号量状态时,以及当许可不可用时。在基于AQS构建的同步器中,只可能在一个时刻发生阻塞,从而降低上下文切换的开销,并提高吞吐量。在设计AQS时充分考虑了可伸缩性,因此java.util.concurrent 中所有基于AQS构建的同步器都能获得这个优势。
AbstractQueuedSynchronizer介绍
大多数开发者都不会直接使用AQS,标准同步器类的集合能够满足绝大多数情况的需求。但如果能了解标准同步器类的实现方式,那么对于理解它们的工作原理是非常有帮助的。
在基于AQS构建的同步器类中,最基本的操作包括各种形式的获取操作和释放操作。获取操作是一种依赖状态的操作,并且通常会阻塞。当使用锁或信号量时,“获取”操作的含义就很直观,即获取的是锁或者许可,并且调用者可能会一直等待直到同步器类处于可被获取的状态。在使用CountDownLatch时,“获取”操作意味着“等待并直到闭锁到达结束状态”,而在使用FutureTask时,则意味着“等待并直到任务已经完成”。“释放”并不是一个可阻塞的操作,当执行“释放”操作时,所有在请求时被阻塞的线程都会开始执行。
如果一个类想成为状态依赖的类,那么它必须拥有一些状态。AQS负责管理同步器类中的状态,它管理了一个整数状态信息,可以通过getstate,setState以及compareAndSetState等 protected类型方法来进行操作。这个整数可以用于表示任意状态。例如,ReentrantLock用它来表示所有者线程已经重复获取该锁的次数,Semaphore用它来表示剩余的许可数量,FutureTask 用它来表示任务的状态(尚未开始、正在运行、已完成以及已取消)。在同步器类中还可以自行管理一些额外的状态变量,例如,ReentrantLock保存了锁的当前所有者的信息,这样就能区分某个获取操作是重人的还是竞争的。
重要入口方法
AQS里面最重要的就是两个操作和一个状态:获取操作(acquire)、释放操作(release)、同步状态(state)。两个操作通过各种条件限制,总共有8个重要的方法,6个获取方法,2个释放方法,如下:
- acquire(int):独占模式的获取,忽略中断。
- acquireInterruptibly(int):独占模式的获取,可中断
- tryAcquireNanos(int, long):独占模式的获取,可中断,并且有超时时间。
- release(int):独占模式的释放。
- acquireShared(int):共享模式的获取,忽略中断。
- acquireSharedInterruptibly(int):共享模式的获取,可中断
- tryAcquireSharedNanos(int, long):共享模式的获取,可中断,并且有超时时间。
- releaseShared(int):共享模式的释放。
- 而各个获取方法和释放方法其实大同小异,因此本文只对acquire(int)和release(int)方法展开详解(即独占模式下忽略中断的获取和释放),搞懂了这2个方法,读懂其他6个方法也是基本没有什么阻碍。
几个点
一些比较难理解或者容易搞混的知识点,先在这里介绍一下,有助于阅读本文和源码。
- 注意区分文中提到的队列是“同步队列”还是“条件队列”。“同步队列”通过prev属性和next属性来维护队列,“条件队列”通过nextWaiter属性来维护队列。另外,有些书将prev属性和next属性维护的队列称为“同步队列”,将nextWaiter维护的队列称为“等待队列”。根据源码的注释,其实两个队列都可以称为“等待队列”,因此特以“同步队列”和“条件队列”来区分,请注意。注:本文讲的内容基本都是“同步队列”,“条件队列”是用于Condition的实现。(参考基础属性中的图)
- nextWaiter可以分为3种情况:1)共享模式的节点,值固定为源码中的常量SHARED;2)独占模式的普通节点:值固定为源码中的常量EXCLUSIVE,也就是null;3)独占模式的条件队列节点:值指向下一个线程等待在Condition上的节点。如果觉得不好理解,可以参考基础属性下面的图。
- AQS里的队列是“CLH”锁定队列的变种, CLH通常用于自旋锁。
- prev属性主要用于处理CANCELLED状态。如果节点被取消,其后继节点会向前遍历重新链接到未被取消的前驱节点。
- acquire(int) 和 release(int) 方法解释起来比较拗口,正常的语法,动词后面应该带有名词,例如:acquireLock,但是在AQS的源码中并没有这样。因此,在本文中可能会将acquire直接解释成“获取”或直接用“acquire”。
- 在实际的使用中,acquire一般都指获取锁。如ReentrantLock中的实现。
- 文中提到的唤醒后继节点,即对后继节点的线程使用LockSupport.unpark方法,与之前的park方法(阻塞节点线程)对应。
- head节点(头节点)一般是指当前acquire成功的节点(通常就是当前获取到锁的节点),在设置成头节点后,会将该节点的线程设置为null。
- waitStatus=CANCELLED的节点是要丢弃(跳过)的节点,在cancelAcquire(Node)方法中,最直接的办法应该是将node节点移除,但是源码中进行了更优的处理,再移除node节点的同时,将node前面和后面的连续节点waitStatus=CANCELLED的也一并移除了。(参考下文cancelAcquire方法的图)
基础属性
static final class Node { /** Marker to indicate a node is waiting in shared mode */ static final Node SHARED = new Node(); // 标记节点正在以共享模式等待 /** Marker to indicate a node is waiting in exclusive mode */ static final Node EXCLUSIVE = null; // 标记节点正在以独占模式等待 // 表示线程已取消:由于在同步队列中等待的线程等待超时或者被中断, // 需要从同步队列中取消等待,节点进入该状态将不会变化(即要移除/跳过的节点) static final int CANCELLED = 1; // 表示后继节点处于park,需要唤醒:后继节点的线程处于park,而当前节点的线 // 程如果进行释放操作或者被取消,将会通知后继节点,使后继节点的线程得以运行 static final int SIGNAL = -1; // 表示线程正在等待状态:即节点在等待队列中,节点线程等待在Condition上, // 当其他线程对Condition调用了signal()方法后,该节点将会从等待队列中转移到同步队列中 //(即该节点的线程调用了Condition.await()方法,需要先唤醒才能进入同步队列) static final int CONDITION = -2; // 表示下一次共享模式同步状态获取讲会无条件地被传播下去 static final int PROPAGATE = -3; // 即上面的CANCELLED/SIGNAL/CONDITION/PROPAGATE,初始状态为0 volatile int waitStatus; // 等待状态 volatile Node prev; // 前驱节点 volatile Node next; // 后继节点 volatile Thread thread; // 节点的线程(获取同步状态的线程) // 条件队列(注意和同步队列区分)中的后继节点:参见addConditionWaiter方法, // 表示下一个等待Condition的Node,如果当前节点是共享的,那么这个字段将是一个 // SHARED常量,也就是说节点类型(独占和共享)和等待队列中的后继节点共用一个字段。 Node nextWaiter; final boolean isShared() { // 如果节点在共享模式下等待,则返回true。 return nextWaiter == SHARED; } // 返回节点的前驱节点,如果为null,则抛出NullPointerException final Node predecessor() throws NullPointerException { Node p = prev; if (p == null) throw new NullPointerException(); else return p; } Node() { // 用于创建头节点或SHARED标记 } Node(Thread thread, Node mode) { // Used by addWaiter this.nextWaiter = mode; this.thread = thread; } Node(Thread thread, int waitStatus) { // Used by Condition this.waitStatus = waitStatus; this.thread = thread; } } // 同步队列的头节点,使用懒汉模式初始化。 除了初始化,它只能通过setHead方法修改。 // 注意:如果头节点存在,其waitStatus保证不是CANCELLED。 private transient volatile Node head; // 同步队列的尾节点,使用懒汉模式初始化。仅通过enq方法修改,用于添加新的等待节点。 private transient volatile Node tail; // 同步状态, volatile修饰,很多同步类的实现都用到了该变量, // 例如:ReentrantLock、CountDownLatch等 private volatile int state; // 返回当前的同步状态 protected final int getState() { return state; } // 设置同步状态值 protected final void setState(int newState) { state = newState; } // 使用CAS修改同步状态值 protected final boolean compareAndSetState(int expect, int update) { // See below for intrinsics setup to support this return unsafe.compareAndSwapInt(this, stateOffset, expect, update); }
AQS中Node是组成队列的数据结构,如下图是队列的数据结构图:
acquire方法
public final void acquire(int arg) { // tryAcquire(arg)方法:提供给子类实现的,主要用于以独占模式尝试acquire if (!tryAcquire(arg) && // addWaiter方法:添加一个独占模式的节点到同步队列的尾部; // acquireQueued:该节点尝试acquire acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); // 中断当前线程 }
- 首先是调用tryAcquire方法,在AQS中该方法是没有实现的,子类必须实现,主要用于以独占模式尝试acquire。例如在ReentrantLock中的实现逻辑是:先获取当前的同步状态,再使用CAS尝试将同步状态修改成期望值,如果修改成功将拥有独占访问权的线程设置为当前线程。在ReentrantLock中,acquire指的是获取锁,而tryAcquire即为尝试获取锁。
- 如果tryAcquire返回false,则尝试acquire失败了,则会调用addWaiter方法(详解见下文代码块1),添加一个独占模式的节点到同步队列尾部。 并调用acquireQueued方法(详解见下文代码块3)尝试acquire。
- 最后,如果acquireQueued返回true,则调用selfInterrupt方法中断当前线程,这是因为acquireQueued返回true就是代表线程被中断。
代码块1:addWaiter方法
private Node addWaiter(Node mode) { // 以当前线程和mode为参数,创建一个节点 Node node = new Node(Thread.currentThread(), mode); Node pred = tail; // 将pred赋值为当前尾节点 if (pred != null) { // pred不为空 // 将新创建的节点的前驱节点设置为pred,即将刚创建的节点放到尾部 node.prev = pred; // 使用CAS将尾节点修改为新节点 if (compareAndSetTail(pred, node)) { // 尾节点修改成功后,将pred的后继节点设置为新节点,与上文node.prev=pred对应 pred.next = node; return node; } } // 如果pred为空,代表此时同步队列为空,调用enq方法将新节点添加到同步队列 enq(node); return node; }
根据当前线程和入参mode创建一个新的Node,并放到尾部。如果同步队列为空,则调用enq方法(详解见下文代码块2)添加节点。
代码块2:enq方法
// 将节点插入队列,如果队列为空则先进行初始化,再插入队列。 private Node enq(final Node node) { for (;;) { Node t = tail; // 将t赋值为尾节点 // 如果尾节点为空,则初始化head和tail节点 if (t == null) { // 使用CAS将头节点赋值为一个新创建的无状态的节点 if (compareAndSetHead(new Node())) tail = head; // 初始化尾节点 } else { // 如果尾节点不为空,使用CAS将当前node添加到尾节点 node.prev = t; // 将node的前驱节点设置为t if (compareAndSetTail(t, node)) { // 使用CAS将尾节点设置为node // 成功将尾节点修改为node后,将t的后驱节点设置为node,与node.prev=t对应 t.next = node; return t; } } } }
- 如果队列为空,则先初始化head和tail节点(介绍属性时说过了,head和tail采用懒汉模式初始化),再使用CAS将node添加到队列尾部。
- 如果队列不为空,直接使用CAS将node添加到队列尾部。
该方法和上面的addWaiter方法其实很相似,只是多了一个队列为空时的初始化head和tail操作。
代码块3:acquireQueued方法
// 添加完节点后,立即尝试该节点是否能够成功acquire final boolean acquireQueued(final Node node, int arg) { boolean failed = true; try { boolean interrupted = false; // 用于判断是否被中断过 for (;;) { // 自旋过程 final Node p = node.predecessor(); // 将p赋值为node的前驱节点 // 如果p为头节点,则node节点尝试以独占模式acquire(acquire一般为获取锁) if (p == head && tryAcquire(arg)) { // node节点成功以独占模式acquire,调用setHead方法将node设置为头节点 setHead(node); p.next = null; // 断开原头节点与node节点的关联 failed = false; return interrupted; // 返回node是否被中断过 } // shouldParkAfterFailedAcquire: 校验node是否需要park(park:会将node的线程阻塞) // 只有当前驱节点等待状态为SIGNAL,才能将node进行park,因为当前驱节点为SIGNAL // 时,会保证来唤醒自己,因此可以安心park if (shouldParkAfterFailedAcquire(p, node) && // node进入park状态,直到被前驱节点唤醒,被唤醒后返回线程是否为中断状态 parkAndCheckInterrupt()) interrupted = true; // 在等待过程中被中断 } } finally { if (failed) cancelAcquire(node); // 取消正在进行的acquire尝试,走到这边代表出现异常 } }
- 该方法用于添加完节点后调用,首先判断node节点的前驱节点是否为head,如果是,node会尝试acquire,如果node成功acquire,会调用setHead方法,将node设置为head、将node的thread设置为null、将node的prev设置为null,这保证了数据结构中头节点永远是一个不带Thread的空节点。
- 如果node节点的前驱节点不是head,或者node尝试acquire失败,则会调用shouldParkAfterFailedAcquire方法(详解见下文代码块4)校验node是否需要park(此处park是将node的线程阻塞,LockSupport.park),如果shouldParkAfterFailedAcquire返回true则调用parkAndCheckInterrupt方法(详解见下文代码块5)将node的线程阻塞。
- 如果走到finally方法时,failed为true,则代表出现了异常,调用cancelAcquire方法(详解见下文代码块6)取消正在进行的acquire尝试。
代码块4:shouldParkAfterFailedAcquire方法
// 判断节点是否应该park private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { int ws = pred.waitStatus; // 前驱节点的等待状态 if (ws == Node.SIGNAL) // 如果前驱节点节点等待状态为SIGNAL, return true; // 返回true,表示node节点应该park,等待它的前驱节点来唤醒 // 如果前驱节点的等待状态>0,代表该前驱节点为CANCELLED(取消)状态,需要跳过该节点 if (ws > 0) { // 从pred节点开始向前寻找,直到找到等待状态不为CANCELLED的, do { node.prev = pred = pred.prev; // 将其设置为node的前驱节点 } while (pred.waitStatus > 0); pred.next = node; // 与上面对应 } else { // pred节点使用CAS尝试将等待状态修改为SIGNAL(ws必须为PROPAGATE或0), // 然后返回false(即再尝试一次能否不park直接acquire成功), compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false; // 返回false,代表node还不能park }
- 如果前驱节点pred的waitStatus为SIGNAL,返回true,表示node节点应该park,等待它的前驱节点来唤醒。
- 如果前驱节点pred的waitStatus>0,代表该节点为CANCELLED(取消)状态,需要跳过该节点。从pred节点开始向前寻找,直到找到等待状态不为CANCELLED的,将其设置为node的前驱节点。
- 否则,使用CAS尝试将pred节点的waitStatus修改为SIGNAL,然后返回false,这里直接返回false是为了再执行一次acquireQueued方法for循环的“if (p == head && tryAcquire(arg))”代码,因为如果能tryAcquire成功,则避免了当前线程阻塞,也就减少了上下文切换的开销(关于上下文切换等内容可以参考我的另一篇文章:Java并发:性能与可伸缩性)。
代码块5:parkAndCheckInterrupt方法
private final boolean parkAndCheckInterrupt() { // 等待,然后检查是否被中断 LockSupport.park(this); // 阻塞当前节点的线程 return Thread.interrupted(); // 返回当前线程是否为中断状态 }
调用LockSupport.park方法将当前线程阻塞,并在被唤醒之后,返回当前线程是否为中断状态。
代码块6:cancelAcquire方法
private void cancelAcquire(Node node) { // 取消正在进行的acquire尝试 if (node == null) return; node.thread = null; Node pred = node.prev; // node的前驱节点pred的waitStatus如果为CANCELLED, // 则向前寻找waitStatus不为CANCELLED的前驱节点pred while (pred.waitStatus > 0) node.prev = pred = pred.prev; // 拿到pred的后继节点(不一定为node,请注意) Node predNext = pred.next; node.waitStatus = Node.CANCELLED; // 将node的waitStatus设置为CANCELLED // 如果node为尾节点,则使用CAS将尾节点改为pred节点 // 即将pred后面的节点全部移除,包括node节点和node前面状态为CANCELLED的节点 if (node == tail && compareAndSetTail(node, pred)) { // 将pred的后继节点设置为null,与上面对应 compareAndSetNext(pred, predNext, null); } else { // 否则,node不是尾节点,即node有后继节点,移除了node节点需要保证node // 的后继节点不会受到影响,因此会根据情况决定是否需要唤醒node的后继节点 int ws; // 如果后继节点需要唤醒信号,并且pred可以提供给它,则将pred.next设置为node的后继节点, // 这样在pred释放的时候就会提供一个信号给node的后继节点,从而保证node的后继节点不受影响 if (pred != head && ((ws = pred.waitStatus) == Node.SIGNAL || (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) && pred.thread != null) { Node next = node.next; // 拿到node的后继节点next // 如果next不为null并且等待状态不为CANCELLED if (next != null && next.waitStatus <= 0) // 则使用CAS将pred的后继节点修改为next, // 因为只有pred的waitStatus为SIGNAL时才能走到这边,因此next节点无需唤醒 compareAndSetNext(pred, predNext, next); } else { // 否则,如果pred节点无法提供给node的后继节点信号,则直接唤醒node的后继节点 unparkSuccessor(node); // 唤醒node节点的后继节点 } node.next = node; // help GC } }
- 如果node为空,直接返回。
- 如果node的前驱节点pred的waitStatus为CANCELLED,则向前寻找等待状态不为CANCELLED的前驱节点pred。
- 将predNext赋值为pred节点的后继节点。
- 将node的waitStatus设置为CANCELLED。
- 如果node为尾节点,则使用CAS将尾节点改为pred节点(即将pred后面的节点全部移除,包括node节点和node前面状态为CANCELLED的节点),如果修改尾节点成功,则使用CAS将pred节点的后继节点设置为null。
- 否则,node不是尾节点。判断pred节点是否可以提供给node后继节点唤醒信号。(pred可以提供唤醒信号:即pred满足以下条件:pred不为头节点 && (pred的等待状态为SIGNAL 或 pred的等待状态使用CAS成功修改为SIGNAL) && pred节点的线程不为null)如果可以,则将pred.next设置为node的后继节点,这样在pred释放的时候就会提供一个信号给node的后继节点,从而保证node的后继节点不受影响;如果pred节点无法提供给node的后继节点唤醒信号,则直接调用unparkSuccessor方法(详解见下文代码块7)唤醒node的后继节点。
cancelAcquire(Node)方法涉及的移除节点过程如下图例子:
代码块7:unparkSuccessor方法
private void unparkSuccessor(Node node) { // 唤醒node节点的后继节点 int ws = node.waitStatus; // 如果node的waitStatus<0(即node的waitStatus不为CANCELLED), // 则使用CAS将等待状态改为0,即初始状态(因为下面马上要将node的后继节点唤醒) if (ws < 0) compareAndSetWaitStatus(node, ws, 0); Node s = node.next; // 定义s为node的后继节点 // 如果s为null或者waitStatus为CANCELLED if (s == null || s.waitStatus > 0) { s = null; // 直接将s赋值为null // 并从尾部向前遍历以找到实际未取消的后继节点(离node最近), // 这里的意思是将node之后的空节点或waitStatus=CANCELLED的节点也 // 一并去掉,直接唤醒node之后waitStatus不为CANCELLED的节点 for (Node t = tail; t != null && t != node; t = t.prev) if (t.waitStatus <= 0) s = t; } if (s != null) LockSupport.unpark(s.thread); // 如果s不为null,则唤醒s节点 }
- 如果node的waitStatus<0(即node的后继节点可能需要信号),则使用CAS将等待状态改为0,即初始状态(因为下面马上要将node的后继节点唤醒)。
- 定义s为node的后继节点,如果s为null或者waitStatus为CANCELLED,则从同步队列尾部向前遍历以找到实际未取消的后继节点(离node最近),这里的意思是将node之后的空节点或waitStatus=CANCELLED的节点也一并去掉,直接唤醒node之后waitStatus不为CANCELLED的节点。
- 最后,如果s不为null,则使用LockSupport.unpark哈un型s节点。
release方法
public final boolean release(int arg) { // tryRelease:提供给子类实现的,主要用于以独占模式尝试release(release通常指释放锁) if (tryRelease(arg)) { Node h = head; if (h != null && h.waitStatus != 0) unparkSuccessor(h); // 唤醒头节点的后继节点线程 return true; } return false; }
- 首先是调用tryRelease方法,跟上文的tryAcquire一样,在AQS中该方法是没有实现的,子类必须实现。一般是用于解锁,例如再ReentrantLock中:tryRelease方法会将同步状态值(state)减去入参中要释放的值,如果减完的同步状态值为0,则将独占模式同步器的当前所有者设为null,即代表了解锁的意思。
- 如果tryRelease成功,并且head节点不为空,且状态不为初始状态,则调用unparkSuccessor方法(详解见上文的代码块7)唤醒head节点的后继节点。
参考
AbstractQueuedSynchronizer源码(JDK 1.8)
《Java Concurrency in Practice》