1. 前言
Go 語言最大的魅力就是只需要 go 關鍵字即可快速創建一個 goroutine ，無需關注操作系統的調度細節，即可利用上多核輕松開發出高并發的服務器應用。理解了 Golang 調度器的機制，能讓我們寫出高性能的并發程序，也可以提升我們的問題定位、性能優化的能力。
2. 進程、線程、協程
任何并發程序，無論在應用層是何形式，最終都要被操作系統所管理。由此涉及到以下幾個概念：
-
進程 (Process)：操作系統分配資源的基本單位 -
線程 (Thread)：CPU 調度的基本單位，一個核上同時只能運行一個線程，單線程的棧內存大小約 1MB -
協程 (Coroutine)：輕量級、用戶態線程。在 Go 語言中，有 goroutine的概念。當一個goroutine被創建出來時，分配的棧大小是 2KB，可見其「輕量」
3. 早期的調度模型：GM 模型
系統的設計往往都不是一蹴而就的，伴隨著演進和優化，Golang scheduler 也不例外。1.1 版本前的 go，使用的是相對簡單的 GM 模型來處理 goroutine 的調度，GM 實際是兩個結構體，即：
-
G(Goroutine): 協程結構體，使用 go func()時，就會創建一個G -
M(machine): 處理線程操作的結構體，與操作系統直接交互
GM 模型包含一個全局協程隊列，即所有新建的 G 對象都會排隊等待 M 的處理。如圖：
這樣的設計在高并發下會帶來以下問題：
What’s wrong with current implementation:
Single global mutex (Sched.Lock) and centralized state. The mutex protects all goroutine-related operations (creation, completion, rescheduling, etc). Goroutine (G) hand-off (G.nextg). Worker threads (M’s) frequently hand-off runnable goroutines between each other, this may lead to increased latencies and additional overheads. Every M must be able to execute any runnable G, in particular the M that just created the G. Per-M memory cache (M.mcache). Memory cache and other caches (stack alloc) are associated with all M’s, while they need to be associated only with M’s running Go code (an M blocked inside of syscall does not need mcache). A ratio between M’s running Go code and all M’s can be as high as 1:100. This leads to excessive resource consumption (each MCache can suck up up to 2M) and poor data locality. Aggressive thread blocking/unblocking. In presence of syscalls worker threads are frequently blocked and unblocked. This adds a lot of overhead.
（原文見 Scalable Go Scheduler Design Doc）
翻譯總結一下，即存在以下優化點：
-
全局鎖、中心化狀態帶來的鎖競爭導致的性能下降 -
M 會頻繁交接 G，導致額外開銷、性能下降。每個 M 都得能執行任意的 runnable 狀態的 G -
對每個 M 的不合理的內存緩存分配，進行系統調用被阻塞住的 M 其實不需要分配內存緩存 -
強線程阻塞/解阻塞。頻繁的系統調用導致的線程阻塞/解阻塞帶來了大量的系統開銷。
由此演進出經典的 GMP 調度模型
4. 高效的 GMP 調度模型
為了解決 G 和 M 調度低效的問題，中間層 P(Processor) 被引入了。
-
P(Processor)即管理goroutine資源的處理器
由此得以將原先的系統線程資源管理 M 與 goroutine 對象 G 解耦。
除此之外，GMP 還引入了幾個新概念：
-
LRQ (Local Runnable Queue)本地可運行隊列，這個「本地」，是針對 P 而言的，是指掛載在一個 P 上的可運行 G 隊列 -
GRQ (Global Runnable Queue)全局可運行隊列
如下圖所示：
LRQ 與 GRQ
從 runtime 源碼可知，整體的調度流程如下：
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.
}
翻譯一下，即
-
只有 1/61 的情況下，會檢查 GRQ 來獲取一個 G 來運行 -
如果沒找到，則檢查 LRQ -
如果 LRQ 也為空，則嘗試從其它 P 上偷 G -
如果偷不到，就再檢查 GRQ -
如果還是沒事干，就會從 Network Poller上拿一個。這里的Network Poller是 go 管理網絡調用的模塊，如下圖，當出現網絡 IO 時，就會將當前的 G 移交到Network Poller處理。P.S.Network Poller的實現，又可以扯一篇文章出來了，以后有空專門開一篇分析。
于是 G1 被挪到 Net Poller 進行異步網絡調用，現在 M 就可以執行 G2 了
Work-stealing 機制
GMP高性能的關鍵，在于引入了 work-stealing 機制，如下圖所示：
work-stealing 機制
當一個新的 G 被創建時，它會被追加到它當前 P 的 LRQ 隊尾。當一個 G 被執行完時，它當前的 P 會先嘗試從自己的 LRQ 中 pop 一個 G 出來執行，如果此時隊列為空，則會隨機選取一個 P 并偷走它一半的 G ，對應圖中，也就是 3 個 G
這就好比公司里的卷王，自己的需求做完了，還要悄悄把摸魚大王的需求清單里一半的需求都掛到自己名下，囧
最后一個疑問：GRQ 什么時候被寫入呢？
這又涉及到 G 創建時的分配流程了，我們知道，goroutine 都是由老的 goroutine 分配出來的，mAIn 函數也不例外，因此每個 G 被分配的時候已經有一個老 G 和對應的老 P 了，在掛載 G 到 P 上時，也會優先掛在到老 P 的 LRQ 上去。但是老 P 的 LRQ 其實是有限的，當掛滿的時候，這個新 G 就只能掛到 GRQ 上，等待被調度了。可以參考源碼中 P 的定義，其中 runq 就是 GRQ 了：
type p struct {
...
// Queue of runnable goroutines. Accessed without lock.
runqhead uint32
runqtail uint32
runq [256]guintptr
...
}
5. 小結
本文講解了 go 語言調度器的發展及基于 GMP 的 work-stealing 策略，這個「偷」可以說是非常精妙啦～ 這是 「Golang 并發編程」 系列的第一篇文章，如果對你有幫助，可以點個關注/在看來激勵我繼續寫文章～
