[toc]

原文:Scheduling In Go : Part II - Go Scheduler

前言

這是本系列的第二篇文章爆雹，本文重點介紹Go中的調(diào)度機制

簡介

在本系列的第一篇文章中，主要介紹了操作系統(tǒng)的系統(tǒng)調(diào)度的部分內(nèi)容，我認為那部分內(nèi)容對于理解Go調(diào)度器的語義非常重要释漆。在本篇文章中，我會從語義層面解釋Go調(diào)度器是如何工作的剪决，并重點介紹它的高級特性灵汪。Go調(diào)度器是個非常復雜的系統(tǒng)檀训，可以不用過分關(guān)注小的細節(jié)，重要的是有一個好的調(diào)度器如何工作以及如何表現(xiàn)的概念享言，這有助于你在工程化開發(fā)過程中進行更好的決策峻凫。

你的程序啟動

當你的Go程序啟動時，它會為主機上每個有標識的虛擬內(nèi)核分配一個邏輯處理器（P）览露，如果你的處理器運行在一個可以執(zhí)行多硬件線程的物理內(nèi)核上（超線程）荧琼，那么每個硬件線程會變?yōu)樘摂M內(nèi)核供你的Go程序使用。為了更好的理解這點差牛，請看下一我的MacBook Pro的系統(tǒng)報告命锄。

圖1

94_figure1.png

你可以看見，我有一個四核的處理器偏化，報告中無法體現(xiàn)每個核的硬件線程數(shù)脐恩。英特爾酷睿i7處理器具有超線程功能，因此每個核擁有2個硬件線程侦讨，對于Go程序而言驶冒，意味著有8個虛擬核心可以并行執(zhí)行OS線程。

為了測試這點韵卤，參考下面這段代碼

代碼1

package main

import (
    "fmt"
    "runtime"
)

func main() {

    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    fmt.Println(runtime.NumCPU())
}

在我的本地運行這段代碼骗污，運行結(jié)果輸出的是8沈条，也就是說任何在我這臺機器上運行的Go程序都會分配8個P。

每個P會被分配一個OS線程（M）屋厘，這個‘M’代表的是機器（machine）。這個線程依然由操作系統(tǒng)進行管理擅这，也會如上一篇文章所述景鼠，操作系統(tǒng)會負責將線程放到核心上執(zhí)行。這意味著當我的機器運行Go程序的時候痹扇，我有8個線程可以工作，每個線程會分配一個獨立的P鲫构。

在Go程序的運行過程中结笨，每個Go程序會初始化一個Goroutine(G)湿镀，Goroutine本質(zhì)上是協(xié)程（Coroutine）伐憾，因為我們用的是Go語言树肃，所以把字母C替換成了G胸嘴，于是得到了一個詞Goroutine。你可以把Goroutine理解為應用程序級別的線程乡话，它和OS線程有很多相似之處耳奕。正如OS線程在內(nèi)核上進行上線文切換一樣吮铭，Goroutines在M上進行上下文切換。

最后一個難題是運行隊列(run queue)谓晌。在Go的調(diào)度器中有兩種運行隊列：全局運行隊列（GRQ）和本地運行隊列（LRQ）纸肉。每個P都有一個LRQ，用于管理分配在這個P上的上下文中執(zhí)行的Goroutine姐刁。這些Goroutine輪流在這個P分配的M上進行上下文切換聂使。GRQ用來管理尚未分配給P的Goroutine谬俄，有一個過程是把GRQ上的goroutine移動到LRQ上溃论，這個我們稍后討論钥勋。

圖二描述了全部上面提到的組件辆苔。

圖二

94_figure2.png

協(xié)同調(diào)度

在第一篇文章中我們討論過驻啤，操作系統(tǒng)調(diào)度是一個搶占式調(diào)度街佑，本質(zhì)上你無法預測調(diào)度程序在什么時間執(zhí)行了什么操作沐旨，內(nèi)核做決策的時候一切都是不可控的榨婆，運行在操作系統(tǒng)上的應用程序無法控制內(nèi)核中發(fā)生的事情良风，除非使用了比如“atomic”和“mutex”這類同步原語烟央。

Go調(diào)度器是Go程序運行的一部分，并內(nèi)置在你的應用程序中粮呢，這就說明Go調(diào)度器是運行在內(nèi)核之上的用戶空間啄寡。Go調(diào)度器的當前實現(xiàn)不是搶占式哩照，而是協(xié)同調(diào)度飘弧，也就意味著次伶，調(diào)度程序需要在代碼中明確定義用戶空間事件，并在安全的地方進行調(diào)度決策。

