[toc]

在前面學習了ThreadpoolExecutor線程池之后，我們知道，ThreadPoolExecutor實際上是AbstractExecutorService的一個實現(xiàn)類牵寺。我們再看看AbstractExecutorService的實現(xiàn)類：

AbstractExecutorService及其實現(xiàn)類

在前面已經(jīng)介紹了ThreadPoolExecutor及DelegatedExecutorService(它是ThreadPoolExecutor的一個封裝類钉汗，目的是為了將功能隔離，避免對ThreadPoolExecutor內(nèi)部參數(shù)的調(diào)整)闷尿。那么還有一個非常重要的實現(xiàn)就是ForkJoinPool葫慎，那么我們來看看ForkJoin的基本使用衔彻。

1.ForkJoinPool是什么

ForkJoinPool是自java7開始，jvm提供的一個用于并行執(zhí)行的任務框架幅疼。其主旨是將大任務分成若干小任務，之后再并行對這些小任務進行計算昼接，最終匯總這些任務的結(jié)果爽篷。得到最終的結(jié)果。其廣泛用在java8的stream中慢睡。
這個描述實際上比較接近于單機版的map-reduce逐工。都是采用了分治算法铡溪，將大的任務拆分到可執(zhí)行的任務，之后并行執(zhí)行泪喊，最終合并結(jié)果集棕硫。區(qū)別就在于ForkJoin機制可能只能在單個jvm上運行袒啼，而map-reduce則是在集群上執(zhí)行哈扮。此外，F(xiàn)orkJoinPool采取工作竊取算法蚓再，以避免工作線程由于拆分了任務之后的join等待過程滑肉。這樣處于空閑的工作線程將從其他工作線程的隊列中主動去竊取任務來執(zhí)行。這里涉及到的兩個基本知識點是分治法和工作竊取摘仅。

1.1 分治法

分治法的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題靶庙，這些子問題的相互獨立且與原問題的性質(zhì)相同，求出子問題的解之后娃属，將這些解合并六荒，就可以得到原有問題的解。是一種分目標完成的程序算法矾端。簡單的問題掏击，可以用二分法來完成。
二分法须床，就是我們之前在檢索的時候經(jīng)常用到的Binary Search 铐料。這樣可以迅速將時間復雜度從O(n)降低到O(log n)。那么對應到ForkJoinPool對問題的處理也如此豺旬∧瞥停基本原理如下圖：

分治原理

這只是一個簡化版本的Fork-Join，實際上我們在日常工作中的應用可能比這要復雜很多族阅。但是基本原理類似篓跛。這樣就將一個大的任務，通過fork方法不斷拆解坦刀，直到能夠計算為止愧沟，之后，再將這些結(jié)果用join合并鲤遥。這樣逐次遞歸沐寺，就得到了我們想要的結(jié)果。這就是再ForkJoinPool中的分治法盖奈。

1.2 工作竊然煳搿（work-stealing）

工作竊取是指當某個線程的任務隊列中沒有可執(zhí)行任務的時候，從其他線程的任務隊列中竊取任務來執(zhí)行，以充分利用工作線程的計算能力究孕，減少線程由于獲取不到任務而造成的空閑浪費啥酱。在ForkJoinpool中，工作任務的隊列都采用雙端隊列Deque容器厨诸。我們知道镶殷，在通常使用隊列的過程中，我們都在隊尾插入微酬，而在隊頭消費以實現(xiàn)FIFO绘趋。而為了實現(xiàn)工作竊取。一般我們會改成工作線程在工作隊列上LIFO,而竊取其他線程的任務的時候得封，從隊列頭部取獲取埋心。示意圖如下：

工作竊取

工作線程worker1、worker2以及worker3都從taskQueue的尾部popping獲取task忙上，而任務也從尾部Pushing拷呆，當worker3隊列中沒有任務的時候，就會從其他線程的隊列中取stealing疫粥，這樣就使得worker3不會由于沒有任務而空閑茬斧。這就是工作竊取算法的基本原理。
可以想象梗逮，要是不使用工作竊取算法项秉，那么我們在不斷fork的過程中，可能某些worker就會一直處于join的等待中慷彤。工作竊取的思想娄蔼，實際實在golang協(xié)程的底層處理中也是如此。

2.簡單使用

在弄清楚了fork-join是什么了之后底哗，我們來看看JUC中為我們提供的forkjoin是如何工作的岁诉。
在juc中，實現(xiàn)Fork-join框架有兩個類跋选，分別是ForkJoinPool以及提交的任務抽象類ForkJoinTask涕癣。對于ForkJoinTask，雖然有很多子類前标，但是我們在基本的使用中都是使用了帶返回值的RecursiveTask和不帶返回值的RecursiveAction類坠韩。

ForkJoinTask及其實現(xiàn)類

我們通過繼承這兩個類來實現(xiàn)兩種類型的計算。

2.1 不帶返回值的計算

RecursiveAction可以實現(xiàn)不帶返回值的fork-join計算炼列。實現(xiàn)如下：

package com.dhb.forkjoinpool;

import java.util.concurrent.RecursiveAction;

public class PrintTask extends RecursiveAction {

    private static final long serialVersionUID = 1L;

    private static final int THRESHOLD = 9;

    private  int start;

    private  int end;

    public PrintTask(int start, int end) {
        super();
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {

        if(end - start  < THRESHOLD) {
            for(int i=start;i<=end;i++) {
                System.out.println(Thread.currentThread().getName()+",i="+i);
            }
        }else {
            int middle = (start + end) / 2;
            PrintTask firstTask = new PrintTask(start,middle);
            PrintTask secondTask = new PrintTask(middle+1,end);
            invokeAll(firstTask,secondTask);
        }

    }
}

再執(zhí)行如下main方法：

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.TimeUnit;

public class ForkJoinPoolTest {

