概述

Go 語言在併發編程方面有強大的能力，這離不開語言層面對併發編程的支持。本節會介紹 Go 語言運行時調度器的實現原理，其中包含調度器的設計與實現原理、演變過程以及與運行時調度相關的數據結構。

談到 Go 語言調度器，我們繞不開的是操作系統、進程與線程這些概念，線程是操作系統調度時的最基本單元，而 Linux 在調度器並不區分進程和線程的調度，它們在不同操作系統上也有不同的實現，但是在大多數的實現中線程都屬於進程：

多個線程可以屬於同一個進程並共享內存空間。因爲多線程不需要創建新的虛擬內存空間，所以它們也不需要內存管理單元處理上下文的切換，線程之間的通信也正是基於共享的內存進行的，與重量級的進程相比，線程顯得比較輕量。

雖然線程比較輕量，但是在調度時也有比較大的額外開銷。每個線程會都佔用 1M 以上的內存空間，在切換線程時不止會消耗較多的內存，恢復寄存器中的內容還需要向操作系統申請或者銷燬資源，每一次線程上下文的切換都需要消耗 ~1us 左右的時間，但是 Go 調度器對 Goroutine 的上下文切換約爲 ~0.2us，減少了 80% 的額外開銷。

Go 語言的調度器通過使用與 CPU 數量相等的線程減少線程頻繁切換的內存開銷，同時在每一個線程上執行額外開銷更低的 Goroutine 來降低操作系統和硬件的負載。

設計原理

今天的 Go 語言調度器有着優異的性能，但是如果我們回頭看 Go 語言的 0.x 版本的調度器會發現最初的調度器不僅實現非常簡陋，也無法支撐高併發的服務。調度器經過幾個大版本的迭代纔有今天的優異性能，歷史上幾個不同版本的調度器引入了不同的改進，也存在着不同的缺陷:

• 單線程調度器 — Go 0.x

• 改進：只包含 40 多行代碼；

• 缺陷：程序中只能存在一個活躍線程，由 G-M 模型組成；

• 多線程調度器 — Go 1.0

• 改進：允許運行多線程的程序；

• 缺陷：全局鎖導致競爭嚴重；

• 任務竊取調度器 — Go 1.1

• 改進 1：引入了處理器 P，構成了目前的 G-M-P 模型；

• 改進 2：在處理器 P 的基礎上實現了基於工作竊取的調度器；

• 缺陷 1：在某些情況下，Goroutine 不會讓出線程，進而造成飢餓問題；

• 缺陷 2：時間過長的垃圾回收（Stop-the-world，STW）會導致程序長時間無法工作；

• 搶佔式調度器  — Go 1.2 ~ 至今

• 改進：實現基於信號的真搶佔式調度；

• 缺陷 1：垃圾回收在掃描棧時會觸發搶佔調度；

• 缺陷 2：搶佔的時間點不夠多，還不能覆蓋全部的邊緣情況；

• 改進：通過編譯器在函數調用時插入搶佔檢查指令，在函數調用時檢查當前 Goroutine 是否發起了搶佔請求，實現基於協作的搶佔式調度；

• 缺陷：Goroutine 可能會因爲垃圾回收和循環長時間佔用資源導致程序暫停；

• 基於協作的搶佔式調度器 - 1.2 ~ 1.13

• 基於信號的搶佔式調度器 - 1.14 ~ 至今

• 非均勻存儲訪問調度器 — 提案

• 改進：對運行時的各種資源進行分區；

• 缺陷：實現非常複雜，到今天還沒有提上日程；

除了多線程、任務竊取和搶佔式調度器之外，Go 語言社區目前還有一個非均勻存儲訪問（Non-uniform memory access，NUMA）調度器的提案。在這一節中，我們將依次介紹不同版本調度器的實現原理以及未來可能會實現的調度器提案。

單線程調度器

0.x 版本調度器只包含兩種結構 — 表示 Goroutine 的 G 和表示線程的 M 兩種結構，全局也只有一個線程。我們可以在 clean up scheduler 提交中找到單線程調度器的源代碼，在這時 Go 語言的調度器還是由 C 語言實現的，調度函數 runtime.scheduler:9682400 也只包含 40 多行代碼 ：

static void scheduler(void) {
 G* gp;
 lock(&sched);

 if(gosave(&m->sched)){
  lock(&sched);
  gp = m->curg;
  switch(gp->status){
  case Grunnable:
  case Grunning:
   gp->status = Grunnable;
   gput(gp);
   break;
  ...
  }
  notewakeup(&gp->stopped);
 }

 gp = nextgandunlock();
 noteclear(&gp->stopped);
 gp->status = Grunning;
 m->curg = gp;
 g = gp;
 gogo(&gp->sched);
}

