Go 調(diào)度程序的任務(wù)是在多個運行在一個或多個處理器上的系統(tǒng)線程上分發(fā)出可運行的 goroutine昨寞。在多線程計算中，調(diào)度已經(jīng)出現(xiàn)了兩種模式：工作共享與工作竊取腋腮。
- 工作共享：當一個處理器創(chuàng)建新的線程時，它試圖將一部分線程遷移到其他的處理器上執(zhí)行，期望更充分的利用那些 IDLE 狀態(tài)的處理器煮剧。
- 工作竊瑞惺辍：未被充分利用的處理器會主動尋找其他處理器上的線程，并“竊取”一些線程猾瘸。
與工作共享模式相比界赔，工作竊取模式線程的遷移發(fā)生的頻率更低。當所有的處理器都有工作要運行時牵触，沒有任何線程被遷移淮悼。一旦有了空閑處理器，就會考慮遷移揽思。
Go 從 1.1 版本開始就有了一個工作竊取模式的調(diào)度程序袜腥，它是由 Dmitry Vyukov 貢獻的。這篇文章將深入地解釋什么是工作竊取的調(diào)度程序钉汗，以及如何實現(xiàn)一個羹令。
調(diào)度的基礎(chǔ)
Go有一個 M:N 的調(diào)度程序鲤屡，它可以使用多核處理器。在任何時候福侈，M 個 goroutine 都需要被分發(fā)在最多 GOMAXPROCS 個處理器上運行的 N 個系統(tǒng)線程上酒来。Go調(diào)度程序使用以下術(shù)語來描述 goroutines、線程和處理器:
- G：goroutine
- M：系統(tǒng)線程(Machine)
- P：處理器
有一個特定于處理器的本地 goroutine 隊列和一個全局的 goroutine 隊列肪凛。每個系統(tǒng)線程都應(yīng)該被分配給一個處理器堰汉，如果處理器被阻塞或被系統(tǒng)調(diào)用，那么可能處理器上會沒有線程伟墙。在任何時候翘鸭，最多有
GOMAXPROCS 個處理器被用于分配。任何時候远荠，一個線程都只能運行在一個處理器上矮固。如果有需要調(diào)度器也可以創(chuàng)建更多的線程。
- image.png
每一輪的調(diào)度都只是找到一個可運行的 goroutine 并執(zhí)行它譬淳。在每一輪的調(diào)度中档址，搜索都按照以下順序進行:
runtime.schedule() {
// only 1/61 of the time, check the global runnable queue for a G.
// if not found, check the local queue.
// if not found,
// try to steal from other Ps.
// if not, check the global runnable queue.
// if not found, poll network.
}
一旦找到一個可運行的 goroutine ，它就會被執(zhí)行邻梆，直到被阻塞守伸。
注意：看起來全局隊列比局部隊列優(yōu)先級更高，但是偶爾檢查全局隊列只是為了避免系統(tǒng)線程在局部隊列中的 goroutine 用盡前只調(diào)用局部 goroutine 隊列中的 goroutine浦妄。
竊取
當一個 goroutine 被創(chuàng)建或一個已經(jīng)存在的 goroutine 變?yōu)榭梢赃\行狀態(tài)尼摹，它被推送到當前處理器上的一個可運行的 goroutines 隊列中，當處理器執(zhí)行完一個 goroutine剂娄，它將試圖從自己的局部可運行 goroutine 隊列中彈出這個 goroutine蠢涝。如果隊列為空，處理器會隨機選擇一個其他處理器阅懦，并試圖從這個處理器的局部可運行 goroutine 隊列中偷取一半數(shù)量的可運行 goroutine和二。
- image.png
在上面的例子中，P2 這個處理器無法找到任何可執(zhí)行的 goroutines耳胎。因此惯吕，它隨機選擇另一個處理器 P1，并將 3 個 goroutines 偷到自己的局部隊列中怕午。P2 將執(zhí)行這些 goroutines废登，而調(diào)度器也將在多個處理器之間更均衡的調(diào)度。
旋轉(zhuǎn)線程
調(diào)度程序總是希望將可運行的 goroutines 分發(fā)到線程中郁惜，以便充分利用處理器堡距，但同時我們又需要限制過多的任務(wù)來節(jié)省 CPU 資源。與此相矛盾的是，調(diào)度器還需要能夠擴展到高吞吐量和CPU密集的程序中吏颖。
如果性能很關(guān)鍵搔体，那么經(jīng)常性的搶占將顯得十分的昂貴，并且對高吞吐量的程序來說這也是個嚴重的問題半醉。操作系統(tǒng)線程之間不應(yīng)該頻繁的傳遞可運行的 goroutine疚俱，因為這將導(dǎo)致延遲的增加。另外缩多，在有系統(tǒng)調(diào)用的情況下呆奕，系統(tǒng)線程需要不斷的 block 與 unblock，這也是非常昂貴的同時也增加了很多額外的開銷衬吆。
為了減少線程間傳遞梁钾，調(diào)度器實現(xiàn)了“旋轉(zhuǎn)線程”。旋轉(zhuǎn)線程雖然消耗了額外的 CPU 資源逊抡，但是它們最小化了操作系統(tǒng)線程的搶占姆泻。一個線程正在旋轉(zhuǎn)，如果:
- 一個擁有線程的處理器正在尋找一個可執(zhí)行的 goroutine冒嫡。
- 一個沒有所屬處理器的線程正在尋找一個可以依附的處理器
- 當它準備一個 goroutine 時拇勃，如果有一個空閑的處理器并且沒有其他的旋轉(zhuǎn)線程，調(diào)度程序會取消一個額外的線程孝凌，然后旋轉(zhuǎn)這個線程方咆。
在任何時候，都有最多 GOMAXPROCS 個線程在旋轉(zhuǎn)蟀架。當一個旋轉(zhuǎn)的線程找到工作后瓣赂，它就會脫離自旋狀態(tài)。
如果空閑的線程沒有處理器可分配片拍，則已分配到處理器上的空閑線程不會阻塞煌集。當新的 goroutine 被創(chuàng)建或者一個線程被阻塞時，調(diào)度程序?qū)⒋_保至少有一個旋轉(zhuǎn)的線程捌省，這確保了當沒有可運行的 goroutine 時程序仍可以運行牙勘，也避免過多的線程 block/unblock。
Go調(diào)度程序做了很多工作所禀，以避免對操作系統(tǒng)線程的過度搶占，通過將它們調(diào)度到正確的和未充分利用的處理器上放钦，并實現(xiàn)了“旋轉(zhuǎn)”線程色徘，以避免出現(xiàn)阻塞/未阻塞的轉(zhuǎn)換。
調(diào)度事件可以通過執(zhí)行跟蹤程序跟蹤操禀。如果你認為你的處理器利用率很低褂策，那么你可以排查一下正在發(fā)生什么。
