ForkJoin实现分而治之

38次阅读

共计 1519 个字符,预计需要花费 4 分钟才能阅读完成。

  • 对于简单的并行任务可以通过 ” 线程池 +Future” 方案来解决。
  • 如果任务额之间有聚合关系 (AND 聚合或者 OR 聚合) 用 CompletableFuture 解决。
  • 批量的并行任务用 CompletionService 解决。

并发编程可以分为三个层面的问题:分工,协作,互斥。

ForkJoin 有什么用

Fork/Join 是一个并行计算的框架,主要就是用来支持分治任务模型的,这个计算框架里的 Fork 对应的是分治任务模型里的任务分解,Join 对应的是结果合并。

什么是分治

把一个复杂的问题分解成多个相似的子问题, 然后把子问题分解成更小的子问题, 知道子问题简单到可以直接求解。

算法领域有分治算法(归并排序、快速排序都属于分治算法,二 分法查找也是一种分治算法);大数 MapReduce 也是。

分治模型

分治任务可以分成两个阶段:任务分解,结果合并。

Fork/Join 的使用

Fork/Join 计算框架主要包含两部分,一部分是分治任务的线程池 ForkJoinPool,另一部分是分治任务 ForkJoinTask。这两部分的关系类似 ThreadPoolExecutor 和 Runnable 的关系,都可以理解为提交任务到线程池,只不过分治任务有自己独特类型 ForkJoinTask。

ForkJoinTask
  • ForkJoinTask 是一个抽象类最核心的是 fork()方法和 join()方法,fork()会异步地执行一个子任务,join()会阻塞当前线程来等待子任务的执行结果。
  • ForkJoinTask 有连个子类:

    • RecursiveAction:用递归的方式来处理分治任务,compute()方法没有返回值。
    • RecursiveTask:用递归的方式来处理分治任务,compute()方法有返回值。

使用 ForkJoinTask 实现计算斐波那契数列

package com.thread;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

/**
 * 实现斐波那契数列
 * 求出第 n 个斐波那契数列值
 **/
public class ForkJoinDemo {public static void main(String[] args) {
        // 创建分治任务线程池
        ForkJoinPool fjp = new ForkJoinPool(4);
        // 创建分治任务
        Fibonacci fib = new Fibonacci(4);
        // 启动分治任务
        Integer result = fjp.invoke(fib);
        // 输出结果
        System.out.println(result);
    }
    static class Fibonacci extends RecursiveTask<Integer>{
        final int n;
        public Fibonacci(int n){this.n = n;}
        @Override
        protected Integer compute() {if (n <= 1){return  n;}
            Fibonacci f1 = new Fibonacci(n-1);
            // 创建⼦任务
            f1.fork();
            Fibonacci f2 = new Fibonacci(n-2);
            // 等待子任务结果, 并合并结果.
            return f2.compute() + f1.join();
        }
    }
}

ForkJoinPool 与 ForkJoinTask 关系类似 ThreadPoolExecutor 和 Runnable 的关系。

ForkJoinPool 有窃取队列的性质,空闲队列会窃取忙队列的任务

建议用不同的 ForkJoinPool 执行不同类型的计算任务


码字不易如果对你有帮助请给个关注

爱技术爱生活 QQ 群: 894109590

正文完
 0