AbstractQueuedSynchronizer JUC同步框架

作者: doug lea

原文: gee.cs.oswego.edu/dl/papers/a…

参考: www.jianshu.com/p/c5a18eb6d…

文中会出现一些 "[number]"的标记, 对应了原文中doug lea的参考文献引用的编号

摘要

J2SE1.5 java.util中的大多数同步器(锁、屏障等)。
使用基于小性框架构 AbstractQueuedSynchronizer 构造并发包.
该框架为原子管理同步状态,阻塞唤醒线程,以及排队提供了通用机制。
本文介绍了该框架的原理、设计、实现、使用和性能。
复制代码

类别和主题描述符

D.1.3 [Programming Techniques]: Concurrent Programming – Parallel Programming
D.1.3 [编程技术]: 并发编程 - 并行编程
复制代码

关键词

同步(Synchronization), Java
复制代码

1.前言

java 发行版 J2SE-1.5 引入包 java.util.concurrent, 包括一组通过 JCP(Java Community Process) 
JSR(Java Specification Request) 166 创建的中级并发支持类.
复制代码

在这些组件中有一组同步器——抽象数据类型(ADT)类, 来维护内部同步状态(例如:表示lock/unlock), 
更新和检查状态, 若状态需要阻塞线程, 再通过其他线程状态的改变唤醒线程.
组件示例: 各种形式的互斥锁(exclusion locks), 读写锁(read-write locks), 信号量(semaphores),
屏障(barriers), 事件指示器(event indicators), 交接队列(handoff queues, 即SynchronizedQueue)
复制代码

ADT: 此处的ADT指的是 abstract class AbstractQueuedSynchronizer //抽象类

众所周知(如[2]), 同步器之间几乎可以互相实现. 例如用可重入锁实现信号量, 反之亦然. 然而，
这样做通常需要足够的的复杂性、开销和灵活性，不是最好解决方案. 此外这个方案在概念上没有
吸引力. 如果这些结构没有比其他结构更原始,开发人员不应该选择其中一个作为构建其他组件的
基础. 于是, JSR 166 建立了一个以 "AbstractQueuedSynchronizer(aqs)" 为中心的类库, aqs
提供了大多数 "synchronizers" 公用的机制, "synchronizers" 只需补充实现各自的特性即可。
复制代码

本文的其余部分将讨论此框架的需求、设计和实现背后的主要思想、示例用法以及显示其性能
特征的一些测试
复制代码

2.需求

2.1 功能

同步器有两类方法[7]: 
    至少执行一次 "acquire" 方法阻塞调用线程, 除非/直到同步状态允许它继续
    至少执行一次 "release" 操作改变同步状态,唤醒一条或多条线程.
    
JUC 没有为同步器定义一个统一的API. 有些使用公用接口(Lock), 其他的使用其专门的版本.
所以 acquire release,在不同类的不同方法中调用. 例如, Lock.lock,Semaphore.acquire,
CountDownLatch.await, FutureTask.get 都使用框架中的 acquire 操作.
复制代码

必要情况下, 框架对同步器提供的一些支持:
    非阻塞同步尝试(tryLock) 和 阻塞版本
    可选的超时时间: tryAcquireNanos(time)
    响应线程中断: acquire acquireInterruptibly

独享锁,共享锁模式。

JUC定义了一个接口"Condition", 支持监视器风格的 await/signal 操作.
复制代码

2.2 性能目标

Java内置锁(使用synchronized method|同步方法和 blocks|同步代码块)长期以来一直有个性能问题.
    关于"synchronized"的构造有相当多的文献([1],[3]).对内置锁的优化主要集中在最小化空间开销
(因为每个Java对象都有一个监视器)和单处理器中上下文的时间开销.
    这两个工作对同步器都不是特别重要:程序员只在需要的时候构造同步器,创建监视器。2.越来越多的程序
运行在多核多线程的环境下，在这种环境下资源竞争是不可避免的。
    通常的JVM策略只对  "zero-contention(零争用)" 情况优化锁,将其他情况留给不那么可预测的慢路径[12].
复制代码

