Doug Lea 关于Java 7引入的他写的Fork/Join框架的论文

0. 摘要

这个框架通过（递归的）把问题划分为子任务，然后并行的执行这些子任务，等所有的子任务都结束的时候，再合并最终结果的这种方式来支持并行计算编程。就设计层面来说主要是围绕如何高效的去构建和管理任务队列以及工作线程来展开的。

1. 简介

Fork/Join并行方式是获取良好的并行计算性能的一种最简单同时也是最有效的设计技术。
Fork/Join并行算法是我们所熟悉的分治算法的并行版本，典型的用法如下：

fork将会启动一个新的并行 Fork/Join子任务
join会一直等待直到所有的子任务都结束。
Fork/Join算法，如同其他分治算法一样，总是会递归的、反复的划分子任务，直到这些子任务可以用足够简单的、短小的顺序方法来执行。

2. 设计

Fork/Join程序可以在任何支持以下特性的框架之上运行：框架能够让构建的子任务并行执行，并且拥有一种等待子任务运行结束的机制。
然而，java.lang.Thread类（同时也包括POSIX pthread，这些也是Java线程所基于的基础）对Fork/Join程序来说并不是最优的选择：

• Fork/Join任务对同步和管理有简单的和常规的需求。相对于常规的线程来说，Fork/Join任务所展示的计算布局将会带来更加灵活的调度策略。例如，Fork/Join任务除了等待子任务外，其他情况下是不需要阻塞的。因此传统的用于跟踪记录阻塞线程的代价在这种情况下实际上是一种浪费。
• 对于一个合理的基础任务粒度来说，构建和管理一个线程的代价甚至可以比任务执行本身所花费的代价更大。尽管粒度是应该随着应用程序在不同特定平台上运行而做出相应调整的。但是超过线程开销的极端粗粒度会限制并行的发挥。

简而言之，Java标准的线程框架对Fork/Join程序而言太笨重了。但是既然线程构成了很多其他的并发和并行编程的基础，完全消除这种代价或者为了这种方式而调整线程调度是不可能（或者说不切实际的）。

尽管这种思想已经存在了很长时间了，但是第一个发布的能系统解决这些问题的框架是Cilk^[5]。Cilk和其他轻量级的框架是基于操作系统的基本的线程和进程机制来支持特殊用途的Fork/Join程序。这种策略同样适用于Java，尽管Java线程是基于低级别的操作系统的能力来实现的。创造这样一个轻量级的执行框架的主要优势是能够让Fork/Join程序以一种更直观的方式编写，进而能够在各种支持JVM的系统上运行。

FJTask框架是基于 Cilk设计的一种演变。框架采用和操作系统把线程映射到 CPU上相同的方式来把任务映射到线程上。只是他们会使用 Fork/Join程序的简单性、常规性以及一致性来执行这种映射。尽管这些框架都能适应不能形式的并行程序，他们优化了 Fork/Join的设计：

• 一组工作者线程池是准备好的。每个工作线程都是标准的（『重量级』）处理存放在队列中任务的线程（这地方指的是Thread类的子类FJTaskRunner的实例对象）。通常情况下，工作线程应该与系统的处理器数量一致。在Java中，虚拟机和操作系统需要相互结合来完成线程到处理器的映射。然后对于计算密集型的运算来说，这种映射对于操作系统来说是一种相对简单的任务。任何合理的映射策略都会导致线程映射到不同的处理器。
• 所有的Fork/Join任务都是轻量级执行类的实例，而不是线程实例。在Java中，独立的可执行任务必须要实现Runnable接口并重写run方法。在FJTask框架中，这些任务将作为子类继承FJTask而不是Thread，它们都实现了Runnable接口。（对于上面两种情况来说，一个类也可以选择实现Runnable接口，类的实例对象既可以在任务中执行也可以在线程中执行。因为任务执行受到来自FJTask方法严厉规则的制约，子类化FJTask相对来说更加方便，也能够直接调用它们。）
• 我们将采用一个特殊的队列和调度原则来管理任务并通过工作线程来执行任务。这些机制是由任务类中提供的相关方式实现的：主要是由fork、join、isDone（一个结束状态的标示符），和一些其他方便的方法，例如调用coInvoke来分解合并两个或两个以上的任务。
• 一个简单的控制和管理类（这里指的是FJTaskRunnerGroup）来启动工作线程池，并初始化执行一个由正常的线程调用所触发的Fork/Join任务（就类似于Java程序中的main方法）。

作为一个给程序员演示这个框架如何运行的标准实例，这是一个计算法斐波那契函数的类。

class Fib extends FJTask {
    static final int threshold = 13;
    volatile int number; // arg/result

    Fib(int n) {
        number = n;
    }

