概述

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

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

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

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

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

設計原理

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

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

• 改進：只包含 40 多行代碼；
• 缺陷：程序中只能存在一個活躍線程，由 G-M 模型組成；

2.多線程調度器 — Go 1.0

• 改進：允許運行多線程的程序；
• 缺陷：全局鎖導致競爭嚴重；

3.任務竊取調度器 — Go 1.1

• 改進1：引入了處理器 P，構成了目前的 G-M-P 模型；
• 改進2：在處理器 P 的基礎上實現了基于工作竊取的調度器；
• 缺陷1：在某些情況下，Goroutine 不會讓出線程，進而造成饑餓問題；
• 缺陷2：時間過長的垃圾回收（Stop-the-world，STW）會導致程序長時間無法工作；

4..搶占式調度器 — Go 1.2 ~ 至今

基于協作的搶占式調度器 - 1.2 ~ 1.13

• 改進：通過編譯器在函數調用時插入搶占檢查指令，在函數調用時檢查當前 Goroutine 是否發(fā)起了搶占請求，實現基于協作的搶占式調度；
• 缺陷：Goroutine 可能會因為垃圾回收和循環(huán)長時間占用資源導致程序暫停；

基于信號的搶占式調度器 - 1.14 ~ 至今

• 改進：實現基于信號的真搶占式調度；
• 缺陷1：垃圾回收在掃描棧時會觸發(fā)搶占調度；
• 缺陷2：搶占的時間點不夠多，還不能覆蓋全部的邊緣情況；

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

• 改進：對運行時的各種資源進行分區(qū)；
• 缺陷：實現非常復雜，到今天還沒有提上日程；

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

單線程調度器

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：

• 獲取調度器的全局鎖；
• 調用 runtime.gosave:9682400 保存棧寄存器和程序計數器；
• 調用 runtime.nextgandunlock:9682400 獲取下一個需要運行的 Goroutine 并解鎖調度器；
• 修改全局線程 m 上要執(zhí)行的 Goroutine；
• 調用 runtime.gogo:9682400 函數運行最新的 Goroutine；

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

多線程調度器

Go 語言在 1.0 版本正式發(fā)布時就支持了多線程的調度器，與上一個版本幾乎不可用的調度器相比，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);
}

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

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

• 調度器和鎖是全局資源，所有的調度狀態(tài)都是中心化存儲的，鎖競爭問題嚴重；
• 線程需要經?；ハ鄠鬟f可運行的 Goroutine，引入了大量的延遲；
• 每個線程都需要處理內存緩存，導致大量的內存占用并影響數據局部性；
• 系統調用頻繁阻塞和解除阻塞正在運行的線程，增加了額外開銷；

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

任務竊取調度器

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

• 在當前的 G-M 模型中引入了處理器 P，增加中間層；
• 在處理器 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);
}

• 如果當前運行時在等待垃圾回收，調用 runtime.gcstopm:779c45a 函數；
• 調用 runtime.runqget:779c45a 和 runtime.findrunnable:779c45a 從本地或者全局的運行隊列中獲取待執(zhí)行的 Goroutine；
• 調用 runtime.execute:779c45a 在當前線程 M 上運行 Goroutine；

當前處理器本地的運行隊列中不包含 Goroutine 時，調用 runtime.findrunnable:779c45a 會觸發(fā)工作竊取，從其它的處理器的隊列中隨機獲取一些 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 組成的環(huán)形的運行隊列 runq，還反向持有一個線程。調度器在調度時會從處理器的隊列中選擇隊列頭的 Goroutine 放到線程 M 上執(zhí)行。

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

搶占式調度器

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

• 某些 Goroutine 可以長時間占用線程，造成其它 Goroutine 的饑餓；
• 垃圾回收需要暫停整個程序（Stop-the-world，STW），最長可能需要幾分鐘的時間，導致整個程序無法工作；

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

基于協作的搶占式調度

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

runtime: add stackguard0 to G

為 Goroutine 引入 stackguard0 字段，該字段被設置成 StackPreempt 意味著當前 Goroutine 發(fā)出了搶占請求；

