goroutine 調度器原理

【導讀】goroutine 調度是怎麼實現的？本文細緻明白地解釋了 goroutine 的迭代和設計，一起來學習吧！

goroutine 調度器的概念

說到 “調度”，首先會想到操作系統對進程、線程的調度。操作系統調度器會將系統中的多個線程按照一定算法調度到物理 CPU 上去運行。傳統的編程語言比如 C、C++ 等的併發實現實際上就是基於操作系統調度的，即程序負責創建線程，操作系統負責調度。

儘管線程的調度方式相對於進程來說，線程運行所需要資源比較少，在同一進程中進行線程切換效率會高很多，但實際上多線程開發設計會變得更加複雜，要考慮很多同步競爭等問題，如鎖、競爭衝突等。

線程是操作系統調度時的最基本單元，而 Linux 在調度器並不區分進程和線程的調度，只是說線程調度因爲資源少，所以切換的效率比較高。

使用多線程編程會遇到以下問題：

這便有了 “協程”，線程分爲內核態線程和用戶態線程，用戶態線程需要綁定內核態線程，CPU 並不能感知用戶態線程的存在，它只知道它在運行 1 個線程，這個線程實際是內核態線程。

用戶態線程實際有個名字叫協程（co-routine），爲了容易區分，使用協程指用戶態線程，使用線程指內核態線程。

協程跟線程是有區別的，線程由 CPU 調度是搶佔式的，協程由用戶態調度是協作式的，一個協程讓出 CPU 後，才執行下一個協程。

Go 中，協程被稱爲 goroutine（但其實並不完全是協程，還做了其他方面的優化），它非常輕量，一個 goroutine 只佔幾 KB，並且這幾 KB 就足夠 goroutine 運行完，這就能在有限的內存空間內支持大量 goroutine，支持了更多的併發。雖然一個 goroutine 的棧只佔幾 KB，但實際是可伸縮的，如果需要更多內容，runtime 會自動爲 goroutine 分配。

而將所有的 goroutines 按照一定算法放到 CPU 上執行的程序就稱爲 goroutine 調度器或 goroutine scheduler。

不過，一個 Go 程序對於操作系統來說只是一個用戶層程序，對於操作系統而言，它的眼中只有 thread，它並不知道有什麼叫 Goroutine 的東西的存在。goroutine 的調度全要靠 Go 自己完成，所以就需要 goroutine 調度器來實現 Go 程序內 goroutine 之間的 CPU 資源調度。

在操作系統層面，Thread 競爭的 CPU 資源是真實的物理 CPU，但對於 Go 程序來說，它是一個用戶層程序，它本身整體是運行在一個或多個操作系統線程上的，因此 goroutine 們要競爭的所謂 “CPU” 資源就是操作系統線程。這樣 Go scheduler 的要做的就是：將 goroutines 按照一定算法放到不同的操作系統線程中去執行。這種在語言層面自帶調度器的，稱之爲原生支持併發。

goroutine 調度器的演進

調度器的任務是在用戶態完成 goroutine 的調度，而調度器的實現好壞，對併發實際有很大的影響。

G-M 模型

現在的 Go 語言調度器是 2012 年重新設計的，在這之前的調度器稱爲老調度器，老調度器採用的是 G-M 模型，在這個調度器中，每個 goroutine 對應於 runtime 中的一個抽象結構：G，而 os thread 作爲物理 CPU 的存在而被抽象爲一個結構：M(machine)。M 想要執行 G、放回 G 都必須訪問全局 G 隊列，並且 M 有多個，即多線程訪問同一資源需要加鎖進行保證互斥 / 同步，所以全局 G 隊列是有互斥鎖進行保護的。

這個結構雖然簡單，但是卻存在着許多問題。它限制了 Go 併發程序的伸縮性，尤其是對那些有高吞吐或並行計算需求的服務程序。主要體現在如下幾個方面：

所以用了 4 年左右就被替換掉了。

G-P-M 模型

面對之前調度器的問題，Go 設計了新的調度器，並在其中引入了 P（Processor），另外還引入了任務竊取調度的方式（work stealing）