該函數會遵循如下的過程調度 Goroutine：

1. 獲取調度器的全局鎖；

2. 調用 runtime.gosave:9682400 保存棧寄存器和程序計數器；

3. 調用 runtime.nextgandunlock:9682400 獲取下一個需要運行的 Goroutine 並解鎖調度器；

4. 修改全局線程 m 上要執行的 Goroutine；

5. 調用 runtime.gogo:9682400 函數運行最新的 Goroutine；

雖然這個單線程調度器的唯一優點就是能運行，但是這次提交已經包含了 G 和 M 兩個重要的數據結構，也建立了 Go 語言調度器的框架。

多線程調度器

Go 語言在 1.0 版本正式發佈時就支持了多線程的調度器，與上一個版本幾乎不可用的調度器相比，Go 語言團隊在這一階段實現了從不可用到可用的跨越。我們可以在 pkg/runtime/proc.c 文件中找到 1.0.1 版本的調度器，多線程版本的調度函數 runtime.schedule:go1.0.1 包含 70 多行代碼，我們在這裏保留了該函數的核心邏輯：

static void schedule(G *gp) {
 schedlock();
 if(gp != nil) {
  gp->m = nil;
  uint32 v = runtime·xadd(&runtime·sched.atomic, -1<<mcpuShift);
  if(atomic_mcpu(v) > maxgomaxprocs)
   runtime·throw("negative mcpu in scheduler");

  switch(gp->status){
  case Grunning:
   gp->status = Grunnable;
   gput(gp);
   break;
  case ...:
  }
 } else {
  ...
 }
 gp = nextgandunlock();
 gp->status = Grunning;
 m->curg = gp;
 gp->m = m;
 runtime·gogo(&gp->sched, 0);
}

整體的邏輯與單線程調度器沒有太多區別，因爲我們的程序中可能同時存在多個活躍線程，所以多線程調度器引入了 GOMAXPROCS 變量幫助我們靈活控制程序中的最大處理器數，即活躍線程數。

多線程調度器的主要問題是調度時的鎖競爭會嚴重浪費資源，Scalable Go Scheduler Design Doc 中對調度器做的性能測試發現 14% 的時間都花費在 runtime.futex:go1.0.1 上，該調度器有以下問題需要解決：

1. 調度器和鎖是全局資源，所有的調度狀態都是中心化存儲的，鎖競爭問題嚴重；

2. 線程需要經常互相傳遞可運行的 Goroutine，引入了大量的延遲；

3. 每個線程都需要處理內存緩存，導致大量的內存佔用並影響數據局部性；

4. 系統調用頻繁阻塞和解除阻塞正在運行的線程，增加了額外開銷；

這裏的全局鎖問題和 Linux 操作系統調度器在早期遇到的問題比較相似，解決的方案也都大同小異。

任務竊取調度器

2012 年 Google 的工程師 Dmitry Vyukov 在 Scalable Go Scheduler Design Doc 中指出了現有多線程調度器的問題並在多線程調度器上提出了兩個改進的手段：

1. 在當前的 G-M 模型中引入了處理器 P，增加中間層；

2. 在處理器 P 的基礎上實現基於工作竊取的調度器；

基於任務竊取的 Go 語言調度器使用了沿用至今的 G-M-P 模型，我們能在 runtime: improved scheduler 提交中找到任務竊取調度器剛被實現時的源代碼，調度器的 runtime.schedule:779c45a 在這個版本的調度器中反而更簡單了：

static void schedule(void) {
    G *gp;
 top:
    if(runtime·gcwaiting) {
        gcstopm();
        goto top;
    }

    gp = runqget(m->p);
    if(gp == nil)
        gp = findrunnable();

    ...

    execute(gp);
}

1. 如果當前運行時在等待垃圾回收，調用 runtime.gcstopm:779c45a 函數；

2. 調用 runtime.runqget:779c45a 和 runtime.findrunnable:779c45a 從本地或者全局的運行隊列中獲取待執行的 Goroutine；

3. 調用 runtime.execute:779c45a 在當前線程 M 上運行 Goroutine；

當前處理器本地的運行隊列中不包含 Goroutine 時，調用 runtime.findrunnable:779c45a 會觸發工作竊取，從其它的處理器的隊列中隨機獲取一些 Goroutine。

