并发编程08-ForkJoin原理与应用

任务的性质

CPU密集型（CPU-bound）

​ CPU密集型也叫计算密集型，指的是系统的硬盘、内存性能相对CPU要好很多，此时，系统运作大部分的状况是CPULoading100%，CPU要读/写I/O(硬盘/内存)，I/O在很短的时间就可以完成，而CPU还有许多运算要处理，CPULoading很高。在多重程序系统中，大部份时间用来做计算、逻辑判断等CPU动作的程序称之CPUbound。例如一个计算圆周率至小数点一千位以下的程序，在执行的过程当中绝大部份时间用在三角函数和开根号的计算，便是属于CPUbound的程序。CPUbound的程序一般而言CPU占用率相当高。这可能是因为任务本身不太需要访问I/O设备，也可能是因为程序是多线程实现因此屏蔽掉了等待I/O的时间。

​ 线程数一般设置为：线程数=CPU核数+1(现代CPU支持超线程)

IO密集型（I/Obound）

​ IO密集型指的是系统的CPU性能相对硬盘、内存要好很多，此时，系统运作，大部分的状况是CPU在等I/O(硬盘/内存)的读/写操作，此时CPULoading并不高。I/Obound的程序一般在达到性能极限时，CPU占用率仍然较低。这可能是因为任务本身需要大量I/O操作，而pipeline做得不是很好，没有充分利用处理器能力。

​ 线程数一般设置为：线程数=（（线程等待时间+线程CPU时间）/线程CPU时间）*CPU数目

CPU密集型vsIO密集型

​ 我们可以把任务分为计算密集型和IO密集型。

​ 计算密集型任务的特点是要进行大量的计算，消耗CPU资源，比如计算圆周率、对视频进行高清解码等等，全靠CPU的运算能力。这种计算密集型任务虽然也可以用多任务完成，但是任务越多，花在任务切换的时间就越多，CPU执行任务的效率就越低，所以，要最高效地利用CPU，计算密集型任务同时进行的数量应当等于CPU的核心数。计算密集型任务由于主要消耗CPU资源，因此，代码运行效率至关重要。Python这样的脚本语言运行效率很低，完全不适合计算密集型任务。对于计算密集型任务，最好用C语言编写。

​ 第二种任务的类型是IO密集型，涉及到网络、磁盘IO的任务都是IO密集型任务，这类任务的特点是CPU消耗很少，任务的大部分时间都在等待IO操作完成（因为IO的速度远远低于CPU和内存的速度）。对于IO密集型任务，任务越多，CPU效率越高，但也有一个限度。常见的大部分任务都是IO密集型任务，比如Web应用。IO密集型任务执行期间，99%的时间都花在IO上，花在CPU上的时间很少，因此，用运行速度极快的C语言替换用Python这样运行速度极低的脚本语言，完全无法提升运行效率。对于IO密集型任务，最合适的语言就是开发效率最高（代码量最少）的语言，脚本语言是首选，C语言最差。

一般而言、一般的web后台系统都大多做IO密集类操作，毕竟存在大量的sql或者存在导出操作

一个问题

​ 如何充分利用多核CPU，计算很大数组中所有整数的和？

1、单线程累加

public class SumSequential {

    public static long sum(int[] arr){
        return SumUtils.sumRange(arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = Utils.buildRandomIntArray(200000);
        System.out.printf("The array length is: %d\n", arr.length);

        long begin = System.currentTimeMillis();
        long result = sum(arr);

        long end = System.currentTimeMillis();
        System.out.printf("The result is: %d\n", result);
        System.out.println("单线程:"+ (end - begin));
    }
}
The array length is: 200000
The result is: 9905876
单线程:5

2、多线程拆分（定义步长，1为2,2分为4,4分为8）

public class SumRecursiveMT {
    public static class RecursiveSumTask implements Callable<Long> {
        public static final int SEQUENTIAL_CUTOFF = 1;
        int lo;
        int hi;
        int[] arr; // arguments
        ExecutorService executorService;

        RecursiveSumTask( ExecutorService executorService, int[] a, int l, int h) {
            this.executorService = executorService;
            this.arr = a;
            this.lo = l;
            this.hi = h;
        }

