Java Fork Join 框架（三）实现

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf

作者：Doug Lea  译者：Alex  校对：方腾飞

这个框架是由大约800行纯Java代码组成，主要的类是FJTaskRunner，它是java.lang.Thread的子类。FJTasks 自己仅仅维持一个关于结束状态的布尔值，所有其他的操作都是通过当前的工作线程来代理完成的。JFTaskRunnerGroup类用于创建工作线程，维护一些共享的状态（例如：所有工作线程的标示符，在偷取操作时需要），同时还要协调启动和关闭。

更多实现的细节文档可以在util.concurrent并发包中查看。这一节只着重讨论两类问题以及在实现这个框架的时候所形成的一些解决方案：支持高效的双端列表操作（push, pop 和 take）， 并且当工作线程在尝试获取新的任务时维持偷取的协议。

3.1双端队列

（校注：双端队列中的元素可以从两端弹出，其限定插入和删除操作在队列的两端进行。）

为了能够获得高效以及可扩展的执行任务，任务管理需要越快越好。创建、发布、和弹出（或者出现频率很少的获取）任务在顺序编程模式中会引发程序调用开销。更低的开销可以使得程序员能够构建更小粒度的任务，最终也能更好的利用并行所带来的益处。

Java虚拟机会负责任务的内存分配。Java垃圾回收器使我们不需要再去编写一个特殊的内存分配器去维护任务。相对于其他语言的类似框架，这个原因使我们大大降低了实现FJTasks的复杂性以及所需要的代码数。

双端队列的基本结构采用了很常规的一个结构——使用一个数组（尽管是可变长的）来表示每个队列，同时附带两个索引：top 索引就类似于数组中的栈指针，通过push和pop操作来改变。Base 索引只能通过take操作来改变。鉴于FJTaskRunner操作都是无缝的绑定到双端队列的细节之中，（例如，fork直接调用push），所以这个数据结构直接放在类之中，而不是作为一个单独的组件。

但是双端队列的元素会被多线程并发的访问，在缺乏足够同步的情况下，而且单个的Java数组元素也不能声明为volitile变量（校注：声明成volatile的数组，其元素并不具备volatile语意），每个数组元素实际上都是一个固定的引用，这个引用指向了一个维护着单个volitile引用的转发对象。一开始做出这个决定主要是考虑到Java内存模型的一致性。但是在这个级别它所需要的间接寻址被证明在一些测试过的平台上能够提升性能。可能是因为访问邻近的元素而降低了缓存争用，这样内存里面的间接寻址会更快一点。

实现双端队列的主要挑战来自于同步和他的撤销。尽管在Java虚拟机上使用经过优化过的同步工具，对于每个push和pop操作都需要获取锁还是让这一切成为性能瓶颈。然后根据以下的观察结果我们可以修改Clik中的策略，从而为我们提供一种可行的解决方案：

• Push和pop操作仅可以被工作线程的拥有者所调用。
• 对Take的操作很容易会由于偷取任务线程在某一时间对take操作加锁而限制。（双端队列在必要的时间也可以禁止take操作。）这样，控制冲突将被降低为两个部分同步的层次。
• Pop和take操作只有在双端队列为空的时候才会发生冲突，否则的话，队列会保证他们在不同的数组元素上面操作。

把top和base索引定义为volitile变量可以保证当队列中元素不止一个时，pop和take操作可以在不加锁的情况下进行。这是通过一种类似于Dekker算法来实现的。当push 预递减到top时:

If (–top >=base)…

和take 预递减到 base时:

If(++base < top)…

在上述每种情况下他们都通过比较两个索引来检查这样是否会导致双端队列变成一个空队列。一个不对称的规则将用于防止潜在的冲突：pop会重新检查状态并在获取锁之后继续（对take所持有的也一样），直到队列真的为空才退出。而Take操作会立即退出，特别是当尝试去获得另外一个任务。与其他类似使用Clik的THE协议一样，这种不对称性是唯一重要的改变。

使用volitile变量索引push操作在队列没有满的情况下不需要同步就可以进行。如果队列将要溢出，那么它首先必须要获得队列锁来重新设置队列的长度。其他情况下，只要确保top操作排在队列数组槽盛在抑制干涉带之后更新。

在随后的初始化实现中，发现有好几种JVM并不符合Java内存模型中正确读取写入的volitile变量的规则。作为一个工作区，pop操作在持有锁的情况下重试的条件已经被调整为：如果有两个或者更少的元素，并且take操作加了第二把锁以确保内存屏障效果，那么重试就会被触发。只要最多只有一个索引被拥有者线程丢失这就是满足的，并且只会引起轻微的性能损耗。

3.2 抢断和闲置

在抢断式工作框架中，工作线程对于他们所运行的程序对同步的要求一无所知。他们只是构建、发布、弹出、获取、管理状态和执行任务。这种简单的方案使得当所有的线程都拥有很多任务需要去执行的时候，它的效率很高。然而这种方式是有代价的，当没有足够的工作的时候它将依赖于试探法。也就是说，在启动一个主任务，直到它结束，在有些fork/join算法中都使用了全面停止的同步指针。

主要的问题在于当一个工作线程既无本地任务也不能从别的线程中抢断任务时怎么办。如果程序运行在专业的多核处理器上面，那么可以依赖于硬件的忙等待自旋循环的去尝试抢断一个任务。然而，即使这样，尝试抢断还是会增加竞争，甚至会导致那些不是闲置的工作线程降低效率（由于锁协议，3.1节中）。除此之外，在一个更适合此框架运行的场景中，操作系统应该能够很自信的去运行那些不相关并可运行的进程和线程。

Java中并没有十分健壮的工作来保证这个，但是在实际中它往往是可以让人接受的。一个抢断失败的线程在尝试另外的抢断之前会降低自己的优先级，在尝试抢断之间执行Thread.yeild操作，然后将自己的状态在FJTaskRunnerGroup中设置为不活跃的。他们会一直阻塞直到有新的主线程。其他情况下，在进行一定的自旋次数之后，线程将进入休眠阶段，他们会休眠而不是放弃抢断。强化的休眠机制会给人造成一种需要花费很长时间去划分任务的假象。但是这似乎是最好的也是通用的折中方案。框架的未来版本也许会支持额外的控制方法，以便于让程序员在感觉性能受到影响时可以重写默认的实现。