P：Processor，它包含了運行 goroutine 的資源，如果線程想運行 goroutine，必須先獲取 P，P 中還包含了可運行的 G 隊列。work stealing：當 M 綁定的 P 沒有可運行的 G 時，它可以從其他運行的 M 那裏偷取 G。G-P-M 模型的結構如下圖：

從上往下是調度器的 4 個部分：

全局隊列（Global Queue）：存放等待運行的 G。P 的本地隊列：同全局隊列類似，存放的也是等待運行的 G，存的數量有限，不超過 256 個。新建 G 時，G 優先加入到 P 的本地隊列，如果隊列滿了，則會把本地隊列中一半的 G 移動到全局隊列。P 列表：所有的 P 都在程序啓動時創建，並保存在數組中，最多有 GOMAXPROCS 個。M：線程想運行任務就得獲取 P，從 P 的本地隊列獲取 G，P 隊列爲空時，M 也會嘗試從全局隊列拿一批 G 放到 P 的本地隊列，或從其他 P 的本地隊列偷一半放到自己 P 的本地隊列。M 運行 G，G 執行之後，M 會從 P 獲取下一個 G，不斷重複下去。Goroutine 調度器和 OS 調度器是通過 M 結合起來的，每個 M 都代表了 1 個內核線程，OS 調度器負責把內核線程分配到 CPU 的核上執行。

有關 P 和 M 的個數問題

P 的數量

由啓動時環境變量 $GOMAXPROCS 或者是由 runtime 的方法 GOMAXPROCS() 決定。這意味着在程序執行的任意時刻都只有 $GOMAXPROCS 個 goroutine 在同時運行。

M 的數量

M 與 P 的數量沒有絕對關係，一個 M 阻塞，P 就會去創建或者切換另一個 M，所以，即使 P 的默認數量是 1，也有可能會創建很多個 M 出來。

搶佔式調度

G-P-M 模型中還實現了搶佔式調度，所謂搶佔式調度指的是在 coroutine 中要等待一個協程主動讓出 CPU 才執行下一個協程，在 Go 中，一個 goroutine 最多佔用 CPU 10ms，防止其他 goroutine 被餓死，這也是 goroutine 不同於 coroutine 的一個地方。在 goroutine 中先後實現了兩種搶佔式調度算法，分別是基於協作的方式和基於信號的方式。

基於協作的搶佔式調度

G-P-M 模型的實現是 Go scheduler 的一大進步，但此時的調度器仍然有一個問題，那就是不支持搶佔式調度，導致一旦某個 G 中出現死循環或永久循環的代碼邏輯，那麼 G 將永久佔用分配給它的 P 和 M，位於同一個 P 中的其他 G 將得不到調度，出現 “餓死” 的情況。當只有一個 P 時 (GOMAXPROCS=1) 時，整個 Go 程序中的其他 G 都會被餓死。所以後面 Go 設計團隊在 Go 1.2 中實現了基於協作的搶佔式調度。

這種搶佔式調度的原理則是在每個函數或方法的入口，加上一段額外的代碼，讓 runtime 有機會檢查是否需要執行搶佔調度。

基於協作的搶佔式調度的工作原理大致如下：

  1. 編譯器會在調用函數前插入一個 runtime.morestack 函數

  2. Go 語言運行時會在垃圾回收暫停程序、系統監控發現 Goroutine 運行超過 10ms 時發出搶佔請求，此時會設置一個 StackPreempt 字段值爲 StackPreempt ，標示當前 Goroutine 發出了搶佔請求。

  3. 當發生函數調用時，可能會執行編譯器插入的 runtime.morestack 函數，它調用的 runtime.newstack 會檢查 Goroutine 的 stackguard0 字段是否爲 StackPreempt

  4. 如果 stackguard0 是 StackPreempt，就會觸發搶佔讓出當前線程

這種實現方式雖然增加了運行時的複雜度，但是實現相對簡單，也沒有帶來過多的額外開銷，所以在 Go 語言中使用了 10 幾個版本。因爲這裏的搶佔是通過編譯器插入函數實現的，還是需要函數調用作爲入口才能觸發搶佔，所以這是一種協作式的搶佔式調度。這種解決方案只能說局部解決了 “餓死” 問題，對於沒有函數調用，純算法循環計算的 G，scheduler 依然無法搶佔。

