并发工具类我们已经讲了很多,这些工具类的「目标」是让我们只关注任务本身,并且忽视线程间合作细节,简化了并发编程难度的同时,也增加了很多安全性。工具类的对使用者的「目标」虽然一致,但每一个工具类本身都有它独特的应用场景,比如:
将上面三种通用场景形象化展示一下:
结合上图相信你的脑海里已经浮现出这几个工具类的具体实现方式,感觉这已经涵盖了所有的并发场景。
TYTS,以上这些方式的子线程接到任务后不会再继续拆分成「子子」任务,也就是说,子线程即便接到很大或很复杂的任务也得硬着头皮努力执行完,很显然这个大任务是问题关键
如果能把大任务拆分成更小的子问题,直到子问题简单到可以直接求解就好了,这就是分治的思想
在计算机科学中,分治法是一种很重要的算法。字面上的解释是「分而治之」,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解就变成了子问题解的合并。
这个技巧是很多高效算法的基础,如排序算法 (快速排序,归并排序),傅立叶变换 (快速傅立叶变换)……,如果你是搞大数据的,MapReduce 就是分支思想的典型,如果你想更详细的理解分治相关的算法,请参考这篇一文图解分治算法和思想
结合上面的描述,相信你脑海中已经构建出来分治的模型了:
那所有的大任务都能用分治算法来解决吗?很显然不是的
总体来说,分治法所能解决的问题一般具有以下几个特征:
了解了分治算法的核心思想,我们就来看看 Java 是如何利用分治思想拆分与合并任务的吧
有子任务,自然要用到多线程。我们很早之前说过,执行子任务的线程不允许单独创建,要用线程池管理。秉承相同设计理念,再结合分治算法, ForkJoin 框架中就出现了 ForkJoinPool 和 ForkJoinTask。正所谓:
天对地,雨对风。大陆对长空。山花对海树,赤曰对苍穹
套用已有知识,简单理解就是这样滴:
我们之前说过无数次,JDK 不会重复造轮子,这里谈及相似是为了让大家有个简单的直观印象,内里肯定有所差别,我们先大致看一下这两个类:
又是这个男人,Doug Lea
,怎么就那么牛(破音)
可以看到 ForkJoinTask
实现了 Future
接口(那就是具有 Future 接口的特性),同样如其名,fork()
和 join()
自然是它的两个核心方法
fork()
: 异步执行一个子任务(上面说的拆分)join()
: 阻塞当前线程等待子任务的执行结果(上面说的合并)另外,从上面代码中可以看出,ForkJoinTask
是一个抽象类,在分治模型中,它还有两个抽象子类 RecursiveAction
和 RecursiveTask
那这两个子抽象类有什么差别呢?如果你打开 IDE,你应该一眼就能看出差别,so easy
两个类里面都定义了一个抽象方法 compute()
,需要子类重写实现具体逻辑
那子类要遵循什么逻辑重写这个方法呢?
遵循分治思想,重写的逻辑很简单,就是回答三个问题:
用「伪代码」再翻译一下上面这段话,大概就是这样滴:
(作为程序员,如果你写过递归运算,这个逻辑理解起来是非常简单的)
介绍到这里,就可以用 ForkJoin 干些事情了——经典 Fibonacci 计算就可以用分治思想(不信,你逐条按照上面分治算法适用情况自问自答一下?),直接借用官方 Docs (注意看 compute 方法),额外添加个 main 方法来看一下:
执行结果如下:
进展到这里,相信基本的使用就已经搞定了,上面代码中使用了 ForkJoinPool,那问题来了:
池化既然是一类思想,Java 已经有了
ThreadPoolExecutor
,为什么又要搞出个ForkJoinPool
呢?
借助下面这张图,先来回忆一下 ThreadPoolExecutor 的实现原理(详情请看为什么要使用线程池):
一眼就能看出来这是典型的生产者/消费者
模式,消费者线程都从一个共享的 Task Queue 中消费提交的任务。ThreadPoolExecutor 简单的并行操作主要是为了执行时间不确定的任务(I/O 或定时任务等)
JDK 重复造轮子是不可能的,分治思想其实也可以理解成一种父子任务依赖的关系,当依赖层级非常深,用 ThreadPoolExecutor
来处理这种关系很显然是不太现实的,所以 ForkJoinPool
作为功能补充就出现了
任务拆分后有依赖关系,还得减少线程之间的竞争,那就让线程执行属于自己的 task 就可以了呗,所以较 ThreadPoolExecutor
的单个 TaskQueue 的形式,ForkJoinPool
是多个 TaskQueue的形式,简单用图来表示,就是这样滴:
有多个任务队列,所以在 ForkJoinPool 中就有一个数组形式的成员变量 WorkQueue[]
。那问题又来了
任务队列有多个,提交的任务放到哪个队列中呢?(上图中的
Router Rule
部分)
这就需要一套路由规则,从上面的代码 Demo 中可以理解,提交的任务主要有两种:
为了进一步区分这两种 task,Doug Lea 就设计一个简单的路由规则:
submission task
放到 WorkQueue 数组的「偶数」
下标中worker task
放在 WorkQueue 的「奇数」
下标中,并且只有奇数下标才有线程( worker )与之相对应局部丰富一下上图就是这样滴:
每个任务执行时间都是不一样的(当然是在 CPU 眼里),执行快的线程的工作队列的任务就可能是空的,为了最大化利用 CPU 资源,就允许空闲线程拿取其它任务队列中的内容,这个过程就叫做 work-stealing
(工作窃取)
当前线程要执行一个任务,其他线程还有可能过来窃取任务,这就会产生竞争,为了减少竞争,WorkQueue 就设计成了一个双端队列:
线程(worker)操作自己的 WorkQueue 默认是 LIFO 操作(可选FIFO),当线程(worker)尝试窃取其他 WorkQueue 里的任务时,这个时候执行的是FIFO操作,即从 base 端窃取,用图丰富一下就是这样滴:
这样的好处非常明显了:
从 WorkQueue 的成员变量的修饰符中也能看出一二了(base 有 volatile 修饰,而 top 却没有):
到这里,相信你已经了解 ForkJoinPool 的基本实现原理了,但也会伴随着很多疑问(这都是怎么实现的?),比如:
保留住这些问题,一点点看源码来了解一下吧:
ForkJoinPool 的源码涉及到大量的位运算,这里会把核心部分说清楚,想要理解的更深入,还需要大家自己一点点追踪查看
结合上面的铺垫,你应该知道 ForkJoinPool 里有三个重要的角色:
源码分析的整个流程也是围绕这几个类的方法来说明,但在了解这三个角色之前,我们需要先了解 ForkJoinPool 都为这三个角色铺垫了哪些内容
故事就得从 ForkJoinPool 的构造方法说起
除了以上三个构造方法之外,在 JDK1.8 中还增加了另外一种初始化 ForkJoinPool 对象的方式(QQ:这是什么设计模式?):
Common 是在静态块里面初始化的(只会被执行一次):
因为这是一个单例通用的 ForkJoinPool,所以切记:
如果使用通用 ForkJoinPool,最好只做 CPU 密集型的计算操作,不要有不确定性的 I/O 内容在任务里面,以防拖垮整体
上面所有的构造方法最后都会调用这个私有方法:
参数有点多,在这里解释一下每个参数的含义:
序号 | 参数名 | 描述/解释 |
---|---|---|
1 | parallelism | 并行度,这并不是定义的线程数,具体线程数,以及 WorkQueue 的长度等都是根据这个并行度来计算的,通过上面 makeCommonPool 方法可以知道,parallelism 默认值是 CPU 核心线程数减 1 |
2 | factory | 很常见了,创建 ForkJoinWorkerThread 的工厂接口 |
3 | handler | 每个线程的异常处理器 |
4 | mode | 上面说的 WorkQueue 的模式,LIFO/FIFO; |
5 | workerNamePrefix | ForkJoinWorkerThread的前缀名称 |
6 | ctl | 线程池的核心控制线程字段 |
在构造方法中就已经有位运算了,太难了:
想知道 ForkJoinPool 的成员变量 config 要表达的意思,就要仔细拆开来看
parallelism & SMASK
其实就是要保证并行度的值不能大于 SMASK,上面所有的构造方法在传入 parallelism 的时候都会调用 checkParallelism
来检查合法性:
可以看到 parallelism 的最大值就是 MAX_CAP
了,0x7fff
肯定小于0xffff
。所以 config 的值其实就是:
这里假设 parallelism 就是 MAX_CAP
, 然后与 mode 进行或运算
,其中 mode 有三种:
下面以 LIFO_QUEUE 和 FIFO_QUEUE 举例说明:
所以 parallelism | mode
根据 mode 的不同会产生两种结果,但是会得到一个确认的信息:
config 的第 17 位表示模式,低 15 位表示并行度 parallelism
当我们需要从 config 中获取模式 mode 时候,只需要用mode 掩码 (MODE_MASK)和 config 做与运算
就可以了
所以一张图概括 config 就是:
上面这段代码就是将并行度 parallelism 补码转换为 long 型,以 MAX_CAP
作为并行度为例,np 的值就是
这个 np 的值,就会用作 ForkJoinPool 成员变量 ctl 的计算:
np << AC_SHIFT
即 np 向左移动 48 位,这样原来的低 16 位变成了高 16 位,再用 AC 掩码(AC_MASK) 做与运算
,也就是说 ctl 的 49 ~ 64 位表示活跃线程数np << TC_SHIFT
即 np 向左移动 32 位,这样原来的低 16 位变成了 33 ~ 48 位,再用 TC 掩码做与运算
,也就是说 ctl 的 33 ~ 48 位表示总线程数最后二者再进行或运算,如果并行度还是 MAX_CAP
,那 ctl 的最后结果就是:
到这里,我们才阅读完一个构造函数的内容,从最终的结论可以看出,初始化后 AC = TC,并且 ctl 是一个小于零的数,ctl 是 64 位的 long 类型,低 32 位是如何构造的并没有在构造函数中体现出来,但注释给了明确的说明:
这段注释主要说明了低 32 位的作用(后面会从源码中体现出来,这里先有个印象会对后面源码阅读有帮助),按注释含义先完善一下 ctl 的值:
1:不活动(inactive)
;0:活动(active)
,后15表示版本号,防止 ABA 问题注释中还说,另 sp=(int)ctl
,即获取 64 位 ctl 的低 32 位(SS | ID
),因为低 32 位都是创建出线程之后才会存在的值,所以推断出,如果 sp != 0, 就存在等待的工作线程,唤醒使用就行,不用创建新的线程。这样就通过 ctl 可以获取到有关线程所需要的一切信息了
除了构造方法所构建的成员变量,ForkJoinPool 还有一个非常重要的成员变量 runState
,和你之前了解的知识一样,线程池也需要状态来进行管理
runState
有上面 6 种状态切换,按注释所言,只有 SHUTDOWN
状态是负数,其他都是整数,在并发环境更改状态必然要用到锁,ForkJoinPool 对线程池加锁和解锁分别由 lockRunState
和 unlockRunState
来实现 (这两个方法可以暂且不用深入理解,可以暂时跳过,只需要理解它们是帮助安全更改线程池状态的锁即可)
不深入了解可以,但是我不能不写啊...... 你待会不是得回看吗?
或运算
的下半段 CASawaitRunStateLock
方法上面代码 33 ~ 34 (Flag1)行以及 36 ~ 50 (Flag2) 行,如果你没看后续代码,现在来理解是有些困难的,我这里先提前说明一下:
Flag1: 当完整的初始化 ForkJoinPool 时,直接利用了 stealCounter 这个原子变量,因为初始化时(调用 externalSubmit 时),才会对 StealCounter 赋值。所以,这里的逻辑是,当状态不是 STARTED 或者 stealCounter 为空,让出线程等待,也就是说,别的线程还没初始化完全,让其继续占用锁初始化即可
Flag2: 我们在讲等待/通知模型时就说,不要让无限自旋尝试,如果资源不满足就等待,如果资源满足了就通知,所以,如果 (runState & RSIGNAL) == 0
成立,说明有线程需要唤醒,直接唤醒就好,否则也别浪费资源,主动等待一会
当阅读到这的代码时,马上就抛出来两个问题:
Q1: 既然是加锁,为什么不用已有的轮子 ReentrantLock 呢?
**PS:**如果你读过并发系列 Java AQS队列同步器以及ReentrantLock的应用 ,你会知道 ReentrantLock 是用一个完整字段 state 来控制同步状态。但这里在竞争锁的时候还会判断线程池的状态,如果是初始化状态主动 yield 放弃 CPU 来减少竞争;另外,用一个完整的 runState 不同位来表示状态也体现出更细的粒度吧
Q2: synchronized 大法虽好,但是我们都知道这是比较重量级的锁,为什么还在这里应用了呢?
PS: 首先 synchronized 经过不断优化,没有它刚诞生时那么重,另外按照 Flag 2 的代码含义,进入 synchronized 同步块的概率还是很低的,可以用最简单的方式稳稳兜底(奥卡姆剃刀了原理?)
有加锁自然要解锁,向下看 unlockRunState
解锁的逻辑相对简单多了,总体目标是清除锁标记位。如果顺利将状态修改为目标状态,自然解锁成功;否则表示有别的线程进入了wait,需要调用notifyAll唤醒,重新尝试竞争
这两个方法贯穿着后续代码分析的始终,多注意 unlockRunState
的入参即可,另外你也看到了通知都是用的 notifyAll,而不是 notify,这个问题我们之前重点说明过,你还记得为什么吗?如果不记得,打开并发编程之等待通知机制 回忆一下吧
第一层知识铺垫已经差不多了,前进
回到本文最开始带有 main 函数的 demo,我们向 ForkJoinPool 提交任务调用的是 invoke 方法, 其实 ForkJoinPool 还支持 submit 和 execute 两种方式来提交任务。并发的玩法非常类似,这三类方法的作业也很好区分:
在这三大类基础上又重载了几个更细粒度的方法,这里不一一列举:
相信你已经发现了,提交任务的方法都会调用 externalPush(task) 这个用法,源码的主角终于要登场了
但是......
如果你看 externalPush 代码,第一行就是声明一个 WorkQueue 数组变量,为了后续流程更加丝滑,咱还得铺垫一点 WorkQueue 的知识(又要铺垫)
一看这么多成员变量,还是很慌的,不过,我们只需要把我几个主要的就足够了
我们上面说了,WorkQueue 是一个双端队列,线程池有 runState,WorkQueue 有 scanState
操作线程池需要锁,操作队列也是需要锁的,qlock 就派上用场了
WorkQueue 中也有个 config,但是和 ForkJoinPool 中的是不一样的,WorkQueue 中的config 记录了该 WorkQueue 在 WorkQueue[] 数组的下标以及 mode
其他字段的含义我们就写在代码注释中吧,主角重新登场,这次是真的
文章前面说过,task 会细分成 submission task
和 worker task
,worker task
是 fork
出来的,那从这个入口进入的,自然也就是 submission task
了,也就是说:
invoke()
| submit()
| execute()
等方法提交的 task, 是 submission task
,会放到 WorkQueue 数组的偶数索引位置fork()
方法生成出的任务,叫 worker task,会放到 WorkQueue 数组的奇数索引位置该方法上的注释也写的很清楚,具体请参考代码注释
上面加了三处 Flag,为了让大家更好的理解代码还是有必要做进一步说明的:
Flag1: ThreadLocalRandom 是 ThreadLocal 的衍生物,每个线程默认的 probe 是 0,当线程调用ThreadLocalRandom.current()时,会初始化 seed 和 probe,维护在线程内部,这里就知道是生成一个随机数就好,具体细节还是值得大家自行看一下
Flag2: 这里包含的信息还是非常多的
Flag3: 看过 flag2 的描述,你也就很好理解 Flag 3 了,如果是第一次提交任务,必走 Flag 3 的 externalSubmit
方法
这个方法很长,但没超过 80 行,具体请看方法注释
Flag1.1 : 有个细节需要说一下,我们在 Java AQS队列同步器以及ReentrantLock的应用 时提到过使用锁的范式以及为什么要这样用,ForkJoinPool
这里同样遵循这种范式
Flag1.2: 简单描述这个过程,就是根据不同的并行度来初始化不同大小的 WorkQueue[]数组,数组大小要求是 2 的 n 次幂,所以给大家个表格直观理解一下并行度和队列容量的关系:
并行度p | 容量 |
---|---|
1,2 | 4 |
3,4 | 8 |
5 ~ 8 | 16 |
9 ~ 16 | 32 |
Flag 1,2,3: 如果你理解了上面这个方法,很显然,第一次执行这个方法内部的逻辑顺序应该是 Flag1
——> Flag3
——>Flag2
externalSubmit 如果任务成功提交,就会调用 signalWork
方法了
前面铺垫的知识要大规模派上用场(一大波僵尸来袭),are you ready?
如果 ForkJoinPool 的 ctl 成员变量的作用已经忘了,赶紧向上翻重新记忆一下
假设程序刚开始执行,那么活动线程数以及总线程数肯定都没达到并行度要求,这时就会调用 tryAddWorker
方法了
tryAddWorker 的逻辑就非常简单了,因为是操作线程池,同样会用到 lockRunState
/unlockRunState
的锁控制
一切顺利,就要调用 createWorker 方法来创建真正的 Worker 了,形势逐渐明朗
介绍过了 WorkerQueue 和 ForkJoinTask,上文说的三个重要角色中的最后一个 ForkJoinWorkerThread
终于登场了
Worker 线程是如何与 WorkQueue 对应的,就藏在 fac.newThread(this)
这个方法里面,下面这点代码展示一下调用过程
很显然核心内容在 registerWorker
方法里面了
到这里线程是顺利创建成功了,可是如果线程没有创建成功,就需要 deregisterWorker来做善后工作了
deregisterWorker 方法接收刚刚创建的线程引用和异常作为参数,来做善后工作,将 registerWorker 相关工作撤销回来
总之 deregisterWorker 方法从线程池里注销线程,清空WorkQueue,同时更新ctl,最后做可能的替换,根据线程池的状态决定是否找一个自己的替代者:
deregisterWorker 线程解释清楚了是为了帮助大家完整理解流程,但 registerWorker 成功后的流程还没走完,咱得继续,有了 Worker,那就调用 wt.start()
干活吧
ForkJoinWorkerThread 继承自Thread,调用start() 方法后,自然要调用自己重写的 run() 方法
方法的重点自然是进入到 runWorker
runWorker 是很常规的三部曲操作:
具体请看注释
先来看 scan 方法
ForkJoinPool 的任务窃取机制要来了,如何 steal 的,就藏在scan 方法中
如果顺利扫描到任务,那就要调用 runTask 方法来真正的运行这个任务了
马上就接近真相了,steal 到任务了,就干点正事吧
Flag1: doExec 方法才是真正执行任务的关键,它是链接我们自定义 compute 方法的核心,来看 doExec 方法
形势一片大好,挺住,揭开 exec 的面纱,就看到本质了
到这里,我们已经看到本质了,绕了这么一大圈,终于和我们自己重写的compute方法联系到了一起,真是不容易,但是 runWorker 三部曲还差最后一曲 awaitWork 没谱,我们来看看
上面说的是 scan 到了任务,要是没有scan到任务,那就得将当前线程阻塞一下,具体标注在注释中,可以简单了解一下
到这里,ForkJoinPool 的完整流程算是有个基本了解了,但是我们前面讲的这些内容都是从 submission task 作为切入点的。刚刚聊到的 compute 方法,我们按照分治算法范式写了自己的逻辑,具体请回看文中开头的demo,很关键的一点是,我们在 compute 中调用了 fork 方法,这就给我们了解 worker task 的机会了,继续来看 fork 方法
Fork 方法的逻辑很简单,如果当前线程是 ForkJoinWorkerThread 类型,也就是说已经通过上文注册的 Worker,那么直接调用 push 方法将 task 放到当前线程拥有的 WorkQueue 中,否则就再调用 externalPush 重走我们已上说的所有逻辑(你敢再走一遍吗?)
有 fork 就有 join,继续看一下 join 方法()
join 的核心调用在 doJoin,但是看到这么多级联三元运算符,我慌了
我们将 doJoin 方法用我们最熟悉的 if/else 做个改动,是不是就豁然开朗了
其中 awaitJoin 和 externalAwaitDone 都用到了 Helper(帮助) 和 Compensating(补偿) 两种策略,这两种策略大家完全可以自行阅读了,尤其是 awaitJoin 方法,强烈推荐大家自行阅读,其中 pop 的过程在这里,这里不再展开
到这里,有关 ForkJoinPool 相关的内容就算是结束了,为了让大家有个更好的理解 fork/join 机制,我们还是画几张图解释一下
假设我们的大任务是 Task(8), 最终被分治成可执行的最小单元是 Task(1)
按照分治思想拆分任务的整体目标就是这样滴:
从外部先提交一个大的 Task(8),将其放在偶数槽位中(请注意颜色对应)
不满足并行度,会创建 Worker 1 来扫描,并从 base 端窃取到任务 task(8),执行到 compute, fork
出两个 task(4), 并 push到 WorkQueue 中
在执行任务时始终会确认是否满足并行度要求,如果没有就会继续创建新的Worker,与此同时,也会继续 fork 任务,直到最小单元。Worker1 会从 top 端 pop 出来 task(4) 来继续 compute 和 fork,并重新 push 到 WorkQueue 中
task(2) 还不是最小单元,所以会继续 pop 出 task(2),并最终 fork 出两个 task(1) push 到 WorkQueue中
task(1) 已经是最小粒度了,可以直接 pop 出来执行,获取最终结果;在 Worker1 进行这些 pop 操作的同时,为了满足并行度要求也会创建的其他Worker,比如 Worker 2,这时 Worker2 会从 Worker 1 所在队列的 base 端窃取任务
Worker 2 依旧是按照这个规则进行 pop->fork,到最终可以 exec 任务,假设 Worker 1 的任务先执行完,要 join 结果,当 join task(4) 时,通过 hint 定位到是谁偷走了 task(4),这时顺藤摸瓜找到 Worker2,如果 Worker2 还有任务没执行完,Worker1 再窃取回来帮着执行,这样互帮互助,最终快速完成任务
这又是一篇长文,很多小伙伴私下都建议我将长文拆开,一方面读者好消化,另一方面我自己也在数量的体现上变得高产。几次想拆开,但好多文章拆开就失去了连续性(大家都有遗忘曲线)。过年没回老家,就有时间撸文章了。为了更好的理解源码,文章的基础铺垫内容很多,看到这,你应该很累了,想要将更零散的知识点串起来,那就多看代码注释回味一下,然后一起膜拜 Doug Lea 吧