Java锁(一)AbstractQueuedSynchronizer分析

作为一个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,这里做一些简要的分析。

基本的思想是表现为一个同步器,支持下面两个操作:

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;

要支持上面两个操作就必须有下面的条件:

1.    原子操作的同步状态(Atomically managing synchronization state

2.    阻塞和唤醒线程(Blocking and unblocking threads

3.    保持队列(Maintaining queues

 

(一)原子操作的同步状态

AbstractQueuedSynchronizervolatile int state,使用一个32位的整数来描述状态位,并暴露出getStatesetState以及compareAndSet操作来读取和更新这个状态。这些方法都依赖于j.u.c.atomic包的支持,这个包提供了兼容JSR133volatile在读和写上的语义,并且通过使用本地的compare-and-swapload-linked/store-conditional指令来实现compareAndSetState,使得仅当同步状态拥有一个期望值的时候,才会被原子地设置成新值。

基于AQS的具体实现类必须根据暴露出的状态相关的方法定义tryAcquiretryRelease方法,以控制acquirerelease操作。当同步状态满足时,tryAcquire方法必须返回true,而当新的同步状态允许后续acquire时,tryRelease方法也必须返回true。这些方法都接受一个int类型的参数用于传递想要的状态。例如:可重入锁中,当某个线程从条件等待中返回,然后重新获取锁时,为了重新建立循环计数的场景。很多同步器并不需要这样一个参数,因此忽略它即可。

(二)阻塞和唤醒线程

标准的JAVA API里面是无法挂起(阻塞)一个线程,然后在将来某个时刻再唤醒它的。JDK 1.0API里面有Thread.suspendThread.resume,并且一直延续了下来。但是这些都是过时的API,而且也是不推荐的做法。在JDK 5.0以后利用JNILockSupport类中实现了此特性。

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方面:

1.    其他某个线程以当前线程作为目标调用 unpark

2.    其他某个线程中断interrupt当前线程;

3.    该调用不合逻辑地(即毫无理由地)返回。

 由于park()立即返回,其中第三条就决定了需要循环检测,所以通常情况下需要在循环中去检测竞争资源来决定是否进行下一次阻塞。

(三)保持队列

    同步队列的最佳选择是自身没有使用底层锁来构造的非阻塞数据结构,目前,业界对此很少有争议。而其中主要有两个选择:一个是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;

其中state描述的有多少个线程取得了锁,对于互斥不可重入锁来说state<=1

head/tail加上CAS操作就构成了一个CLHFIFO队列,队列中的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的其他特性和实现。

Java锁系列其他文章

1、  AbstractQueuedSynchronizer基础类分析

2、  ReentrantLock独占锁分析

3、  CountDownLatch共享锁分析

4、  ConditionObject分析

5、  CyclicBarrier分析