運行時 G-M-P 模型中引入的處理器 P 是線程和 Goroutine 的中間層，我們從它的結構體中就能看到處理器與 M 和 G 的關係：

struct P {
 Lock;

 uint32 status;
 P* link;
 uint32 tick;
 M* m;
 MCache* mcache;

 G** runq;
 int32 runqhead;
 int32 runqtail;
 int32 runqsize;

 G* gfree;
 int32 gfreecnt;
};

處理器持有一個由可運行的 Goroutine 組成的環形的運行隊列 runq，還反向持有一個線程。調度器在調度時會從處理器的隊列中選擇隊列頭的 Goroutine 放到線程 M 上執行。

基於工作竊取的多線程調度器將每一個線程綁定到了獨立的 CPU 上，這些線程會被不同處理器管理，不同的處理器通過工作竊取對任務進行再分配實現任務的平衡，也能提升調度器和 Go 語言程序的整體性能，今天所有的 Go 語言服務都受益於這一改動。

搶佔式調度器

對 Go 語言併發模型的修改提升了調度器的性能，但是 1.1 版本中的調度器仍然不支持搶佔式調度，程序只能依靠 Goroutine 主動讓出 CPU 資源才能觸發調度。Go 語言的調度器在 1.2 版本中引入基於協作的搶佔式調度解決下面的問題：

• 某些 Goroutine 可以長時間佔用線程，造成其它 Goroutine 的飢餓；

• 垃圾回收需要暫停整個程序（Stop-the-world，STW），最長可能需要幾分鐘的時間，導致整個程序無法工作；

1.2 版本的搶佔式調度雖然能夠緩解這個問題，但是它實現的搶佔式調度是基於協作的，在之後很長的一段時間裏 Go 語言的調度器都有一些無法被搶佔的邊緣情況，例如：for 循環或者垃圾回收長時間佔用線程，這些問題中的一部分直到 1.14 才被基於信號的搶佔式調度解決。

基於協作的搶佔式調度

我們可以在 pkg/runtime/proc.c 文件中找到引入基於協作的搶佔式調度後的調度器。Go 語言會在分段棧的機制上實現搶佔調度，利用編譯器在分段棧上插入的函數，所有 Goroutine 在函數調用時都有機會進入運行時檢查是否需要執行搶佔。Go 團隊通過以下的多個提交實現該特性：

• runtime: add stackguard0 to G

• 爲 Goroutine 引入 stackguard0 字段，該字段被設置成 StackPreempt 意味着當前 Goroutine 發出了搶佔請求；

• runtime: introduce preemption function (not used for now)

• 引入搶佔函數 runtime.preemptone:1e112cd 和 runtime.preemptall:1e112cd，這兩個函數會改變 Goroutine 的 stackguard0 字段發出搶佔請求；

• 定義搶佔請求 StackPreempt；

• runtime: preempt goroutines for GC

• 在 runtime.stoptheworld:1e112cd 中調用 runtime.preemptall:1e112cd 設置所有處理器上正在運行的 Goroutine 的 stackguard0 爲 StackPreempt；

• 在 runtime.newstack:1e112cd 中增加搶佔的代碼，當 stackguard0 等於 StackPreempt 時觸發調度器搶佔讓出線程；

• runtime: preempt long-running goroutines

• 在系統監控中，如果一個 Goroutine 的運行時間超過 10ms，就會調用 runtime.retake:1e112cd 和 runtime.preemptone:1e112cd；

• runtime: more reliable preemption

• 修復 Goroutine 因爲週期性執行非阻塞的 CGO 或者系統調用不會被搶佔的問題；

上面的多個提交實現了搶佔式調度，但是還缺少最關鍵的一個環節 — 編譯器如何在函數調用前插入函數，我們能在非常古老的提交 runtime: stack growth adjustments, cleanup 中找到編譯器插入函數的雛形，最新版本的 Go 語言會通過 cmd/internal/obj/x86.stacksplit 插入 runtime.morestack，該函數可能會調用 runtime.newstack 觸發搶佔。從上面的多個提交中，我們能歸納出基於協作的搶佔式調度的工作原理：

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

2. Go 語言運行時會在垃圾回收暫停程序、系統監控發現 Goroutine 運行超過 10ms 時發出搶佔請求 StackPreempt；

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

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

這種實現方式雖然增加了運行時的複雜度，但是實現相對簡單，也沒有帶來過多的額外開銷，總體來看還是比較成功的實現，也在 Go 語言中使用了 10 幾個版本。因爲這裏的搶佔是通過編譯器插入函數實現的，還是需要函數調用作爲入口才能觸發搶佔，所以這是一種協作式的搶佔式調度。

