分治算法(Divide-and-Conquer)

　　分治算法(Divide-and-Conquer)把任務(wù)遞歸的拆分為各個(gè)子任務(wù)，這樣可以更好的利用系統(tǒng)資源，盡可能的使用所有可用的計(jì)算能力來(lái)提升應(yīng)用性能。

　　首先看一下 Fork/Join 框架的任務(wù)運(yùn)行機(jī)制：

　　work-stealing(工作竊取)算法

　　work-stealing(工作竊取)算法: 線程池內(nèi)的所有工作線程都嘗試找到并執(zhí)行已經(jīng)提交的任務(wù)，或者是被其他活動(dòng)任務(wù)創(chuàng)建的子任務(wù)(如果不存在就阻塞等待)。這種特性使得 ForkJoinPool 在運(yùn)行多個(gè)可以產(chǎn)生子任務(wù)的任務(wù)，或者是提交的許多小任務(wù)時(shí)效率更高。尤其是構(gòu)建異步模型的 ForkJoinPool 時(shí)，對(duì)不需要合并(join)的事件類型任務(wù)也非常適用。

　　在 ForkJoinPool 中，線程池中每個(gè)工作線程(ForkJoinWorkerThread)都對(duì)應(yīng)一個(gè)任務(wù)隊(duì)列(WorkQueue)，工作線程優(yōu)先處理來(lái)自自身隊(duì)列的任務(wù)(LIFO或FIFO順序，參數(shù) mode 決定)，然后以FIFO的順序隨機(jī)竊取其他隊(duì)列中的任務(wù)。

　　具體思路如下：

　　每個(gè)線程都有自己的一個(gè)WorkQueue，該工作隊(duì)列是一個(gè)雙端隊(duì)列。 隊(duì)列支持三個(gè)功能push、pop、pollpush/pop只能被隊(duì)列的所有者線程調(diào)用，而poll可以被其他線程調(diào)用。 劃分的子任務(wù)調(diào)用fork時(shí)，都會(huì)被push到自己的隊(duì)列中。默認(rèn)情況下，工作線程從自己的雙端隊(duì)列獲出任務(wù)并執(zhí)行。當(dāng)自己的隊(duì)列為空時(shí)，線程隨機(jī)從另一個(gè)線程的隊(duì)列末尾調(diào)用poll方法竊取任務(wù)。