JUC的主要性能目标是可伸缩性: 在争用同步器时, 可以预测并保持效率。理想状态下无论多少线
程通过同步点,通过同步点所需的开销都应该是常量. 其中主要目标是缩小"允许通过同步点但是还未通
过的总时间"(减少"临界区"的空闲时间).
实现目标的同时需要考虑资源上的平衡: 总的CPU时间, 内存流量, 线程调度开销. 例如：自旋锁通常
比阻塞锁耗时更短，但通常会CPU空转并产生内存争用, 短时自旋长时阻塞.
    两种风格: 大多数应用程序应该最大限度地提高总吞吐量, 容忍一定概率的饥饿度。 在资源控制等
应用程序中, 最重要的是保证线程间访问的公平性, 容忍较差的聚合吞吐量。没有一个框架能够代表用户
在这些冲突的目标之间做出决定;公平政策需要交由用户选择。
    不管同步器在内部设计得有多好，它都会遇到性能瓶颈。因此，框架提供监视和检查基本操作，方便
允许用户发现和缓解瓶颈, 提供一种方法来确定有多少线程被阻塞是最有效的。
复制代码

允许通过但还没通过: 同步状态已经可以被线程获取, 但是没有线程来获取

key word: 资源平衡 内存争用 公平/非公平 监视和检查

3.设计和实现

同步器背后的基本思想非常简单。
acquire 操作流程:
    while (同步状态不允许acquire) {
        当前线程入队, 若它还不在队列中
        当前线程可能阻塞
    }
    当前线程出队如果在队列中

release 操作流程:
    更新同步状态
    if (状态允许阻塞线程获取)
        解锁一个或多个队列中的的线程
复制代码

流程需要协调三个基本组件间协调:
    原子管理同步状态
    阻塞/唤醒线程
    维护队列
    
    也许可以创建一个框架允许三个组件独立变化,但效果不太好.例如: 节点中保存的信息必须与唤醒需要的信息相匹配,
对外开放的方法需要依赖同步状态.
    同步器框架的核心设计决策是如何选择这三个组件的具体实现。
复制代码

3.1 同步状态 Synchronization State

Class AbstractQueuedSynchronizer 使用一个(32bit)int维护synchronization state, 对外开放getState、setState
和 compareAndSetState来访问和更新此状态。这些方法依赖于JSR-133(jmm)支持提供的 volatile 读写, 以及通过访问本地指令
compare-and-swap or loadlinked/store-conditional 实现 compareAndSetState,只有当状态具有给定的期望值时，才原子地
将状态设置为给定的新值。
复制代码

同步状态为32位int型。虽然JSR-166提供了long原子操作,但是必须在足够多的平台上使用内部锁来模拟这些操作，导致同步不
能很好地执行。在将来可能出现基于64bit的基类, 目前32已经足够。只有CyclicBarrier需要64bit，所以CyclicBarrier内部使
用了Lock(就像JUC中大多数高级工具)
复制代码

基于AbstractQueuedSynchronizer的具体类必须根据这些对外开放的状态方法,定义tryacquisition和tryRelease方法,以便控
制acquire and release操作。如果获得同步，tryacquisition方法必须返回true, 如果新的同步状态允许其他线程获取同步, 
tryRelease 方法返回 true。这些方法接受一个int参数，该参数可用于通信所需的状态;例如, 在重入锁中, 重新获取锁时会重新
建立递归计数，许多同步器不需要这样的参数，所以忽略它。
复制代码

3.2 阻塞

JSR-166 之前只有基于 监视器 阻塞/唤醒的 java api 来创建同步器. 唯一的方案Thread.suspend and Thread.resume, 
有两个问题: 1. 不会释放锁, 2. 调用顺序颠倒: 如果先resume 再 suspend, 线程会永远挂起.
复制代码

JUC.locks LockSupport 针对第二个问题提供了 LockSupport.park() 和 LockSupport.unpark().方法park阻塞当前线程，
除非或直到发出unpark(允许虚假觉醒). unpark不"计数"，在park前无论调用多少次"unpark"只能唤醒一次"park"。
复制代码

