idea java文件叉子

硬件趋势推动编程习惯

语言，库和框架决定了我们编写程序的方式。 即使Alonzo Church在1934年表明，所有已知的计算框架在它们可以表示的程序集中都是等效的，但真正的程序员实际编写的程序集是由编程模型（由语言，库和语言驱动）构成的。框架-易于表达。

反过来，当今的主流硬件平台决定了我们创建语言，库和框架的方式。 从第一天开始，Java语言就已经支持线程和并发。 该语言包括同步原语（例如synchronized和volatile ，类库包括类（如Thread 。 但是，1995年明智的并发原语反映了当时的硬件现实：大多数商用系统根本不提供并行性，甚至最昂贵的系统也仅提供有限的并行性。 在那些日子里，线程主要用于表示异步 ，而不是并发 ，因此，这些机制通常足以满足当时的需求。

随着多处理器系统变得越来越便宜，利用它们提供的硬件并行性需要更多的应用程序，并且程序员发现使用语言和类库提供的低级原语编写并发程序既困难又容易出错。 在Java 5中，将java.util.concurrent包添加到Java平台，为构建并发应用程序提供了一组有用的组件：并发集合，队列，信号量，锁存器，线程池等。 这些机制非常适合具有较粗粒度任务的程序。 应用程序只需要对工作进行分区，以使并发任务的数量始终不少于可用处理器的（少量）数量。 使用单个请求的处理作为Web服务器，邮件服务器或数据库服务器中的工作单元，应用程序通常可以满足该要求，因此这些机制足以保持适度并行硬件的充分利用。

展望未来，硬件趋势十分明显。 摩尔定律不会提供更高的时钟速率，而是每个芯片提供更多的内核。 很难想象，如何使用诸如用户请求之类的粗粒度任务边界使十几个处理器繁忙，但是这种技术无法扩展到数千个处理器-流量在短时间内可能呈指数增长，但最终硬件趋势胜出。 随着我们进入多核时代，即使有很多工作要做，我们也将需要找到更细粒度的并行性，否则就有使处理器空闲的风险。 随着主要硬件平台的变化，如果我们希望跟上潮流，软件平台也必须随之变化。 为此，Java 7将包括一个用于表示一类更细粒度的并行算法的框架 ： fork-join框架 。

暴露更细粒度的并行性

今天，大多数服务器应用程序都将用户请求-响应处理作为其工作单元。 服务器应用程序运行的并发线程或请求通常比可用处理器多得多。 原因是因为在大多数服务器应用程序中，对请求的处理包括相当数量的I / O，这并不需要太多的处理器。 （所有网络服务器应用程序都执行大量的套接字I / O，因为通过套接字接收到请求；许多应用程序也执行相当数量的磁盘（或数据库）I / O。）如果每个任务都花费90％的时间等待要完成I / O，需要并发任务数量是处理器的10倍，才能充分利用处理器。 随着处理器数量的增加，可能没有足够的并发请求来保持所有处理器繁忙。 但是，仍然可以使用并行性来改进另一种性能指标：用户必须等待获得响应的时间。

作为典型网络服务器应用程序的示例，请考虑数据库服务器。 当请求到达数据库服务器时，它将经历一系列阶段。 首先，对SQL语句进行解析和验证。 然后必须选择一个查询计划。 对于复杂的查询，数据库服务器可以评估许多不同的候选计划，以最大程度地减少预期的I / O操作数。 搜索查询计划可能是一项占用大量CPU的任务。 在某个时候，考虑更多的候选计划将达到负回报点，但是评估太少的候选计划几乎肯定会比需要的I / O多。 从磁盘检索数据后，可能需要对所得数据集进行更多处理； 查询可能包含诸如SUM或AVERAGE之类的聚合操作，或者可能需要对数据集进行排序。 然后，必须对结果进行编码并将其返回给请求者。

与大多数服务器请求一样，处理SQL查询涉及计算和I / O的混合。 没有多少额外的CPU功能可以减少完成I / O所需的时间（尽管您可以使用额外的内存通过缓存先前I / O操作的结果来减少I / O的数量），但是可以缩短通过并行处理请求处理的CPU密集型部分（例如计划评估和排序）所花费的时间。 在评估候选查询计划时，可以同时评估不同的计划。 在对数据集进行排序时，可以将大数据集分解为较小的数据集，分别进行并行排序，然后合并。 这样做可以改善用户对性能的感知（即使可能需要执行更多的工作才能满足请求），因为结果接收速度更快。

分而治之

合并排序是分而治之算法的一个示例，该算法将问题递归分解为子问题，然后将子问题的解决方案组合起来以得出最终结果。 分而治之算法通常在顺序环境中很有用，但在并行环境中可能变得更加有效，因为子问题通常可以同时解决。

典型的并行分治算法采用清单1所示的形式：

清单1.通用分治式并行算法的伪代码

