作为一个 java 开发者,并发编程是不可或缺的,在并发的过程,Lock 是并发的关键。
本系列文章主要来讲解锁的原理和机制。
在理解 J.U.C 原理以及锁机制之前,我们来介绍 J.U.C 框架最核心也是最复杂的一个基础类:java.util.concurrent.locks.AbstractQueuedSynchronizer。
上面的继承体系中,AbstractQueuedSynchronizer 是 CountDownLatch/Semaphore/RenntrantReadWriteLock /Worker/ReentrantLock 的基础,因此 AbstractQueuedSynchronizer 是 Lock/Executor 实现的前提。公平锁、不公平锁、Condition、CountDownLatch、Semaphore 等放到后面的篇幅中说明。AQS 采用模板方法模式,为一个抽象类,但是没抽象方法,每个 sync 子类都需要实现 5 个受保护的方法。
这个 5 个方法在 AQS 都抛出 throw new UnsupportedOperationException();
完整的设计原理可以参考 Doug Lea 的论文 [java.util.concurrent Synchronizer Framework](aqs.pdf),这里做一些简要的分析。
AQS 操作
基本的思想是表现为一个同步器,支持下面两个操作:
1、AQS 获取锁
//判断当前状态是否允许获取锁
while(synchronization state does not allow acquire) {
//当前线程入队列
enqueue current thread if not already queued;
//阻塞当前线程
possibly block current thread;
}
//状态位允许获取锁时就修改状态, 如果进了队列就从队列中移除
dequeue current thread if it was queued;
2、AQS 释放锁
//更新同步状态
update synchronization state;
//当前状态允许阻塞线程获取,唤醒队列中的一个或者更多线程
if(state may permit a blocked thread to acquire)
unlock one or more queued threads;
AQS 条件
要支持上面两个操作就必须有下面的条件:
- 原子操作的同步状态(Atomically managing synchronization state)
- 阻塞和唤醒线程(Blocking and unblocking threads)
- 保持队列(Maintaining queues)
1、原子操作的同步状态
AbstractQueuedSynchronizer 中同步状态 volatile int state,使用一个 32 位的整数来描述状态位,并暴露出 getState、setState 以及 compareAndSet 操作来读取和更新这个状态。这些方法都依赖于 j.u.c.atomic 包的支持,这个包提供了兼容 JSR133 中 volatile 在读和写上的语义,并且通过使用本地的 compare-and-swap 或 load-linked/store-conditional 指令来实现 compareAndSetState,使得仅当同步状态拥有一个期望值的时候,才会被原子地设置成新值。
基于 AQS 的具体实现类必须根据暴露出的状态相关的方法定义 tryAcquire 和 tryRelease 方法,以控制 acquire 和 release 操作。当同步状态满足时,tryAcquire 方法必须返回 true,而当新的同步状态允许后续 acquire 时,tryRelease 方法也必须返回 true。这些方法都接受一个 int 类型的参数用于传递想要的状态。例如:可重入锁中,当某个线程从条件等待中返回,然后重新获取锁时,为了重新建立循环计数的场景。很多同步器并不需要这样一个参数,因此忽略它即可。
2、阻塞和唤醒线程
标准的 JAVA API 里面是无法挂起(阻塞)一个线程,然后在将来某个时刻再唤醒它的。JDK 1.0 的 API 里面有 Thread.suspend 和 Thread.resume,并且一直延续了下来。但是这些都是过时的 API,而且也是不推荐的做法。在 JDK 5.0 以后利用 JNI 在 LockSupport 类中实现了此特性。
LockSupport.park()
LockSupport.park(Object)
LockSupport.parkNanos(Object, long)
LockSupport.parkNanos(long)
LockSupport.parkUntil(Object, long)
LockSupport.parkUntil(long)
LockSupport.unpark(Thread)
上面的 API 中 park()是在当前线程中调用,导致线程阻塞,带参数的 Object 是挂起的对象,这样监视的时候就能够知道此线程是因为什么资源而阻塞的。
而 park()返回的原因有以下 3 方面:
- 其他某个线程以当前线程作为目标调用 unpark;
- 其他某个线程中断 interrupt 当前线程;
- 该调用不合逻辑地(即毫无理由地)返回。
由于 park()立即返回,其中第三条就决定了需要循环检测,所以通常情况下需要在循环中去检测竞争资源来决定是否进行下一次阻塞。
3、保持队列
同步队列的最佳选择是自身没有使用底层锁来构造的非阻塞数据结构,目前,业界对此很少有争议。而其中主要有两个选择:
- 一个是 Mellor-Crummey 和 Scott 锁(MCS 锁)的变体,
- 另一个是 Craig,Landin 和 Hagersten 锁(CLH 锁)的变体
一直以来,CLH 锁仅被用于自旋锁。但是,在这个框架中,CLH 锁显然比 MCS 锁更合适。因为 CLH 锁可以更容易地去实现“取消(cancellation)”和“超时”功能,因此我们选择了 CLH 锁作为实现的基础。但是最终的设计已经与原来的 CLH 锁有较大的出入,因此下文将对此做出解释。
CLH 队列实际上并不那么像队列,因为它的入队和出队操作都与它的用途(即用作锁)紧密相关。它是一个链表队列,通过两个字段 head 和 tail 来存取,这两个字段是可原子更新的,两者在初始化时都指向了一个空节点。
AQS 里面有三个核心字段:
private volatile int state;
private transient volatile Node head;
private transient volatile Node tail;
**Sync queue **同步队列,是一个双向列表。包括 head 节点和 tail 节点。head 节点主要用作后续的调度。
**Condition queue ** 非必须,单向列表。当程序中存在 cindition 的时候才会存在此列表。
其中 state 描述的有多少个线程取得了锁,对于互斥不可重入锁来说 state⇐1。
head/tail 加上 CAS 操作就构成了一个 CLH 的 FIFO 队列,队列中的 Node 为一个双向链表。
AQS 中入队列(enqueue),采用 CAS 操作,每次比较尾结点是否一致,然后插入的到尾结点中。
出队列(dequeue),由于每一个节点也缓存了一个状态,决定是否出队列,因此当不满足条件时就需要自旋等待,一旦满足条件就将头结点设置为下一个节点。
CLH 锁的优点在于其入队和出队操作是快速、无锁的,以及无障碍的(即使在竞争下,某个线程总会赢得一次插入机会而能继续执行);且探测是否有线程正在等待也很快(只要测试一下 head 是否与 tail 相等);同时,“释放”状态是分散的,避免了一些不必要的内存竞争。
对于于独占锁和共享锁中,入队列和出队列的具体过程,后续会详细讲解,本文先讲解下同步队列中的 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;
/** 线程在condition上等待 */
static final int CONDITION = -2;
/**
* 下一个acquireShared应该无条件传播
*/
static final int PROPAGATE = -3;
/**
* CANCELLED: 节点因为超时或者对应的线程被interrupt被取消
* SIGNAL: 节点的继任节点是(或者将要成为)BLOCKED状态(例如通过LockSupport.park()操作)。
* 因此当前节点一旦被释放(解锁)或者取消,就需要唤醒它的后继节点。
* 为避免竞争,acquire方法必须首先表明他们需要一个信号,然后重试原子acquire方法,
* 如果失败,就阻塞。
* CONDITION: 节点当前是在状态队列中(因为不满足一个条件(Condition)而被阻塞),
* 直到节点的状态变成0,它才被使用作为一个同步队列节点。
* PROPAGATE: releaseShared应该被传播到其他的节点,它在doReleaseShared方法中被设置(仅头节点)
* 0: 正常状态,新生的非CONDITION节点都是此状态
*
*/
volatile int waitStatus;
/**
* 前驱节点
*/
volatile Node prev;
/**
* 后继节点
*/
volatile Node next;
/**
* 节点关联的线程
*/
volatile Thread thread;
/**
* 下一个在等待状态(condition)的节点,或者特殊的值 SHARED.
*/
Node nextWaiter;
}
AQS 在 J.U.C 里面是一个非常核心的工具,而且也非常复杂,里面考虑到了非常多的逻辑实现,本文主要介绍了一些理论背景和相关的数据结构,后续会介绍 AQS 的其他特性和实现。