论文翻译 | 【深入挖掘Java技术】「底层原理专题」深入分析一下并发编程之父Doug Lea的纽约州立大学的ForkJoin框架的本质和原理

简介: 本文深入探讨了一个Java框架的设计、实现及其性能。该框架遵循并行编程的理念,通过递归方式将问题分解为多个子任务,并利用工作窃取技术进行并行处理。所有子任务完成后,其结果被整合以形成完整的并行程序。在总体设计上,该框架借鉴了Cilk工作窃取框架的核心理念。其核心技术主要聚焦于高效的任务队列构建和管理,以及工作线程的管理。经过实际性能测试,我们发现大多数程序的并行加速效果显著,但仍有优化空间,未来可能需要进一步研究改进方案。

前提介绍

Doug Lea在州立大学奥斯威戈分校(Doug Lea)

摘要

本文深入探讨了一个Java框架的设计、实现及其性能。该框架遵循并行编程的理念,通过递归方式将问题分解为多个子任务,并利用工作窃取技术进行并行处理。所有子任务完成后,其结果被整合以形成完整的并行程序。

在总体设计上,该框架借鉴了Cilk工作窃取框架的核心理念。其核心技术主要聚焦于高效的任务队列构建和管理,以及工作线程的管理。经过实际性能测试,我们发现大多数程序的并行加速效果显著,但仍有优化空间,未来可能需要进一步研究改进方案。


引言

Fork/Join并行是一种简单而高效的设计技术。它的算法思想是分而治之算法的并行版本,其典型形式包括:首先将问题分解为两个或更多的子问题,然后对每个子问题进行独立求解,最后将各个子问题的解合并以形成最终的解决方案。

Result solve(Problem problem) {
   
   
     if (problem is small) 
         directly solve problem
     else {
   
   
         split problem into independent parts
         fork new subtasks to solve each part
         join all subtasks
         compose result from subresults
     }
}
  • fork操作会启动一个新的并行fork/join子任务。
  • join连接操作会导致当前任务不继续执行,直到子任务完成。

fork/join算法与其他一样,fork/join算法几乎总是递归的、反复拆分子任务,直到它们小到可以用简单、简短的顺序方法解决为止。使用简单、简短的顺序方法。

FJTask是支持这种编程风格的JavaTM框架。FJTask 作为java.util.concurrent包的一部分,可从 http://gee.cs.oswego.edu 获取。

设计

任何支持构建并行执行的子任务的框架来运行fork/join程序。支持构建并行执行的子任务、的框架运行。

不过,java.lang.Thread类(以及 POSIX pthreads 通常是 Java 线程的基础)不是支持 fork/join 程序的最优的工具。

性能优秀

fork/join任务的同步和管理要求相对简单和有规律。其产生的计算图允许采用不同于通用线程所需的调度策略。例如,除了等待子任务外,fork/join 任务从不需要阻塞。因此,通用线程的阻塞状态跟踪被视为一种资源浪费。

此外,fork/join 框架还可以利用工作窃取技术,将任务从繁忙的线程转移到空闲线程,进一步优化并行处理。

任务粒度合理

在基本任务粒度合理的情况下,构建和管理线程的成本可能高于任务本身的计算时间。虽然粒度可以在特定平台上运行程序时进行调整,但极粗粒度会限制利用并行性的机会。

简而言之,标准的线程框架过于复杂,无法满足大多数分叉/连接程序的需求。然而,线程作为其他类型并行和并行编程方式的基础,要仅仅为了支持这种编程风格而消除其开销或调整线程本身的调度是不可能的,或者至少是不切实际的。

Cilk框架和基础

虽然这些想法肯定有更长的历史,但第一个为这些问题提供系统解决方案的编程框架是Cilk。Cilk和其他轻量级可执行框架是在操作系统的基本线程或进程机制之上的特殊目的的框架,支持fork/join。

fork/join的可移植性

这种策略同样适用于Java,尽管Java线程又依赖于更低级别的操作系统功能。创建这样一个Java轻量级执行框架的主要优点是允许fork/join程序以更可移植的方式编写,并在各种支持JVM的系统上运行。

FJTask框架

FJTask框架是基于Cilk中使用的设 计的一个变体。其他变体存在于 Hood, Filaments,stackthreads,以及一些相关的轻量级系统中。

class ATask extends FJTask {
   
   
     public void run() {
   
   
         split...
         fork...
         join...
         compose...
 }
}

可执行任务。所有这些框架都将任务映射到线程,其方式与操作系统将线程映射到CPU相同,但在执行映射时,fork/join框架利用了fork/join程序的简单性、规律性和约束。虽然所有这些框架都可以适应(在不同程度上)以不同风格编写的并行程序,但它们针对fork/join设计进行了优化。