這種設計的亮點在于看起來調(diào)度器是搶占式的版确，你無法預測Go調(diào)度器要做什么绒疗，因為這個調(diào)度決策是并不是由開發(fā)者決定的，而是在Go運行過程中進行的惕虑。因此以搶占式調(diào)度器的方式去思考就變的很重要溃蔫，因為它具有不確定性琳猫，這不是一件容易的事脐嫂。

Goroutine的狀態(tài)

與線程一樣账千，Goroutine也擁有三個狀態(tài)，可以是三種狀態(tài)中的一種：Waiting,Runnable或者Executing

Waiting:這個狀態(tài)表示Goroutine目前已經(jīng)停止并等待一些東西再繼續(xù)運行鞭衩。這可能是在等待系統(tǒng)的操作（系統(tǒng)調(diào)用）或同步調(diào)用（原子操作和互斥操作）等醋旦。這些類型的延遲是性能不佳的根本原因饲齐。

Runnable:這個狀態(tài)表示咧最，Goroutine需要在M上的時間片來運行指令矢沿，如果同時有很多Goroutine需要時間片捣鲸，那么這個等待時間就會變長栽惶，同樣的疾嗅，每個Goroutine獲取的每個時間片就更短代承。這種類型的延遲也是性能不佳的原因论悴。

Executing:這個狀態(tài)表示墓律，Goroutine已被置于M并正在執(zhí)行其指令只锻，與應用程序相關(guān)的工作即將完齐饮，這是每個人都期望的結(jié)果。

上下文切換

Go調(diào)度器需要明確定義的用戶空間事件握恳，并在代碼中的安全點進行上下文切換乡洼，這些事件和安全點在方法調(diào)用中體現(xiàn)束昵。函數(shù)調(diào)用對Go調(diào)度器的運行狀況至關(guān)重要锹雏。今天（使用Go 1.11或更低版本）术奖，如果你運行一段沒有任何方法調(diào)用的tight loop采记，那么將會因為調(diào)度器和垃圾回收器而出現(xiàn)延遲唧龄，函數(shù)調(diào)用在合理的時間范圍內(nèi)發(fā)生是至關(guān)重要的。

注意：在Go的1.12版本有一項提議被采納掖鱼，Go的調(diào)度器允許在執(zhí)行tight loop時應用非協(xié)作搶占的技術(shù)戏挡。

Go程序中有四類事件可能觸發(fā)調(diào)度決策褐墅。

• 使用關(guān)鍵字go
• 垃圾回收
• 系統(tǒng)調(diào)用
• 同步和編排治理

使用關(guān)鍵詞go

關(guān)鍵字go是你創(chuàng)建Goroutine的方式妥凳。一旦創(chuàng)建了新的Goroutine逝钥，調(diào)度器就有可能進行一次調(diào)度決策拱镐。

垃圾回收

由于GC在運行過程中會使用自己的Goroutine沃琅，這些Goroutine都需要M上的時間片益眉，因此這會導致GC產(chǎn)生大量的調(diào)度混亂郭脂。但是調(diào)度器非常了解Goroutine在做什么，會作出明智的調(diào)度決策屿衅，其中一項是決策是砸泛，當一個Goroutine要接觸一個沒有被使用的堆時拴竹，會對它進行一次上下文切換（PS：原文是“One smart decision is context-switching a Goroutine that wants to touch the heap with those that don’t touch the heap during GC”栓拜，不知道這么理解對不對）幕与。當GC運行時，會有許多決策潮饱。

系統(tǒng)調(diào)用

Goroutine進行系統(tǒng)調(diào)用會導致Goroutine阻塞M香拉，有時調(diào)度器會進行上線文切換凫碌，將這個Goroutine換下盛险，并將一個新的Goroutine換到這個M上苦掘。然而有的時候赐写，需要新的M來繼續(xù)執(zhí)行在P中排隊的Goroutine挺邀，這是如何工作的的將在下一章詳細解釋端铛。

同步和編排治理

如果調(diào)用了原子操作禾蚕，互斥或者通道换淆，會導致Goroutine阻塞倍试，調(diào)度器會上線文切換一個新的Goroutine運行县习，一旦這個Goroutine可以再次運行了谆趾，它會重新排隊并最終通過上下文切換回到M上沪蓬。

