Golang MGP 調度器

【導讀】本文詳細介紹了 Go 語言的 MGP 模型中調度器的設計和演進。

Go 調度器

我們知道 Go 裏面有成千上萬 coroutine 需要調度執行，而這裏面起關鍵作用的就是 Go 的調度器，那麼 Go 的調度器在哪裏呢？因爲我們寫 Go 代碼的時候從未顯式創建過調度器實例。爲了瞭解調度器，我們先來了解下 Go 的運行時（Runtime)。

爲什麼要有 Runtime

開銷上

我們知道操作系統是可以調度線程的，那麼我們可不可以直接讓操作系統調用 go 的線程呢。
POSIX 線程 (POSIX 是線程標準，定義了創建和操縱線程的一套 API) 通常是在已有的進程模型中增加的邏輯擴展，所以線程控制和進程控制很相似。線程也有自己的信號掩碼 (signal mask)，線程也可以設置 CPU 親和性(CPU affinity)，也可以放進 cgroups 中進行資源管理。假如 goroutines (go 的執行單元) 對應線程的話，使用這些特性對線程進行控制管理就增加了開銷，因爲 go 程序運行 goroutines (go 的執行單元)不需要這些特性。這類消耗在 goroutine 達到比如 10,0000 個的時候就會很大。所以 go 需要有個運行時在調度 goroutines 而不是隻是讓操作系統調度線程。

垃圾回收上

go 包含垃圾回收 (GC) 的特性，在垃圾回收的時候所有 goroutines 必須處於暫停的狀態，這樣 go 的內存纔會處於一種一致的狀態. 所以我們必須等待所有線程處於內存一致的狀態才能進行垃圾回收。

在沒有調度器的時候，線程調度是隨操作系統的意的，你不得不試圖去等待所有的已經暫停和還沒暫停的線程，而且不知道等多久 (如果線程進入了阻塞狀態比如 sleep 中是無法立即響應 signal 的)。

在有調度器的時候，調度器可以決定只在內存一致的時候才發起調度（即只要有活躍的線程就不執行新的任務），因此當需要執行 gc 的時候，調度器便決定只在內存一致的時候才發起調度，所以所有線程都無法再次活躍，調度器只需要等待當前活躍的線程暫停即可。後面還會講到調度器還想辦法避免一個活躍的線程長時間不停下來。

需要調度器自然就需要運行調度器的運行時。

基於這兩個原因， golang 需要一個運行時 (Runtime).

或者簡單的講，要想做協程線程調度就要有運行時。要想做垃圾回收就要有運行時。

什麼是 Runtime

上面可以分析出 Runtime 所擔任的職責：goroutines 調度，垃圾回收，當然還提供 goroutines 執行的環境。

所以這也相當於簡要解釋了什麼是 Runtime。

go 的可執行程序可以分成兩個層：用戶代碼和運行時，運行時提供接口函數供用戶代碼調用，用來管理 goroutines, channels 和其他一些內置抽象結構。用戶代碼對操作系統 API 的任何調用都會被運行時層截取，以方便調度和垃圾回收。分層如如些：

初代調度器

Go 的調度程序是 Go 運行時的一個更重要的方面。運行時會跟蹤每個 Goroutine，並將安排它們在線程池中運行。goroutines 與線程分離（解耦不強綁定），但運行於線程之上。如何有效地將 goroutine 調度到線程上對於 go 程序的高性能至關重要。

Goroutines 的背後邏輯是：它們能夠同時運行，與線程類似，但相比之下非常輕量。因此，程序運行時，Goroutines 的個數應該是遠大於線程的個數的。

同時多線程在程序中是很有必要的，因爲當 goroutine 調用了一個阻塞的系統調用，比如 sleep，那麼運行這個 goroutine 的線程就會被阻塞，那麼這時運行時至少應該再創建一個線程來運行別的沒有阻塞的 goroutine。線程這裏可以創建不止一個，可以按需不斷地創建，而活躍的線程（處於非阻塞狀態的線程）的最大個數存儲在變量GOMAXPROCS中。

go 運行時使用 3 個結構來跟蹤所有成員來支持調度器的工作。

一個 G 代表一個 goroutine，包含當前棧，當前狀態和函數體。

struct G
{
    byte∗ stackguard; // stack guard information
    byte∗ stackbase; // base of stack
    byte∗ stack0; // current stack pointer
    byte∗ entry; // initial function
    void∗ param; // passed parameter on wakeup
    int16 status; // status
    int32 goid; // unique id
    M∗ lockedm; // used for locking M’s and G’s
    ...
}

一個 M 代表一個線程，包含全局 G 隊列，當前 G ，內存等。