    public static void main(String[] args) throws Exception{
        testNoResultTask();
    }

    private static void testNoResultTask() throws InterruptedException{
        ForkJoinPool pool = new ForkJoinPool();
        pool.submit(new PrintTask(1,50));
        pool.awaitTermination(2, TimeUnit.SECONDS);
        pool.shutdown();
    }
}

上述代碼執(zhí)行：

ForkJoinPool-1-worker-1,i=1
ForkJoinPool-1-worker-1,i=2
ForkJoinPool-1-worker-1,i=3
ForkJoinPool-1-worker-1,i=4
ForkJoinPool-1-worker-1,i=5
ForkJoinPool-1-worker-1,i=6
ForkJoinPool-1-worker-2,i=26
ForkJoinPool-1-worker-1,i=7
ForkJoinPool-1-worker-2,i=27
ForkJoinPool-1-worker-3,i=14
ForkJoinPool-1-worker-1,i=8
ForkJoinPool-1-worker-3,i=15
ForkJoinPool-1-worker-2,i=28
ForkJoinPool-1-worker-3,i=16
ForkJoinPool-1-worker-3,i=17
ForkJoinPool-1-worker-3,i=18
ForkJoinPool-1-worker-3,i=19
ForkJoinPool-1-worker-3,i=20
ForkJoinPool-1-worker-1,i=9
ForkJoinPool-1-worker-5,i=45
ForkJoinPool-1-worker-3,i=21
ForkJoinPool-1-worker-4,i=33
ForkJoinPool-1-worker-7,i=39
ForkJoinPool-1-worker-2,i=29
ForkJoinPool-1-worker-7,i=40
ForkJoinPool-1-worker-4,i=34
ForkJoinPool-1-worker-4,i=35
ForkJoinPool-1-worker-4,i=36
ForkJoinPool-1-worker-4,i=37
ForkJoinPool-1-worker-4,i=38
ForkJoinPool-1-worker-3,i=22
ForkJoinPool-1-worker-3,i=23
ForkJoinPool-1-worker-5,i=46
ForkJoinPool-1-worker-5,i=47
ForkJoinPool-1-worker-5,i=48
ForkJoinPool-1-worker-1,i=10
ForkJoinPool-1-worker-1,i=11
ForkJoinPool-1-worker-1,i=12
ForkJoinPool-1-worker-1,i=13
ForkJoinPool-1-worker-5,i=49
ForkJoinPool-1-worker-3,i=24
ForkJoinPool-1-worker-7,i=41
ForkJoinPool-1-worker-7,i=42
ForkJoinPool-1-worker-7,i=43
ForkJoinPool-1-worker-2,i=30
ForkJoinPool-1-worker-7,i=44
ForkJoinPool-1-worker-3,i=25
ForkJoinPool-1-worker-5,i=50
ForkJoinPool-1-worker-2,i=31
ForkJoinPool-1-worker-2,i=32

可以看到上述線程將1-50并行的print出來只搁。

2.2 帶返回值的計算

通過實現(xiàn)RecursiveTask來進行帶有返回值的計算。如我們需要計算1-1000000的累加結(jié)果俭尖。實現(xiàn)如下：

package com.dhb.forkjoinpool;

import java.util.concurrent.RecursiveTask;

public class CalculateTask extends RecursiveTask<Integer> {

    private static final long serialVersionUID = 1L;
    private static final int THRESHOLD = 49;
    private int start;
    private int end;

    public CalculateTask(int start, int end) {
        this.start = start;
        this.end = end;
    }


    @Override
    protected Integer compute() {
        if (end - start <= THRESHOLD) {
            int result = 0;
            for (int i = start; i <= end; i++) {
                result += i;
            }
            return result;
        } else {
            int middle = (start + end) / 2;
            CalculateTask firstTask = new CalculateTask(start, middle);
            CalculateTask secondTask = new CalculateTask(middle + 1, end);
            invokeAll(firstTask,secondTask);
            return firstTask.join() + secondTask.join();
        }
    }

}

主函數(shù)如下：

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.TimeUnit;

public class ForkJoinPoolTest {

    public static void main(String[] args) throws Exception{
        testHasResultTask();
    }
    
