一、介紹
運用java8lambda表達式大半年了，一直都知道底層運用的是Fork/Join結(jié)構(gòu)，今日總算有機會來學(xué)學(xué)Fork/Join結(jié)構(gòu)了。
Fork/Join結(jié)構(gòu)是Java7提供的一個用于并行履行使命的結(jié)構(gòu)，是一個把大使命切割成若干個小使命，終究匯總每個小使命成果后得到大使命成果的結(jié)構(gòu)。
Fork/Join的運行流程示意圖：
比方，一個1+2+3+…+100的作業(yè)使命，咱們能夠把它Fork成10個子使命，別離核算這10個子使命的運行成果。最終再把10個子使命的成果Join起來，匯總成最終的成果。
為了減少線程間的競賽，一般把這些子使命別離放到不同的行列里，并為每個行列創(chuàng)立一個獨自的線程來履行行列里的使命，線程和行列一一對應(yīng)?？墒牵械木€程會先把自己行列里的使命干完，而其他線程對應(yīng)的行列里還有使命等候處理。干完活的線程與其等著，不如去幫其它線程干活，所以它就去其他線程的行列里盜取一個使命來履行。而在這時它們會訪問同一個行列，所以為了減少盜取使命線程和被盜取使命線程之間的競賽，一般會運用雙端行列，被盜取使命線程永遠從雙端行列的頭部拿使命履行，而盜取使命的線程永遠從雙端行列的尾部拿使命履行。線程的這種履行辦法，咱們稱之為“作業(yè)盜取”算法。
二、規(guī)劃
完成Fork/Join結(jié)構(gòu)的規(guī)劃，大略需求兩步：
1.切割使命
首要咱們需求創(chuàng)立一個ForkJoin使命，把大使命切割成子使命，假如子使命不行小，則持續(xù)往下分，直到切割出的子使命滿足小。
在Java中咱們能夠運用ForkJoinTask類，它提供在使命中履行fork()和join()操作的機制，一般情況下，咱們只需求承繼它的子類：
RecursiveAction—用于沒有回來成果的使命
RecursiveTask—用于有回來成果的使命
2.使命履行并回來成果
切割的子使命別離放在雙端行列里，然后啟動幾個線程別離從雙端行列里獲取使命履行。子使命履行完的成果都統(tǒng)一放在一個行列里，啟動一個線程從行列里拿數(shù)據(jù)，然后兼并這些數(shù)據(jù)。
在Java中使命的履行需求經(jīng)過ForkJoinPool來履行。
回到頂部
三、示例
來一個阿里面試題：百萬級Integer數(shù)據(jù)量的一個array求和。
publicclassArrayCountTaskextendsRecursiveTask<Long>{/**
*閾值
*/privatestaticfinalIntegerTHRESHOLD=10000;privateInteger[]array;privateIntegerstart;privateIntegerend;publicArrayCountTask(Integer[]array,Integerstart,Integerend){this.array=array;this.start=start;this.end=end;
}@OverrideprotectedLongcompute(){longsum=0;//最小子使命核算if(end-start<=THRESHOLD){for(inti=start;i<end;i++){
sum+=array[i];
}
}else{//把大于閾值的使命持續(xù)往下拆分，有點相似遞歸的思維。recursive便是遞歸的意思。intmiddle=(start+end)>>>1;
ArrayCountTaskleftArrayCountTask=newArrayCountTask(array,start,middle);
ArrayCountTaskrightArrayCountTask=newArrayCountTask(array,middle,end);//履行子使命//leftArrayCountTask.fork();//rightArrayCountTask.fork();//invokeAll辦法運用invokeAll(leftArrayCountTask,rightArrayCountTask);//等候子使命履行完，并得到其成果LongleftJoin=leftArrayCountTask.join();
LongrightJoin=rightArrayCountTask.join();//兼并子使命的成果sum=leftJoin+rightJoin;
}returnsum;
}
}
publicstaticvoidmain(String[]args){//1.造一個int類型的百萬等級數(shù)組Integer[]array=newInteger[150000000];for(inti=0;i<array.length;i++){
array[i]=newRandom().nextInt(100);
}//2.普通辦法核算成果longstart=System.currentTimeMillis();longsum=0;for(inti=0;i<array.length;i++){
sum+=array[i];
}longend=System.currentTimeMillis();
System.out.println(“普通辦法核算成果：”+sum+”，耗時：”+(end-start));longstart2=System.currentTimeMillis();//3.fork/join結(jié)構(gòu)辦法核算成果ArrayCountTaskarrayCountTask=newArrayCountTask(array,0,array.length);
ForkJoinPoolforkJoinPool=newForkJoinPool();
sum=forkJoinPool.invoke(arrayCountTask);longend2=System.currentTimeMillis();
System.out.println(“fork/join結(jié)構(gòu)辦法核算成果：”+sum+”，耗時：”+(end2-start2));//結(jié)論：//1.電腦i5-4300m，雙核四線程//2.數(shù)組量少的時分，fork/join結(jié)構(gòu)要進行線程創(chuàng)立/切換的操作，功能不明顯。//3.數(shù)組量超過100000000，fork/join結(jié)構(gòu)的功能才開始體現(xiàn)。}
ForkJoinTask與一般使命的主要差異在于它需求完成compute辦法，在這個辦法里，首要需求判斷使命是否滿足小，假如滿足小就直接履行使命。假如不滿足小，就必須切割成兩個子使命，每個子使命在調(diào)用fork辦法時，又會進入compute辦法，看看當時子使命是否需求持續(xù)切割成子使命，假如不需求持續(xù)切割，則履行當時子使命并回來成果。運用join辦法會等候子使命履行完并得到其成果。
在履行子使命時調(diào)用fork辦法并不是最佳的選擇，最佳的選擇是invokeAll辦法。由于履行compute()辦法的線程本身也是一個worker線程，當對兩個子使命調(diào)用fork()時，這個worker線程就會把使命分配給另外兩個worker，可是它自己卻停下來等候不干活了！這樣就白白浪費了Fork/Join線程池中的一個worker線程，導(dǎo)致了4個子使命至少需求7個線程才干并發(fā)履行。
比方甲把400分成兩個200后，fork()寫法相當于甲把一個200分給乙，把另一個200分給丙，然后，甲成了監(jiān)工，不干活，等乙和丙干完了他直接匯報作業(yè)。乙和丙在把200分拆成兩個100的過程中，他倆又成了監(jiān)工，這樣，本來只需求4個工人的活，現(xiàn)在需求7個工人才干完成，其中有3個是不干活的。
ForkJoinPool由ForkJoinTask數(shù)組和ForkJoinWorkerThread數(shù)組組成，F(xiàn)orkJoinTask數(shù)組擔任將寄存程序提交給ForkJoinPool的使命，而ForkJoinWorkerThread數(shù)組擔任履行這些使命，F(xiàn)orkJoinWorkerThread體現(xiàn)的便是“作業(yè)盜取”算法。
當咱們調(diào)用ForkJoinTask的fork辦法時，程序會調(diào)用ForkJoinWorkerThread的pushTask辦法異步地履行這個使命，然后立即回來成果。
當咱們調(diào)用ForkJoinTask的join辦法時，程序會堵塞當時線程并等候獲取成果。
ForkJoinPool運用submit或invoke提交的差異：invoke同步履行，調(diào)用之后需求等候使命完成，才干履行后邊的代碼；submit是異步履行，只要在Future調(diào)用get的時分會堵塞。
ForkJoinPool承繼自AbstractExecutorService，不是為了替代ExecutorService，而是它的補充，在某些使用場景下功能比ExecutorService更好。