struct M
{
    G∗ curg; // current running goroutine
    int32 id; // unique id
    int32 locks ; // locks held by this M
    MCache ∗mcache; // cache for this thread
    G∗ lockedg; // used for locking M’s and G’s
    uintptr createstack [32]; // Stack that created this thread
    M∗ nextwaitm; // next M waiting for lock
    ...
};

SCHED:

SCHED 是全局單例，用來跟蹤 G 隊列和 M 隊列，和維護其他一些信息。

struct Sched {
    Lock; // global sched lock .
    // must be held to edit G or M queues
    G ∗gfree; // available g’ s ( status == Gdead)
    G ∗ghead; // g’ s waiting to run queue
    G ∗gtail; // tail of g’ s waiting to run queue
    int32 gwait; // number of g’s waiting to run
    int32 gcount; // number of g’s that are alive
    int32 grunning; // number of g’s running on cpu
    // or in syscall
    M ∗mhead; // m’s waiting for work
    int32 mwait; // number of m’s waiting for work
    int32 mcount; // number of m’s that have been created
    ...
};

運行時剛啓動時會啓動一些 G , 其中一個負責垃圾回收，其中一個負責調度，其中一個負責用戶的入口函數。一開始運行時只有一個 M 被創建，隨後，用戶層面的更多 G 被創建，然後更多的 M 被創建出來執行更多的 G 。同時最多同時支持GOMAXPROCS個活躍的線程。

M 代表一個線程，M 需要從全局 G 隊列中取出一個 G 並且執行 G 對應的代碼，如果 G 代碼執行阻塞的系統調用，那麼會首先從空閒的 M 隊列中取出一個 M 喚醒，隨後執行阻塞調用，陷入阻塞。這麼做是因爲線程阻塞後，活躍的線程數肯定就小於GOMAXPROCS了，這時我們就可以增加一個活躍的線程以防止當前有 G 在等在 M。

造成阻塞的都是系統調用，在調用返回之前，線程會一直則塞。但是注意，M 不會在 channel 的操作中阻塞，這是因爲操作系統並不知道 channel ，channel 的所有的操作都是有運行時來處理的。所以如果 goroutine 執行了 channel 操作，這時 goroutine 可能會需要阻塞，但是這個阻塞不是操作系統帶來的阻塞，因此 M 並不需要一起阻塞。這種場景下，這個 G 會被標記爲 waiting，然後原來執行這個 G 的 M 會繼續去執行別的 G。waiting 的 G 在 channel 操作完成後會設爲 runable 狀態，並等待空閒的 M 來執行，不一定是先前那個 M 了。

初代的問題

初代的調度器相對簡單，所以也存在一定的問題，當然初代調度器的目的不是要馬上做到成熟，只是在有限的時間內做出一個還可以的版本。

Dmitry Vyukov（新調度器的作者）寫的一個論文列舉了老調度器存在的問題：