这个简单的机制在某种程度上类似于solars -9线程库[11]、WIN32“消耗性事件”和LinuxNPTL线程库中使用的机制，因此可以
有效地映射到Java运行的最常见平台上的每一个线程库, 提供良好的运行性能。(Solaris和Linux上当前的 "Sun Hotspot JVM"
实际上使用了 "pthread condvar" 来适应当前的运行时设计)。park 支持相对超时和绝对超时, 并与 JVM thread.interrupt
集成在一起————中断一个线程并唤醒他(什么骚操作).
复制代码

3.3 队列

框架的核心是维护阻塞线程的队列，这里将其限制为FIFO队列。因此，aqs不支持基于优先级的同步。毫无争议，非阻塞数据结构
是实现同步队列最好的选择，这些数据结构不需要使用"lower-level"锁来构造。
非阻塞数据结构有两个选择: MCS [9] 和CLH [5][8][10]。历史上，CLH只被用于过自旋锁。对于同步器框架CLH更容易使用, 因
为CLH更易于处理取消和超时, 所以选了CLH作为同步队列的基础. 最终实现和CLH相差甚远。
CLH不是很像队列, 因为CLH出队入队的操作跟它作为锁的特性密切相关。它是一个链表队列, 通过原子操作更新head和tail，两个
节点指向虚拟节点。
复制代码

新节点，"node"，使用原子性操作入队:
    do { 
        pred = tail;
    } while(!tail.compareAndSet(pred, node));
复制代码

每个节点能否拿到锁, 依赖于前一个节点的状态:
    while (pred.status != RELEASED) ; // spin
复制代码

通过自旋之后的出队操作, 将当前节点设置为 "head":
    head = node;
复制代码

CLH锁的优点之一是，入队和出队速度快，无锁，无阻塞(即使在争用状态下，一个线程也总是会在插入竞争中获胜，从而取得进展);
检查有没有线程在等待也很简单(判断head和tail是否是一样), 而且RELEASED状态是分散开的,减少竞争。
CLH的最初版本, 节点之间甚至没有连接。在自旋锁中，pred被作为一个局部变量。Scott and Scherer[10] 发现显式的维护前置
节点, CLH能处理超时和节点取消(如果上一个节点取消, 跳过这个节点)。
复制代码

对CLH的主要修改是为一个节点提供方法定位后续节点。在自旋锁中, 节点只需要修改自身状态, 后继节点就能注意到。所以不需要
连接后继节点。但是在阻塞同步器中，节点需要显式地park(unpark)它的后继者。
AQS的节点有一个next属性关联到它的后继节点。但是没有什么技术可以"无锁地""原子地"向双向队列中插入一个节点，所以这个属
性没有作为原子性插入节点的一部分(pred与next只需要保证一个原子更新成功即可，另一个直接赋值):
    pred.next = node;
next连接通常只被当做一种优化的访问路径。如果一个节点的后继节点不存在了（可能被取消了），可以通过从tail遍历每个节点的
pred属性找到一个实际存在的节点。
复制代码

第二个改动, 每个节点中使用一个status属性来控制线程的阻塞和唤醒。同步器框架中, 排队的线程只有通过 tryAcquire 方法才能
在 acquire 操作中返回; 只有 RELEASED 状态已经不够用了。
1.确保活动的线程在head才允许调用 tryAcquire; 这种情况下可能获取失败,重新阻塞。
2.这种情况可以通过检查前一个节点是否是head判断是否调用tryAcquire。
与自旋锁相比，这样减少了读取head的内存争用（只读取一次，而自旋锁在一直循环读取）。但是，取消的状态还是需要在节点中维护。
复制代码

队列节点状态字段还用于避免不必要的对park和unpark的调用。虽然这些方法与阻塞原语(blocking primitives 操作系统级别)性能
相当，但调用park时在 JAVA|JVM|OS 之间会有一些无法避免的开销。线程先设置一个"signal me"节点, 调用park之前检查同步和节
点状态, 若realse线程调用unpark且重置同步状态，避免了不必要的阻塞(阻塞唤醒 比较耗时)。
aqs实现CLH, 依赖垃圾收集来管理节点的存储回收，避免了复杂性和开销。退出队列时, 将确定不再用到的属性置为null. help GC

