J.U.C framework

gistfile1.txt

J.U.C并发框架（1）


翻译：书卷多情

在J2SE1.5中，java.util.concurrent包下的大部分同步工具（锁、阻塞等）以AbstractQueuedSynchronizer类为基础来构建。这个框架提供了一些常用机制用于自动管理并发状态、阻塞及非阻塞线程和队列。本论文描述了该框架的根源、设计实现、用法及性能。
关键字：synchronized, java

1、介绍
javatm发布的J2SE-1.5介绍了java.util.concurrent包，是一个通过JCP(Java Community Process)和JSR创建的一个支持中间并发类的集合。这些组件都是同步组件，由抽象数据类型（ADT）类来支持内部同步状态（比如：表示一个锁是locked还是unlocked状态），并更新及监控该状态，如果其他线程修改了状态并且状态允许，则根据该状态，至少有一个方法调用线程阻塞。例如：各种形式的互斥锁、读写锁、信号量、barriers、futures、事件指示器、及队列。
众所周知（见[2]），几乎所有的同步类可以用来实现对应的其他同步类，比如，我们有可能通过重置锁创建信号量，反过来了也可以通过信号量创建重置锁。然而，这么做是挺复杂，不方便工程开发使用。再进一步说，也无美感。如果他们之间没有本质的区别，对开发人员来说也是一场灾难，因为他们就需要从中任意选出一个出来，创建另一个同步对象。所以，JSR166建立了一个以AbstractQueuedSynchronizer为中心的小框架提供给开发人员。
2、要求
2.1 功能
同步通过两个办法来执行[7]：至少一个线程受到阻塞直到同步允许的获取锁操作，及至少一个修改同步状态、允许一个或多个线程进入非阻塞状态的释放锁操作。
J.U.C包没有去定义一个统一的同步API，有些是通过常用接口（如：Lock接口）定义的，但其他的则只包括了特定的版本。所以，不同的类中定义的获取锁和释放锁的方法名也不一样。比如，Lock.lock，Semaphore.acquire, CountDownLatch.await和FutureTask.get都表示的是获取操作。但也有一致的情况。每个同步类都具有：
*非阻塞同步（如tryLock）和阻塞同步
*可以选择最长等待时间，以便放弃等待
*可以取消的中断。要区分开可取消的中断和不可取消的中断
同步可以根据互斥还是共享状态来划分。互斥状态下，同步一次只允许一条线程执行，阻塞后，有可能还会是同一条线程继续执行。共享状态允许在某时间内多条线程执行。通常的锁当然持有的是互斥状态，但信号量可以允许某个数量的线程来执行。为了得到最广泛的应用，该框架使用了两种状态。
J.U.C包也定义Condition接口，支持监控await/signal操作，而在互斥的Lock类中，监控的是内置锁。
2.2 性能目标
java的内置锁（使用synchronized关键字来进行阻塞），长期以来大量受到关注的是关于性能方面。然而关注点都考虑在单核处理器上的单线程使用时，如何使占用的空间最小(因为每个java类都可以当做锁来使用)，及消耗的时间最短。这两种办法都没有关注到同步的重点，同步的重点是：程序员只有在需要的时候才创建同步，所以没必要因担心造成浪费而压缩空间，而在多线程的设计中（越来越多的机器采用多核处理器的情况下），使用互斥同步也仅仅只是偶尔现象。所以JVM的策略就是对锁在最初的无竞争条件下的优化。
相反，原始的性能目标是稳定性。可以预测维护效率，或者，特殊情况下考虑并发。理想状态下，至少有一个条件需要满足，就是不管有多少个线程，都要有一个并发点。而这些目标中的主要关键点就是让能够释放并发（锁）但是还没有释放的线程所响应的时间尽可能小。而这么做又要考虑资源分配，包括总CPU请求时间，存储路径、和线程调度响应时间。比如，自旋锁的请求时间通常比阻塞锁要短，但会浪费周期，消耗内存，所以不常应用。
（性能）目标通常考虑两种用途。很多应用应考虑最大化吞吐量、响应时间、最好还要避免线程饥饿。但在资源控制等应用中，更重要的是考虑减少线程吞吐量让线程能够公平的执行。在这些相互矛盾的目标中，没有一个框架可以决定用户的操作中到底倾向于哪一个，但必须要支持不同的公平策略。
不管他们内部设计得多么巧妙，并发在一些应用中都会产生一些瓶颈。因此，框架必须让用户能够监控内部基本操作，让用户发现和减少瓶颈。这种让瓶颈最小化的方法可以让用户决定允许多少个线程阻塞。
3、设计和实现
并发的基本思想还是比较直观的。一个获取操作如下：
while (并发状态不允许获取锁 {
如果当前线程没有入队，将当前线程入队；
可能阻塞当前线程；
}
如果当前线程在队列中，将当前线程出队；
释放操作如下：
更新并发状态
if (状态允许，允许一个阻塞线程获取锁)
将一个或多个阻塞线程进入非阻塞状态

这些操作需要3个基本条件：
1、	自动管理并发状态
2、	阻塞和唤醒线程
3、	维护FIFO队列

可以创建一个框架来独立实现这三个条件。但这么做可能不高效且无用。因为比如在队列中的结点的信息必须与需要释放阻塞结点进入非阻塞状态的结点信息相符合，提供的接口方法签名也要具有并发状态的特质。
并发框架设计的中心就是要选择一个这三者条件的具体实现，且能够在这三个方面有很大的选择使用范围。这样应用的范围会受到限制，但避免从新创建并发类，也提供了一个效率足够高的并发框架。

3.1 并发状态
AbstractQueuedSynchronizer 类维护并发状态只用一个32位的int类型，且提供getState, setState, 和compareAndSetState 三个方法来获取和更新状态， 这些方法反过来依赖于JSR133提供的volatile提供的读写语义，compareAndSet方法则是通过本地的compare-and-swap 或loadlinked/store-conditional 指令来实现， 这些方法原子性的将状态更新为一个给定的值。

将并发状态限定为32位的int是一个具有实际意义的决定.同时JSR166也提供64位的long类型的原子操作，类似于使用内部锁，但结果并不理想。将来它可能添加long类型的状态，会成为使用64位的状态的第二选择（也就是说long类型的控制参数）。但现在还不需要在包中添加这个类。当前32位已经足够绝大部分的应用使用的了。J.U.C包中只有一个类，CyclicBarrier 有可能会用到，所以它用锁代替（这也是在该包中其他使用更高位的类的方式）。

实现了AbstractQueuedSynchronizer 的具体的类必须定义tryAcquire和tryRelease方法，这两个方法提供状态方法接口，以便于控制获取和释放操作。如果并发获取了锁，tryAaquire必须返回true，如果更新以后的并发状态允许获取，tryRelease必须返回true。这两个方法只一个int型的参数来进行通信；如在reentrant lock中，当从一个等待条件队列中重新获取锁的时候，会重新建立递归相加。很多并发类不需要这个参数，所以会忽略它。

3.2 阻塞
在JSR166之前，还没有一个JAVA API提供给一个建立在不是内置锁的基础之上的阻塞和非阻塞线程算法。而唯一提供这个算法的Thread.suspend和Thread.resume方法以及被取消，因为会产生无法解决的竞争问题：如果一个非阻塞线程在阻塞线程执行suspend方法之前调用resume方法，那么这个resume操作无效。
java.util.concurrent.locks包包括一个LockSupport类，该类里有能够解决这个问题的方法。LockSupport.part只有在LockSupport.unpart以及执行的时候才会被调用。（也允许伪唤醒（？））。 调用unpart方法不会去计算（锁）。所以在一个park之前的多个unpark，只会释放一个park线程。而且，这是线程级别上的应用，而不是并发类级别上的应用。一个线程调用park，很可能由于前面调用了过多的unpark而立即得到相应。但在缺乏unpark的情况下，这个调用就会受到阻塞。所以需要确保这个（阻塞）状态的清除，但没必要这么做。如果需要的话，调用多次park还更加高效。

这个简单的机制类似于Solaris-9的线程，在win32下的“可消费事件”，以及linux的NPTL线程，运行效率也和java在这些平台上的运行效率一致。（但目前Sun Hotspot JVM在Solaris和Linux上的相关的实现是采用pthread condvar来实现，来满足运行时的设计要求）。park方法也提供一些可选参数支持过期，且和JVM的Thread.interrupt整合起来使用，来中断一个线程对它进行unpark.

3.3队列
该框架的核心维持的是一个阻塞线程的队列，在这里是FIFO队列。因此框架不提供优先级并发。
这些天来一直有争论的是，是否关于并发队列采用非阻塞式的数据结构是最适合的，这样他们就不需要自己创建低级别的锁。而且也有两个锁来直接使用：Mellor-Crummey和Scott(MCS)锁[9]，和Craig,Landin,Hagersten(CLH)锁[5][8][10]。以前CLH锁只用于自旋锁。但在并发框架中CLH锁比MCS锁更适用，因为在处理取消和超时操作上更容易，所以会选择CLH锁。讨论的结果就是从最初的CLH锁能够根据需求扩张进行更大范围的使用。

一个CLH队列不太像一个队列，因为入队和出队操作都和它作为一个锁的操作紧密相关。这是一个链接队列，head和tail两个字段进行原子性更新，他们最初都指向一个伪节点。

head	node的状态	tail






一个新的节点，node，会通过如下原子性操作入队：
do { pred = tail;
} while(!tail.compareAndSet(pred, node));

每个节点的释放状态都存储在它的前一个节点上，所以一个自旋锁的“自旋“就如下：
while (pred.status != RELEASED) ; // spin

这样自旋以后，出队操作就只要简单的把头节点设为获取锁的节点
head=node;
CLH锁的优点就是入队和出队操作快速、且非阻塞（即使在竞争条件下，一个线程总是会插入竞争中不断的执行）；检测到其他线程是否等待的过程也很快（只需要检测头节点和尾节点是否一样）；释放状态是分散的，避免了内存的竞争。

CLH锁的原始设计是没有链接节点的。在自旋锁中的pred以局部变量存储。但Scott和Scherer通过节点的前任节点持有状态来展示，CLH锁可以处理超时和其他形式的取消操作；如果一个节点的前任节点取消了，该节点可以使用前任节点的状态属性。

做阻塞式并发只需要有效的更新CLH队列，让它提供一个节点来指向它的后继者。自旋锁中，一个节点只需要更新它的状态，通过该状态告知后继节点准备自旋，所以不需要链接。但是在阻塞式并发中，一个节点需要明确唤醒（unpark）它的后继节点。
一个AQS队列节点包括一个next属性，指向它的后继者。但是因为没有实际的技术能够使无锁的双向链表能够使用compareAndSet进行原子性插入，所以该链表在插入的时候不是原子性的，只是简单的赋值：
pred.next=node;
这在反射中都会用到。next链接只是为了优化路径。如果一个节点通过next检测到没有后继节点（或者，后继节点被取消），它会反过来从尾节点向前遍历，使用pred看看是否是只有一个节点。
第二部分的更改就是使用每个节点里的status属性来控制阻塞，不是自旋。在并发框架下，一个线程队列只能从一个子类定义的tryAcquire方法中的获取操作返回；一个单一的“释放”位并不够。但控制也要确保调用tryAcquire的头节点线程是活的；在这种情况下它还是有可能会获取不到，然后重新阻塞。这不需要每个节点的状态标识因为只需要当前节点的前任节点是头节点就可以允许。这也不像自旋锁，自旋锁没有足够的内存空间读取头节点，但在状态属性中必须由取消状态。
队列节点状态属性页用于避免无用的park和unpark调用。这两个方法相对阻塞方式来说相当快，它避免了java和JVM运行时和OS的边界交互。调用park之前，一个线程设置了“signal me”位，之后在调用park之前重新检测一次并发和节点状态。一个释放线程去清除这个状态。这样就可以避免线程进行不必要的阻塞，特别是对于需要花费时间进行等待的锁来说。这也避免了请求一个释放线程来检测后继者，除非它的后继者设置了signal位，

CLH锁和其他语言下的锁不同的地方就是GC，对GC的依赖需要在出队的时候将节点设置为Null
其他更多的优化包括CLH队列的伪结点的延迟初始化，在J2SE1.5源代码文档中有。
忽略这些细节，获取操作的一般情况如下（不包括非中断式、非超时）：
if (!tryAcquire(arg)) {
node = create and enqueue new node;
pred = node's effective predecessor;
while (pred is not head node || !tryAcquire(arg)) {
if (pred's signal bit is set)
park();
else
compareAndSet pred's signal bit to true;
pred = node's effective predecessor;
}
head = node;
}
释放操作:
if (tryRelease(arg) && head node's signal bit is set) {
compareAndSet head's signal bit to false;
unpark head's successor, if one exists
}
主循环迭代的次数依赖于tryAcquire。否则，在没有取消操作的情况下，每个组件获取和释放操作都是常量时间 O(1)，分别计算线程相互之间的花费、不考虑park期间OS的线程调度。

可以取消操作只需要检测park内部的获取循环的中断或者超时。一个基于超时或中断的可取消线程设置它的节点属性并unpark它的后继节点，让后继节点可以重置链接。取消中的检测前任节点、后继节点和重置状态可能包括O(n)遍历（此处n是队列的长度）。因为线程永远不会阻塞一个取消操作，链接和状态属性可以快速恢复稳定。

3.4 条件队列
并发框架提供一个ConditionObject类来按照Lock接口维护互斥并发。一个锁对象中可以有很多个条件对象，提供经典的监控方法： await, signal 和signalAll操作，这些操作包括超时和监控内部方法。ConditionObject让条件对象和其他并发操作整合可以高效的执行，且调整了一些设计思路。这个类只支持java类型的监控原则，即只有锁持有着当前线程的条件才能够进行条件操作。因此，ReentrantLock中的ConditionObject的做法和内置监控锁是一样的（如Object.wait等）,只是方法名不同而已，这更实用，因为用户可以给每个锁加入若干个条件对象。

ConditionObject使用和其他并发对象一样的内置节点队列，但是维护的条件队列不同。signal队列的操作通过从条件队列迁移到锁队列来进行，不需要重新获取锁之前唤醒signal线程。
基本的等待操作是：
create and add new node to condition queue;
release lock;
block until node is on lock queue;
re-acquire lock;
signal操作是：
transfer the first node from condition queue to lock queue;

因为这些操作只有在持有锁的情况下才能进行，所以他们可以使用链接队列操作（使用节点上的nextWaiter属性）来维护条件队列。迁移操作指示简单的把条件队列的第一个节点释放掉，然后使用CHL捕获该节点并插入锁队列中。

实现这些操作比较复杂的是处理超时或者调用Thread.interrupt而引起的条件等待的取消。一个取消操作和获取信号操作在遇到竞争的时候花费的时间差不多，他们都要确认内置锁。在JSR133的修正版中，这些操作要求，如果一个中断发生在获取信号之前，那么await方法必须在重新获取锁之后抛出InterruptedException异常。但是如果在获取信号之后中断，那么await方法必须设置中断状态，直接返回，而不要抛出异常。
为了维护一个比较适合的顺序，队列节点状态记录了节点是否被移动。获取信号代码和取消代码都会通过compareAndSet来设置这个状态。如果一个获取信号操作没有能够在竞争中获取锁，如果还有下个节点的话，它会移动下个节点。如果取消操作失败，它必须放弃迁移，并且等待重新获取锁。后者也就是自旋无限循环的操作方法。一个取消了等待的线程不能进行获取锁操作，直到该节点成功插入锁队列，所以必须自旋等待获取信号线程成功的调用compareAndSet方法插入CHL队列中。因为自旋很少，所以使用Thread.yield来调度其他线程，理想的情况是一条线程获取信号，而不是直接运行。这样对取消插入节点就很有利，组织者情况下需要去确认插入的节点是否超标的情况极少。在其他的情况下，在单核处理器中为了维持性能，都不会使用自旋或者挂起。