手?jǐn)]一款簡單高效的線程池（二）
在上一章中，我們給大家簡單介紹了傳統(tǒng) C++的線程池實(shí)現(xiàn)方案中存在的一些問題，并且立下 flag 要做一款簡單好用、高性能的線程池。接下來，我們就用幾章的內(nèi)容，把曾經(jīng)吹過的牛 B，編程實(shí)現(xiàn)。
大家好，我是不會寫代碼的純序員——Chunel Feng[1]。這篇文章是線程池優(yōu)化系列連載的第二篇。主要跟大家介紹幾種線程池優(yōu)化思路，包括：local-thread 機(jī)制、lock-free 機(jī)制、work-stealing 機(jī)制。
還是要提前說明一下，多線程并發(fā)的知識博大精深，且涉及內(nèi)容極其廣泛。以下介紹的內(nèi)容也僅局限在我個人的認(rèn)知范圍。如果大家有什么意見和建議，請多多指教。
首先，還是照例，先上源碼鏈接：CGraph 源碼鏈接[2] 其中，線程池的實(shí)現(xiàn)在 /src/UtilsCtrl/ThreadPool/ 文件夾中。
local-thread 機(jī)制
上一章，我們分析傳統(tǒng)的線程池的一個瓶頸，在于多個 thread 去【爭搶】pool 中任務(wù)隊(duì)列中的第一個 task，這里是有鎖操作，會有一定的性能開銷。而引入 local-thread 技術(shù)就是為了在一定程度上減少這種開銷。
C++11 版本開始，已經(jīng)引入了thread_local關(guān)鍵字，但是很少見有人用。具體到做工程的童鞋，其實(shí)更喜歡的方式，應(yīng)該是自己封裝一個屬于自己的 thread 類，那這里的東東不就都是local了么。
為此，CGraph 中封裝了 UThreadPrimary 類，其中就包含了一個 UWorkStealingQueue 類的對象。這是一個類似 std::deque 結(jié)構(gòu)的雙向隊(duì)列，可以從頭部彈出節(jié)點(diǎn)，也可以從尾部彈出節(jié)點(diǎn)。
把原先 pool 中 queue 中的任務(wù)，放到不同的 n 個線程的私有的 n 個 queue（UWorkStealingQueue 類型）中，線程執(zhí)行任務(wù)的時候就不需要再從 pool 的 queue 中獲取去【爭搶】了。從而是不是就達(dá)到了“增加扇出”的效果。
再往前想一步，最初的線程池模型中，外部寫入的時候也是寫入 pool 中的 queue，會存在一個【爭搶】寫入，也會在 queue 被讀的時候，無法搶到鎖。那寫入 thread 中的 queue 的話，是不是也一定程度上提升了“增加扇入”的效果。畢竟，跟你競爭的只有本線程的讀操作了啊。
local-thread 還有一點(diǎn)內(nèi)容，就是本線程執(zhí)行過程中，產(chǎn)生的 task（盡可能的）放在本線程的 queue 中執(zhí)行。這樣也是local的一種體現(xiàn)，而且也會在一定程度上增加線程的親和性——這個跟線程內(nèi)部資源的緩存有關(guān)。
lock-free 機(jī)制
lock-free 是無鎖編程的技術(shù)，也叫做 lockless 技術(shù)。lock-free 也分好幾種維度，比如：基于 atomic 的、基于內(nèi)部封裝 mutex 的、基于 cas 機(jī)制的。當(dāng)然可能還有一些我不知道的，歡迎補(bǔ)充。
無鎖，乍一聽像是并發(fā)編程的時候不用上鎖了。但在你不加鎖的時候，別人在暗中默默的幫你加了鎖。舉個例子，C++11 中的std::atomic<int>類型，就是一種無鎖類型。但其實(shí)在這種類型的變量，做多線程并發(fā)的i++的時候，在變量內(nèi)部維護(hù)了一個 spin-lock（自旋鎖，確保當(dāng)前線程不被切換）和一個 cas（樂觀鎖，確保最終數(shù)值正確）。說是無鎖，實(shí)際上看進(jìn)去之后會發(fā)現(xiàn)，還不止有一個鎖——只是外部程序不感知罷了。
CGraph 中的 UAtomicQueue 類，采用的也是類似的技術(shù)。不過并不是 cas，而是內(nèi)部加入 std::mutex 和 std::condition_variable 來進(jìn)行控制。還有，剛才聊到的 UWorkStealingQueue 類，也屬于無鎖類型——僅是外部看上去無鎖罷了。在內(nèi)部封裝的過程中，我們也在一些特定的情況下使用了 yield()方法讓出線程的執(zhí)行權(quán)限，實(shí)測效果是有明顯提升的。
這里后期可以考慮嘗試使用 cas 的方式實(shí)現(xiàn)一下，理論上 cas 是比直接內(nèi)部上鎖快一些的。
work-stealing 機(jī)制
任務(wù)偷竊機(jī)制——這種技術(shù)常被用于線程之間相互 backup 的場景中，Java 版本的線程池中也有這項(xiàng)技術(shù)。
通俗解釋一下，比如當(dāng)前線程池里有 3 個線程，分別為 thd1，thd2 和 thd3 吧。每個線程中的 local queue 中都包含了 100 個任務(wù)——已經(jīng)很負(fù)載均衡了吧。我們設(shè)想極端一些哈，比如 thd3 的 task 都是sleep 1s，而 thd1 和 thd2 中的 task 都是sleep 1ms。如果每個 thd 僅執(zhí)行自己 local queue 中的內(nèi)容，那這個任務(wù)總體的耗時應(yīng)該是max(100ms, 100ms, 100s) = 100s。
但是在所有任務(wù)開始執(zhí)行的 100ms 后，thd1 和 thd2 就已經(jīng)無工可做了（像極了 35 歲后的純序員本員），但是 thd3 還是在苦苦支撐著，一直到 100s 結(jié)束。這顯然是不太合理的。
一種比較合理的做法是，在 thd1 和 thd2 在執(zhí)行 local 任務(wù)結(jié)束之后，可以去 thd3 的隊(duì)列中去 stealing 一些任務(wù)（就是sleep 1s的那種）執(zhí)行——這就是所謂的 work-stealing 機(jī)制。這種機(jī)制的優(yōu)勢也是很明顯的，針對剛才描述的情況，原先 100s 才能執(zhí)行完的任務(wù)，整體耗時瞬間就被降低到 30+s 左右。
需要說明的是，work-stealing 機(jī)制并不是一個萬金油。比如，上面提到的頭部/尾部彈出，明顯會打亂任務(wù)執(zhí)行順序，所以這種機(jī)制更適合那種“可執(zhí)行任務(wù)一把梭哈”的情況——對，我指的就是CGraph這種圖執(zhí)行框架。因?yàn)樾枰环湃刖€程池中的任務(wù)，都是可以無序并發(fā)執(zhí)行的，有依賴的任務(wù)也不會被放入 pool 中啊。
還有一個問題哈，當(dāng) thread 本地沒有 task 的時候，從哪個 thread 去 stealing 呢？一般的做法，是在初始化的 pool 時候給每個線程設(shè)定編號：比如 0~7，用 index 表示。thread5 進(jìn)行 stealing 的時候，一般是從 thread6 的 queue 中開始，然后 thread7、thread0... 依次遞推到 thread4。這樣做的好處，是避免了大家都從某一個 thread 開始 stealing 而導(dǎo)致的不均衡。每個線程在 local 執(zhí)行任務(wù)的時候，從 UWorkStealingQueue 的頭部彈出 task，在偷/被偷的時候從 UWorkStealingQueue 尾部彈出 task。
有些時候，work-stealing 機(jī)制甚至可能成為“累贅”。舉個例子，pool 中一共有 100 個線程吧，那當(dāng) thread0 中 queue 無任務(wù)的時候，thread0 會去遍歷其他的 99 個 thread——就為了盜取一個任務(wù)。這個遍歷有阻塞耗時不說，也會影響到 thread0 去執(zhí)行新來的 local task——像極了天天幫同事排查 bug，但是自己一大堆 bug 卻來不及修復(fù)的純序員本員。
我們之前提過 local 的內(nèi)容親和性是最高的，理應(yīng)優(yōu)先執(zhí)行，對吧。針對這種情況，一種可行的解決辦法是設(shè)定“盜取范圍”（對應(yīng) CGraph 中的CGRAPH_MAX_TASK_STEAL_RANGE參數(shù)）。比如，thread0 僅可以從相鄰的 3 個線程（也就是 thread1、thread2 和 thread3）中盜取任務(wù)，如果在這 3 個 thread 中都盜取不到，那就重新嘗試看 local 的 queue。其他線程亦是如此。也就是說，大家僅關(guān)系自己本地的 task 和自己若干個鄰居的 task，離得遠(yuǎn)的就不用問了。這種“事不關(guān)己高高掛起”（低情商說法）行為，在很多情況下卻是好事，因?yàn)樗€有一種高情商說法，就是“專注于自己的工作”，嘿嘿。
隨便放幾句相關(guān)的代碼哈，更多代碼大家去 github 上面看哈。
/*** 從其他線程竊取一個任務(wù)* @param task* @return*/bool stealTask(UTaskWrapperRef task) {if (unlikely(pool_threads_->size() < CGRAPH_DEFAULT_THREAD_SIZE)) {/*** 線程池還未初始化完畢的時候，無法進(jìn)行steal。* 確保程序安全運(yùn)行。*/return false;}/*** 竊取的時候，僅從相鄰的primary線程中竊取* 待竊取相鄰的數(shù)量，不能超過默認(rèn)primary線程數(shù)*/int range = CGRAPH_MAX_TASK_STEAL_RANGE % CGRAPH_DEFAULT_THREAD_SIZE;for (int i = 0; i < range; i++) {/*** 從線程中周圍的thread中，竊取任務(wù)。* 如果成功，則返回true，并且執(zhí)行任務(wù)。*/int curIndex = (index_ + i + 1) % CGRAPH_DEFAULT_THREAD_SIZE;if (nullptr != (*pool_threads_)[curIndex]&& (((*pool_threads_)[curIndex]))->work_stealing_queue_.trySteal(task)) {return true;}}return false;}
我實(shí)測的一個結(jié)果，在開 16 個 thread 運(yùn)行 48 路大批量空跑 task（就是所有的 task 都是return 0，這樣可以一定程度體現(xiàn)出來 pool 的調(diào)度能力）情況下，如果不設(shè)定 steal 范圍，大概是 194s 的樣子，已經(jīng)退化到跟普通線程池基本持平的水平了。而把 steal 范圍設(shè)置為 4 之后，直接降低到了 163s 左右。不要問我怎么發(fā)現(xiàn)這個問題，火焰圖會教你做人的。
本章小結(jié)
本章主要是介紹了一些線程池在設(shè)計過程中，有哪些優(yōu)化點(diǎn)。總結(jié)一下就是下圖中畫紅框的地方，主要的目的就是可以增加扇入扇出。今天分享的這幾點(diǎn)偏硬核，都是我在自測過程中，的的確確可以增加調(diào)度性能的方案。我們也會在接下來的文章中，繼續(xù)介紹 CGraph 中線程池的相關(guān)優(yōu)化內(nèi)容和思路。
如果你對這方面的內(nèi)容也感興趣，請加我微信以便隨時聯(lián)系。有什么實(shí)用的功能，我們可以嘗試去一起實(shí)現(xiàn)。有什么好的指教和意見，也歡迎隨時提出來，以便我們改進(jìn)和提高。
接下來一章，我們將會跟大家介紹一下其他的一些線程池優(yōu)化機(jī)制，比如主輔線程、自動擴(kuò)縮容等。歡迎大家繼續(xù)關(guān)注。
推薦閱讀
?純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——執(zhí)行邏輯[3]?純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——循環(huán)邏輯[4]?純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——參數(shù)傳遞[5]?純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——條件判斷[6]?純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——線程池優(yōu)化（一）[7]
引用鏈接
[1] Chunel Feng: http://www.chunel.cn[2] CGraph 源碼鏈接: https://github.com/ChunelFeng/CGraph[3] 純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——執(zhí)行邏輯: http://www.chunel.cn/archives/cgraph-run-introduce[4] 純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——循環(huán)邏輯: http://www.chunel.cn/archives/cgraph-loop-introduce[5] 純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——參數(shù)傳遞: http://www.chunel.cn/archives/cgraph-param-introduce[6] 純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——條件判斷: http://www.chunel.cn/archives/cgraph-condition-introduce[7] 純序員給你介紹圖化框架的簡單實(shí)現(xiàn)——線程池優(yōu)化（一）: http://www.chunel.cn/archives/cgraph-threadpool-1-introduce