线程并发--Fork/Join框架

使用Fork/Join框架的目的：在多个CPU的情况下，充分利用多个CPU从而达到提高程序的运行速度。

含义：Fork/Join框架是Java 7提供的一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。Fork/Join框架最主要的两个关键词分割和合并，Fork表示分割，Join表示合并。

为什么需要分割和合并：

因为在多CPU的情况下，可能会出现CPU数量>任务数量，那么有的CPU就会出现空闲情况，那么我们就将一个任务分割成几等分，让每个CPU都能执行，执行完毕之后再将任务合并成完整的任务。

以下为Fork/Join框架分析图：

Fork/Join框架分析图

在Java的Fork/Join框架操作步骤：

1).ForkJoinTask:我们要使用Fork/Join框架，首先需要创建一个ForkJoin任务。该类提供了在任务中执行fork和join的机制。Fork/Join框架提供了两个子类：
    a).RecursiveAction：用于没有返回结果的任务
    b).RecursiveTask:用于有返回结果的任务
2).ForkJoinPool:ForkJoinTask需要通过ForkJoinPool来执行

需求：使用Fork/Join框架实现1-1000000总和

public class ForkJoinDemo {
    public static void main(String[] args) throws Exception {
        CountTask countTask = new CountTask(0,1000);
        ForkJoinPool pool = new ForkJoinPool();
        ForkJoinTask<Long> ret = pool.submit(countTask);
        System.out.println(ret.get());
    }
}

class CountTask extends RecursiveTask<Long> {
    private static final long threshold = 2L;// 临界值，因为分割需要临界值
    private long min;
    private long max;

    public CountTask(long min, long max) {
        this.min = min;
        this.max = max;
    }

    @Override
    protected Long compute() {
        // 分割
        long len = max - min;
        if (len <= threshold) {// 比临界值还小无需分割
            long sum = 0;
            for (long i = min; i < max; i++) {
                sum += i;
            }
            return sum;
        } else {
            long mid = (max + min) / 2;//求中间值
            CountTask count1 = new CountTask(min, mid);
            count1.fork();
            CountTask count2 = new CountTask(mid + 1, max);
            count2.fork();
            // 合并
            return count1.join() + count2.join();
        }
    }
}

Fork/Join框架实现方式-工作窃取：

    将任务分割出的子任务会添加到当前工作线程所维护的双端队列中，进入队列的头部。当一个工作线程的队列里暂时没有任务时，它会随机从其他工作线程的队列的尾部获取一个任务(工作窃取算法)。