以下來自 Scalable Go Scheduler Design Doc (https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/edit#heading=h.mmq8lm48qfcw)

第一個問題是全局鎖，無論是修改 M 還是 G 的隊列還是其他 SCHED 結構的相關字段，都需要獲取這個全局鎖，當遇到高吞吐高併發的程序的時候，這個設計會導致調度器的性能問題。

第二個是當前有很多 M 之間傳遞 G 的情況，比如新建的 G 會被被放到全局隊列，而不是在 M 本地執行，這導致了不必要的開銷和延遲，應該優先在創建 G 的 M 上執行就可以了。

第三個問題是每一個 M 現在都持有一個內存，包括了阻塞狀態的 M 也是持有的。Active 狀態的 M 跟總的 M 個數之比可以達到 1:100 。這就導致了過多的內存消耗，以及較差的數據局部性。數據局部性怎麼理解呢？數據局部性這裏是指 G 當前在 M 運行後對 M 的內存進行了預熱，後面如果再次調度到同一個 M 那麼可以加速訪問，可想而知，因爲現在 G 調度到同一個 M 的概率不高，所以數據局部性不好。

第四個是 M 持續的阻塞和喚醒帶來的開銷。比如 M 找不到 P （目的是一有 P 釋放就結合），M 找到了 P 但找不到 G（目的是一有 runable 的 G 就執行），此時 M 就會進入頻繁阻塞 / 喚醒來進行檢查的邏輯，以便及時發現新的 P 新的 G 來執行。

新調度器

調度器細節

Dmitry Vyukov 的方案是引入一個結構 P ，用來模擬處理器， M 依舊錶示操作系統線程，G 依舊錶示一個 goroutine。

GOMAXPROCS用來控制 P 的個數，同時 P 作爲 M 執行 G 代碼時的必需資源。

新的 P 結構會帶走原來的 M 和 SCHED 結構中的一些屬性，比如 MCache 從 M 移到了 P，而 G 隊列也被分成兩類，SCHED 結構保留全局 G 隊列，同時每個 P 中都會有一個本地的 G 隊列。

P 的本地隊列可以解決舊調度器中單一全局鎖的問題。注意 P 的本地 G 隊列還是可能面臨一個併發訪問的場景，比如下面講到的竊取算法。爲了避免加鎖，這裏 P 的本地隊列是一個 LockFree 的隊列，竊取 G 時使用 CAS 原子操作來完成。

而 P 的 MCache 也就意味着不必爲每一個 M 都配備一塊內存，避免了過多的內存消耗。

當一個新的 G 被創建的時候，G 被放到當前 M 所關聯的 P 的本地隊列結尾，這樣 G 雖然不是立即執行，但最終會得到執行。

當 P 執行系統調用即將阻塞時，M 會釋放 P ，並進入阻塞，直到系統調用返回時， M 會嘗試獲取空閒的 P，有的話繼續執行，沒有就把 G 會放到全局 G ，而 M 會進入空閒的 M 隊列。

由於每個 P 都有 G 隊列，那麼當一個 P 的 G 隊列執行完了的時候，另一個 P 卻可能堆積了很多 G，所以新的調度器有個 G 的調度算法，一般都叫做竊取算法（stealing algorithm）。

當一個 P 執行完本地所有的 G 之後，會嘗試隨機挑選一個受害者 P，從它的 G 隊列中竊取一半的 G。當嘗試若干次竊取都失敗之後，會從全局 G 隊列中獲取 G 。那麼一次從全局隊列取多少個呢，取 當前個數 /GOMAXPROCS 個 (忽略其他一些限值檢查)。所以可以看到這個全局隊列使用的頻率很低，雖然也是全局鎖但是不至於影響性能。當然光竊取失敗時獲取是不夠的可能會導致全局隊列飢餓。P 的算法中還會每個 N 輪調度之後就去全局隊列拿一個 G 。那麼全局隊列的 G 又是誰放進去的呢？是在新建 G 時 P 的本地 G 隊列放不下的時候會放半數 G 到全局隊列去, 阻塞的系統調用返回時找不到空閒 P 也會放到全局隊列。

在竊取到的 G 中，有一些 G 是標記了它綁定的 M 的，遇到這類 G 的話，當前 M 就會檢查這個綁定的 M 是否是空閒狀態，如果是空閒的話（不空閒就有問題了，這個 M 是專門執行這個 G 的不會執行別的 G ）就會把這個 M 喚醒，然後把 P 和 G 交給它去執行，自己則進入阻塞狀態。這部分邏輯是實現協程和線程一一綁定的關係，參見 LockOSThread (https://github.com/golang/go/wiki/LockOSThread)。

同時新調度器中引入了線程自旋，自旋有好處有壞處，好處是避免線程被阻塞陷入內核，壞處是自旋屬於空轉，浪費 CPU 。只能說適度使用自旋是可以帶來好處的。新方案在兩個地方引入自旋：

M 找不到 P（目的是一有 P 釋放就結合）
M 找到了 P 但找不到 G（目的是一有 runable 的 G 就執行）

由於 P 最多隻有GOMAXPROCS，所以自旋的 M 最多隻允許GOMAXPROCS個，多了就沒有意義了。同時當有類型 1 的自旋 M 存在時，類型 2 的自旋 M 就不阻塞，阻塞會釋放 P，一釋放 P 就馬上被類型 1 的自旋 M 搶走了，沒必要。

在新 G 被創建，M 進入系統調用，M 從空閒被激活這三種狀態變化前，調度器會確保至少有一個自旋 M 存在，除非沒有空閒的 P。

我們來分析下，當新 G 創建，如果有可用 P，就意味着新 G 可以被立即執行，即便不在同一個 P 也無妨，所以我們保留一個自旋的 M（這時應該不存在類型 1 的自旋只有類型 2 的自旋）就可以保證新 G 很快被運行。當 M 進入系統調用，意味着 M 不知道何時可以醒來，那麼 M 對應的 P 中剩下的 G 就得有新的 M 來執行，所以我們保留一個自旋的 M 來執行剩下的 G（這時應該不存在類型 2 的自旋只有類型 1 的自旋）。如果 M 從空閒變成活躍，意味着可能一個處於自旋狀態的 M 進入工作狀態了，這時要檢查並確保還有一個自旋 M 存在，以防還有 G 或者還有 P 空着的。

現在來看下面這個圖應該在理解上就沒有大問題了：

dance between gmp

問題總結

到這裏，老調度器中的問題已經一一被解決了。我們來一一回顧下：

全局鎖的問題

G 被分成全局 G 隊列和 P 的本地 G 隊列，全局 G 隊列依舊是全局鎖，但是使用場景明顯很少，P 本地隊列使用無鎖隊列，使用原子操作來面對可能的併發場景。

G 傳遞帶來開銷的問題

G 創建時就在 P 的本地隊列，可以避免在 G 之間傳遞（竊取除外）; 當 G 開始執行了，系統調用返回後 M 會嘗試獲取可用 P，獲取到了的話可以避免在 M 之間傳遞。

內存消耗問題

內存 MCache 只存在 P 結構中，P 最多隻有GOMAXPROCS個，遠小於 M 的個數，所以內存沒有過多的消耗。

數據局部性問題

新建的 G 放在本地隊列，所以 G 對 P 的數據局部性好；系統調用後嘗試獲取可用 P 並執行，而且優先獲取調用阻塞前的 P ，所以 G 對 M 數據局部性好，G 對 P 的數據局部性也好；由於總的內存數目最多隻有GOMAXPROCS而不是 M 的個數了，因此 G 調度到擁有同一塊內存的執行單元的概率也就變大了，數據局部性也就變好了。

數據局部性還可以更好的，比如 M 選擇空閒 P 時可以優先選擇上一次綁定過的 P 。

頻繁阻塞和喚醒

通過引入自旋，保證任何時候都有處於等待狀態的自旋 M ，避免在等待可用的 P 和 G 時頻繁的阻塞和喚醒。

Go 程序的啓動過程

整個程序始於一段彙編:

// _rt0_amd64 is common startup code for most amd64 systems when using
// internal linking. This is the entry point for the program from the
// kernel for an ordinary -buildmode=exe program. The stack holds the
// number of arguments and the C-style argv.
TEXT _rt0_amd64(SB),NOSPLIT,$-8
 MOVQ 0(SP), DI // argc
 LEAQ 8(SP), SI // argv
 JMP runtime·rt0_go(SB)

而在隨後的 runtime·rt0_go（也是彙編程序）中，go 一共做了這麼幾件事：

綁定 m0 和 g0

m0 和 g0 是什麼呢，m0 就是程序的主線程，程序啓動必然會擁有一個主線程，這個就是 m0.

每一個 m 結構中會包含兩個主要的 g ：

type m struct {
 g0      *g     // goroutine with scheduling stack
 ...
 curg          *g       // current running goroutine
 ...
}

可以看到 m 中的 g0 負責調度，curg 是具體的任務 g。因此這裏的 g0 也就是 m0 的 g0。而 m0 的 curg 現在還是空的。

創建 p，綁定 m0 和 p0

這裏並不是去初始化 g0，而是創建出了所需的 p，p 的數目優先取環境變量GOMAXPROCS, 否則默認是 cpu 核數。隨後把第一個 p（便於理解可以叫它 p0）與 m0 進行綁定，這樣 m0 就有他自己的 p 了，就有條件執行後續的任務 g 了。

新建任務 g 到 p0 本地隊列

這裏 m0 的 g0 會執行調度任務（runtime.newproc)，創建一個 g，g 指向runtime.main()(還不是我們 main 包中的 main）, 並放到 p 的本地隊列。這樣 m0 就已經同時具有了任務 g 和 p ，什麼條件都具備了。

執行統一的調度任務

調度器實現中有個同一個調度器入口，叫mstart(), 這個實現中會去獲取一個空閒的 p（如果沒有），然後執行schedule(), schedule 中就會去不停的尋找可用的 g 來執行。這裏其實初始工作已經全部完成並且把調度器啓動起來了。後面可以不用管了，可以自動跑起來了。

持續調度

由於前一個步驟已經在 p0 中插入了一個指向runtime.main的 g，所以顯然之後第一個跑起來的任務 g 就是runtime.main。

runtime.main的工作包括：啓動 sysmon 線程（這個線程遊離在調度器之外，不受調度器管理，下面再講）；啓動 gc 協程；執行 init，這個就是統一執行我們代碼中書寫的各種 init 函數；執行 main 函數，這個就是我們 main 包中的 main，可以看到，到這裏我們的函數入口才終於被執行到了。

再後面就是前面講過的 GMP 模型的工作過程了，main 會創建 g ，g 被放入 p，並且觸發 m 的創建，如此循環往復。

Sysmon 線程

我們前面遺留了一些沒有解釋的工作流程，一個是調度器如何搶佔長時間不返回的 g，一個是 sysmon 是做什麼的. 這裏可以一起解釋了。因爲調度器就是通過 sysmon 來進行搶佔的。

sysmon 也叫監控線程，它無需 P 也可以運行，他是一個死循環，每20us~10ms循環一次，循環完一次就 sleep 一會，爲什麼會是一個變動的週期呢，主要是避免空轉，如果每次循環都沒什麼需要做的事，那麼 sleep 的時間就會加大。

sysmon 主要做下面幾個事:

釋放閒置超過 5 分鐘的 span 物理內存；
如果超過 2 分鐘沒有垃圾回收，強制執行；
將長時間未處理的 netpoll 結果添加到全局 G 隊列；
向長時間運行的 G 任務發出搶佔調度；
收回因 syscall 長時間阻塞的 P；

那麼搶佔就是發生在第 4 點。

當 sysmon 發現一個 p 一直處於 running 狀態超過了 10ms，那麼就給這個 g 設置一個標誌位，隨後等到這個 g 調用新函數的時候，會檢查到這個標誌位，並且重新進行調度，不讓這個 g 繼續執行。

不過並不是設置了標誌位就一定會被調度，這裏有兩個條件，一個是 g 必須調用函數，否則如果是一個簡單的死循環是無法搶佔成功的；另一個條件是即使調用了新函數，如果新函數所需的棧空間很少，那麼也不會觸發檢查這個標誌位，只有調用了會觸發棧空間檢查（所需棧大於 128 字節，詳見知乎回答 https://www.zhihu.com/question/308020301/answer/587239642）的函數，纔會搶佔成功。

第 5 點是什麼意思呢，我們知道 g 中調用系統調用後會解綁 p，然後 m 和 g 進入阻塞，而 p 此時的狀態就是 syscall ，表明這個 p 的 g 正在 syscall 中，這時的 p 是不能被調度給別的 m 的。如果在短時間內阻塞的 m 就喚醒了，那麼 m 會優先來重新獲取這個 p，能獲取到就繼續綁回去，這樣有利於數據的局部性。

但是當 m 較長時間沒有喚醒的話，p 繼續等的成本就有點大了，這個時候 sysmon 就會吧他設爲 idle，重新調度給需要的 M 。這個時間界限是 10ms，超過 10ms 就會被 sysmon 回收用於調度。

go 的協程模型

這部分跟調度器關係不大，主要是補充一個知識點。

golang 的 goroutines 是基於 CSP(Communicating Sequential Processes) 理論模型來設計的。

CSP 主要是指兩個獨立的 Process，通過共享 Channel 來交互。併發模型除了 CSP 另外還有 Actors 模型。

CSP 和 Actors 簡介

CSP 模型就是 coroutine+channel 的模式。

coroutine 之間通信是通過 channel 實現的，coroutine 之間可以共享 channel 。

比如 golang 就是基於 CSP 實現的。

Actors 模型就是 coroutine+message 的模式。

coroutine 之間通信是通過 message 實現的，message 是明確的發送給某個 coroutine 的。

比如 erlang 就是基於 Actors 實現的。

CSP 和 Actors 的區別

同步異步

CSP 的通信機制通常是同步的，任務被推進 channel 後立即被對端收到並執行，如果對端正忙，則發送者就阻塞無法推送該任務，golang 對 channel 進行了修改，支持緩存任務，可以緩存多個任務等待執行，避免發送者阻塞。

Actors 的通信機制通常是異步的，消息發送時發送者不會阻塞，接收者也不一定馬上收到，收到也不一定馬上執行。erlang 中的 actor 角色非常廣泛，可以是同個 runtime 下的，也可以是 runtime 間的，甚至可以是機器間的。

匿名性

CSP 中的 channel 通常是匿名的，任務放進 channel 後你並不知道對端是誰在接收。

Actors 中的 message 通常有確定目標，你需要確切的知道對方的地址 (ID/NAME/PORT 等) 才能將信息發送出去。

耦合性

CSP 中 channel 是共享的，可以多個生產者可多個消費者公用，生產者消費者之間不強關聯。

Actors 中你必須知道對方的地址 (ID/NAME/PORT 等)，這導致生產者和消費者之間發生耦合，對方 actor 是不可替換的。

容錯

CSP 沒有定義容錯方面的內容，所以開發者需要自己處理 channel 接收和發送的錯誤，這些錯誤處理邏輯可能會到處都是。

Actors 支持容錯，你可以定義錯誤的類型，錯誤處理方式，錯誤的級別等。

轉自：yizhi.ren/2019/06/03/goscheduler/

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/X05cooPuUAaCjsxONLIzDQ