    public static void testHasResultTask() throws Exception {
        int result1 = 0;
        for (int i = 1; i <= 1000000; i++) {
            result1 += i;
        }
        System.out.println("循環(huán)計算 1-1000000 累加值：" + result1);

        ForkJoinPool pool = new ForkJoinPool();
        ForkJoinTask<Integer> task = pool.submit(new CalculateTask(1, 1000000));
        int result2 = task.get();
        System.out.println("并行計算 1-1000000 累加值：" + result2);
        pool.awaitTermination(2, TimeUnit.SECONDS);
        pool.shutdown();
    }
}

上述代碼執(zhí)行結(jié)果：

循環(huán)計算 1-1000000 累加值：1784293664
并行計算 1-1000000 累加值：1784293664

這樣就非常容易的實現(xiàn)了一個基于并行的計算氢惋。

3.ForkJoin源碼注釋

在我們看源碼的過程種，前面也對Doug Lea 的論文《A Java Fork/Join Framework（Doug Lea 關(guān)于java Fork/Join框架的論文翻譯）》進行了翻譯。在論文中作者詳細闡述了java中Fork/join的基本原理明肮。而且這些原理在實現(xiàn)的過程中，還在源碼中寫了大段的注釋缭付。這些注釋翻譯如下：

3.1 類注釋

ForkJoinPool是一個用于運行ForkJoinTask的ExecutorService柿估。提供了一個非ForkJoinTask客戶端的提交點，以及執(zhí)行管理和監(jiān)控操作陷猫。
ForkJoinPool不同于其他種類的ExecutorService,其主要是通過工作竊取來進行：ForkJoinPool中的所有線程都會嘗試查找并執(zhí)行提交到線程池中由其他活動創(chuàng)建的任務秫舌，如果不存在這些任務，則進行阻塞绣檬。當大多數(shù)任務派生其他子任務的時候足陨，以及從外部客戶端向pool中提交諸多小任務的時候，這可以實現(xiàn)高效處理娇未，尤其是在構(gòu)造函數(shù)中將asyncMode 設置為true的時候墨缘。ForkJoinPool也可能適用于從未加入的事件樣式任務。
靜態(tài)的commonPool方法可以適用于大多數(shù)應用程序零抬，任何未顯示提交到指定pool的ForkJoinTask都將使用公共的pool镊讼，這樣會減少資源的使用，在不使用期間緩慢回收線程平夜，并在后續(xù)使用時將其恢復蝶棋。
對于需要單獨或者自定義的pool，可以使用給定目標并行度來創(chuàng)建ForkJoinPool忽妒。默認情況下玩裙，并行度等于處理器的數(shù)量，pool嘗試通過動態(tài)添加段直，暫统越Γ或恢復內(nèi)部工作線程來維護足夠的活動（或可用）線程，即使某些任務因等待加入其他任務而停滯不前坷牛。但是罕偎，面對阻塞的I/O或其他非托管同步，無法保證此類調(diào)整京闰。嵌套的ManagedBlocker接口可擴展可容納的同步類型颜及。
除了執(zhí)行線程和生命周期的控制方法之外，此類還提供了狀態(tài)檢查方法蹂楣，getStealCount俏站。旨在幫助開發(fā)、調(diào)整和監(jiān)控fork / join應用程序痊土。同樣肄扎，方法toString以方便的形式返回池的狀態(tài)指示，以進行非正式監(jiān)控。
與其他ExecutorService一樣犯祠，下表總結(jié)了三種主要的任務執(zhí)行方法旭等。這些被設計為主要供尚未在當前池中進行派生/聯(lián)接計算的客戶端使用。這些方法的主要形式接受ForkJoinTask的實例衡载，但是重載形式還允許混合執(zhí)行基于普通Runnable和Callable的活動搔耕。但是，已經(jīng)在池中執(zhí)行的任務通常應改為使用表中列出的內(nèi)部計算形式痰娱，除非使用通常不聯(lián)接的異步事件樣式任務弃榨，在這種情況下，方法選擇之間幾乎沒有區(qū)別梨睁。
<table BORDER CELLPADDING=3 CELLSPACING=1>
<caption>Summary of task execution methods</caption>
<tr>
<td></td>
<td ALIGN=CENTER> <b>Call from non-fork/join clients</b></td>
<td ALIGN=CENTER> <b>Call from within fork/join computations</b></td>
</tr>
<tr>
<td> <b>Arrange async execution</b></td>
<td> {@link #execute(ForkJoinTask)}</td>
<td> {@link ForkJoinTask#fork}</td>
</tr>
<tr>
<td> <b>Await and obtain result</b></td>
<td> {@link #invoke(ForkJoinTask)}</td>
<td> {@link ForkJoinTask#invoke}</td>
</tr>
<tr>
<td> <b>Arrange exec and obtain Future</b></td>
<td> {@link #submit(ForkJoinTask)}</td>
<td> {@link ForkJoinTask#fork} (ForkJoinTasks <em>are</em> Futures)</td>
</tr>
</table>
默認情況下鲸睛，共的池是使用默認構(gòu)造函數(shù)構(gòu)造的，但是可以通過三個參數(shù)來設置和控制這些參數(shù)坡贺。（ System#getProperty）官辈。

如果存在SecurityManager且沒有指定工廠類遍坟，那么默認的池將使用一個工廠類提供的線程钧萍。改線程沒有啟動Permissions。系統(tǒng)的類加載器用于加載這些類政鼠。在建立這些設置的時候出現(xiàn)任何錯誤风瘦，將使用默認參數(shù)，通過將parallelism屬性設置為零和/或使用可能返回{@code null}的工廠公般，可以禁用或限制公共池中線程的使用万搔。但是這樣做可能會導致未連接的任務永遠無法執(zhí)行。
實現(xiàn)注意：
ForkJoinPool將運行線程的最大數(shù)量限制為32767官帘。嘗試創(chuàng)建大于最大數(shù)目的池會導致{@code IllegalArgumentException}瞬雹。
這個實現(xiàn)只在池關(guān)閉或者內(nèi)部資源耗盡的時候才拒絕提交任務。通過拋出RejectedExecutionException異常刽虹。

3.2 關(guān)于原理的注釋

在代碼中也存在大段注釋酗捌，大意為：

3.2.1 ForkJoinPool實現(xiàn)概述

此類及其內(nèi)部的嵌套類為一組工作線程提供了主要的功能和控制，來自非ForkJoin線程的提交進入提交隊列涌哲，之后通常將這些提交拆分為子任務胖缤，這些子任務可能會被其他線程竊取。優(yōu)先規(guī)則優(yōu)先處理其自身隊列按照LIFO或者FIFO（取決于模式定義）的任務阀圾。然后處理其他隊列中的隨機FIFO竊取任務哪廓。該框架最初是實現(xiàn)工作竊取來支持樹形并行性工具的。隨著時間的流逝初烘，其可伸縮性優(yōu)勢導致了擴展和更改涡真。以更好的支持更多不同使用的上下文分俯。由于大部分內(nèi)部方法和嵌套類是相互關(guān)聯(lián)的，因此此處介紹他們的主要原理和描述哆料。單個方法和嵌套類僅僅包含有關(guān)詳細信息的簡短注釋缸剪。

3.2.2 WorkQueues

大多數(shù)操作發(fā)生在工作竊取隊列中，（在內(nèi)嵌的workQeue中）东亦。這個隊列是Deques的特殊形式橄登。僅支持四種可能的最終操作中的三種，push讥此、pop和poll（也稱為竊取）谣妻。在進一步的約束下萄喳，push和pop僅從其所有線程處或者擴展線程調(diào)用，此時處于鎖定狀態(tài)蹋半，而poll可以從其他線程調(diào)用他巨，如果你不熟悉他們，則在繼續(xù)閱讀之前Herlihy和Shavit的著作《The Art of Multiprocessor programming》第十六章對此進行了更加詳細的描述减江。主要的工作竊取隊列的設計大致與Chase和Lev的論文 《Dynamic Circular Work-Stealing Deque》和Michael染突，Saraswat和Vechev撰寫的《Idempotent work stealing》。與之最大的不同在于由于GC的要求辈灼，即使在生成大量的任務的程序中份企，我們也需要盡快清空已占用的空間。為了實現(xiàn)這一點巡莹，我們將CAS與pull竊取操作從索引的base和top移動到slots本身司志。
添加任務則采用經(jīng)典的數(shù)組push(task)操作：

 q.array[q.top] = task; ++q.top;

實際的代碼需要對數(shù)組進行非空檢查和大小檢查。需要正確的屏蔽訪問降宅，并可能的等待worker開始掃描的信號骂远。見下文，成功的pop和poll都需要通過cas操作實現(xiàn)從非null到null腰根。
pop操作的過程為(始終由任務所有者執(zhí)行) ：

if ((base != top) and
     (the task at top slot is not null) and
        (CAS slot to null))
       decrement top and return task;

而而poll操作(通常由竊取者執(zhí)行)是：

if ((base != top) and
    (the task at base slot is not null) and
    (base has not changed) and
       (CAS slot to null))
      increment base and return task;

由于我們依賴于引用的情況激才，因此不需要在base和top上做標記，他們是在任何基于循環(huán)數(shù)組隊列中使用的簡單整數(shù)额嘿。請參見ArrayDeque瘸恼。對索引的更新保證top==base意味著隊列是空的。如果沒有完全提交push册养、pop或者poll則可能會出錯钞脂，使隊列看起來不空，方法isEmpty（）用來檢查最后一個元素不空的情況捕儒。因此冰啃，單獨考慮的輪詢操作不是無等待的邓夕，一個竊取線程無法成功的繼續(xù)直到另外一個正在進行的竊取線程完成。（或者如果先前是空的則這是一次push操作阎毅。）然而焚刚，總的來說，我們至少保證了概率的非阻塞性扇调，如果一次竊取微能成功矿咕，竊取線程總是會隨機選擇下一個不同的隊列進行下一次嘗試。因此狼钮，為了讓一次竊取繼續(xù)碳柱，任何正在進行的輪詢或者對任何空隊列的新推送都可以完成。這就是為什么我們通常使用方法pollAt及其變量熬芜，在base索引處嘗試一次莲镣，否則就考慮其他操作，而不是執(zhí)行方法poll涎拉，后者會重試瑞侮。
這種方法還支持用戶模式，在這種模式下鼓拧，本地任務采用FIFO而不是LIFO半火，只需要使用poll而不是pop。這在從不連接任務的消息傳遞框架中非常有用季俩。然而钮糖，這兩種模式都不考慮親和力、負載酌住、緩存位置等藐鹤。因此很少在給定的機器上提供最佳性能，但通過平均這些因素赂韵，可移植地提供良好的吞吐量娱节。此外，即使我們試圖使用這些信息祭示，我們通常也沒有利用這些信息的基礎肄满，例如，某些任務集從緩存親和力中獲利质涛，但其他任務集則受到緩存污染效應的損害稠歉。因此，即使他需要掃描汇陆，長期吞吐量通常最好使用隨機選擇策略怒炸，而不是定向選擇策略，因此只要適用毡代，就可以使用足夠質(zhì)量的廉價隨機化阅羹。各種Marsaglia xorshift（有些具有不同的移位常數(shù)）在使用點內(nèi)聯(lián)勺疼。
工作隊列也可以用類似的方法處理提交到pool的任務。我們不能將這些任務混合在worker使用的同一個隊列中捏鱼。相反我們使用散列的形式將提交隊列與提交線程隨機關(guān)聯(lián)起來执庐，ThreadLocalRandom probe 的值用作選擇現(xiàn)有隊列的hashcode。并且可以在與其他提交者發(fā)生競爭的時候隨機重新定位导梆。從本質(zhì)上講轨淌，提交者的行為類似于worker，只不過他們被限制在執(zhí)行他們被提交的本地任務或者在countedcompleter的情況下與其他具有相同根任務的任務看尼。在共享模式下插入任務需要一個鎖递鹉，主要是為了在調(diào)整大小的情況下進行保護，但是我們只使用了一個簡單的spinlock藏斩，使用字段qlock躏结。因為遇到繁忙隊列的提交者會繼續(xù)嘗試或者創(chuàng)建其他隊列，他們僅在創(chuàng)建和注冊新隊列的時候才會阻塞灾茁。另外，qlock在關(guān)閉時飽和到不可鎖定值-1谷炸，在成功的情況下北专，解鎖任然可以并且通過更便宜的順序?qū)懭雚lock來執(zhí)行，但是在不成功的情況下使用cas旬陡。

3.2.3 管理

工作竊取機制的主要吞吐量的優(yōu)勢來自于分散控制拓颓。worker大多從自己或者彼此手中接任務，速度可以超過每秒10億次描孟，pool自身創(chuàng)建山涡、激活蠢正、阻塞、停用和終止線程。所有的這些都只需要最少的中心信息看政。只有少數(shù)的屬性可以全局跟蹤和維護，因為我們將它們打包到少數(shù)變量中瞄勾。通常在不阻塞或者鎖定的情況下保持原子性塘揣。幾乎所有的基本的原子控制狀態(tài)都保存在兩個volatile變量中。這兩個變量最常被讀取憋他，而不是寫入孩饼，做為狀態(tài)和一致性檢查。另外竹挡，字段config保持不變性的配置狀態(tài)镀娶。
字段ctl包含64位信息，這些信息用于原子的添加揪罕，停用梯码、入隊（在事件隊列上）宝泵。出隊或重新激活worker所需要的信息，為了實現(xiàn)將這些內(nèi)容都打包到一個字段上忍些。我們將最大并行度設置為(1<<15)-1,這個值已經(jīng)遠遠超出了現(xiàn)實中的工作范圍鲁猩。以允許對這個值進行id、計數(shù)罢坝、以及取反操作廓握。適用于16位的子字段。
字段runState保存可鎖定狀態(tài)位嘁酿，STARTED隙券、STOP等。還保護對workQueues的更新闹司。當用作鎖的時候娱仔，它通常僅保留幾條指令。唯一的例外是一次性數(shù)組的初始化和不常見的調(diào)整大小游桩。因此幾乎總是在經(jīng)過短暫的自旋之后才可用牲迫。自旋之后，方法awaitRunStateLock（僅在初始化cas失敗的時候才調(diào)用）在內(nèi)置Monitor上的使用wait/notify的機制來進行阻塞借卧。對于高度競爭的鎖盹憎，這將是一個很糟糕的主意。但是大多數(shù)pool在自旋之后沒有競爭的情況下運行铐刘，因此陪每，做為更保守的替代方法，它可以很好地工作镰吵，因為我們沒有內(nèi)部對象的monitor檩禾，因此可以使用stealCounter（這個方法是原子的，但是它也必須延遲初始化疤祭，請參閱externalSubmit）盼产。
runState和ctl僅在一種情況下交互，決定添加一個工作線程（請參閱tryAddWorker）在這種情況下勺馆，ctl 的CAS是在持有鎖的情況下進行的辆飘。

• 記錄工作隊列
  工作隊列記錄在工作隊列數(shù)組中。該數(shù)組在首次使用的時候創(chuàng)建（請參閱externalSubmit）谓传。并在必要的時候進行擴展蜈项。在記錄新工作線程和取消記錄終止工作線程時對數(shù)組的更新受到runState鎖的保護，但彼此并發(fā)可讀续挟，并且可以直接訪問該數(shù)組紧卒。我們還確保對數(shù)組引用本身的讀取永遠不會過時。為了簡化基于索引的操作诗祸，數(shù)組大小始終為2的冪跑芳，并且所有讀取器都必須允許空槽位轴总。worker隊列處于奇數(shù)的索引處，共享的（提交）隊列處于偶數(shù)索引博个。最多64個槽位怀樟。以限制增長。即便隊列需要擴展以增加更多的worker也如此盆佣。以這種方式將它們分組在一起可簡化并加速對任務的scan操作往堡。
  所有工作線程的創(chuàng)建都是按需創(chuàng)建的。由任務提交共耍，替換虑灰、終止的worker或補償被阻止的worker觸發(fā)。但是痹兜，所有其他的支持代碼已設置為可與其他策略一起使用穆咐。為確保不保留會阻止GC的工作程序的引用。對workerQueue的所有訪問均通過對workerQueues數(shù)組的索引（這是此處某些混亂代碼的來源之一）進行字旭。本質(zhì)上对湃，workQueues數(shù)組用作弱引用機制。因此遗淳，例如ctl的stack top子字段存儲索引拍柒，而不是引用。
  排隊空閑的worker與HPC工作竊取框架不同洲脂，我們不能讓worker無限制的輪詢發(fā)現(xiàn)任何任務斤儿。并且除非有任務可用剧包。否則我們不能start/resume這些workers恐锦。另外一方面，在提交或者新生成的任務的時候疆液，我們必須迅速使它們生效一铅。在許多情況下，激活工作人員的加速時間是整體性能的主要限制因素堕油。在程序啟動的時候潘飘，通過JIT編譯和分配會更加復雜。因為掉缺，我們盡可能的簡化這個過程卜录。
• ctl字段
  原子的維護活動和worker的數(shù)量。以及用于放置等待線程的隊列眶明，以便可以定位它們發(fā)出的信號艰毒。主動計數(shù)也起著靜態(tài)的指標作用。因此當工作人員認為沒有更多的要執(zhí)行的任務的時候搜囱，主動計數(shù)就會減少丑瞧。隊列實際上就是Treiber堆棧的一種形式柑土。堆棧是按最近使用的順序激活線程的理想選擇。這改善了性能和局部性绊汹』粒克服了易于爭用和無法釋放 工作程序的缺點。（除非其在堆棧上位于頂部）西乖。當worker找不到任務的時候狐榔，將他們推入閑置的worker堆棧，由ctl較低的32位字段表示浴栽。我們將worker停放荒叼。最高堆棧狀態(tài)保存工作程序的scanState字段值。其索引和狀態(tài)典鸡，以及一個版本計數(shù)器被廓。該計數(shù)器除了count字段之外，還用作版本標記萝玷，用以提供對Treiber堆棧ABA問題的保護嫁乘。
  工作程序和pool都使用scanState來管理和跟蹤工作程序是不活動的。（可能處于阻塞球碉，等待信號）蜓斧，這是對任務進行掃描（當兩個都不持有它的線程正在忙于運行任務時）。取消激活工作程序之后睁冬，將設置其scanState字段挎春。并阻止其執(zhí)行任務。即使它必須對其進行掃描一次豆拨，也可以避免排隊直奋。請注意，scanState更新延遲隊列CAS釋放施禾，因此使用時需要注意脚线。排隊時，scanState的低16位必須保持其池的索引弥搞。因此我們在初始化的時候?qū)⑺饕胖迷诖颂幱事獭Ｕ垍⒁姡╮egisterWorker）否則將其保留在索引處，或在必要時將其還原攀例。
  內(nèi)存排序船逮，有關(guān)分析請參閱Le, Pop, Cohen, and Nardelli撰寫的《PPoPP 2013》類似于本文中使用的工作竊取算法中的內(nèi)存排序要求。我們通常需要比最小順序更強的命令粤铭，因為有時我們必須向worker發(fā)出信號挖胃。要求像Dekker一樣的全屏障以防止信號丟失。要安排足夠的排序而又不花費過多的費用，則需要在表示訪問限制的受支持方法之間進行權(quán)衡冠骄。最重要的操作是從隊列中獲取并更新ctl狀態(tài)伪煤，這需要完整的CAS。使用Unsafe提供的volatile的模擬讀取Array的槽位凛辣。從其他線程訪問WorkQueue的base抱既，top和array需要對這些讀取中的任何一個進行volatile加載。我們申明base索引為volatile的約定扁誓，并始終在其他字段之前讀取防泵，或者線程必須確保有序的更新，因此寫操作將使用有序的內(nèi)部函數(shù)蝗敢。除非他們可以負擔其他寫操作的內(nèi)容捷泞。其他WorkQueue字段（例如currentSteal）也具有類似的約定和原理，這些字段僅由所有者寫入但被其他人觀察到寿谴。
• 創(chuàng)建woker
  要創(chuàng)建一個工作程序锁右，我們預增加總數(shù)，用作保留讶泰，并嘗試通過其工廠構(gòu)建一個ForkJoinWorkerThread咏瑟。新線程將調(diào)用registerWorker，在此構(gòu)造一個WorkQueue痪署。并在workQueues數(shù)組中分配一個索引码泞。必要時擴展該數(shù)組。然后啟動線程狼犯。如果這些步驟有任何異常余寥。或者worker返回空值悯森，則deregisterWorker會調(diào)整計數(shù)并進行相應的記錄宋舷，如果返回空值。則pool將繼續(xù)以少于目標數(shù)的worker狀態(tài)運行呐馆。如果出現(xiàn)異常肥缔，則通常將異常傳播到某些外部調(diào)用的地方莲兢。輔助索引的分配避免了在workQueues數(shù)組的開頭開始依次進行打包時發(fā)生的掃描偏差汹来。我們將數(shù)組視為簡單的2的冪的哈希表。并根據(jù)需要進行擴展改艇。seedIndex增量可確保在需要調(diào)整大小或注銷并替換worker之前不會發(fā)生沖突收班。此后將發(fā)生沖突的可能性保持在較低水平，我們不能在這里將ThreadLocalRandom的getProbe()用于類似的目的谒兄。因為線程尚未啟動摔桦。但是這樣做是為了實現(xiàn)外部線程創(chuàng)建提交隊列。
  停用并等待，排隊遇到了一些固有的種類邻耕，最值得注意的是鸥咖，產(chǎn)生任務的線程可能會錯過看到（和發(fā)信號）另一個尋找worker但是尚未進入等待隊列的線程。當worker找不到要進行竊取的任務的時候兄世，它會停用并排隊啼辣，通常，由于GC或者OS調(diào)度御滩。缺少任務是短暫的鸥拧，為了減少錯誤警報的停用，掃描程序會在掃描期間計算隊列的狀態(tài)和校驗和削解。此處和其他地方使用的穩(wěn)定性檢查是快照技術(shù)的概率變體富弦，請參閱Herlihy＆Shavit。工作者放棄并嘗試僅在兩次掃描的總和穩(wěn)定之后才停用它氛驮。此外腕柜，為避免丟失信號，它們在成功入隊后重復此掃描過程矫废，直到再次穩(wěn)定媳握。在這種狀態(tài)下，工作程序無法執(zhí)行/運行它看到的任務磷脯，直到將其從隊列中釋放為止蛾找，因此工作程序本身最終會嘗試釋放其自身或任何后續(xù)任務（請參見tryRelease）。否則赵誓，在進行空掃描時打毛，停用的工作人員會在阻塞（通過停車）之前使用自適應本地自旋構(gòu)造（請參閱awaitWork）。請注意有關(guān)Thread.interrupts圍繞停放和其他阻塞的不尋常約定：由于中斷僅用于提醒線程檢查終止（無論如何在阻塞時進行檢查）俩功，因此我們在調(diào)用任何Park之前清除狀態(tài)（使用Thread.interrupted）幻枉，以便由于通過其他一些不相關(guān)的調(diào)用來設置狀態(tài)以中斷用戶代碼，因此Park不會立即返回诡蜓。
• 信號和激活
  當且僅當至少可以找到并執(zhí)行一個線程的時候熬甫，才創(chuàng)建或者激活工作程序。在由worker或外部提交者將其推送到之前（可能是）的空隊列的時候蔓罚，會在空閑狀態(tài)向worker發(fā)出信號椿肩。或者工作量小于給定的并行度豺谈，則會創(chuàng)建工作線程郑象。每當其他線程從工作中刪除任務并注意到那里還有其他任務時，這些主要信號就會被其他人支持茬末。在大多數(shù)平臺上厂榛，發(fā)信號（釋放）的開銷時間非常長，發(fā)信號的線程與線程實際取得進展之間的時間可能非常長，因此值得從關(guān)鍵路徑上分擔這些延遲击奶。另外辈双，由于不活動的工作人員通常是在重新掃描或旋轉(zhuǎn)而不是阻塞，所以我們設置并清除了WorkQueues的“ parker”字段柜砾，以減少不必要的unpark的調(diào)用辐马。這需要進行二次重新檢查，以避免信號遺漏局义。
  Trimming workers.需要在不使用的一段時間之后釋放資源喜爷，如果pool在IDLE_TIMEOUT期間保持靜止，則在處于靜止狀態(tài)時開始等待的工作程序?qū)⒊瑫r并終止萄唇，（請參閱awaitWork）隨著線程數(shù)的減少檩帐，該時間段將增加，最終遣散所有worker另萤。同樣湃密，當存在兩個以上的備用線程時，多余的線程會在下一個靜態(tài)點立即終止四敞。 （兩次填充可避免滯后現(xiàn)象泛源。）
  Shutdown and Termination,調(diào)用shutdownNow會使用tryTerminate以原子的方式設置runState位。調(diào)用線程以及此后終止的所有其他工作線程忿危，通過設置其（qlock）狀態(tài)达箍。取消其未處理的任務并喚醒它們，反復執(zhí)行直到穩(wěn)定為止铺厨，以幫助終止其他線程（但循環(huán)受工作線程數(shù)量限制） ）缎玫。調(diào)用non-abrupt shutdown（）通過檢查是否應該終止終止來開始此操作。這主要取決于維持共識的“ ctl”的活動計數(shù)位-每當靜態(tài)時解滓，trywaiter從awaitWork調(diào)用赃磨。但是，外部提交者不參與該共識洼裤。因此邻辉，tryTerminate會掃描隊列（直到穩(wěn)定），以確保缺少正在進行中的提交腮鞍，并且工作人員將在觸發(fā)終止的“停止”階段之前對其進行處理值骇。（注意：啟用關(guān)閉功能后，如果調(diào)用helphelpQuiescePool會發(fā)生內(nèi)在沖突缕减。兩者都等待靜止雷客，但是tryTerminate偏向于在helpQuiescePool完成之前不會觸發(fā)芒珠。）

3.2.4 Joining Tasks

當一個worker正在等待join另外一個唄竊取的任務的時候桥狡，可以采取任何行動。因為我們將許多任務復制到一個工作的pool上，所以我們不能僅僅讓他阻塞裹芝，如如Thread.join中一樣部逮。我們也不能僅僅將joiner的運行時堆棧重新分配給另一個，然后在以后替換它嫂易，這將是“ continuation”的一種形式兄朋，即使可能，也不一定是一個好主意怜械，因為我們既需要無阻塞的任務颅和，又需要繼續(xù)執(zhí)行進展。相反缕允，我們結(jié)合了兩種策略：

• Helping: 安排加入者執(zhí)行一些如果沒有發(fā)生竊取將要運行的任務峡扩。
• Compensating: 除非已有足夠的活動線程，否則方法tryCompensate（）可能會創(chuàng)建或重新激活備用線程以補償阻塞的連接器障本，直到它們解除阻塞為止教届。
• 第三種形式（在tryRemoveAndExec中實現(xiàn)）相當于幫助了一個假設的補償器：如果我們可以很容易地看出補償器的可能動作是竊取并執(zhí)行要加入的任務，則加入線程可以直接這樣做驾霜，而無需執(zhí)行任何操作案训。補償線程（盡管以較大的運行時堆棧為代價，但通常值得進行權(quán)衡）粪糙。

ManagedBlocker擴展API不能使用Helping强霎，因此僅依賴于方法awaitBlocker中的補償。

helpStealer中的算法需要一種“線性幫助”形式蓉冈。每個worker（在currentSteal字段中）記錄它從其他worker（或提交）中竊取的最新任務脆栋。它還記錄（在currentJoin字段中）它當前正在主動加入的任務。 helpStealer方法使用這些標記來嘗試尋找可以幫助完成主動加入的任務的工作人員（即從中竊取任務并執(zhí)行該任務）洒擦。因此椿争，如果要加入的任務沒有被竊取，則連接器執(zhí)行的任務將由其自己的本地雙端隊列執(zhí)行熟嫩。這是Wagner＆Calder的 《Leapfrogging: a portable technique for implementing efficient futures》SIGPLAN Notices, 1993 它的不同之處在于：

• （1）我們僅在竊取時在工人之間維護依賴關(guān)系鏈接秦踪，而不使用按任務記帳。有時這需要對workQueues數(shù)組進行線性掃描以找到盜竊者掸茅，但是通常不需要這樣做椅邓，因為盜竊者會留下提示（可能會變得陳舊/錯誤），以查找盜竊者的位置昧狮。這只是一個提示景馁，因為一個工人可能曾多次偷竊，而提示僅記錄了其中一個（通常是最新的）逗鸣。提示將成本隔離到需要的時間合住，而不是增加每個任務的開銷绰精。
• （2）它是“淺”的，忽略了嵌套和潛在的周期性相互竊取透葛。
• （3）這是故意的：字段currentJoin僅在主動加入時更新笨使，這意味著我們在長期任務，GC停頓等過程中會錯過鏈中的鏈接（這是正常的僚害，因為在這種情況下進行阻塞通常是個好主意） 硫椰。
• （4）我們使用校驗和來限制找到工作的嘗試的次數(shù)，然后回退到暫停該工作程序萨蚕，并在必要時將其替換為另一個靶草。

CountedCompleters的helping操作不需要跟蹤currentJoins：方法helpComplete可以執(zhí)行和執(zhí)行與正在等待的任務具有相同根目錄的任何任務（優(yōu)先于本地polls而不是非本地輪詢）。但是岳遥，這仍然需要完成程序鏈的遍歷爱致，因此效率不如使用沒有顯式聯(lián)接的CountedCompleters。
補償?shù)哪康牟⒉皇且_保在任何給定時間都運行無阻塞線程的目標并行度寒随。此類的某些先前版本對任何阻塞的連接立即采用補償糠悯。但是，實際上妻往，絕大多數(shù)阻塞是GC和其他JVM或OS活動的暫時性副產(chǎn)品互艾，這些副產(chǎn)品由于更換而變得更糟。當前讯泣，僅在通過檢查字段WorkQueue.scanState確認所有據(jù)稱活動的線程正在處理任務之后才嘗試進行補償纫普，從而消除了大多數(shù)誤報。同樣好渠，在最不常見的情況下昨稼，繞過補償（允許更少的線程）是很少有好處的：當隊列為空的工人（因此沒有繼續(xù)任務）在聯(lián)接上阻塞時，仍然有足夠的線程來確比活動假栓。
補償機制可能是有界的。 commonPool的界限（請參閱commonMaxSpares）可以使JVM在耗盡資源之前更好地應對編程錯誤和濫用霍掺。在其他情況下匾荆，用戶可能會提供限制線程構(gòu)造的工廠。與其他所有池一樣杆烁，此池中的邊界影響不精確牙丽。當線程注銷時，總的工作人員計數(shù)會減少兔魂，而不是在線程退出并且JVM和OS回收資源時減少烤芦。因此，同時處于活動狀態(tài)的線程數(shù)可能會暫時超出限制析校。

3.2.5 Common Pool

靜態(tài)的公共的pool在靜態(tài)初始化之后始終存在构罗。由于不需要使用它铜涉，或者任何其他創(chuàng)建的pool，因此我們將初始構(gòu)造開銷和占用空間最小化到大約十二個字段的設置绰播，而沒有嵌套分配骄噪。在第一次提交到pool期間尚困，大多數(shù)引導發(fā)生在externalSubmit方法中蠢箩。
當外部線程提交到公共的pool的時候，他們可以在join的時候執(zhí)行子任務的處理事甜，（請參閱externalHelpComplete和相關(guān)方法）通過此呼叫者幫助策略谬泌，可以明智地將公共池并行度級別設置為比可用核心總數(shù)少一個（或多個），對于純呼叫者運行逻谦，甚至可以設置為零掌实。我們不需要記錄是否將外部的提交提交到公共pool中-否則，外部helping方法會迅速返回邦马。否則贱鼻，這些提交者將被阻止等待完成，因此在不適用的情況下滋将，額外的工作量（使用大量的任務狀態(tài)檢查）在限制ForkJoinTask.join之前是有限的輪換等待的一種奇怪形式。
作為托管環(huán)境中更合適的默認值，除非存在系統(tǒng)屬性覆蓋顶吮，否則當存在SecurityManager時威彰，我們將使用子類InnocuousForkJoinWorkerThread的工作程序。這些工作程序沒有權(quán)限設置掘宪，不屬于任何用戶定義的ThreadGroup蛾扇，并且在執(zhí)行任何頂級任務后請擦除所有ThreadLocals（請參閱WorkQueue.runTask）。關(guān)聯(lián)的機制（主要在ForkJoinWorkerThread中）可能取決于JVM魏滚，并且必須訪問特定的Thread類字段才能實現(xiàn)此效果镀首。

3.2.6 Style notes

內(nèi)存排序主要依賴于Unsafe內(nèi)部函數(shù)，這些內(nèi)部函數(shù)承擔進一步的責任鼠次，即明確執(zhí)行空檢查和邊界檢查蘑斧，否則將由JVM隱式執(zhí)行。這樣寫代碼可能會非常丑陋须眷，但也反映了需要控制非呈活躍的代碼中很少有不變量的異常情況下的結(jié)果。因此花颗，這些顯式檢查無論如何都會以某種形式存在捕传。使用之前，所有字段都被讀入本地扩劝，如果它們是引用庸论，則進行空檢查职辅。通常以“ C”類樣式在方法或塊的開頭列出聲明，并在首次遇到時使用內(nèi)聯(lián)分配來完成聂示。數(shù)組邊界檢查通常是通過用array.length-1進行掩碼來執(zhí)行的域携，array.length-1依賴于不變的條件，即這些數(shù)組是用正長度創(chuàng)建的鱼喉，而該長度正好是自相矛盾地檢查的秀鞭。幾乎所有顯式檢查都會導致繞過/返回，而不是引發(fā)異常扛禽，因為它們可能由于關(guān)機期間的取消/吊銷而合法地出現(xiàn)锋边。
在類ForkJoinPool，F(xiàn)orkJoinWorkerThread和ForkJoinTask之間编曼，有很多表示層級的耦合豆巨。WorkQueue的字段維護由ForkJoinPool管理的數(shù)據(jù)結(jié)構(gòu)，因此可以直接訪問掐场。減少這種情況幾乎沒有意義往扔，因為無論如何表示形式的任何相關(guān)的將來更改都將需要伴隨算法更改。幾種方法本質(zhì)上無處不在熊户，因為它們必須累積對局部變量中保存的字段的一致讀取集萍膛。還有其他編碼異常（包括一些看上去不必要的懸掛式空檢查），即使在解釋（未編譯）時也可以幫助某些方法合理地執(zhí)行敏弃。
該文件中的聲明順序為（除少數(shù)例外）：

• （1）靜態(tài)實用程序函數(shù)
• （2）嵌套（靜態(tài)）類
• （3）靜態(tài)字段
• （4）字段以及在解壓縮某些字段時使用的常量
• （5）內(nèi)部控制方法
• （6）對ForkJoinTask方法的回調(diào)和其他支持
• （7）導出的方法
• （8）以最小相關(guān)順序進行初始化的靜態(tài)代碼塊

4.總結(jié)

本文介紹了ForkJoin的基本使用卦羡，及其基本的工作原理，雖然ForkJoin實際的代碼非常復雜麦到，但是通過本文我們應該了解到ForkJoinPool底層的分治算法和工作竊取原理绿饵。此外本文也介紹了ForkJoinPool的一些實現(xiàn)原理，這將在后續(xù)源碼介紹中瓶颠，逐步詳細說明拟赊。ForkJoin不僅在java8之后的stream中廣泛使用。golang等其他語言的協(xié)程機制粹淋，也是采用類似的原理來實現(xiàn)的吸祟。我們需要重點掌握Fork-Join的本質(zhì)。