        public Long call() throws Exception { // override
            System.out.format("%s range [%d-%d] begin to compute %n",
                    Thread.currentThread().getName(), lo, hi);
            long result = 0;
            if (hi - lo <= SEQUENTIAL_CUTOFF) {
                for (int i = lo; i < hi; i++)
                    result += arr[i];

                System.out.format("%s range [%d-%d] begin to finished %n",
                        Thread.currentThread().getName(), lo, hi);
            }
            else {
                RecursiveSumTask left = new RecursiveSumTask(executorService, arr, lo, (hi + lo) / 2);
                RecursiveSumTask right = new RecursiveSumTask(executorService, arr, (hi + lo) / 2, hi);
                Future<Long> lr = executorService.submit(left);
                Future<Long> rr = executorService.submit(right);

                result = lr.get() + rr.get();
                System.out.format("%s range [%d-%d] finished to compute %n",
                        Thread.currentThread().getName(), lo, hi);
            }

            return result;
        }
    }


    public static long sum(int[] arr) throws Exception {
        int nofProcessors = Runtime.getRuntime().availableProcessors();
        ExecutorService executorService = Executors.newFixedThreadPool(4);
        //ExecutorService executorService = Executors.newCachedThreadPool();

        RecursiveSumTask task = new RecursiveSumTask(executorService, arr, 0, arr.length);
        long result =  executorService.submit(task).get();
        return result;
    }

    public static void main(String[] args) throws Exception {
        int[] arr = Utils.buildRandomIntArray(200000);
        System.out.printf("The array length is: %d\n", arr.length);

        long result = sum(arr);

        System.out.printf("The result is: %d\n", result);

    }
}
//无法正常运行 4个线程无法完成递归
The array length is: 200000
pool-1-thread-1 range [0-200000] begin to compute 
pool-1-thread-2 range [0-100000] begin to compute 
pool-1-thread-3 range [100000-200000] begin to compute 
pool-1-thread-4 range [0-50000] begin to compute 

3、多线程拆分（定义步长，拆分为 数组长度/步长 个线程去计算对应段的素组长度）

public class SumMultiThreads {
    public final static int NUM = 1000;
    public static long sum(int[] arr, ExecutorService executor) throws Exception {
        long result = 0;
        int numThreads = arr.length / NUM > 0 ? arr.length / NUM : 1;

        SumTask[] tasks = new SumTask[numThreads];
        Future<Long>[] sums = new Future[numThreads];
        for (int i = 0; i < numThreads; i++) {
            tasks[i] = new SumTask(arr, (i * NUM), ((i + 1) * NUM));
            sums[i] = executor.submit(tasks[i]);
        }

        for (int i = 0; i < numThreads; i++) {
            result += sums[i].get();
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        int[] arr = Utils.buildRandomIntArray(200000);

        int numThreads = arr.length / NUM > 0 ? arr.length / NUM : 1;
        long begin = System.currentTimeMillis();

        System.out.printf("The array length is: %d\n", arr.length);
        ExecutorService executor = Executors.newFixedThreadPool(numThreads);

        long result = sum(arr, executor);

        long end = System.currentTimeMillis();
        System.out.printf("The result is: %d\n", result);
        System.out.println("多线程:"+ (end - begin));
    }
}
The array length is: 200000
The result is: 9904260
多线程:177

分治法

基本思想：把一个规模大的问题划分为规模较小的子问题，然后分而治之，最后合并子问题的解得到原问题的解。
步骤：
1、分割原问题：
2、求解子问题：
3、合并子问题的解为原问题的解。
在分治法中，子问题一般是相互独立的，因此，经常通过递归调用算法来求解子问题。

拆分任务

递归分解

public class SumRecursiveMT {
    public static class RecursiveSumTask implements Callable<Long> {
        public static final int SEQUENTIAL_CUTOFF = 1000;
        int lo;
        int hi;
        int[] arr; // arguments
        ExecutorService executorService;

        RecursiveSumTask( ExecutorService executorService, int[] a, int l, int h) {
            this.executorService = executorService;
            this.arr = a;
            this.lo = l;
            this.hi = h;
        }

        public Long call() throws Exception { // override
            System.out.format("%s range [%d-%d] begin to compute %n",
                    Thread.currentThread().getName(), lo, hi);
            long result = 0;
            if (hi - lo <= SEQUENTIAL_CUTOFF) {
                for (int i = lo; i < hi; i++)
                    result += arr[i];

                System.out.format("%s range [%d-%d] begin to finished %n",
                        Thread.currentThread().getName(), lo, hi);
            }
            else {
                RecursiveSumTask left = new RecursiveSumTask(executorService, arr, lo, (hi + lo) / 2);
                RecursiveSumTask right = new RecursiveSumTask(executorService, arr, (hi + lo) / 2, hi);
                Future<Long> lr = executorService.submit(left);
                Future<Long> rr = executorService.submit(right);

                result = lr.get() + rr.get();
                System.out.format("%s range [%d-%d] finished to compute %n",
                        Thread.currentThread().getName(), lo, hi);
            }

            return result;
        }
    }