異步系統(tǒng)調(diào)用

當你運行的操作系統(tǒng)能夠異步執(zhí)行系統(tǒng)調(diào)用的時候跷叉，可以使用稱為網(wǎng)絡輪詢器("network poller")""的東西來更有效地處理系統(tǒng)調(diào)用性芬。這是通過在這些相應的OS中使用kqueue（MacOS），epoll（Linux）或iocp（Windows）來實現(xiàn)的峭拘。

基于網(wǎng)絡的系統(tǒng)調(diào)用可以使用操作系統(tǒng)的異步處理鸡挠，今天我們使用的很多操作系統(tǒng)都可以實現(xiàn)拣展。network poller這個名字的由來正是因為它主要用來處理網(wǎng)絡請求备埃。通過使用network poller來進行網(wǎng)絡系統(tǒng)調(diào)用按脚，調(diào)度器就可以防止Goroutine在進行系統(tǒng)調(diào)用時阻塞M敦冬。這有助于保持M執(zhí)行P的LRQ中的Goroutine時可用脖旱，且無需創(chuàng)建新的M萌庆，這也有助于減少OS上的調(diào)度負載踊兜。

查看其工作原理的最佳方法是運行示例。

圖3

94_figure3.png

圖3顯示了基本調(diào)度圖毁葱。Goroutine-1正在M上執(zhí)行倾剿，還有3個Goroutine在LRQ上等待獲取M時間片前痘。網(wǎng)絡輪詢器此時空閑芹缔。

圖4

94_figure4.png

在圖4中最欠，Goroutine-1想要進行網(wǎng)絡系統(tǒng)調(diào)用芝硬，因此Goroutine-1被移動到網(wǎng)絡輪詢器并且發(fā)起異步網(wǎng)絡系統(tǒng)調(diào)用拌阴。一旦Goroutine-1移動到網(wǎng)絡輪詢器迟赃，M現(xiàn)在可以執(zhí)行LRQ上的其他Goroutine捺氢。在這種情況下摄乒，Goroutine-2被上下文切換到了M上馍佑。

圖5

94_figure5.png

在圖5中拭荤，異步網(wǎng)絡系統(tǒng)調(diào)用由網(wǎng)絡輪詢器完成舅世，并且Goroutine-1被移回到P的LRQ中雏亚。一旦Goroutine-1可以上下文切換回M罢低，這段Go負責的相關(guān)代碼可以再次執(zhí)行网持。這里最大的優(yōu)點是功舀，要執(zhí)行網(wǎng)絡系統(tǒng)調(diào)用不需要額外的M辟汰。網(wǎng)絡輪詢器具有OS線程莉擒，它一直在處理有效的事件循環(huán)涨冀。

同步系統(tǒng)調(diào)用

當Goroutine想要進行無法異步完成的系統(tǒng)調(diào)用時會發(fā)生什么鹿鳖？在這種情況下翅帜，網(wǎng)絡輪詢器不能被使用涝滴，并且進行系統(tǒng)調(diào)用的Goroutine將阻塞M.很不幸歼疮，我們沒有辦法防止這種情況發(fā)生韩脏。不能異步進行的系統(tǒng)調(diào)用的一個示例是基于文件的系統(tǒng)調(diào)用赡矢。如果你正在使用CGO吹散，調(diào)用C函數(shù)時也可能會有其他情況阻塞M.

注意：Windows操作系統(tǒng)確實能夠進行基于文件的異步系統(tǒng)調(diào)用送浊。從技術(shù)上講袭景，在Windows上運行時耸棒，可以使用網(wǎng)絡輪詢器与殃。

讓我們來看看將導致M阻塞的同步系統(tǒng)調(diào)用（如文件I / O）所發(fā)生的情況幅疼。

圖6

94_figure6.png

圖6再次展示了我們的基本調(diào)度圖爽篷，但是這次Goroutine-1將進行同步系統(tǒng)調(diào)用阻塞M1悴晰。

圖7

94_figure7.png

在圖7中，調(diào)度程序能夠識別Goroutine-1已導致M阻塞逐工。此時铡溪，調(diào)度器將M1與P分離，同時附加仍然阻塞的Goroutine-1泪喊。然后調(diào)度器引入新的M2來為P提供服務棕硫。此時，可以從LRQ中選擇Goroutine-2并且在M2上進行上下文切換哈扮。如果由于之前的交換而已經(jīng)存在M，那么此次轉(zhuǎn)換會比新建一個M要快瘤泪。