runtime: introduce preemption function (not used for now)

• 引入搶占函數 runtime.preemptone:1e112cd 和 runtime.preemptall:1e112cd，這兩個函數會改變 Goroutine 的 stackguard0 字段發(fā)出搶占請求；
• 定義搶占請求 StackPreempt；

runtime: preempt goroutines for GC

• 在 runtime.stoptheworld:1e112cd 中調用 runtime.preemptall:1e112cd 設置所有處理器上正在運行的 Goroutine 的 stackguard0 為 StackPreempt；
• 在 runtime.newstack:1e112cd 中增加搶占的代碼，當 stackguard0 等于 StackPreempt 時觸發(fā)調度器搶占讓出線程；

runtime: preempt long-running goroutines

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

runtime: more reliable preemption

修復 Goroutine 因為周期性執(zhí)行非阻塞的 CGO 或者系統調用不會被搶占的問題；

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

• 編譯器會在調用函數前插入 runtime.morestack；
• Go 語言運行時會在垃圾回收暫停程序、系統監(jiān)控發(fā)現 Goroutine 運行超過 10ms 時發(fā)出搶占請求 StackPreempt；
• 當發(fā)生函數調用時，可能會執(zhí)行編譯器插入的 runtime.morestack，它調用的 runtime.newstack 會檢查 Goroutine 的 stackguard0 字段是否為 StackPreempt；
• 如果 stackguard0 是 StackPreempt，就會觸發(fā)搶占讓出當前線程；

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

基于信號的搶占式調度

基于協作的搶占式調度雖然實現巧妙，但是并不完備，我們能在 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 增加新的狀態(tài)和字段來支持搶占。Go 團隊通過下面的一系列提交實現了這一功能，我們可以按時間順序分析相關提交理解它的工作原理：

runtime: add general suspendG/resumeG

• 掛起 Goroutine 的過程是在垃圾回收的棧掃描時完成的，我們通過 runtime.suspendG 和 runtime.resumeG 兩個函數重構棧掃描這一過程；
• 調用 runtime.suspendG 時會將處于運行狀態(tài)的 Goroutine 的 preemptStop 標記成 true；
• 調用 runtime.preemptPark 可以掛起當前 Goroutine、將其狀態(tài)更新成 _Gpreempted 并觸發(fā)調度器的重新調度，該函數能夠交出線程控制權；

runtime: asynchronous preemption function for x86

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

runtime: use signals to preempt Gs for suspendG

• 支持通過向線程發(fā)送信號的方式暫停運行的 Goroutine；
• 在 runtime.sighandler 函數中注冊 SIGURG 信號的處理函數 runtime.doSigPreempt；
• 實現 runtime.preemptM，它可以通過 SIGURG 信號向線程發(fā)送搶占請求；

runtime: implement async scheduler preemption

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

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

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

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

將 _Grunning 狀態(tài)的 Goroutine 標記成可以被搶占，即將 preemptStop 設置成 true；

調用 runtime.preemptM 觸發(fā)搶占；

3.runtime.preemptM會調用 runtime.signalM 向線程發(fā)送信號 SIGURG；

4.操作系統會中斷正在運行的線程并執(zhí)行預先注冊的信號處理函數 runtime.doSigPreempt；

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

6.runtime.sigctxt.pushCall 會修改寄存器并在程序回到用戶態(tài)時執(zhí)行 runtime.asyncPreempt；

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

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

9.runtime.preemptPark 會修改當前 Goroutine 的狀態(tài)到 _Gpreempted 并調用 runtime.schedule 讓當前函數陷入休眠并讓出線程，調度器會選擇其它的 Goroutine 繼續(xù)執(zhí)行；

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

• 該信號需要被調試器透傳；
• 該信號不會被內部的 libc 庫使用并攔截；
• 該信號可以隨意出現并且不觸發(fā)任何后果；
• 我們需要處理多個平臺上的不同信號；

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

非均勻內存訪問調度器

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

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

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

小結

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

以上就是詳解Go語言中調度器的原理與使用的詳細內容，更多關于Go語言調度器的資料請關注腳本之家其它相關文章！