    public static long sum(int[] arr) throws Exception {
        int nofProcessors = Runtime.getRuntime().availableProcessors();
        //ExecutorService executorService = Executors.newFixedThreadPool(nofProcessors);
        ExecutorService executorService = Executors.newCachedThreadPool();

        RecursiveSumTask task = new RecursiveSumTask(executorService, arr, 0, arr.length);
        long result =  executorService.submit(task).get();
        return result;
    }

    public static void main(String[] args) throws Exception {
        int[] arr = Utils.buildRandomIntArray(200000);
        System.out.printf("The array length is: %d\n", arr.length);
        long begin = System.currentTimeMillis();
        long result = sum(arr);
        long end = System.currentTimeMillis();
        System.out.printf("The result is: %d\n", result);
        System.out.println("递归:"+ (end - begin));

    }
}

什么是Fork/Join框架？

​ Fork/Join框架是Java7提供了的一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务（互不依赖），最终汇总每个小任务结果后得到大任务结果的框架。

​ 对Java而言，对支持Concurrency(并发)/Parallelism(并行)的不断完善，明显地体现在优化并发与并行
Java 1 支持threads, locks, condition queues
Java 5 引入了 thread pools, blocking queues, concurrent collections
Java 7 加入了fork-join库
Java 8 加入了 parallel streams

​ Fork就是把一个大任务切分为若干子任务并行的执行，Join就是合并这些子任务的执行结果，最后得到这个大任务的结果。比如计算1+2+…..＋10000，可以分割成10个子任务，每个子任务分别对1000个数进行求和，最终汇总这10个子任务的结果。如下图所示：

Fork/Jion特性：

1、ForkJoinPool不是为了替代ExecutorService，而是它的补充，在某些应用场景下性能比ExecutorService更好。（见JavaTip:When to use ForkJoinPool vs ExecutorService ）

2、ForkJoinPool 主要用于实现“分而治之”的算法，特别是分治之后递归调用的函数，例如quicksort等。

3、ForkJoinPool最适合的是计算密集型的任务，如果存在I/O，线程间同步，sleep()等会造成线程长时间阻塞的情况时，最好配合使用ManagedBlocker。

ForkJoinPool框架主要类

​ ForkJoinPool 实现ForkJoin的线程池——对应ThreadPool
​ ForkJoinWorkerThread 实现ForkJoin的线程

ForkJoinTask一个描述ForkJoin的抽象类——对应Runnable/Callable
RecursiveAction 无返回结果的ForkJoinTask类似Runnable
RecursiveTask 有返回结果的ForkJoinTask类似Callable
CountedCompleter 在任务完成执行后会触发执行一个自定义的钩子函数

ForkJoinPool 提交任务

返回值	方法名
void	execute(ForkJoinTask<?> task) execute(Runnable task)
T	invoke(ForkJoinTask task)
List	invokeAll(Collection<? extends Callable> tasks)
ForkJoinTask	submit(ForkJoinTask task) submit(Callable task) submit(Runnable task) submit(Runnable task, T result)

ForkJoinTask

ForkJoinTask主要包括两个方法分别实现任务的分拆与合并：

1、fork()类似于Thread.start()，但是它并不立即执行任务，而是将任务放入工作队列中
2、跟Thread.join()不同，ForkJoinTask的join()方法并不简单的阻塞线程
利用工作线程运行其他任务
当一个工作线程中调用join()，它将处理其他任务，直到注意到目标子任务已经完成

ForkJoinTask	fork()–Arranges to asynchronously execute this task in the appropriate pool
V	join()–Returns the result of the computation when itis done

1、ForkJoinPool中的所有的工作线程均有一个自己的工作队列WorkQueue

• 双端队列（Deque)
• 从队头取任务
• 线程私有，不共享
  

2、ForkJoinTask中fork的子任务，将放入运行该任务的工作线程的队头

• 工作线程以LIFO（LAST IN FIRST OUT）的顺序来处理它队列中的任务

  

3、为了最大化CPU利用率，空闲的线程将从其他线程的队列中“窃取”任务来执行

• 从工作队列的队尾“窃取”任务，以减少竞争

• 任务的“窃取”是以**FIFO(FIRST IN FIRST OUT)**顺序进行的，因为先放入的任务往往表示更大的工作量

4、WorkQueue双端队列最小化任务“窃取”的竞争

• push()/pop()仅在其所有者工作线程中调用
  • 这些操作都是通过CAS来实现的，是Wait-free的
• poll() 则由其他工作线程来调用“窃取”任务
  • 可能不是wait-free

5、异常处理

ForkJoinTask 在执行的时候可能会抛出异常，但是我们没办法在主线程里直接捕获异常，所以 ForkJoinTask 提供了 isCompletedAbnormally() 方法来检查任务是否已经抛出 异常或已经被取消了，并且可以通过 ForkJoinTask 的 getException 方法获取异常。示例 如下

if(task.isCompletedAbnormally()){ 
	System.out.println(task.getException()); 
}

getException 方法返回 Throwable 对象，如果任务被取消了则返回CancellationException。如果任务没有完成或者没有抛出异常则返回 null

6、ForkJoinPool构造函数

private ForkJoinPool(int parallelism,
                     ForkJoinWorkerThreadFactory factory,
                     UncaughtExceptionHandler handler,
                     int mode,
                     String workerNamePrefix) {
    this.workerNamePrefix = workerNamePrefix;
    this.factory = factory;
    this.ueh = handler;
    this.config = (parallelism & SMASK) | mode;
    long np = (long)(-parallelism); // offset ctl counts
    this.ctl = ((np << AC_SHIFT) & AC_MASK) | ((np << TC_SHIFT) & TC_MASK);
}

重要参数解释
①parallelism：并行度（ the parallelism level），默认情况下跟我们机器的cpu个数保持 一致，使用 Runtime.getRuntime().availableProcessors()可以得到我们机器运行时可用的 CPU个数。

②factory：创建新线程的工厂（ the factory for creating new threads）。默认情况下使 用ForkJoinWorkerThreadFactory defaultForkJoinWorkerThreadFactory。

③handler：线程异常情况下的处理器（Thread.UncaughtExceptionHandler handler），该处理器在线程执行任务时由于某些无法预料到的错误而导致任务线程中断时 进行一些处理，默认情况为null。

④asyncMode：这个参数要注意，在ForkJoinPool中，每一个工作线程都有一个独立的任 务队列，asyncMode表示工作线程内的任务队列是采用何种方式进行调度，可以是先进先 出FIFO，也可以是后进先出LIFO。如果为true，则线程池中的工作线程则使用先进先出方 式进行任务调度，默认情况下是false。

7、ForkJoinTask fork 方法

fork() 做的工作只有一件事，既是把任务推入当前工作线程的工作队列里。可以参看以下的 源代码：

public final ForkJoinTask<V> fork() {
    Thread t;
    if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
        ((ForkJoinWorkerThread)t).workQueue.push(this);
    else
        ForkJoinPool.common.externalPush(this);
    return this;
}

8、ForkJoinTask join 方法

join() 的工作则复杂得多，也是 join() 可以使得线程免于被阻塞的原因——不像同名 的 Thread.join()。

1. 检查调用 join() 的线程是否是 ForkJoinThread 线程。如果不是（例如 main 线 程），则阻塞当前线程，等待任务完成。如果是，则不阻塞。
2. 查看任务的完成状态，如果已经完成，直接返回结果。
3. 如果任务尚未完成，但处于自己的工作队列内，则完成它。
4. 如果任务已经被其他的工作线程偷走，则窃取这个小偷的工作队列内的任务 （以 FIFO 方式），执行，以期帮助它早日完成欲 join 的任务。
5. 如果偷走任务的小偷也已经把自己的任务全部做完，正在等待需要 join 的任务 时，则找到小偷的小偷，帮助它完成它的任务。
6. 递归地执行第5步

9、ForkJoinPool.submit 方法

public <T> ForkJoinTask<T> submit(ForkJoinTask<T> task) {
    if (task == null)
        throw new NullPointerException();
    externalPush(task);
    return task;
}

ForkJoinPool 自身拥有工作队列，这些工作队列的作用是用来接收由外部线程 （非 ForkJoinThread 线程）提交过来的任务，而这些工作队列被称 为 submitting queue 。 submit() 和 fork() 其实没有本质区别，只是提交对象变成了 submitting queue 而已（还有一些同步，初始化的操作）。

submitting queue 和其他 work queue 一样，是工作线程”窃取“的对象，因此当其中的任务被一个工作线程 成功窃取时，就意味着提交的任务真正开始进入执行阶段。

10、Fork/Join框架执行流程

RecursiveTask使用实例

public class LongSumMain {
	/** for time conversion */
//获取逻辑处理器数量
	static final int NCPU = Runtime.getRuntime().availableProcessors();
	static long calcSum;