设计思路

线程映射关系

已经建立了一个工作线程池。每个工作线程都是一个标准的(“重的”)线程(这里是线程子类FJTaskRunner的一个实例),它负责处理队列中保存的任务。通常,系统上的工作线程数量和CPU核心数一样多。在Cilk等本地框架中,这些线程被映射到内核线程或轻量级进程,然后再映射到CPU。

在Java中,必须信任JVM和OS才能将这些线程映射到CPU。然而,对于操作系统来说,这是一个相对简单的任务,因为这些线程是计算密集型的。任何合理的映射策略都会将这些线程映射到不同的CPU核心上。

拆分子任务

在FJTask框架中,所有的fork/join任务都是轻量级可执行类的实例,而不是线程的实例。这些任务子类化FJTask,而不是线程,因为独立的可执行任务需要实现接口Runnable并定义一个run方法。

此外,这些任务都实现了Runnable接口,这使得它们可以作为正在执行的任务或线程的一部分交替运行。由于任务在FJTask方法支持的受限制的规则下操作,因此对FJTask进行子类化更加方便,以便能够直接调用它们。

排队及调度

在特殊目的的排队和调度规则下,任务通过工作线程得以执行和管理。这些机制通过任务类中的方法触发,主要包括fork、join、完成状态指示器isDone,以及一些实用的方法,如coInvoke,即分叉并随后连接两个或多个任务。

设置调度管理

一个简单的控制和管理工具(这里是FJTaskRunnerGroup)在从普通线程(如在Java程序中执行主任务的线程)调用时,设置工作池并启动给定的分叉/连接任务的执行。

标准示例

作为程序员如何看待这个框架的标准示例,这里是一个计算斐波那契函数的类。

 static final int threshold = 13; 
 volatile int number; // arg/result
     Fib(int n) {
   
    number = n; }
     int getAnswer() {
   
   
         if (!isDone()) 
            throw new IllegalStateException();
             return number;
    }
 public void run() {
   
   
     int n = number;
     if (n <= threshold) // granularity ctl
         number = seqFib(n);
     else {
   
   
         Fib f1 = new Fib(n − 1);
         Fib f2 = new Fib(n − 2);
         coInvoke(f1, f2); 
         number = f1.number + f2.number;
     }
 }
 public static void main(String[] args) {
   
   
     try {
   
   
         int groupSize = 2; // for example 
         FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize);
         Fib f = new Fib(35); // for example
         group.invoke(f);
         int result = f.getAnswer();
         System.out.println("Answer: " +result);
     }catch (InterruptedException ex) {
   
   } 
     }
     int seqFib(int n) {
   
   
         if (n <= 1) return n;
             else return seqFib(n−1) + seqFib(n−2);
     }
}

这个版本的运行速度至少比在一个新的java.lang中运行的同等程序快30倍。它在维护多线程Java程序的内在可移植性的同时也做到了这一点。程序员典型感兴趣的调优参数:

  • 在构建工作线程时,其数量通常应与平台上的可用CPU数量相匹配(或更少,以保留处理用于其他非相关目的),有时甚至可能更多,以吸收非计算任务。

  • 一个粒度参数用于确定何时生成任务的成本超过了潜在的并行性带来的好处。这个参数更多地依赖于算法本身,而不是平台。通常,我们可以设定一个阈值,当在单处理器上运行时能获得良好的结果,但当存在多个CPU时仍能充分利用它们。这种方法的好处在于它与JVM的动态编译机制相契合,能够更优化地处理小方法。此外,数据局部性的优势也使得fork/join算法在某些情况下优于其他类型的算法。

未完待续

本节内容,给大家带来了对应的fork/join框架的前世今生,以及基于框架的fork和join机制的论文介绍,后续接下来会给大家带来对应的【线程盗取篇章】:论文翻译 | 【深入挖掘Java技术】「底层原理专题」深入分析一下并发编程之父Doug Lea的纽约州立大学的ForkJoin框架的本质和原理(线程盗取)