圖8

94_figure8.png

在圖8中灶泵，由Goroutine-1產(chǎn)生的阻塞系統(tǒng)調(diào)用完成。此時对途，Goroutine-1移回LRQ并再次由P服務赦邻。M1會放在側(cè)面以備將來再次使用。

工作竊取

調(diào)度器的另一面是一個竊取工作的調(diào)度程序实檀。這有助于在一些領域保持有效的調(diào)度惶洲。首先按声，你期望的最后一件事就是M進入等待狀態(tài)，因為一旦發(fā)生這種情況恬吕，操作系統(tǒng)就會將M從核心通過上下文切換取下签则。這意味著P無法完成任何工作，即使Goroutine處于可運行狀態(tài)铐料，直到M重新進行上下文切換回核心渐裂。竊取工作也有助于平衡所有P的Goroutine，從而更好地分配工作并更有效地完成工作钠惩。

讓我們來看一個例子柒凉。

圖9

94_figure9.png

在圖9中，我們有一個多線程Go程序篓跛，其中有兩個P膝捞，每個服務于四個Goroutine，GRQ中有一個Goroutine愧沟。如果一個P的所有Goroutine很快執(zhí)行完畢會發(fā)生什么蔬咬？

圖10

94_figure10.png

在圖10中，P1沒有更多的Goroutine來執(zhí)行沐寺。但是Goroutine處于可運行狀態(tài)林艘，無論是在LRQ中還是在GRQ中。這時需要P1開始竊取工作混坞。竊取工作的規(guī)則如下北启。

代碼2

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.
}

因此，基于清單2中的這些規(guī)則拔第，P1需要檢測在P2的LRQ上的 Goroutine并獲取它找到的一半。

圖11

94_figure11.png

在圖11中场钉，Goroutine的一半來自P2蚊俺，現(xiàn)在P1可以執(zhí)行那些Goroutine。
如果P2完成為其所有Goroutine并且P1的LRQ中沒有任何東西會發(fā)生什么逛万？

圖12

94_figure12.png

在圖12中泳猬，P2完成了所有工作，現(xiàn)在需要竊取一些宇植。首先得封，它將查看P1的LRQ，但它找不到任何Goroutine指郁。接下來忙上，它將查看GRQ。在那里它會找到Goroutine-9闲坎。

圖13

94_figure13.png

在圖13中疫粥，P2從GRQ竊取了Goroutine-9并開始執(zhí)行工作茬斧。所有這些偷竊工作的好處在于它允許M保持忙碌而不會空閑。這項工作竊取在內(nèi)部被視為旋轉(zhuǎn)操作梗逮。這種自旋還有其他好處项秉，在JBD（一個女工程師）的一篇博客work-stealing里有很好的解釋

實例

有了相應的機制和語義，我們來看看如何將所有這些結(jié)合在一起慷彤，以便Go調(diào)度器能夠執(zhí)行更多的工作娄蔼。想象一下用C編寫的多線程應用程序，其中程序管理兩個OS線程底哗，它們相互傳遞消息岁诉。

圖14

94_figure14.png

在圖14中，有2個線程來回傳遞消息艘虎。線程1在Core1上進行上下文切換唉侄，線程1將其消息發(fā)送到線程2。

注意：消息的傳遞方式并不重要野建。重要的是運行過程中線程的狀態(tài)属划。

圖15

94_figure15.png

在圖15中，一旦線程1完成發(fā)送消息候生，它現(xiàn)在需要等待響應同眯。這將導致線程1在Core 1上進行上下文切換進入等待狀態(tài)。一旦線程2收到有關(guān)該消息的通知唯鸭，它就會進入可運行狀態(tài)⌒胛希現(xiàn)在操作系統(tǒng)可以執(zhí)行上下文切換并在Core上執(zhí)行線程2，接下來目溉，線程2處理消息并將新消息發(fā)送回線程1明肮。

圖16

94_figure16.png

在圖16中，T2的消息被T1接受缭付，再次進行上線文切換∈凉溃現(xiàn)在T2從執(zhí)行狀態(tài)切換到等待狀態(tài)和T1從等待狀態(tài)切換到可運行狀態(tài)最后回到執(zhí)行狀態(tài)，允許它處理并發(fā)回新消息陷猫。

