高并发编程 / 并行任务组件 ForkJoinPool 工作窃取算法设计思路分析

2024-11-03
河北
本文字数：3693 字
阅读完需：约 12 分钟

ForkJoinTask 与工作窃取算法是 Java 并行计算的精髓，专为充分利用多核处理器而设计。这种算法通过将大型任务分解为小块，允许线程动态地“窃取”其他线程的任务来执行，从而实现工作负载的平衡。对于需要处理大量数据或执行复杂计算的开发者来说，理解这一算法的机制是提高程序性能的关键。它不仅简化了并行编程的复杂性，还极大地提升了计算效率，特别是在面对大规模并行处理任务时。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 'mvcc' 获得手写数据库事务代码
欢迎点赞，关注，评论。
关注公号 Solomon 肖哥弹架构获取更多精彩内容

历史热点文章

1、ForkJoinTask 工作窃取算法思路

步骤：

开始：并行计算的起点。
线程 X - 任务队列 X：每个线程都有自己的任务队列。
线程 X 执行任务：线程从自己的任务队列中取出任务并执行。
线程 X 空闲? ：检查线程是否空闲（即任务队列为空）。
窃取任务：如果线程空闲，它会尝试从其他线程的任务队列中窃取任务。

2、ForkJoinTask 工作窃取算法实现思路

分治算法思想：
ForkJoinTask 框架采用分治算法的思想，将一个大任务分解（fork）成若干个子任务，这些子任务可以并行执行，最后将结果合并（join）。
Fork/Join 工作方式：
ForkJoinTask 需要通过 ForkJoinPool 来执行。ForkJoinPool 由 ForkJoinTask 数组和 ForkJoinWorkerThread 数组组成，其中 ForkJoinTask 数组负责存放提交的任务，而 ForkJoinWorkerThread 负责执行这些任务。
任务分解与执行：
任务被分解成更小的任务，直到达到某个阈值，然后这些小任务被加入到工作队列中。
工作窃取算法：
当一个工作线程的队列中没有任务时，它会从其他工作线程的队列尾部随机窃取任务来执行，这种机制称为工作窃取算法。
线程管理：
ForkJoinPool 中的每个 ForkJoinWorkerThread 线程都有一个独立的任务等待队列，用于存储子任务。
任务窃取实现：
ForkJoinPool 会维护一个优先级队列，用于存储等待被窃取的任务。当一个新任务到达时，ForkJoinPool 会根据任务的优先级将任务分配给一个空闲的工作线程进行处理。
并行级别：
ForkJoinPool 的理想并行级别是处理器核心数，这可以通过 Runtime.getRuntime().availableProcessors() 获取。
任务的 Fork 和 Join 操作：
ForkJoinTask 提供了 fork() 方法用于异步执行任务，以及 join() 方法用于等待任务完成并获取结果。
任务执行流程：
在 ForkJoinTask 的 compute() 方法中，如果任务足够小，则直接执行；否则，分解成子任务并递归执行这些子任务。
工作窃取的实现细节：
工作窃取算法的实现涉及到线程之间的任务队列操作，包括尝试从其他线程的任务队列中窃取任务以及在窃取成功后调整队列状态。

2.1 实现流程

思路流程：

主线程：提交需要并行处理的任务到ForkJoinPool的任务队列。
任务队列：存放主线程提交的任务，等待被工作线程处理。
工作线程：ForkJoinPool中的工作线程，它们有自己的本地任务队列。
本地队列：每个工作线程的本地任务队列，用于存放分解后的任务。
执行任务：工作线程从本地队列中取出任务并执行。
完成：任务执行完成后，工作线程会检查是否还有未执行的任务。
窃取任务：如果工作线程的本地队列为空，它会尝试从其他工作线程的本地队列中窃取任务来执行。

3、ForkJoinTask 工作窃取算法应用场景

ForkJoinTask 与工作窃取算法的应用场景非常广泛，以下是一些典型的应用场景：