还有一些更进一步的小优化，包括将head和tail的初始化延迟到第一次有线程等待时。
复制代码

忽略这些细节, 对于基本的acquire（排他，不响应中断，不超时）的大致实现：
if (!tryAcquire(arg)) {
    node = create and enqueue new node;  // 创建 入队 新节点
    pred = node effective predecessor; // 有效前节点
    while (pred is not head node || !tryAcquire(arg)) {
        if (pred signal bit is set)   // pred 状态为 signal
            park();                     // 阻塞
        else
            compareAndSet pred signal bit to true;    // 将前节点状态改为signal
            pred = node effective predecessor;        // 找到有效前节点
    }
    head = node;                        // pred is head node && tryAcquire(arg)
}

release :
if (tryRelease(arg) && head node signal bit is set) {
    compareAndSet head signal bit to false;   // cas head signal 
    unpark head successor, if one exists
}
复制代码

虽然acquire中tryAcquire可能会循环多次，但是，如果不考虑被取消的节点和每个平台对于park
的不同实现的话, acquire和release中的单个操作分摊到每个线程中都是常量时间O(1)。
唤醒后需要检查超时和中断时支持取消功能, 因为超时或者中止而取消的线程设置节点状态并且唤醒
下一个节点。因为有取消节点存在,找到有效的前节点,后节点以及重置状态可能会花费O(n)次的遍历
(n是队列长度). 因为线程不会再次阻塞以取消的操作,所以链接和状态很快的重建
复制代码

3.4 Condition Queues

同步框架提供 "ConditionObject"类 供同步器实现独享锁, 并且遵循"Lock"接口的API。一个锁可以
绑定多个条件对象。提供经典的 monitor-style await, signal, and signalAll, 以及这些操作的
超时版本,检查和监视的方法
"ConditionObject" 类可以用来与其他同步器配合，修复一些设计缺陷。拥有"condition"的锁被当前
线程持有时(see[4]替代方案), 提供"Java-style monitor"访问规则, 不同之处只在于方法名称、额
外功能以及用户可以为每个锁声明多个条件。
"ConditionObject" 使用了和同步器相同的内部队列节点,但是在一个单独的条件队列中维护它们。
signal 操作将节点从条件队列转移到锁队列, 而不是唤醒等待线程.
基本 "await" 操作: 
    在条件队列中创建添加锁;
    释放锁;
    阻塞直到节点移动到锁队列;
    re-acquire锁;
"signal" 操作: 
    从等待队列转移到锁队列
复制代码

因为这些操作只在持有锁时执行, 他们可以使用顺序链表操作(nextWaiter)维持等待队列, 传输操作断
开等待队列的第一个节点, 然后使用CLH插入将其附加到锁队列。
实现这些操作的主要复杂性在于处理因为超时和Thread.interrupt引起的 condition waits取消.取消
操作如果与signal操作发生的时间非常接近的话,可能会产生竞争,它们的竞争结果符合Java内置monitor
(built-in monitors)的规范。 JSR-133修订版中, 如果中断发生在signal之前，那么await必须在被
唤醒时抛出InterruptedException；如果中断发生在signal之后，那么await必须无异常地返回，但是
需要设置它的线程中断状态。
复制代码

为了保持顺序, 队列节点状态记录是否正在(已经)传输.signal和cancel都会去CAS这个状态.如果signal
失败, signal下一个节点(如果有的话)。如果取消操作失败,则必须中止传输,然后重新获取await lock.
后一种情况引入了潜在的无界自旋。等待取消不能获取锁直到节点成功的插入lock 队列,因此必须自旋
等待 signalling thread 执行cas 插入CLH队列成功. 这里很少需要自旋, 占用一个线程. 这里使用了
Thread.yield让出取消节点的线程的CPU时间片。理想情况下正好被signal线程轮转到，那么显然自旋很
快就会结束.虽然可以实现一些策略来帮助解决取消节点的自旋,但是这种情形太少见了,没有多大意义,
反而会增加些额外的消耗. 在其他任何情形下，都不会有自旋或yield，所以在单核的情况下能够保证
不错的性能。
复制代码

4. 使用(USAGE)