    int getAnswer() {
        if (!isDone())
            throw new IllegalStateException();
        return number;
    }

    public void run() {
        int n = number;
        if (n <= threshold) // granularity ctl
            number = seqFib(n);
        else {
            Fib f1 = new Fib(n - 1);
            Fib f2 = new Fib(n - 2);
            coInvoke(f1, f2);
            number = f1.number + f2.number;
        }
    }

    public static void main(String[] args) {
        try {
            int groupSize = 2; // for example
            FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize);
            Fib f = new Fib(35); // for example
            group.invoke(f);
            int result = f.getAnswer();
            System.out.println("Answer: " + result);
        } catch (InterruptedException ex) {
        }
    }

    int seqFib(int n) {
        if (n <= 1) return n;
        else return seqFib(n − 1) + seqFib(n − 2);
    }
}

在保持性能的同时这个程序仍然维持着Java多线程程序的可移植性。对程序员来说通常有两个参数值的他们关注

• 对于工作线程的创建数量，通常情况下可以与平台所拥有的处理器数量保持一致（或者更少，用于处理其他相关的任务，或者有些情况下更多，来提升非计算密集型任务的性能）
• 一个粒度参数代表了创建任务的代价会大于并行化所带来的潜在的性能提升的临界点。这个参数更多的是取决于算法而不是平台。通常在单处理器上运行良好的临界点，在多处理器平台上也会发挥很好的效果。作为一种附带的效益，这种方式能够与Java虚拟机的动态编译机制很好的结合，而这种机制在对小块方法的优化方面相对于单块的程序来说要好。这样，加上数据本地化的优势，Fork/Join算法的性能即使在单处理器上面的性能都较其他算法要好。

2.1 work−stealing

Fork/Join框架的核心在于轻量级调度机制。FJTask采用了Cilk的work-stealing所采用的基本调度策略：

• 每一个工作线程维护自己的调度队列中的可运行任务
• 队列以双端队列的形式被维护，不仅支持后进先出 —— LIFO的push和pop操作，还支持先进先出 —— FIFO的take操作
• 对于一个给定的工作线程来说，任务所产生的子任务将会被放入到工作者自己的双端队列中
• 工作线程使用后进先出 —— LIFO（最新的元素优先）的顺序，通过弹出任务来处理队列中的任务
• 当一个工作线程的本地没有任务去运行的时候，它将使用先进先出 —— FIFO的规则尝试随机的从别的工作线程中拿（『窃取』）一个任务去运行
• 当一个工作线程触及了join操作，如果可能的话它将处理其他任务，直到目标任务被告知已经结束（通过isDone方法）。所有的任务都会无阻塞的完成。
• 当一个工作线程无法再从其他线程中获取任务和失败处理的时候，它就会退出（通过yield、sleep和/或者优先级调整）并经过一段时间之后再度尝试直到所有的工作线程都被告知他们都处于空闲的状态。在这种情况下，他们都会阻塞直到其他的任务再度被上层调用。

使用LIFO处理每个工作线程自己的任务，使用FIFO获取别的任务，这是一种被广泛使用的进行递归Fork/Join设计的一种调优手段。

让窃取任务的线程从队列拥有者相反的方向进行操作会减少线程竞争。同样体现了递归分治算法的大任务优先策略。因此，更早期被窃取的任务有可能会提供一个更大的单元任务，从而使得窃取线程能够在将来进行递归分解。

作为上述规则的一个后果，对于一些基础的操作而言，使用相对较小粒度的任务比那些仅仅使用粗粒度划分的任务以及那些没有使用递归分解的任务的运行速度要快。尽管相关的少数任务在大多数的Fork/Join框架中会被其他工作线程窃取，但是创建许多组织良好的任务意味着只要有一个工作线程处于可运行的状态，那么这个任务就有可能被执行。

3. 实现

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

只着重讨论两类问题以及在实现这个框架的时候所形成的一些解决方案：支持高效的双端列表操作（push、pop和take）， 并且当工作线程在尝试获取新的任务时维持窃取的协议。

3.1 双端队列

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

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

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

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

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

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

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

把top和base索引定义为volatile变量可以保证当队列中元素不止一个时，pop和take操作可以在不加锁的情况下进行。这是通过一种类似于Dekker算法来实现的。当push预递减到top时：
if (–top >= base) ...
和take预递减到base时：
if(++base < top) ...
在上述每种情况下他们都通过比较两个索引来检查这样是否会导致双端队列变成一个空队列。一个不对称的规则将用于防止潜在的冲突：pop会重新检查状态并在获取锁之后继续（对take所持有的也一样），直到队列真的为空才退出。而take操作会立即退出，特别是当尝试去获得另外一个任务。

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

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

3.2 抢断和闲置

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

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

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