- 浏览: 1871474 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
July01:
最近了解到一款StratoIO打印控件,功能如下:1、Html ...
jquery打印指定的div -
GentlemanQc:
...
quartz系列(二)spring3.2.5与quartz2.1.7集群版集成简要说明 -
静夜独窗:
你好,能说一下server.xml增加的配置是怎么影响性能的吗 ...
tomcat7.0性能优化-挑战极限精简版 -
beyondfengyu:
beyondfengyu 写道如果每个客户进程的时间不同步,时 ...
java并发(二十二)分布式锁 -
beyondfengyu:
如果每个客户进程的时间不同步,时间超前的进程是不是更容易得到锁 ...
java并发(二十二)分布式锁
如果让我个人理解什么是fork-join,我立刻会想到hadoop的map/reduce。他们是同一种模型。更早之前,笔者就看过关于fork-join的相关文章,但是理解的都不够深刻。自从深入研究了java多线程这块的相关技术,再回头来看fork-join,觉得真是个了不起的技术。
概述
fork/join框架是ExecutorService接口的一种具体实现,目的是为了帮助你更好地利用多处理器带来的好处。它是为那些能够被递归地拆解成子任务的工作类型量身设计的。其目的在于能够使用所有可用的运算能力来提升你的应用的性能。
类似于ExecutorService接口的其他实现,fork/join框架会将任务分发给线程池中的工作线程。fork/join框架的独特之处在与它使用工作窃取(work-stealing)算法。完成自己的工作而处于空闲的工作线程能够从其他仍然处于忙碌(busy)状态的工作线程处窃取等待执行的任务。 fork/join框架的核心是ForkJoinPool类,它是对AbstractExecutorService类的扩展。ForkJoinPool实现了工作偷取算法,并可以执行ForkJoinTask任务。
Divide and conquer
合并排序是 divide-and-conquer 算法的一个例子,在这种算法中将一个问题递归分解成子问题,再将子问题的解决方案组合得到最终结果。 divide-and-conquer 算法也可用于顺序环境中,但是在并行环境中更加有效,因为可以并行处理子问题。
并行 divide-and-conquer 算法首先对问题进行评估,确定其大小是否更适合使用顺序解决方案;通常,可通过将问题大小与某个阙值进行比较完成。如果问题大到需要并行分解,算法会将其分解成两个或更多子问题,并以并行方式对子问题递归调用算法本身,然后等待子问题的结果,最后合并这些结果。用于选择顺序和并行执行方法的理想阙值是协调并行任务的成本。如果协调成本为 0,更多的更细粒度的任务会提供更好的并行性;在需要转向顺序方法之前,协调成本越低,就可以划分更细粒度的任务。
递归(旧的方法)
如果从一个数组中,选一个最大值。我一般都会采用递归调用。这样的话只有当前线程的一个方法是运行的,其他方法都阻塞在线程栈中。所以在多核情况下,其他CPU都是空闲,没有得到充分利用。
并行计算(fork-join)
类似hadoop的map/reduce,可以将任务拆分成多个块,然后最终将这些子结果集合并成最终结果集。它的行为表现为当前任务是暂停的,并行执行两个子任务,而当前任务等待两个子任务的完成。然后就可以将两个子任务的结果进行合并。这种并行分解方法常常称作 fork-join,因为执行一个任务将首先分解(fork)为多个子任务,然后再合并(join)(完成后)。
使用fork/join框架的第一步是编写执行一部分工作的代码。你的代码结构看起来应该与下面所示的伪代码类似:
示例代码如下:求
工作窃取
fork-join 框架通过一种称作工作窃取(work stealing) 的技术减少了工作队列的争用情况。每个工作线程都有自己的工作队列,这是使用双端队列(或者叫做 deque)来实现的(Java 6 在类库中添加了几种 deque 实现,包括 ArrayDeque 和 LinkedBlockingDeque)。当一个任务划分一个新线程时,它将自己推到 deque 的头部。当一个任务执行与另一个未完成任务的合并操作时,它会将另一个任务推到队列头部并执行,而不会休眠以等待另一任务完成(像 Thread.join() 的操作一样)。当线程的任务队列为空,它将尝试从另一个线程的 deque 的尾部 窃取另一个任务。
可以使用标准队列实现工作窃取,但是与标准队列相比,deque 具有两方面的优势:减少争用和窃取。因为只有工作线程会访问自身的 deque 的头部,deque 头部永远不会发生争用;因为只有当一个线程空闲时才会访问 deque 的尾部,所以也很少存在线程的 deque 尾部的争用(在 fork-join 框架中结合 deque 实现会使这些访问模式进一步减少协调成本)。跟传统的基于线程池的方法相比,减少争用会大大降低同步成本。此外,这种方法暗含的后进先出(last-in-first-out,LIFO)任务排队机制意味着最大的任务排在队列的尾部,当另一个线程需要窃取任务时,它将得到一个能够分解成多个小任务的任务,从而避免了在未来窃取任务。因此,工作窃取实现了合理的负载平衡,无需进行协调并且将同步成本降到了最小。
标准实现
除了能够使用fork/join框架来实现能够在多处理系统中被并行执行的定制化算法(如前文中的ForkBlur.java例子),在Java SE中一些比较常用的功能点也已经使用fork/join框架来实现了。在Java SE 8中,java.util.Arrays类的一系列parallelSort()方法就使用了fork/join来实现。这些方法与sort()系列方法很类似,但是通过使用fork/join框架,借助了并发来完成相关工作。在多处理器系统中,对大数组的并行排序会比串行排序更快。这些方法究竟是如何运用fork/join框架并不在本教程的讨论范围内。想要了解更多的信息,请参见Java API文档。 其他采用了fork/join框架的方法还包括java.util.streams包中的一些方法,此包是作为Java SE 8发行版中Project Lambda的一部分。想要了解更多信息,请参见Lambda Expressions一节。
参考资料
http://www.ibm.com/developerworks/cn/java/j-jtp11137.html
嗯,有点像是map reduce。
那个例子是jdk的吗,反正我感觉很眼熟,但是在这个fork-join上我没看明白。。。因为fib计算是依赖的,我没仔细琢磨,正常来说每个f(n)都依赖于前两个,所以你并行计算没意义了。
但是查找这种就是另外的情况了。
好的,我换个别的例子改造一下, 感谢支持
概述
fork/join框架是ExecutorService接口的一种具体实现,目的是为了帮助你更好地利用多处理器带来的好处。它是为那些能够被递归地拆解成子任务的工作类型量身设计的。其目的在于能够使用所有可用的运算能力来提升你的应用的性能。
类似于ExecutorService接口的其他实现,fork/join框架会将任务分发给线程池中的工作线程。fork/join框架的独特之处在与它使用工作窃取(work-stealing)算法。完成自己的工作而处于空闲的工作线程能够从其他仍然处于忙碌(busy)状态的工作线程处窃取等待执行的任务。 fork/join框架的核心是ForkJoinPool类,它是对AbstractExecutorService类的扩展。ForkJoinPool实现了工作偷取算法,并可以执行ForkJoinTask任务。
Divide and conquer
合并排序是 divide-and-conquer 算法的一个例子,在这种算法中将一个问题递归分解成子问题,再将子问题的解决方案组合得到最终结果。 divide-and-conquer 算法也可用于顺序环境中,但是在并行环境中更加有效,因为可以并行处理子问题。
并行 divide-and-conquer 算法首先对问题进行评估,确定其大小是否更适合使用顺序解决方案;通常,可通过将问题大小与某个阙值进行比较完成。如果问题大到需要并行分解,算法会将其分解成两个或更多子问题,并以并行方式对子问题递归调用算法本身,然后等待子问题的结果,最后合并这些结果。用于选择顺序和并行执行方法的理想阙值是协调并行任务的成本。如果协调成本为 0,更多的更细粒度的任务会提供更好的并行性;在需要转向顺序方法之前,协调成本越低,就可以划分更细粒度的任务。
递归(旧的方法)
如果从一个数组中,选一个最大值。我一般都会采用递归调用。这样的话只有当前线程的一个方法是运行的,其他方法都阻塞在线程栈中。所以在多核情况下,其他CPU都是空闲,没有得到充分利用。
并行计算(fork-join)
类似hadoop的map/reduce,可以将任务拆分成多个块,然后最终将这些子结果集合并成最终结果集。它的行为表现为当前任务是暂停的,并行执行两个子任务,而当前任务等待两个子任务的完成。然后就可以将两个子任务的结果进行合并。这种并行分解方法常常称作 fork-join,因为执行一个任务将首先分解(fork)为多个子任务,然后再合并(join)(完成后)。
使用fork/join框架的第一步是编写执行一部分工作的代码。你的代码结构看起来应该与下面所示的伪代码类似:
if (当前这个任务工作量足够小) 直接完成这个任务 else 将这个任务或这部分工作分解成两个部分 分别触发(invoke)这两个子任务的执行,并等待结果
示例代码如下:求
import java.util.concurrent.ForkJoinPool; import java.util.concurrent.RecursiveTask; /** * @author piaohailin * @date 2014-3-26 */ public class Fibonacci extends RecursiveTask<Long> { private static final long serialVersionUID = 7875142223684511653L; private final long n; Fibonacci(long n) { this.n = n; } protected Long compute() { if (n <= 1) { return n; } Fibonacci f1 = new Fibonacci(n - 1); f1.fork(); Fibonacci f2 = new Fibonacci(n - 2); return f2.compute() + f1.join(); } public static void main(String[] args) { Fibonacci task = new Fibonacci(10); ForkJoinPool pool = new ForkJoinPool(4); pool.invoke(task); System.out.println(task.getRawResult()); } }
工作窃取
fork-join 框架通过一种称作工作窃取(work stealing) 的技术减少了工作队列的争用情况。每个工作线程都有自己的工作队列,这是使用双端队列(或者叫做 deque)来实现的(Java 6 在类库中添加了几种 deque 实现,包括 ArrayDeque 和 LinkedBlockingDeque)。当一个任务划分一个新线程时,它将自己推到 deque 的头部。当一个任务执行与另一个未完成任务的合并操作时,它会将另一个任务推到队列头部并执行,而不会休眠以等待另一任务完成(像 Thread.join() 的操作一样)。当线程的任务队列为空,它将尝试从另一个线程的 deque 的尾部 窃取另一个任务。
可以使用标准队列实现工作窃取,但是与标准队列相比,deque 具有两方面的优势:减少争用和窃取。因为只有工作线程会访问自身的 deque 的头部,deque 头部永远不会发生争用;因为只有当一个线程空闲时才会访问 deque 的尾部,所以也很少存在线程的 deque 尾部的争用(在 fork-join 框架中结合 deque 实现会使这些访问模式进一步减少协调成本)。跟传统的基于线程池的方法相比,减少争用会大大降低同步成本。此外,这种方法暗含的后进先出(last-in-first-out,LIFO)任务排队机制意味着最大的任务排在队列的尾部,当另一个线程需要窃取任务时,它将得到一个能够分解成多个小任务的任务,从而避免了在未来窃取任务。因此,工作窃取实现了合理的负载平衡,无需进行协调并且将同步成本降到了最小。
标准实现
除了能够使用fork/join框架来实现能够在多处理系统中被并行执行的定制化算法(如前文中的ForkBlur.java例子),在Java SE中一些比较常用的功能点也已经使用fork/join框架来实现了。在Java SE 8中,java.util.Arrays类的一系列parallelSort()方法就使用了fork/join来实现。这些方法与sort()系列方法很类似,但是通过使用fork/join框架,借助了并发来完成相关工作。在多处理器系统中,对大数组的并行排序会比串行排序更快。这些方法究竟是如何运用fork/join框架并不在本教程的讨论范围内。想要了解更多的信息,请参见Java API文档。 其他采用了fork/join框架的方法还包括java.util.streams包中的一些方法,此包是作为Java SE 8发行版中Project Lambda的一部分。想要了解更多信息,请参见Lambda Expressions一节。
参考资料
http://www.ibm.com/developerworks/cn/java/j-jtp11137.html
评论
5 楼
flashing
2014-03-28
85977328 写道
另外性能开销在fork上,join上没什么开销,只是取结果而已,虽然看上去是阻塞,其实关键的计算消耗是在fork上。合并结果的消耗并不是很大
不过fork-join用法实在太多了,比如数据库查询结果合并
不过fork-join用法实在太多了,比如数据库查询结果合并
嗯,有点像是map reduce。
那个例子是jdk的吗,反正我感觉很眼熟,但是在这个fork-join上我没看明白。。。因为fib计算是依赖的,我没仔细琢磨,正常来说每个f(n)都依赖于前两个,所以你并行计算没意义了。
但是查找这种就是另外的情况了。
4 楼
85977328
2014-03-28
另外性能开销在fork上,join上没什么开销,只是取结果而已,虽然看上去是阻塞,其实关键的计算消耗是在fork上。合并结果的消耗并不是很大
不过fork-join用法实在太多了,比如数据库查询结果合并
不过fork-join用法实在太多了,比如数据库查询结果合并
3 楼
85977328
2014-03-28
不过这个例子,是官方JAVADOC里带的,我就拿过来改造了一下,给用上了
2 楼
85977328
2014-03-28
flashing 写道
这个文章我看了两遍,最后看了一下developworks的原文才明白。
楼主选了个非常不好的例子,Fibonacci是个结果依赖型的计算,fork join算法在这里意义不大。原文是对只读队列的并行二分查找,是个很合适的例子。
楼主选了个非常不好的例子,Fibonacci是个结果依赖型的计算,fork join算法在这里意义不大。原文是对只读队列的并行二分查找,是个很合适的例子。
好的,我换个别的例子改造一下, 感谢支持
1 楼
flashing
2014-03-28
这个文章我看了两遍,最后看了一下developworks的原文才明白。
楼主选了个非常不好的例子,Fibonacci是个结果依赖型的计算,fork join算法在这里意义不大。原文是对只读队列的并行二分查找,是个很合适的例子。
楼主选了个非常不好的例子,Fibonacci是个结果依赖型的计算,fork join算法在这里意义不大。原文是对只读队列的并行二分查找,是个很合适的例子。
发表评论
-
java并发(三十四)协程kilim
2015-10-02 11:29 5552概述 对协程的技术已经觊觎很久,他有高性能的优点,但目前工具对 ... -
java并发(三十三)栅栏CyclicBarrier
2015-09-12 16:09 3343如果说CountDownLatch(闭锁)是一次性的, ... -
java并发(三十二)非阻塞算法
2014-06-25 14:08 1290如果在某算法中,一个线程的失败或挂起不会导致其他线程也 ... -
java并发(三十一)Amdahl定律
2014-05-19 16:15 2168阿姆达尔定律 阿姆达尔(Amdahl)定律是计算机系统设计的重 ... -
java并发(三十)闭锁CountDownLatch
2014-05-07 23:33 869CountDownLatch,一个同步辅助类,在完成一组正在其 ... -
java并发(二十九)构建高效且可伸缩的结果缓存
2014-04-23 11:52 1047概述 几乎所有应用程序,都会使用某种形式的缓存。重用之 ... -
java并发(二十八)并发随机数,原子变量,并发集合
2014-04-13 12:04 4048原子变量 java.util.concurrent.a ... -
java并发(二十七) 并发性标注
2014-04-07 10:49 8945一介绍 <dependency> < ... -
java并发(二十六)正确使用Volatile变量
2014-03-30 19:41 1354概述 您只能在有限的一 ... -
java并发(二十四)多线程结果组装
2014-03-24 22:01 3883本文主要介绍多线程的 ... -
java并发(二十三)阻塞、非阻塞、同步、异步
2014-03-14 17:01 1406因为中文语意的问题, ... -
java并发(二十二)分布式锁
2014-03-12 16:24 18614Redis有一系列的命令, ... -
java并发(二十一)剖析同步器
2014-03-11 18:03 1170虽然许多同步器(如锁,信号量,阻塞队列等)功能上各不相同,但它 ... -
java并发(二十)线程池
2014-03-10 15:02 3859基本介绍 线程池(Thread Pool)对于限制应用程序中同 ... -
java并发(十九)阻塞队列
2014-03-10 14:46 1321阻塞队列与普通队列的 ... -
java并发(十八)信号量
2014-03-10 14:03 1225Semaphore(信号量) 是一个线程同步结构,用于在线程间 ... -
java并发(十七)重入锁死
2014-03-10 11:33 1093重入锁死与死锁和嵌套管程锁死非常相似。当一个线程重新获取锁,读 ... -
java并发(十六)Java中的读/写锁
2014-03-10 10:17 1169相比Java中的锁(Locks in Ja ... -
java并发(十五)Java中的锁
2014-03-09 12:07 926锁像synchronized同步块一样,是一种线程同步机制,但 ... -
java并发(十四)Slipped Conditions
2014-03-09 11:28 1034所谓Slipped conditions,就 ...
相关推荐
Java并发Fork-Join框架原理
Java并发编程学习宝典(漫画版),Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习...
介绍了ForkJoin并发框架,供有java基础者学习,工作配合使用,附件带有PPT,介绍并发与并行区别,和ForkJoin代码范例,资源来自网络,分享分享!
全书分为9章,涵盖了线程管理、线程同步、线程执行器、Fork/Join框架、并发集合、定制并发类、测试并发应用等内容。全书通过60多个简单而非常有效的实例,帮助读者快速掌握Java 7多线程应用程序的开发技术。学习完...
Java 语言从一开始能够支持线程和并发性;该语言包括像 synchronized 和 volatile 这样的同步原语,而类库包含像 Thread 这样的类。然而,1995 年流行的并发原语反映了当时的硬件现状:大多数商用系统根本没有提供...
全书分为9章,涵盖了线程管理、线程同步、线程执行器、Fork/Join框架、并发集合、定制并发类、测试并发应用等内容。全书通过60多个简单而非常有效的实例,帮助读者快速掌握Java7多线程应用程序的开发技术。学习完...
《Java学习指南(第4版)(上、下册)》加入了从Java 6和Java 7发布以后的变化,包括新的语言功能、并发工具(Fork-Join框架)、新的NIO Files API、Java Servlet(3.0)等新主题,作者通过精心挑选的、富有实用性和趣味性...
第45节Fork/Join框架详解00:28:09分钟 | 第46节同步容器与并发容器00:18:44分钟 | 第47节并发容器CopyOnWriteArrayList原理与使用00:15:52分钟 | 第48节并发容器ConcurrentLinkedQueue原理与使用00:31:03分钟 | ...
ForkJoin框架详解.mp4 同步容器与并发容器.mp4 并发容器CopyOnWriteArrayList原理与使用.mp4 并发容器ConcurrentLinkedQueue原理与使用.mp4 Java中的阻塞队列原理与使用.mp4 实战:简单实现消息队列.mp4 并发容器...
例如,通过讲解线程池、Future模式、Fork/Join框架等,帮助读者解决复杂的并发问题,提高系统的响应能力和吞吐量。此外,书中还深入剖析了并发编程中的常见问题,如死锁、活锁、饥饿等,并提供了相应的解决方案和...
聊聊并发系列文章 1. 聊聊并发(一)深入分析Volatile的实现原理 2. 聊聊并发(二)Java SE1.6中...8. 聊聊并发(八)Fork/Join框架介绍 9. 聊聊并发(九)Java中的CopyOnWrite容器 10. 聊聊并发(十)生产者消费者模式
Java高并发相关知识点包括: 线程:Java多线程的实现方式,包括继承...并行计算:Java中的并行计算,包括Fork/Join框架、并行流等。 线程间通信:Java中的线程间通信,包括wait()、notify()、notifyAll()等方法。
第45节Fork/Join框架详解00:28:09分钟 | 第46节同步容器与并发容器00:18:44分钟 | 第47节并发容器CopyOnWriteArrayList原理与使用00:15:52分钟 | 第48节并发容器ConcurrentLinkedQueue原理与使用00:31:03分钟 | ...
Java并发编程的4种风格:Threads,Executors,ForkJoin和Actors 我们生活在一个事情并行发生的世界。自然地,我们编写的程序也反映了这个特点,它们可以并发的执行。当然除了Python代码(译者注:链接里面讲述...
OpenMP(C),ForkJoin(JAVA)和Disruptor(JAVA)质数查找器这是我做过的最有趣的并发程序包之一。 目标保持不变:在输入数组中查找素数。... 该解决方案随附JAVA 7和ForkJoin框架。 可以将其视为一种方法调用结构
JAVA并发编程-2-线程并发工具类一、Fork/Join1、分而治之与工作密取2、使用标准范式3、Fork/Join的同步用法4、Fork/Join的异步用法二、CountDownLatch三、CyclicBarrier四、Semaphore信号量五、Exchanger ...
第45节Fork/Join框架详解00:28:09分钟 | 第46节同步容器与并发容器00:18:44分钟 | 第47节并发容器CopyOnWriteArrayList原理与使用00:15:52分钟 | 第48节并发容器ConcurrentLinkedQueue原理与使用00:31:03分钟 | ...
一、 Fork/Join框架的介绍 21 1、实现步骤: 22 2、工作窃取算法 22 3、分而治之 23 4、Fork/Join使用的标准范式 24 5、Fork/Join框架的异常处理 26 6、Fork/Join框架的实现原理 26 二、闭锁CountDownLatch 28 1、...