基於信號的搶佔式調度

Go 語言在 1.14 版本中實現了非協作的搶佔式調度，在實現的過程中重構已有的邏輯併爲 Goroutine 增加新的狀態和字段來支持搶佔。

基於信號的搶佔式調度的工作原理大致如下：

  1. 程序啓動時，在 runtime.sighandler 函數中註冊一個 SIGURG 信號的處理函數 runtime.doSigPreempt

  2. 在觸發垃圾回收的棧掃描時會調用函數 runtime.suspendG 掛起 Goroutine，此時會執行下面的邏輯：

  1. runtime.preemptM 會調用 runtime.signalM 向線程發送信號 SIGURG；

  2. 操作系統收到信號後會中斷正在運行的線程並執行預先在第 1 步註冊的信號處理函數 runtime.doSigPreempt；

  3. runtime.doSigPreempt 函數會處理搶佔信號，獲取當前的 SP 和 PC 寄存器並調用 runtime.sigctxt.pushCall；

  4. runtime.sigctxt.pushCall 會修改寄存器並在程序回到用戶態時執行 runtime.asyncPreempt；

  5. 彙編指令 runtime.asyncPreempt 會調用運行時函數 runtime.asyncPreempt2；

  6. runtime.asyncPreempt2 會調用 runtime.preemptPark；

  7. runtime.preemptPark 會修改當前 Goroutine 的狀態到 _Gpreempted 並調用 runtime.schedule 讓當前函數陷入休眠並讓出線程，調度器會選擇其它的 Goroutine 繼續執行

_Gpreempted 狀態表示當前 groutine 由於搶佔而被阻塞，沒有執行用戶代碼並且不在運行隊列上，等待喚醒

在上面的選擇 SIGURG 作爲觸發異步搶佔的信號：

  1. 該信號需要被調試器透傳；

  2. 該信號不會被內部的 libc 庫使用並攔截；

  3. 該信號可以隨意出現並且不觸發任何後果；

  4. 需要處理多個平臺上的不同信號；

垃圾回收過程中需要暫停整個程序（Stop the world，STW），有時候可能需要幾分鐘的時間，這會導致整個程序無法工作。所以 STW 和棧掃描是一個可以搶佔的安全點（Safe-points）， Go 語言在這裏先加入搶佔功能。基於信號的搶佔式調度只解決了垃圾回收和棧掃描時存在的問題，它到目前爲止沒有解決全部問題。

go func() 調度流程

基於上面的模型，當我們使用 go func() 創建一個新的 goroutine 的時候，其調度流程如下：

  1. 通過 go func () 來創建一個 goroutine；

  2. 有兩個存儲 G 的隊列，一個是局部調度器 P 的本地隊列、一個是全局 G 隊列。新創建的 G 會先保存在 P 的本地隊列中，如果 P 的本地隊列已經滿了就會保存在全局的隊列中；

  3. G 只能運行在 M 中，一個 M 必須持有一個 P，M 與 P 是 1：1 的關係。M 會從 P 的本地隊列彈出一個可執行狀態的 G 來執行，如果 P 的本地隊列爲空，就會想其他的 MP 組合偷取一個可執行的 G 來執行；

  4. 一個 M 調度 G 執行的過程是一個循環機制；

  5. 當 M 執行某一個 G 時候如果發生了 syscall 或則其餘阻塞操作，M 會阻塞，如果當前有一些 G 在執行，runtime 會把這個線程 M 從 P 中摘除 (detach)，然後再創建一個新的操作系統的線程 (如果有空閒的線程可用就複用空閒線程) 來服務於這個 P；

  6. 當 M 系統調用結束時候，這個 G 會嘗試獲取一個空閒的 P 執行，並放入到這個 P 的本地隊列。如果獲取不到 P，那麼這個線程 M 變成休眠狀態， 加入到空閒線程中，然後這個 G 會被放入全局隊列中。

Goroutine 生命週期

在這裏有一個線程和一個 groutine 比較特殊，那就是 M0 和 G0：

對於下面的簡單代碼：

package main

import "fmt"

// main.main
func main() {
   fmt.Println("Hello scheduler")
}