	static final boolean reportSteals = true;

	public static void main(String[] args) throws Exception {

		int[] array = Utils.buildRandomIntArray(200000000);
		System.out.println("cpu-num:"+NCPU);
		//单线程下计算数组数据总和
		long begin = System.currentTimeMillis();
 		calcSum = seqSum(array);
		long end = System.currentTimeMillis();
		System.out.println("seq sum=" + calcSum);
		System.out.println("单线程:"+ (end - begin));

		//采用fork/join方式将数组求和任务进行拆分执行，最后合并结果
		LongSum ls = new LongSum(array, 0, array.length);
  		ForkJoinPool fjp  = new ForkJoinPool(NCPU); //使用的线程数
		begin = System.currentTimeMillis();
		ForkJoinTask<Long> task = fjp.submit(ls);
		System.out.println("forkjoin sum=" + task.get());
		end = System.currentTimeMillis();
		System.out.println("forkjoin:"+ (end - begin));
		if(task.isCompletedAbnormally()){
			System.out.println(task.getException());
		}

		fjp.shutdown();

	}


	static long seqSum(int[] array) {
		long sum = 0;
		for (int i = 0; i < array.length; ++i)
			sum += array[i];
		return sum;
	}
    
/**
RecursiveTask 并行计算，同步有返回值
ForkJoin框架处理的任务基本都能使用递归处理，比如求斐波那契数列等，但递归算法的缺陷是：
一只会只用单线程处理，
二是递归次数过多时会导致堆栈溢出；
ForkJoin解决了这两个问题，使用多线程并发处理，充分利用计算资源来提高效率，同时避免堆栈溢出发生。
当然像求斐波那契数列这种小问题直接使用线性算法搞定可能更简单，实际应用中完全没必要使用ForkJoin框架，
所以ForkJoin是核弹，是用来对付大家伙的，比如超大数组排序。
最佳应用场景：多核、多内存、可以分割计算再合并的计算密集型任务
*/
cpu-num:12
seq sum=9899269760
单线程:132
forkjoin sum=9899269760
forkjoin:106

class LongSum extends RecursiveTask<Long> {