所有這些上下文切換和狀態(tài)更改都需要時間來執(zhí)行秫舌，這限制了工作的完成速度。由于每個上下文切換可能會產(chǎn)生50納秒的延遲绣檬，并且理論上硬件每納秒執(zhí)行12條指令足陨，因此大約會有600條指令在此期間沒有執(zhí)行。由于這些線程也在不同的內(nèi)核之間切換娇未，因緩存未命中引起額外延遲的可能性也很高墨缘。

相同的例子，這次使用Goroutine和Go調(diào)度器。

圖17

94_figure17.png

在圖17中飒房，有兩個Goroutine正在相互協(xié)調(diào)搁凸，來回傳遞消息。G1在M1上進行上下文切換狠毯，M1在Core 1上運行护糖，因此G1可以執(zhí)行操作將消息發(fā)送給G2。

圖18

94_figure18.png

在圖18中嚼松，一旦G1完成發(fā)送消息嫡良，它需要等待回復，這讓G1在M1上進行上下文切換進入等待狀態(tài)献酗。一旦G2收到這個消息寝受，它將進入可執(zhí)行狀態(tài)，現(xiàn)在Go調(diào)度器可以進行上線文切換罕偎，將G2切換到M1上執(zhí)行很澄，此時仍然在core 1上運行。接下來颜及，G2處理消息并將消息發(fā)送回G1甩苛。

圖19

94_figure19.png

在圖19中，當G2接收到由G2發(fā)送的消息時俏站，再次進行上下文切換⊙镀眩現(xiàn)在G2從執(zhí)行狀態(tài)切換到等待狀態(tài)，G1從等待狀態(tài)切換到可運行狀態(tài)肄扎，最后返回到執(zhí)行狀態(tài)墨林，并它處理并發(fā)回的消息。

表面上的似乎沒有什么不同犯祠。無論使用Threads還是Goroutines旭等，都會發(fā)生相同的上下文切換和狀態(tài)更改。但是衡载，使用Threads和Goroutines之間存在一個主要區(qū)別辆雾，乍一看可能并不明顯。

在使用Goroutines的情況下月劈，全程使用相同的OS線程和核心。這意味著藤乙，從操作系統(tǒng)的角度來看猜揪，操作系統(tǒng)線程永遠不會進入等待狀態(tài);我們使用Threads時因為上下文切換造成的指令損失，在使用Goroutine時不會丟失坛梁。

從本質(zhì)上講而姐，Go已將IO / Blocking工作轉(zhuǎn)變?yōu)椴僮飨到y(tǒng)級別的CPU-bound工作。由于所有上下文切換都是在應用程序級別進行的划咐，因此在使用Threads時拴念，每個上下文切換都不會丟失600條指令（平均）钧萍。調(diào)度器還有助于提高緩存行效率和NUMA。這就是為什么我們不需要比虛擬內(nèi)核更多的線程政鼠。在Go中风瘦，隨著時間的推移，可以完成更多的工作公般，因為Go調(diào)度程序嘗試使用更少的線程并在每個線程上執(zhí)行更多操作万搔，這有助于減少操作系統(tǒng)和硬件的負載。

結(jié)論

Go調(diào)度器在設計方面充分考慮到了操作系統(tǒng)與硬件工作的復雜性官帘，這方面確實令人驚訝瞬雹。在操作系統(tǒng)級別，將IO/Blocking工作轉(zhuǎn)換為CPU-bound工作刽虹，這一點在充分利用CPU方面取得了巨大的成功酗捌，這也是為什么你不需要更多的虛擬內(nèi)核，你可以合理的認為每個虛擬內(nèi)核上只需要一個操作系統(tǒng)線程涌哲，就可以完成所有工作胖缤。這樣對于網(wǎng)絡應用程序和其他應用程序可以不必對OS線程造成阻塞。

作為開發(fā)人員膛虫，你仍然需要了解你的應用程序正在處理的工作類型已經(jīng)正在做什么草姻，你不能無限的創(chuàng)建Goroutine并期望依然擁有驚人的性能。少即是多稍刀，但是通過理解這些Go-scheduler語義撩独，您可以做出更好的工程決策。在下一篇文章中账月，我將探討以保守方式利用并發(fā)性以獲得更好性能的想法综膀，同時平衡可能需要添加到代碼中的復雜因素。