java7中的fork-join
的基本思想就是创立线程池然后试图进行Work Stealing
:
所以任务的创建和线程的触发顺序就显得比较微妙而需要额外小心线程同步的问题,若子任务无返回值,尽量使用invorkAll
方法。也可以参考源码中invokeAll
的使用方法学习fork
、invork
和join
的使用规范:
1 | /** |
输入为两个任务的源码例子:
1 | /** |
两个任务的时候也是先fork t2->invork t1->join t2
这样的流程。
fork操作是把任务放入workQueue
的尾部(push
):
1 | public final ForkJoinTask<V> fork() { |
join操作:
1 | /** |
综上所述,整个标准的调用流程应该是先反序fork
(除了第一个任务),把任务(this)放入队列尾部,调用第一个任务,再顺序join
(也除了第一个任务)。
下面是一个比较复杂、具体的求double
数组平方和的过程。恰当的组织可以让运算保持分而治之的理念,而不是仅仅只是递归。
1 |
|
Applyer
作为一个RecursiveAction
,从最初的一个Applyer(array, 0, n, null)
,分裂为多个任务,放置于任务列表中,空闲的工作线程从列表中取出任务运行compute
方法,计算一个叶节点后, 优先再去寻找右边的叶节点进行计算,若靠右的叶节点们先结束运算,再去任务列表中窃取任务进行计算。
其中getSurplusQueuedTaskCount
方法用于判断当前过剩的任务数量,例如当工作线程数量为10
,而划分的任务数量为14
,则不会有空闲的线程来进行任务窃取,大家都很忙,所以就没必要继续划分任务了。反之,若有空闲的工作线程,而且任务足够大,则应该先把任务划分一下,以方便其他空闲线程窃取自己的任务,加快所有任务的完成。
compute
函数第一个while
循环先对任务数量和当前工作线程数量进行权衡,如果过剩的任务数量小于3,则进行二分。一直到任务数量足够了,跳出循环。使用atLeaf()
函数直接计算(l,f)
范围内的平方和。
计算完当前叶节点的任务后,检查右边叶节点的任务是否被其他线程窃取。若被窃取了则等待其完成,反之则自己计算该任务。然后继续往右遍历任务。
所有任务分布在树的叶节点上,并且以链表的形式串联起来,以便相互窃取任务。(注意到由于线程的工作速度不同,叶节点的深度很可能不是一致的。)
参考:
[1] http://www.molotang.com/articles/694.html
[2] http://www.iteye.com/topic/643724 (其中fork和join用法不符合jdk源码使用规范)