    static final int SEQUENTIAL_THRESHOLD = 1000;
    static final long NPS = (1000L * 1000 * 1000);
    static final boolean extraWork = true; // change to add more than just a sum


    int low;
    int high;
    int[] array;

    LongSum(int[] arr, int lo, int hi) {
        array = arr;
        low = lo;
        high = hi;
    }

    /**
     * fork()方法：将任务放入队列并安排异步执行，一个任务应该只调用一次fork()函数，除非已经执行完毕并重新初始化。
     * tryUnfork()方法：尝试把任务从队列中拿出单独处理，但不一定成功。
     * join()方法：等待计算完成并返回计算结果。
     * isCompletedAbnormally()方法：用于判断任务计算是否发生异常。
     */
    protected Long compute() {
        if (high - low <= SEQUENTIAL_THRESHOLD) {
            long sum = 0;
            for (int i = low; i < high; ++i) {
                sum += array[i];
            }
            return sum;
        } else {
            int mid = low + (high - low) / 2;
            LongSum left = new LongSum(array, low, mid);
            LongSum right = new LongSum(array, mid, high);
            left.fork();
            right.fork();
            long rightAns = right.join();
            long leftAns = left.join();
            return leftAns + rightAns;
        }
    }
}

总结

ForkJoinPool VS ExecutorService

1、ForkJoinPool 最适合的是计算密集型的任务，如果存在I/O，线程间同步，sleep() 等会造成线程长时间阻塞的情况时，最好配合使用ManagedBlocker;

2、Work-Stealing 的适用场景是不同的任务的耗时相差比较大，即某些任务需要运行较长时间，而某些任务会很快的运行完成，这种情况下用 Work-Stealing 很合适；

3、ForkJoinPool是分而治之的思想的体现