// PSEUDOCODE Result solve(Problem problem) { if (problem.size < SEQUENTIAL_THRESHOLD) return solveSequentially(problem); else { Result left, right; INVOKE-IN-PARALLEL { left = solve(extractLeftHalf(problem)); right = solve(extractRightHalf(problem)); } return combine(left, right); } }

并行分治算法的第一件事是评估问题是否很小，以至于顺序解决方案会更快。 通常，这是通过将问题大小与某个阈值进行比较来完成的。 如果问题足够大，可以并行分解，则将问题分为两个或多个子问题，然后在子问题上并行地递归调用自身，等待子问题的结果，然后组合结果。 在顺序执行和并行执行之间进行选择的理想阈值取决于协调并行任务的成本。 如果协调成本为零，那么大量细粒度的任务往往会提供更好的并行性； 协调成本越低，在需要切换到顺序方法之前，我们可以做得越细。

叉连接

清单1中的示例使用了不存在的INVOKE-IN-PARALLEL操作； 它的行为是当前任务被挂起，两个子任务并行执行，并且当前任务等待直到它们完成。 然后，可以将两个子任务的结果合并。 这种并行分解通常称为fork-join，因为执行任务会分叉 （启动）多个子任务，然后将其与 （等待完成） 联接 。

清单2显示了一个适用于fork-join解决方案的问题示例：在大型数组中搜索其最大元素。 当然，这是一个非常简单的示例，但是fork-join技术适用于各种搜索，排序和数据分析问题。

清单2.从大数组中选择一个最大元素

