06-并发Fork-join框架原理解析 图灵学院- forkjoin-short

Fork join实战及原理解析 讲师介绍 荀彧 北京大学博士担任一线互联网公司技术总监参与GitHub多个Java开源软件研发熟悉Java生态体系框架主导200 节点大数据平台建设 背景介绍 从并发到并行 Fork join编程介绍 目录 Fork join最佳实践 Fork join原理分析 硬件的飞速发展 摩尔定律由英特尔 Intel 创始人之一戈登 摩尔 GordonMoore 提出来的集成电路上可容纳的元器件的数目 约每隔18 24个月便会增加一倍 性能也将提升一倍 摩尔定律失效 FreeLunchIsOver 硬件的飞速发展 CPU主频在2003年时就开始停止增长摩尔定律仍然有效晶体管集成度仍然每18 24个月翻倍但是 是给更多的核 core 而不是更快 硬件的飞速发展 按照摩尔定律 CPU核数的发展应如红色线所示但是实际上是蓝色线所示对企业级服务器对于一些消费芯片则更少实际上 芯片厂商是可以生产这些多核的处理器的 为什么不了 因为软件没有准备好 硬件的发展也驱动着软件的发展 对Java而言 对Concurrency Parallelism支持的不断完善 明显地体现了这一点 Java1支持threads locks conditionqueues Java5引入了threadpools blockingqueues concurrentcollections Java7加入了fork join库 Java8加入了parallelstreams 2个概念 ConcurrencyvsParallelism 目标都是最大化CPU的使用率并发可认为是一种程序的逻辑结构的设计模式可以用并发的设计方式去设计模型 然后运行在一个单核系统上可以将这种模型不加修改地运行在多核系统上 实现真正的并行并行是程序执行的一种属性 真正的同时执行 或发生 2个概念 ConcurrencyvsParallelism ConcurrencyisaboutcorrectlyandefficientlycontrollingaccesstosharedresourcesExample constructingthread safedatastructuresPrimitives Locks events semaphores coroutines STMParallelismisaboutusingadditionalresourcestoproduceananswerfasterExample searchingalargedatasetbypartitioning FromConcurrenttoParallel 从一道面试题说起 随着在硬件上多核处理器的发展和广泛使用 并发编程成为程序员必须掌握的一门技术在面试中也经常考查面试者并发相关的知识 如何充分利用多核CPU 计算很大数组中所有整数的和 JavaExecutor框架 Java1 5中引入了Executor框架实现计算逻辑与执行逻辑分离提供了基于ThreadPool的Executor的实现 是否能够满足需求了 从一道面试题说起 单线程相加多线程 线程池 其他 从一道面试题说起 多线程 多线程 线程池 ans0ans1 ansNans Demo SumMultiThreads 从一道面试题说起 递归分解 一种更好的方式 程序如何实现了 从一道面试题说起 递归分解 是否正确 Demo SumRecursiveMT 从一道面试题说起 递归分解 为什么不能正确运行 Demo SumRecursiveMT 1 100 1 50 51 100 1 25 1 12 Thread1 Thread2 Thread3 TaskN Thread4 分治法 DivideandConquer 基本思想 把一个规模大的问题划分为规模较小的子问题 然后分而治之 最后合并子问题的解得到原问题的解 步骤 分割原问题 求解子问题 合并子问题的解为原问题的解 在分治法中 子问题一般是相互独立的 因此 经常通过递归调用算法来求解子问题 分治法典型应用 1 二分搜索 2 大整数乘法 3 Strassen矩阵乘法 4 棋盘覆盖 5 合并排序 6 快速排序 7 线性时间选择 8 汉诺塔 Fork Join并行处理框架 Java1 7引入了一种新的并发框架 Fork JoinFramework主要用于实现 分而治之 的算法 特别是分治之后递归调用的函数提供了的一个用于并行执行任务的框架 是一个把大任务分割成若干个小任务 最终汇总每个小任务结果后得到大任务结果的框架与ThreadPool共存 并不是要替换ThreadPool Fork Join并行处理框架 Java8parallelStream Listnumbers Arrays asList 1 2 3 4 5 6 7 8 9 numbers parallelStream forEach out println 内部就是采用ForkJoinPool 背景介绍 从并发到并行 Fork join编程介绍 目录 Fork join最佳实践 Fork join原理分析 Fork Join并行处理框架 ForkJoinPool框架主要类 ForkJoinPool实现ForkJoin的线程池 ThreadPoolForkJoinWorkerThread实现ForkJoin的线程ForkJoinTask一个描述ForkJoin的抽象类Runnable CallableRecursiveAction无返回结果的ForkJoinTask实现RunnableRecursiveTask有返回结果的ForkJoinTask实现CallableCountedCompleter在任务完成执行后会触发执行一个自定义的钩子函数 Fork Join并行处理框架 ForkJoinPool实现了ExecutorService接口ExecutorService是JavaExecutor框架的基础类其他ExecutorService的实现执行Runnable或Callables任务ForkJoinPool执行ForkJoinTasks任务 Fork Join并行处理框架 ForkJoinPool实现了ExecutorService接口ExecutorService是JavaExecutor框架的基础类其他ExecutorService的实现执行Runnable或Callables任务ForkJoinPool执行ForkJoinTasks任务Executors newWorkStealPool创建ForkJoinPool ForkJoinPool任务提交方法 ForkJoinTask ForkJoinTask封装了数据及其相应的计算支持细粒度的数据并行ForkJoinTask比线程要轻量ForkJoinPool中少量工作线程能够运行大量的ForkJoinTask ForkJoinTask ForkJoinTask主要包括两个方法分别实现任务的分拆与合并 fork 类似于Thread start 但是它并不立即执行任务 而是将任务放入工作队列中跟Thread join 不同 ForkJoinTask的join 方法并不简单的阻塞线程利用工作线程运行其他任务当一个工作线程中调用join 它将处理其他任务 直到注意到目标子任务已经完成 ForkJoinTask ForkJoinTask有3个子类 RecursiveAction无返回值的任务RecursiveTask有返回值的任务CountedCompleter完成任务后将触发其他任务 背景介绍 从并发到并行 Fork join编程介绍 目录 Fork join最佳实践 Fork join原理分析 ForkJoin内部原理 ForkJoinPool中的所有的工作线程均有一个自己的工作队列WorkQueue双端队列 Deque 从队头取任务线程私有 不共享 ForkJoin内部原理 ForkJoinTask中fork的子任务 将放入运行该任务的工作线程的队头工作线程以LIFO的顺序来处理它队列中的任务 ForkJoin内部原理 为了最大化CPU利用率 空闲的线程将从其他线程的队列中 窃取 任务来执行从工作队列的队尾 窃取 任务 以减少竞争任务的 窃取 是以FIFO顺序进行的 因为先放入的任务往往表示更大的工作量支持 窃取 线程进行进一步的递归分解 ForkJoin内部原理 WorkQueue双端队列最小化任务 窃取 的竞争push pop 仅在其所有者工作线程中调用这些操作都是通过CAS来实现的 是Wait free的poll 则由其他工作线程来调用 窃取 任务可能不是wait free ForkjoinvsMapReduce 单机vs分布式 背景介绍 从并发到并行 Fork join编程介绍 目录 Fork join最佳实践 Fork join原理分析 Fork Join最佳实践 最适合的是计算密集型的任务在需要阻塞工作线程时 可以使用ManagedBlocker 是否内联方法IfoneoftheFJThreadshastoblock anewthreadcanbestartedtotakeitsplace不应该在RecursiveTask的内部使用ForkJoinPool invoke 37 SophomoricParallelismandConcurrency Lecture1 5 3 6 2 7 4 8 1 3 2 4