基於信號的搶佔式調度

基於協作的搶佔式調度雖然實現巧妙，但是並不完備，我們能在 runtime: non-cooperative goroutine preemption 中找到一些遺留問題：

• runtime: tight loops should be preemptible

• An empty for{} will block large slice allocation in another goroutine, even with GOMAXPROCS> 1 ?

• runtime: tight loop hangs process completely after some time

• …

Go 語言在 1.14 版本中實現了非協作的搶佔式調度，在實現的過程中我們重構已有的邏輯併爲 Goroutine 增加新的狀態和字段來支持搶佔。Go 團隊通過下面的一系列提交實現了這一功能，我們可以按時間順序分析相關提交理解它的工作原理：

• runtime: add general suspendG/resumeG

• 掛起 Goroutine 的過程是在垃圾回收的棧掃描時完成的，我們通過 runtime.suspendG 和 runtime.resumeG 兩個函數重構棧掃描這一過程；

• 調用 runtime.suspendG 時會將處於運行狀態的 Goroutine 的 preemptStop 標記成 true；

• 調用 runtime.preemptPark 可以掛起當前 Goroutine、將其狀態更新成 _Gpreempted 並觸發調度器的重新調度，該函數能夠交出線程控制權；

• runtime: asynchronous preemption function for x86

• 在 x86 架構上增加異步搶佔的函數 runtime.asyncPreempt 和 runtime.asyncPreempt2；

• runtime: use signals to preempt Gs for suspendG

• 支持通過向線程發送信號的方式暫停運行的 Goroutine；

• 在 runtime.sighandler 函數中註冊 SIGURG 信號的處理函數 runtime.doSigPreempt；

• 實現 runtime.preemptM，它可以通過 SIGURG 信號向線程發送搶佔請求；

• runtime: implement async scheduler preemption

• 修改 runtime.preemptone 函數的實現，加入異步搶佔的邏輯；

目前的搶佔式調度也只會在垃圾回收掃描任務時觸發，我們可以梳理一下上述代碼實現的搶佔式調度過程：

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

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

3. 將 _Grunning 狀態的 Goroutine 標記成可以被搶佔，即將 preemptStop 設置成 true；

4. 調用 runtime.preemptM 觸發搶佔；

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

6. 操作系統會中斷正在運行的線程並執行預先註冊的信號處理函數 runtime.doSigPreempt；

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

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

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

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

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

上述 9 個步驟展示了基於信號的搶佔式調度的執行過程。除了分析搶佔的過程之外，我們還需要討論一下搶佔信號的選擇，提案根據以下的四個原因選擇 SIGURG 作爲觸發異步搶佔的信號；

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

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

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

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

STW 和棧掃描是一個可以搶佔的安全點（Safe-points），所以 Go 語言會在這裏先加入搶佔功能。基於信號的搶佔式調度只解決了垃圾回收和棧掃描時存在的問題，它到目前爲止沒有解決所有問題，但是這種真搶佔式調度是調度器走向完備的開始，相信在未來我們會在更多的地方觸發搶佔。

非均勻內存訪問調度器

非均勻內存訪問（Non-uniform memory access，NUMA）調度器現在只是 Go 語言的提案。該提案的原理就是通過拆分全局資源，讓各個處理器能夠就近獲取，減少鎖競爭並增加數據的局部性。

在目前的運行時中，線程、處理器、網絡輪詢器、運行隊列、全局內存分配器狀態、內存分配緩存和垃圾收集器都是全局資源。運行時沒有保證本地化，也不清楚系統的拓撲結構，部分結構可以提供一定的局部性，但是從全局來看沒有這種保證。

如上圖所示，堆棧、全局運行隊列和線程池會按照 NUMA 節點進行分區，網絡輪詢器和計時器會由單獨的處理器持有。這種方式雖然能夠利用局部性提高調度器的性能，但是本身的實現過於複雜，所以 Go 語言團隊還沒有着手實現這一提案。

小結

Go 語言的調度器在最初的幾個版本中迅速迭代，但是從 1.2 版本之後調度器就沒有太多的變化，直到 1.14 版本引入了真正的搶佔式調度才解決了自 1.2 以來一直存在的問題。在可預見的未來，Go 語言的調度器還會進一步演進，增加觸發搶佔式調度的時間點以減少存在的邊緣情況。

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