Fork/Join

1. 什么是Fork/Join框架

Fork/Join框架是Java7提供了的一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。

我们再通过Fork和Join这两个单词来理解下Fork/Join框架，Fork就是把一个大任务切分为若干子任务并行的执行，Join就是合并这些子任务的执行结果，最后得到这个大任务的结果。比如计算1+2+。。＋10000，可以分割成10个子任务，每个子任务分别对1000个数进行求和，最终汇总这10个子任务的结果。

 

2. 工作窃取算法

工作窃取（work-stealing）算法是指某个线程从其他队列里窃取任务来执行。工作窃取的运行流程图如下：

 

那么为什么需要使用工作窃取算法呢？假如我们需要做一个比较大的任务，我们可以把这个任务分割为若干互不依赖的子任务，为了减少线程间的竞争，于是把这些子任务分别放到不同的队列里，并为每个队列创建一个单独的线程来执行队列里的任务，线程和队列一一对应，比如A线程负责处理A队列里的任务。但是有的线程会先把自己队列里的任务干完，而其他线程对应的队列里还有任务等待处理。干完活的线程与其等着，不如去帮其他线程干活，于是它就去其他线程的队列里窃取一个任务来执行。而在这时它们会访问同一个队列，所以为了减少窃取任务线程和被窃取任务线程之间的竞争，通常会使用双端队列，被窃取任务线程永远从双端队列的头部拿任务执行，而窃取任务的线程永远从双端队列的尾部拿任务执行。

工作窃取算法的优点是充分利用线程进行并行计算，并减少了线程间的竞争，其缺点是在某些情况下还是存在竞争，比如双端队列里只有一个任务时。并且消耗了更多的系统资源，比如创建多个线程和多个双端队列。

 

3. Fork/Join框架的介绍

我们已经很清楚Fork/Join框架的需求了，那么我们可以思考一下，如果让我们来设计一个Fork/Join框架，该如何设计？这个思考有助于你理解Fork/Join框架的设计。

第一步分割任务。首先我们需要有一个fork类来把大任务分割成子任务，有可能子任务还是很大，所以还需要不停的分割，直到分割出的子任务足够小。

第二步执行任务并合并结果。分割的子任务分别放在双端队列里，然后几个启动线程分别从双端队列里获取任务执行。子任务执行完的结果都统一放在一个队列里，启动一个线程从队列里拿数据，然后合并这些数据。

Fork/Join使用两个类来完成以上两件事情：

• ForkJoinTask：我们要使用ForkJoin框架，必须首先创建一个ForkJoin任务。它提供在任务中执行fork()和join()操作的机制，通常情况下我们不需要直接继承ForkJoinTask类，而只需要继承它的子类，Fork/Join框架提供了以下两个子类：
• RecursiveAction：用于没有返回结果的任务。
• RecursiveTask ：用于有返回结果的任务。
• ForkJoinPool ：ForkJoinTask需要通过ForkJoinPool来执行，任务分割出的子任务会添加到当前工作线程所维护的双端队列中，进入队列的头部。当一个工作线程的队列里暂时没有任务时，它会随机从其他工作线程的队列的尾部获取一个任务。

 

 

 

引言

通常，当你实现一个简单的并发应用程序，你实现一些Runnable对象和相应的 Thread对象。在你的程序中，你控制这些线程的创建、执行和状态。Java 5引入了Executor和ExecutorService接口及其实现类进行了改进（比如：ThreadPoolExecutor类）。

执行者框架将任务的创建与执行分离。有了它，你只要实现Runnable对象和使用Executor对象。你提交Runnable任务给执行者，它创建、管理线程来执行这些任务。

 

 

 

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

查看源代码

打印

帮助

Result solve(Problem problem) {

    if (problem is small)

        directly solve problem

        else {

            split problem into independent parts

            fork new subtasks to solve each part

            join all subtasks

            compose result from subresults

        }

}

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

 

 

 

 

2.1Work−Stealing

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

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

 

使用后进先出——LIFO用来处理每个工作线程的自己任务，但是使用先进先出——FIFO规则用于获取别的任务，这是一种被广泛使用的进行递归fork/join设计的一种调优手段。引用[5]讨论了详细讨论了里面的细节。

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

 

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