大规模数值计算：
适用于需要进行大规模数值计算的场景，如科学计算、大数据分析等。这些场景中，可以将大的计算任务分解成多个小任务并行处理，最后合并结果。
图像处理：
在图像处理领域，可以将图像分割成多个区域，每个区域作为一个任务并行处理，如图像滤镜、边缘检测等。
搜索引擎索引：
搜索引擎在构建索引时，需要处理大量的文档。使用 ForkJoinTask 可以并行处理文档，提高索引构建的速度。
分布式数据处理：
在分布式系统中，可以利用 ForkJoinTask 来并行处理数据，特别是在 MapReduce 模式中，可以并行执行 Map 任务和 Reduce 任务。
并行 I/O 操作：
对于需要进行大量 I/O 操作的场景，如文件读写，可以使用 ForkJoinTask 来并行执行 I/O 操作，提高 I/O 效率。
数据库批量处理：
在数据库操作中，可以利用 ForkJoinTask 并行执行批量插入、更新或查询操作，提高数据库操作的效率。
游戏开发：
在游戏开发中，可以利用 ForkJoinTask 并行处理游戏逻辑、物理计算和 AI 计算，提高游戏性能。
并行 Web 服务：
对于高并发的 Web 服务，可以使用 ForkJoinTask 来并行处理用户请求，提高服务的响应速度和吞吐量。
机器学习和深度学习：
在机器学习和深度学习中，可以利用 ForkJoinTask 并行执行模型训练和预测任务，加速学习过程。
实时数据处理：
对于需要实时处理大量数据的场景，如股票交易系统，可以使用 ForkJoinTask 并行处理数据流，提高数据处理的实时性。

4、ForkJoinTask 工作窃取算法代码实现

算法核心思路代码

import java.util.ArrayList;import java.util.List;import java.util.Random;
// 任务class Task implements Comparable<Task> {    int id;    long cost; // 任务耗时
    public Task(int id, long cost) {        this.id = id;        this.cost = cost;    }
    @Override    public int compareTo(Task o) {        return Long.compare(this.cost, o.cost); // 按耗时从小到大排序    }}
// 工作窃取算法的实现public class WorkStealingSimulation {    private static final int NUM_THREADS = Runtime.getRuntime().availableProcessors();    private static final List<Task> globalQueue = new ArrayList<>();    private static final ThreadLocal<WorkQueue> threadLocalQueue = ThreadLocal.withInitial(WorkQueue::new);    private static final Random random = new Random();
    static class WorkQueue {        List<Task> queue = new ArrayList<>();
        void push(Task task) {            synchronized (this) {                queue.add(task);            }        }
        Task pop() {            synchronized (this) {                if (queue.isEmpty()) {                    return null;                }                return queue.remove(0);            }        }
        Task steal() {            synchronized (this) {                if (queue.isEmpty()) {                    return null;                }                int index = random.nextInt(queue.size());                return queue.remove(index);            }        }    }
    public static void main(String[] args) throws InterruptedException {        // 生成任务并分配到全局队列        for (int i = 0; i < 100; i++) {            int taskSize = 10 + random.nextInt(90); // 任务大小在10到99之间            globalQueue.add(new Task(i, taskSize));        }
        // 启动线程并执行任务        for (int i = 0; i < NUM_THREADS; i++) {            new Thread(() -> {                WorkQueue myQueue = threadLocalQueue.get();                while (!globalQueue.isEmpty() || !myQueue.queue.isEmpty()) {                    Task task = myQueue.pop();                    if (task == null) {                        // 如果本地队列为空，尝试从全局队列或他人队列中窃取任务                        task = globalQueue.remove(0);                        if (task == null) {                            task = stealTask();                        }                    }                    if (task != null) {                        processTask(task);                    }                }            }).start();        }    }
    private static void processTask(Task task) {        //任务处理        System.out.println("Processing task " + task.id + " with cost " + task.cost);        try {            Thread.sleep(task.cost);        } catch (InterruptedException e) {            Thread.currentThread().interrupt();        }    }
    private static Task stealTask() {        for (int i = 0; i < NUM_THREADS; i++) {            WorkQueue otherQueue = threadLocalQueue.get();            Task task = otherQueue.steal();            if (task != null) {                return task;            }        }        return null;    }}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/a364a5449714782cf4d724ccf】。文章转载请联系作者。

肖哥弹架构

关注

智慧属心窍之锁 2019-05-27 加入

擅长于通信协议、微服务架构、框架设计、消息队列、服务治理、PAAS、SAAS、ACE\ACP、大模型

发布

暂无评论

创作场景