其運行時所經歷的過程跟上面的生命週期相對應：

  1. runtime 創建最初的線程 m0 和 goroutine g0，並把 2 者關聯。

  2. 調度器初始化：初始化 m0、棧、垃圾回收，以及創建和初始化由 GOMAXPROCS 個 P 構成的 P 列表。

  3. 示例代碼中的 main 函數是 main.main，runtime 中也有 1 個 main 函數——runtime.main，代碼經過編譯後，runtime.main 會調用 main.main，程序啓動時會爲 runtime.main 創建 goroutine，稱它爲 main goroutine，然後把 main goroutine 加入到 P 的本地隊列。

  1. G 擁有棧，M 根據 G 中的棧信息和調度信息設置運行環境

  2. M 運行 G

  3. G 退出，再次回到 M 獲取可運行的 G，這樣重複下去，直到 main.main 退出，runtime.main 執行 Defer 和 Panic 處理，或調用 runtime.exit 退出程序。

調度器的生命週期幾乎佔滿了一個 Go 程序的一生，runtime.main 的 goroutine 執行之前都是爲調度器做準備工作，runtime.main 的 goroutine 運行，纔是調度器的真正開始，直到 runtime.main 結束而結束。

Goroutine 調度器場景分析

場景一

p1 擁有 g1，m1 獲取 p1 後開始運行 g1，g1 使用 go func() 創建了 g2，爲了局部性 g2 優先加入到 p1 的本地隊列：

場景二

g1 運行完成後 (函數：goexit)，m 上運行的 goroutine 切換爲 g0，g0 負責調度時協程的切換（函數：schedule）。

從 p1 的本地隊列取 g2，從 g0 切換到 g2，並開始運行 g2 (函數：execute)。實現了線程 m1 的複用。

場景三

假設每個 p 的本地隊列只能存 4 個 g。g2 要創建 6 個 g，前 4 個 g（g3, g4, g5, g6）已經加入 p1 的本地隊列，p1 本地隊列滿了。

g2 在創建 g7 的時候，發現 p1 的本地隊列已滿，需要執行負載均衡，把 p1 中本地隊列中前一半的 g，還有新創建的 g 轉移到全局隊列

實現中並不一定是新的 g，如果 g 是 g2 之後就執行的，會被保存在本地隊列，利用某個老的 g 替換新 g 加入全局隊列），這些 g 被轉移到全局隊列時，會被打亂順序。

所以 g3,g4,g7 被轉移到全局隊列。

藍色長方形代表全局隊列。

如果此時 G2 創建 G8 時，P1 的本地隊列未滿，所以 G8 會被加入到 P1 的本地隊列：

場景四

在創建 g 時，運行的 g 會嘗試喚醒其他空閒的 p 和 m 組合去執行。假定 g2 喚醒了 m2，m2 綁定了 p2，並運行 g0，但 p2 本地隊列沒有 g，m2 此時爲自旋線程（沒有 G 但爲運行狀態的線程，不斷尋找 g）。

m2 接下來會嘗試從全局隊列 (GQ) 取一批 g 放到 p2 的本地隊列（函數：findrunnable）。m2 從全局隊列取的 g 數量符合下面的公式：

n = min(len(GQ)/GOMAXPROCS + 1, len(GQ/2))

公式的含義是，至少從全局隊列取 1 個 g，但每次不要從全局隊列移動太多的 g 到 p 本地隊列，給其他 p 留點。這是從全局隊列到 P 本地隊列的負載均衡。

假定場景中一共有 4 個 P（GOMAXPROCS=4），所以 m2 只從能從全局隊列取 1 個 g（即 g3）移動 p2 本地隊列，然後完成從 g0 到 g3 的切換，運行 g3：

場景五

假設 g2 一直在 m1 上運行，經過 2 輪後，m2 已經把 g7、g4 也挪到了 p2 的本地隊列並完成運行，全局隊列和 p2 的本地隊列都空了，如下圖左邊所示。

全局隊列已經沒有 g，那 m 就要執行 work stealing：從其他有 g 的 p 哪裏偷取一半 g 過來，放到自己的 P 本地隊列。p2 從 p1 的本地隊列尾部取一半的 g，本例中一半則只有 1 個 g8，放到 p2 的本地隊列，情況如下圖右邊：

場景六

