java Fork/Join框架的简单介绍

是什么?为什么?工作窃取算法

感谢:http://www.infoq.com/cn/articles/fork-join-introduction

 

一、是什么

1.Fork/Join框架是什么

Fork/Join框架是Java7提供的一个用于并行执行任务的框架。

Fork/Join框架可以一个把大任务分割成若干个小任务,最终汇总每个小任务的结果,最后得到大任务结果。

我们可以通过通过Fork和Join这两个单词来理解下Fork/Join框架:

Fork就是把一个大任务切分为若干子任务从而实现并发执行,Join就是合并这些子任务的执行结果,最后得到这个大任务的结果。

2.举个例子

尝试计算1+2+…..+10000(一个大任务),将其分割成10个子任务(大任务进行分割,成为若干子任务),每个子任务负责对1000个数进行求和(子任务并发执行,有各自的结果)。最终汇总这10个子任务的结果,就可以得到最终结果(处理子任务的结果)。

工作原理可以参看示意图:

666

二、为什么

Fork/Join框架是比现有的Executor框架更优秀的解决方案。主要区别在于是否使用了工作窃取算法,线程的利用方式不同。

(1)Executor框架的弊端:

有如下情景:

在一个主任务中创建一些子任务,并且必须保证子任务执行完毕,主任务才能继续执行。就像这样:

777

在这种情况下,执行主任务的线程需要分配更多的线程去执行子任务,然后自身进入等待状态,直到所有子任务都被执行完毕。

在等待期间,执行主任务的线程不执行任何任务,相当于线程资源被浪费,非常可惜。

(2)Fork/Join框架解决这一弊端:

Fork/Join使用了工作窃取算法。

需要等待子任务完成时(执行主任务的线程进入了阻塞状态),执行主任务的线程会去寻找并且执行其他未被执行的任务。这样可以最大化利用线程资源,从而提高应用程序的性能。

三、工作窃取算法

1.什么是工作窃取算法

工作窃取算法是指某个线程从其他队列里窃取任务来执行。

工作窃取的运行流程图如下:

666

2.为什么使用工作窃取算法?

假如我们需要做一个比较大的任务,我们可以把这个任务分割为若干互不依赖的子任务。

为了减少线程间的竞争,于是把这些子任务分别放到不同的队列里,并为每个队列创建一个单独的线程来执行队列里的任务。线程和队列一一对应,比如A线程负责处理A队列里的任务。

但是,有的线程会先把自己队列里的任务干完,而其他线程对应的队列里还有任务等待处理。干完活的线程与其等着,不如去帮其他线程干活,于是它就去其他线程的队列里窃取一个任务来执行。

在这时,两条线程会访问同一个队列。为了减少窃取任务的线程和被窃取的任务线程之间的竞争,通常会使用双端队列,被窃取任务的线程永远从双端队列的头部拿任务执行,而窃取任务的线程永远从双端队列的尾部拿任务执行。

3.工作窃取算法的优缺点

(1)工作窃取算法的优点:

1.充分利用线程资源

很少有处于等待状态的线程,提高了并发效率。

2.减少了线程间的竞争

有各自的任务队列,在执行完之前不会发生窃取,即不会发生线程间的竞争。

(2)工作窃取算法的缺点:

1.在某些情况下依然存在竞争

如果双端队列里只有一个任务,那么不同队列的线程就会竞争执行任务。

2.工作窃取算法消耗了更多的系统资源

比起简单地使用线程执行器执行任务,Fork/Join需要创建多个线程和多个双端队列。这些对象的创建、操作、管理都需要消耗更多的系统资源。

四、总结

本文偏向理论,下次加以实践。

发表评论

电子邮件地址不会被公开。 必填项已用*标注