相关文章
|
8天前
|
安全 Java 开发者
深入理解Java并发编程:线程安全与性能优化
【4月更文挑战第9天】本文将深入探讨Java并发编程的核心概念,包括线程安全和性能优化。我们将详细解析Java中的同步机制,包括synchronized关键字、Lock接口以及并发集合等,并探讨它们如何影响程序的性能。此外,我们还将讨论Java内存模型,以及它如何影响并发程序的行为。最后,我们将提供一些实用的并发编程技巧和最佳实践,帮助开发者编写出既线程安全又高效的Java程序。
21 3
|
11天前
|
Java 调度
Java并发编程:深入理解线程池的原理与实践
【4月更文挑战第6天】本文将深入探讨Java并发编程中的重要概念——线程池。我们将从线程池的基本原理入手,逐步解析其工作过程,以及如何在实际开发中合理使用线程池以提高程序性能。同时,我们还将关注线程池的一些高级特性,如自定义线程工厂、拒绝策略等,以帮助读者更好地掌握线程池的使用技巧。
|
12天前
|
NoSQL Java 数据库连接
深入探索 Java 后台开发的核心技术
【4月更文挑战第5天】本文探讨了Java后台开发的关键技术,包括Spring框架与Spring Boot的使用,MyBatis和Hibernate的ORM选择,关系型与NoSQL数据库的适用场景,线程池与异步处理在并发中的作用,微服务架构及RESTful API设计。这些核心技术有助于开发者打造稳定、高性能的Java后台系统,适应不断发展的云计算和人工智能需求。
|
11天前
|
设计模式 安全 Java
Java并发编程实战:使用synchronized关键字实现线程安全
【4月更文挑战第6天】Java中的`synchronized`关键字用于处理多线程并发,确保共享资源的线程安全。它可以修饰方法或代码块,实现互斥访问。当用于方法时,锁定对象实例或类对象;用于代码块时,锁定指定对象。过度使用可能导致性能问题,应注意避免锁持有时间过长、死锁,并考虑使用`java.util.concurrent`包中的高级工具。正确理解和使用`synchronized`是编写线程安全程序的关键。
|
9天前
|
Java
Java 并发编程:深入理解线程池
【4月更文挑战第8天】本文将深入探讨 Java 中的线程池技术,包括其工作原理、优势以及如何使用。线程池是 Java 并发编程的重要工具,它可以有效地管理和控制线程的执行,提高系统性能。通过本文的学习,读者将对线程池有更深入的理解,并能在实际开发中灵活运用。
|
5天前
|
安全 算法 Java
深入理解Java并发编程:线程安全与性能优化
【4月更文挑战第11天】 在Java中,高效的并发编程是提升应用性能和响应能力的关键。本文将探讨Java并发的核心概念,包括线程安全、锁机制、线程池以及并发集合等,同时提供实用的编程技巧和最佳实践,帮助开发者在保证线程安全的前提下,优化程序性能。我们将通过分析常见的并发问题,如竞态条件、死锁,以及如何利用现代Java并发工具来避免这些问题,从而构建更加健壮和高效的多线程应用程序。
|
10天前
|
Java
Java并发编程:深入理解线程池
【4月更文挑战第7天】在现代软件开发中,多线程编程已经成为一种不可或缺的技术。为了提高程序性能和资源利用率,Java提供了线程池这一强大工具。本文将深入探讨Java线程池的原理、使用方法以及如何根据实际需求定制线程池,帮助读者更好地理解和应用线程池技术。
15 0
|
11天前
|
缓存 安全 Java
Java并发编程进阶:深入理解Java内存模型
【4月更文挑战第6天】Java内存模型(JMM)是多线程编程的关键,定义了线程间共享变量读写的规则,确保数据一致性和可见性。主要包括原子性、可见性和有序性三大特性。Happens-Before原则规定操作顺序,内存屏障和锁则保障这些原则的实施。理解JMM和相关机制对于编写线程安全、高性能的Java并发程序至关重要。
|
1天前
|
设计模式 运维 安全
深入理解Java并发编程:线程安全与性能优化
【4月更文挑战第15天】在Java开发中,多线程编程是提升应用程序性能和响应能力的关键手段。然而,它伴随着诸多挑战,尤其是在保证线程安全的同时如何避免性能瓶颈。本文将探讨Java并发编程的核心概念,包括同步机制、锁优化、线程池使用以及并发集合等,旨在为开发者提供实用的线程安全策略和性能优化技巧。通过实例分析和最佳实践的分享,我们的目标是帮助读者构建既高效又可靠的多线程应用。
|
2天前
|
Java 大数据 云计算
Spring框架:Java后台开发的核心
【4月更文挑战第15天】Spring框架在Java后台开发中占据核心位置,因其控制反转(IoC)、面向切面编程(AOP)、事务管理等特性提升效率和质量。Spring提供数据访问集成、RESTful Web服务和WebSocket支持。优势包括高效开发、灵活扩展、强大生态圈和广泛应用。应用于企业级应用、微服务架构及云计算大数据场景。掌握Spring对Java开发者至关重要。