p1 本地隊列 g5、g6 已經被其他 m 偷走並運行完成，當前 m1 和 m2 分別在運行 g2 和 g8，m3 和 m4 沒有 goroutine 可以運行，m3 和 m4 處於自旋狀態，它們不斷尋找 goroutine。

這裏有一個問題，爲什麼要讓 m3 和 m4 自旋？自旋本質是在運行，線程在運行卻沒有執行 g，就變成了浪費 CPU，銷燬線程可以節約 CPU 資源不是更好嗎？實際上，創建和銷燬 CPU 都是浪費時間的，我們希望當有新 goroutine 創建時，立刻能有 m 運行它，如果銷燬再新建就增加了時延，降低了效率。當然也考慮了過多的自旋線程是浪費 CPU，所以系統中最多有 GOMAXPROCS 個自旋的線程，多餘的沒事做的線程會讓他們休眠（函數：notesleep() 實現了這個思路）。

場景七

假定當前除了 m3 和 m4 爲自旋線程，還有 m5 和 m6 爲自旋線程，g8 創建了 g9，g9 會放入本地隊列。加入此時 g8 進行了阻塞的系統調用，m2 和 p2 立即解綁，p2 會執行以下判斷：如果 p2 本地隊列有 g、全局隊列有 g 或有空閒的 m，p2 都會立馬喚醒 1 個 m 和它綁定，否則 p2 則會加入到空閒 P 列表，等待 m 來獲取可用的 p。本場景中，p2 本地隊列有 g，可以和其他自旋線程 m5 綁定。

場景八

假設 g8 創建了 g9，假如 g8 進行了非阻塞系統調用（CGO 會是這種方式，見 cgocall()），m2 和 p2 會解綁，但 m2 會記住 p，然後 g8 和 m2 進入系統調用狀態。當 g8 和 m2 退出系統調用時，會嘗試獲取 p2，如果無法獲取，則獲取空閒的 p，如果依然沒有，g8 會被記爲可運行狀態，並加入到全局隊列。

場景九

前面說過，Go 調度在 go1.12 實現了搶佔，應該更精確的稱爲基於協作的請求式搶佔，那是因爲 go 調度器的搶佔和 OS 的線程搶佔比起來很柔和，不暴力，不會說線程時間片到了，或者更高優先級的任務到了，執行搶佔調度。go 的搶佔調度柔和到只給 goroutine 發送 1 個搶佔請求，至於 goroutine 何時停下來，那就管不到了。搶佔請求需要滿足 2 個條件中的 1 個：

狀態彙總

從上面的場景中可以總結各個模型的狀態：

G 狀態

G 的主要幾種狀態：

Rlu0iG

P 狀態

zOSt3A

M 狀態

自旋線程：處於運行狀態但是沒有可執行 goroutine 的線程，數量最多爲 GOMAXPROC，若是數量大於 GOMAXPROC 就會進入休眠。

非自旋線程：處於運行狀態有可執行 goroutine 的線程。

調度器設計

從上面的流程可以總結出 goroutine 調度器的一些設計思路：

調度器設計的兩大思想

複用線程：協程本身就是運行在一組線程之上，所以不需要頻繁的創建、銷燬線程，而是對線程進行復用。在調度器中複用線程還有 2 個體現：

  1. work stealing，當本線程無可運行的 G 時，嘗試從其他線程綁定的 P 偷取 G，而不是銷燬線程。

  2. hand off，當本線程因爲 G 進行系統調用阻塞時，線程釋放綁定的 P，把 P 轉移給其他空閒的線程執行。

利用並行：GOMAXPROCS 設置 P 的數量，當 GOMAXPROCS 大於 1 時，就最多有 GOMAXPROCS 個線程處於運行狀態，這些線程可能分佈在多個 CPU 核上同時運行，使得併發利用並行。另外，GOMAXPROCS 也限制了併發的程度，比如 GOMAXPROCS = 核數 / 2，則最多利用了一半的 CPU 核進行並行。

調度器設計的兩小策略

搶佔：

在 coroutine 中要等待一個協程主動讓出 CPU 才執行下一個協程，在 Go 中，一個 goroutine 最多佔用 CPU 10ms，防止其他 goroutine 被餓死，這就是 goroutine 不同於 coroutine 的一個地方。