public class SelectMaxProblem { private final int[] numbers; private final int start; private final int end; public final int size; // constructors elided public int solveSequentially() { int max = Integer.MIN_VALUE; for (int i=start; i<end; i++) { int n = numbers[i]; if (n > max) max = n; } return max; } public SelectMaxProblem subproblem(int subStart, int subEnd) { return new SelectMaxProblem(numbers, start + subStart, start + subEnd); } }

请注意， subproblem()方法不会复制元素。 它仅将数组引用和偏移量复制到现有数据结构中。 这是fork-join问题实现的典型情况，因为递归划分问题的过程将创建大量潜在的新Problem对象。 在这种情况下，搜索任务根本不会修改要搜索的数据结构，因此无需维护每个任务的基础数据集的私有副本，因此无需招致额外的复制开销。

清单3演示了使用fork-join包针对SelectMaxProblem的解决方案，该包计划包含在Java 7中。该包由JSR 166专家组使用代码名称jsr166y公开开发，您可以单独下载并使用它。 Java 6或更高版本。 （它将最终存在于包java.util.concurrent.forkjoin 。） invoke-in-parallel操作是由coInvoke()方法实现的，该方法同时调用多个动作并等待所有动作完成。 ForkJoinExecutor与Executor相似，它是为运行任务而设计的，除了它专门为计算密集型任务设计的，这些任务不会等待另一个由同一ForkJoinExecutor处理的任务而阻塞。

fork-join框架支持ForkJoinTasks几种样式，包括需要显式完成和循环执行的样式。 这里使用的RecursiveAction类直接支持无结果任务的并行递归分解样式。 RecursiveTask类针对结果任务执行相同的问题。 （其他fork-join任务类包括CyclicAction ， AsyncAction和LinkedAsyncAction ；有关如何使用它们的更多详细信息，请参见Javadoc。）

清单3.使用fork-join框架解决select-max问题

public class MaxWithFJ extends RecursiveAction { private final int threshold; private final SelectMaxProblem problem; public int result; public MaxWithFJ(SelectMaxProblem problem, int threshold) { this.problem = problem; this.threshold = threshold; } protected void compute() { if (problem.size < threshold) result = problem.solveSequentially(); else { int midpoint = problem.size / 2; MaxWithFJ left = new MaxWithFJ(problem.subproblem(0, midpoint), threshold); MaxWithFJ right = new MaxWithFJ(problem.subproblem(midpoint + 1, problem.size), threshold); coInvoke(left, right); result = Math.max(left.result, right.result); } } public static void main(String[] args) { SelectMaxProblem problem = ... int threshold = ... int nThreads = ... MaxWithFJ mfj = new MaxWithFJ(problem, threshold); ForkJoinExecutor fjPool = new ForkJoinPool(nThreads); fjPool.invoke(mfj); int result = mfj.result; } }

表1显示了在各种系统上选择500,000个元素数组的最大元素并更改阈值的结果，在该阈值下，顺序版本比并行版本优先。 对于大多数运行，fork-join池中的线程数等于可用的硬件线程数（核心数乘以每核心线程数）。 数字表示为相对于该系统上的顺序版本的加速。

表1.在各种系统上的500k元素阵列上运行select-max的结果

阈值= 500k 阈值= 50k 阈值= 5k 阈值= 500 阈值= -50 奔腾4 HT（2线程） 1.0 1.07 1.02 .82 .2 双至强HT（4线程） .88 3.02 3.2 2.22 .43 8路Opteron（8线程） 1.0 5.29 5.73 4.53 2.03 8核Niagara（32个线程） .98 10.46 17.21 15.34 6.49

结果令人鼓舞，因为它们在各种参数上均显示出良好的加速效果。 因此，只要您避免为问题或底层硬件选择完全不合理的参数，就可以在不做任何调整的情况下获得良好的结果。 对于芯片多线程技术，尚不清楚最佳的加速应该是多少。 显然，诸如超线程之类的CMT方法提供的性能要比同等数量的实际内核要低，但是到底有多少是取决于广泛的因素，包括所执行代码的缓存未命中率。

此处选择的顺序阈值范围从500K（阵列的大小，实际上没有并行性）到50。在这种情况下，顺序阈值50很好地进入了“小得可笑”的范围，结果表明，该值很低顺序阈值，管理fork-join任务的开销占主导。 但是它们确实表明，只要避免使用“高得离谱”和“低得离谱”的参数，就可以在不进行调整的情况下获得良好的结果。 选择Runtime.availableProcessors()作为工作线程的数量通常会提供接近最佳的结果，因为在fork-join池中执行的任务被认为是CPU绑定的，但是同样地，结果对这个参数的影响也是如此之久因为您避免将池的大小设置得太大或太小。

MaxWithFJ类中不需要显式同步。 在问题的整个生命周期中，其所操作的数据都是恒定的，并且ForkJoinExecutor内部具有足够的内部同步，以确保问题数据对子任务可见，并确保子任务结果对与之相连的任务可见。

fork-join框架的剖析

清单3中所示的fork-join框架可以通过多种方式实现。 使用原始线程是可能的。 Thread.start()和Thread.join()提供所有必要的功能。 但是，此方法可能需要更多的线程，而不是VM可以支持的线程。 对于N的问题大小（假设顺序阈值非常小），将需要O（N）个线程来解决该问题（问题树的深度为log ₂ N ，深度为k的二叉树具有2 ^k个节点）。 而且，其中一半人将花一生时间等待子任务完成。 线程创建和使用大量内存的成本很高，从而使该方法望而却步。 （虽然可以使用这种方法，但是代码更加复杂，并且需要非常仔细地调整问题大小和硬件的参数。）

使用常规线程池来实现fork-join也是一个挑战，因为fork-join任务的大部分生命都在等待其他任务。 这种行为是导致线程饥饿死锁的秘诀，除非精心选择参数以限制创建的任务数或池本身不受限制。 常规线程池是为彼此独立的任务而设计的，并且在设计时还考虑了潜在的阻塞，粗粒度的任务-fork-join解决方案不会产生任何结果。 常规线程池中的细粒度任务还会对所有工作线程之间共享的任务队列产生过多争用。

偷工作

fork-join框架通过使用一种称为工作窃取的技术来减少对工作队列的争用。 每个工作线程都有其自己的工作队列，该工作队列使用双端队列或deque实现 。 （Java 6中增加了几个双端队列实现的类库，包括ArrayDeque和LinkedBlockingDeque ）。当任务派生一个新的线程，它推送到自己的双端队列的头。 当一个任务执行与另一个尚未完成的任务的联接操作时，而不是Hibernate直到目标任务完成（如Thread.join()那样）时，它将另一个任务弹出其双端队列的头部并执行该任务。 如果线程的任务队列为空，则它将尝试从另一个线程的双端队列的尾部窃取另一个任务。

可以使用标准队列来实现工作窃取，但是使用双端队列比标准队列有两个主要优点：减少争用和减少窃取。 因为只有工作线程访问过自己的双端队列的头部，所以永远不会争用双端队列的头部。 因为双端队列的尾部仅在线程耗尽时才被访问，所以几乎没有争用任何线程双端队列的尾部。 （合并到fork-join框架中的双端队列实现利用这些访问模式来进一步降低协调成本。）与传统的基于线程池的方法相比，这种争用的减少大大降低了同步成本。 此外，这种方法所隐含的任务的后进先出（LIFO）顺序意味着最大的任务位于双端队列的末尾，因此，当另一个线程必须窃取任务时，它将窃取较大的任务可以分解为较小的物品，从而减少了在不久的将来再次偷窃的需求。 因此，工作窃取可产生合理的负载平衡，而无需集中协调，并且同步成本最低。

摘要

fork-join方法提供了一种表达可并行化算法的便携式方法，而无需事先知道目标系统将提供多少并行性。 各种排序，搜索和数值算法都可以并行分解。 （将来，诸如Arrays.sort()类的标准库机制可能会成为fork-join框架的使用者，从而允许应用程序免费获得并行分解的某些好处。）随着处理器数量的不断增加，我们将需要公开我们程序中固有的更多并行性，以有效利用这些处理器； 诸如排序之类的计算密集型活动的并行分解使程序更容易利用明天的硬件。

---

翻译自: https://www.ibm.com/developerworks/java/library/j-jtp11137/index.html