Class "AbstractQueuedSynchronizer"使用模板方法，试图将上述功能综合在一起作为同步器的基类,
子类只需要实现"state"的检查和更新操作来控制acquire和release即可. 但是这些子类不直接继承aqs,
aqs不能作为同步器ADTs, aqs对外开放了内部控制acquire和release的方法, 不应该让这些类对用户可见。
所有的JUC同步器声明了private内部aqs子类并将所有同步方法委托给它。
复制代码

例如，这里有一个最小的"Mutex"类, state 0 表示unlocked, 1 表示locked。

class Mutex {
  class Sync extends AbstractQueuedSynchronizer {
    public boolean tryAcquire(int ignore) {
      return compareAndSetState(0, 1);
    }
    public boolean tryRelease(int ignore) {
      setState(0); return true;
    }
  }
  private final Sync sync = new Sync();
  public void lock() { sync.acquire(0); }
  public void unlock() { sync.release(0); }
}

    此示例的完整版本以及其他使用指南可以在J2SE文档中找到。当然，有一些变体。例如，tryAcquire可以使用
"test-and-test-and-set". 在cas之前检查一遍.
复制代码

test-and-test-and-set: TTAS自旋锁算法

令人惊讶的是，互斥锁这样对"performance-sensitive"的同步器居然使用"delegation"和"virtual"的方式
来实现。这些是现代动态编译器长期关注的"OO"设计结构, 他们会优化掉这类开销, 尤其是这些使用频繁的同步器。
复制代码

OO: 面向对象

delegation 委派：一个对象请求另一个对象的功能，捕获一个操作并将其发送到另一个对象

virtual 虚拟: 是C语言的虚方法相当于java的抽象方法。例如tryAcquire, 子类需要重写

performance-sensitive: 性能敏感

aqs 提供了各种帮助同步器控制同步的策略。例如: acquire方法包括timeout&interruptible两种版本。
aqs 提供了 "exclusive-mode" 和 "share-mode". share-mode 可以在并且可以通过"cascading signals"
唤醒多个等待的线程
复制代码

cascading signals 级联信号：级联（cascade）在计算机科学里指多个对象之间的映射关系，建立数据之间的级联关系提高管理效率。aqs的级联信号是, 节点状态 static final int PROPAGATE = -3; 当前节点状态为PROPAGATE,下一个节点无条件唤醒。

虽然序列化(永久存储 或 传输)同步器是不明智的,但这些类常被用来构造其他类。例如线程安全的集合,他们
通常需要序列化。
    aqs ConditionObject classes 提供序列化"同步状态"的方法, 但是没有序列化阻塞队列和瞬时状态.大部分
"同步器"反序列化时都重置"同步状态"到初始值,这与"build-in monitor"的反序列化策略一致：总是反序列化到
未锁状态。这相当于"no-op", 但必须显示支持, 为了final field的反序列化.
复制代码

no-op:代表没有操作. 是一个汇编指令,占据很少的空间但是不做任何操作。

4.1 公平性 Controlling Fairness

参考资料: m.aliyun.com/yunqi/artic…

即使同步器是先进先出队列,但不一定公平。注意基本的acquire算法(章节3.3),tryAcquire
在入队前检查&执行.如果恰好在解锁时有一个线程tryAcquire, 会"steal(窃取)"队首的访问权限
复制代码

steal：窃取. 窃取访问,更充分的使用临界区,但会造成饥饿

这种"barging FIFO"策略通常比其他技术提供更高的总吞吐量.在release期间允许Acquire获取锁, 
减少整体时间.同时,release时它只唤醒队首的线程避免过多的、无益的争用。
复制代码

争用: 多个线程同时访问同一数据（内存区域）,其中一次是修改操作

如果传入的线程到达的速度快于unpark唤醒线程的速度, 队首赢得竞争的机会很小, 会导致几乎总是
再次阻塞. 对于"briefly-held"同步器, 在第一个线程唤醒期间，多处理器上通常会发生多个bargings
和release. 净效应来看, barging策略维持了一个或多条线程的高速率, 一定概率上避免了饥饿.
复制代码