全局 G 隊列：

在新的調度器中依然有全局 G 隊列，但功能已經被弱化了，當 M 執行 work stealing 從其他 P 偷不到 G 時，它可以從全局 G 隊列獲取 G。

GPM 可視化調試

有 2 種方式可以查看一個程序 GPM 的數據：

go tool trace

trace 記錄了運行時的信息，能提供可視化的 Web 頁面。

簡單測試代碼：main 函數創建 trace，trace 會運行在單獨的 goroutine 中，然後 main 打印 “Hello trace” 退出。

func main() {
    // 創建trace文件
    f, err := os.Create("trace.out")
    if err != nil {
        panic(err)
    }
    defer f.Close()

    // 啓動trace goroutine
    err = trace.Start(f)
    if err != nil {
        panic(err)
    }
    defer trace.Stop()

    // main
    fmt.Println("Hello trace")
}

運行程序和運行 trace：

$ go run trace.go 
Hello World

會得到一個 trace.out 文件，然後可以用一個工具打開，來分析這個文件:

$ go tool trace trace.out 
2020/12/07 23:09:33 Parsing trace...
2020/12/07 23:09:33 Splitting trace...
2020/12/07 23:09:33 Opening browser. Trace viewer is listening on http://127.0.0.1:56469

接下來通過瀏覽器打開 http://127.0.0.1:33479 網址，點擊 view trace 能夠看見可視化的調度流程：

g 信息

點擊 Goroutines 那一行的數據條，會看到一些詳細的信息：

上面表示一共有兩個 G 在程序中，一個是特殊的 G0，是每個 M 必須有的一個初始化的 G。其中 G1 就是 main goroutine (執行 main 函數的協程)，在一段時間內處於可運行和運行的狀態。

m 信息

點擊 Threads 那一行可視化的數據條，會看到一些詳細的信息：

這裏一共有兩個 M 在程序中，一個是特殊的 M0，用於初始化使用。

p 信息

G1 中調用了 main.main，創建了 trace goroutine g6。G1 運行在 P0 上，G6 運行在 P1 上。

這裏有三個 P。

在看看上面的 M 信息：

可以看到確實 G6 在 P1 上被運行之前，確實在 Threads 行多了一個 M 的數據，點擊查看如下：

多了一個 M2 應該就是 P1 爲了執行 G6 而動態創建的 M2。

Debug trace

示例代碼：

// main.main
func main() {
    for i := 0; i < 5; i++ {
        time.Sleep(time.Second)
        fmt.Println("Hello scheduler")
    }
}

編譯後通過 Debug 方式運行，運行過程會打印 trace：

➜ go build .
➜ GODEBUG=schedtrace=1000 ./one_routine2

結果：

SCHED 0ms: gomaxprocs=4 idleprocs=2 threads=3 spinningthreads=1 idlethreads=0 runqueue=0 [1 0 0 0]
Hello scheduler
SCHED 1003ms: gomaxprocs=4 idleprocs=4 threads=5 spinningthreads=0 idlethreads=3 runqueue=0 [0 0 0 0]
Hello scheduler
SCHED 2007ms: gomaxprocs=4 idleprocs=4 threads=5 spinningthreads=0 idlethreads=3 runqueue=0 [0 0 0 0]
Hello scheduler
SCHED 3010ms: gomaxprocs=4 idleprocs=4 threads=5 spinningthreads=0 idlethreads=3 runqueue=0 [0 0 0 0]
Hello scheduler
SCHED 4013ms: gomaxprocs=4 idleprocs=4 threads=5 spinningthreads=0 idlethreads=3 runqueue=0 [0 0 0 0]
Hello scheduler

各個字段的含義如下：

看第一行，含義是：剛啓動時創建了 4 個 P，其中 2 個空閒的 P，共創建 3 個 M，其中 1 個 M 處於自旋，沒有 M 處於空閒，第一個 P 的本地隊列有一個 G。

另外，可以加上 scheddetail=1 可以打印更詳細的 trace 信息。

命令：

➜ GODEBUG=schedtrace=1000,scheddetail=1 ./one_routine2
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/eX32jJMQBXov-HS8vRxo0Q

猜你喜歡