---

Fork/Join

Java下多线程的开发可以我们自己启用多线程，线程池，还可以使用Fork/Join， Fork/Join可以让我们不去了解诸如Thread，Runnable等相关的知识，只要遵循Fork/Join的开发模式，就可以写出很好的多线程并发程序。

分而治之

Fork/Join在处理分而治之的问题中十分有用。

十大计算机经典算法：快速排序、堆排序、归并排序、二分查找、线性查找、 深度优先、广度优先、Dijkstra、动态规划、朴素贝叶斯分类，有3个属于分而治之，快速排序、归并排序、二分查找。

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小 的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同(子问题相互之间有联系就会变为动态规范算法)， 递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为 2-路归并，与之对应的还有多路归并。

对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大 的有序序列。

为了提升性能，有时我们在半子表的个数小于某个数（比如 15）的情况下， 对半子表的排序采用其他排序算法，比如插入排序。

归并排序(降序)示例

Fork/Join原理

工作密取

即当前线程的Task已经全被执行完毕，则自动取到其他线程的Task池中取出Task继续执行。

ForkJoinPool中维护着多个线程（一般为 CPU 核数）在不断地执行Task，每 个线程除了执行自己职务内的 Task之外，还会根据自己工作线程的闲置情况去获取其他繁忙的工作线程的Task，如此一来就能能够减少线程阻塞或是闲置的时间，提高CPU利用率。

Fork/Join实战

Fork/Join使用的标准范式

我们要使用ForkJoin框架，必须首先创建一个ForkJoin任务。它提供在任务 中执行fork和join的操作机制，通常我们不直接继承ForkjoinTask类，只需要直接继承其子类。

1. RecursiveAction，用于没有返回结果的任务。

2. RecursiveTask，用于有返回值的任务。

Task要通过ForkJoinPool来执行，使用submit或invoke提交，两者的区别是invoke是同步执行，调用之后需要等待任务完成，才能执行后面的代码； submit是异步执行。

join()和get()方法当任务完成的时候返回计算结果。

在我们自己实现的compute方法里，首先需要判断任务是否足够小，如果足够小就直接执行任务。如果不足够小，就必须分割成两个子任务，每个子任务在调用invokeAll方法时，又会进入compute方法，看看当前子任务是否需要继 续分割成孙任务，如果不需要继续分割，则执行当前子任务并返回结果。使用join方法会等待子任务执行完并得到其结果。

CountDownLatch

闭锁，CountDownLatch这个类能够使一个线程等待其他线程完成各自的工作后再执行。例如，应用程序的主线程希望在负责启动框架服务的线程已经启动所有的框架服务之后再执行。

CountDownLatch是通过一个计数器来实现的，计数器的初始值为初始任务 的数量。每当完成了一个任务后，计数器的值就会减1（CountDownLatch.countDown()方法）。当计数器值到达0时，它表示所有的已 经完成了任务，然后在闭锁上等待CountDownLatch.await()方法的线程就可以恢 复执行任务。

应用场景：

实现最大的并行性：有时我们想同时启动多个线程，实现最大程度的并行性。 例如，我们想测试一个单例类。如果我们创建一个初始计数为1的CountDownLatch，并让所有线程都在这个锁上等待，那么我们可以很轻松地完成 测试。我们只需调用 一次countDown()方法就可以让所有的等待线程同时恢复执 行。

开始执行前等待n个线程完成各自任务：例如应用程序启动类要确保在处理 用户请求前，所有N个外部系统已经启动和运行了，例如处理excel中多个表单。