净效应: 一个经济行为可能会产生正的效应和负的效应,净效应是两者相抵以后的效应. 在文本中可以理解为综上所述 briefly-held：瞬间持有, 指持有锁的时间非常短远小于从阻塞状态到被唤醒所消耗的时间.

当有更高的公平性需求时，实现起来也很简单。如果需要严格的公平性，程序员可以把tryAcquire方法定义为，若当
前线程不是队列的头节点（可通过getFirstQueuedThread方法检查，这是框架提供的为数不多的几个检测方法之一）,
则立即失败（返回false）。
一个快一些但不太严格的变体若队列为空，允许tryAcquire执行成功。这种情况下多个线程同时遇到会去竞争以便使
自己第一个获得锁，此时，通常至少有一个线程无需入队, 所有JUC同步器都采用这种公平策略.
复制代码

'JLS' 不提供这样对公平性的调度保证,只能用户自己实现。即使是严格公平的同步器，若一组线程不使用阻塞，JVM会
按照自己的调度规则运行这些线程("JVM线程调度").在单核处理器中线程运行完一个时间片后会切换上下文。如果有一
条线程持有锁,只有等它释放锁并唤醒下一个等待节点.在这条线程在执行完任务,不再需要锁但是还没释放的时候有可能
被切换,因为是公平策略,只能等这条线程再次运行释放锁然后唤醒等待队列中的下一个节点。因此JVM线程调度无形之中
增加了锁的空闲时间。
同步器公平模式在多核处理器系统架构往往产生更大影响. 如果是8核, 8等1,
复制代码

JLS：Java Language Specification,java语言规范 docs.oracle.com/javase/spec…

uniprocessor: 单核处理器

JVM线程调度: 抢占式调度，每个线程将由系统来分配执行时间，线程的切换不由线程本身来决定（Java中，可以通过Thread.yield()让出执行时间，但无法获取执行时间）。线程执行时间系统可控，也不会有一个线程导致整个进程阻塞。

尽管公平锁在'briefly-held'的'高争用'的场景下,表现糟糕。也有公平锁表现良好的时候，例如当它们保护相对较长的
代码体和/或互锁间隔长时，这种情况下barging带来的提神很少,反而会增加"饥饿"的风险。用户可以根据具体场景选择
适合的"同步器"类型。
复制代码

briefly-held: 锁都在极短的时间间隔下被持有（高频率的使用锁）

高争用: 相关的深度好文 www.sohu.com/a/232590588… 锁不慢；锁竞争慢

4.2 同步器 Synchronizers

这一章节是简介了 J.U.C中哪些同步器使用了aqs框架:

ReentrantLock 可重入锁 : 使用同步状态(state) 记录线程递归调用锁的次数。获得锁时记录当前线程id,以便递归计数和
试图解锁时检查线程为当前线程。这个类也使用了ConditionObject, 和其他监测和检验方法。提供公平和非公平(默认)模式,
可用于替代同步关键字(synchronizer)

ReentrantReadWriteLock 可冲入读写锁: 使用同步状态其中16bits维护写锁计数, 另外16bits维护读锁。WriteLock类似于
ReentrantLock, ReadLock 使用acquireShared 方法支持多读

Semaphore: 使用同步状态计数, 使用acquireShared 减少计数, 若state <= 0则线程阻塞, 使用 tryRelease
增加计数(如果释放后计数为整数)唤醒等待节点

CountDownLatch: 使用同步状态表示计数。当计数到达零，所有线程同时释放锁执行之后的代码

FutureTask(jdk 1.8中没使用aqs):  使用同步变量表示Future的运行状态(初始、运行、取消、完成)。调用get()使用park
阻塞调用线程. 当运行状态转变为 取消|完成, 任务完成状态唤醒阻塞线程。

SynchronousQueue: "CSP-style handoff", 线程间同步对象。使用内部等待节点匹配生产者消费者, 它使用同步状态
允许一个生产者在一个消费者消费了对象之后继续生产下一个对象，反之亦然。

用户可以使用J.U.C自定义同步器.例如:很多曾经被考虑过但是没有被采纳进J.U.C的类，它们提供了与 
WIN32 events, binary latches, centrally managed locks, and tree-based barriers 类似的语义和功能。
复制代码