分治算法(Divide-and-Conquer)
分治算法(Divide-and-Conquer)把任務遞歸的拆分為各個子任務，這樣可以更好的利用系統(tǒng)資源，盡可能的使用所有可用的計算能力來提升應用性能。
首先看一下 Fork/Join 框架的任務運行機制：
work-stealing(工作竊取)算法
work-stealing(工作竊取)算法: 線程池內(nèi)的所有工作線程都嘗試找到并執(zhí)行已經(jīng)提交的任務，或者是被其他活動任務創(chuàng)建的子任務(如果不存在就阻塞等待)。這種特性使得 ForkJoinPool 在運行多個可以產(chǎn)生子任務的任務，或者是提交的許多小任務時效率更高。尤其是構(gòu)建異步模型的 ForkJoinPool 時，對不需要合并(join)的事件類型任務也非常適用。
在 ForkJoinPool 中，線程池中每個工作線程(ForkJoinWorkerThread)都對應一個任務隊列(WorkQueue)，工作線程優(yōu)先處理來自自身隊列的任務(LIFO或FIFO順序，參數(shù) mode 決定)，然后以FIFO的順序隨機竊取其他隊列中的任務。
具體思路如下：
每個線程都有自己的一個WorkQueue，該工作隊列是一個雙端隊列。 隊列支持三個功能push、pop、pollpush/pop只能被隊列的所有者線程調(diào)用，而poll可以被其他線程調(diào)用。 劃分的子任務調(diào)用fork時，都會被push到自己的隊列中。默認情況下，工作線程從自己的雙端隊列獲出任務并執(zhí)行。當自己的隊列為空時，線程隨機從另一個線程的隊列末尾調(diào)用poll方法竊取任務。
京公網(wǎng)安備 11010802030320號