Go語言 設(shè)計(jì)與演化

線程池

先看一些簡單點(diǎn)的吧。一個(gè)常規(guī)的 線程池+任務(wù)隊(duì)列 的模型如圖所示：

把每個(gè)工作線程叫worker的話，每條線程運(yùn)行一個(gè)worker，每個(gè)worker做的事情就是不停地從隊(duì)列中取出任務(wù)并執(zhí)行：

while(!empty(queue)) {
    q = get(queue); //從任務(wù)隊(duì)列中取一個(gè)(涉及加鎖等)
    q->callback(); //執(zhí)行該任務(wù)
}

當(dāng)然，這是最簡單的情形，但是一個(gè)很明顯的問題就是一個(gè)進(jìn)入callback之后，就失去了控制權(quán)。因?yàn)闆]有一個(gè)調(diào)度器層的東西，一個(gè)任務(wù)可以執(zhí)行很長很長時(shí)間一直占用的worker線程，或者阻塞于io之類的。

也許用Go語言表述會(huì)更地道一些。好吧，那么讓我們用Go語言來描述。假設(shè)我們有一些“任務(wù)”，任務(wù)是一個(gè)可運(yùn)行的東西，也就是只要滿足Run函數(shù)，它就是一個(gè)任務(wù)。所以我們就把這個(gè)任務(wù)叫作接口G吧。

type G interface {
    Run() 
}

我們有一個(gè)全局的任務(wù)隊(duì)列，里面包含很多可運(yùn)行的任務(wù)。線程池的各個(gè)線程從全局的任務(wù)隊(duì)列中取任務(wù)時(shí)，顯然是需要并發(fā)保護(hù)的，所以有下面這個(gè)結(jié)構(gòu)體：

type Sched struct {
    allg  []G
    lock    *sync.Mutex
}

以及它的變量

var sched Sched

每條線程是一個(gè)worker，這里我們給worker換個(gè)名字，就把它叫M吧。前面已經(jīng)說過了，worker做的事情就是不停的去任務(wù)隊(duì)列中取一個(gè)任務(wù)出來執(zhí)行。于是用Go語言大概可以寫成這樣子：

func M() {
    for {
        sched.lock.Lock()    //互斥地從就緒G隊(duì)列中取一個(gè)g出來運(yùn)行
        if sched.allg > 0 {
            g := sched.allg[0]
            sched.allg = sched.allg[1:]
            sched.lock.Unlock()
            g.Run()        //運(yùn)行它
        } else {
            sched.lock.Unlock()
        }
    }
}

接下來，將整個(gè)系統(tǒng)啟動(dòng)：

for i:=0; i<GOMAXPROCS; i++ {
    go M()
}

假定我們有一個(gè)滿足G接口的main，然后它在自己的Run中不斷地將新的任務(wù)掛到sched.allg中，這個(gè)線程池+任務(wù)隊(duì)列的系統(tǒng)模型就會(huì)一直運(yùn)行下去。

可以看到，這里在代碼取中故意地用Go語言中的G，M，甚至包括GOMAXPROCS等取名字。其實(shí)本質(zhì)上，Go語言的調(diào)度層無非就是這樣一個(gè)工作模式的：幾條物理線程，不停地取goroutine運(yùn)行。

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

上面的情形太簡單了，就是工作線程不停地取goroutine運(yùn)行，這個(gè)還不能稱之為調(diào)度。調(diào)度之所以為調(diào)度，是因?yàn)橛幸恍?fù)雜的控制機(jī)制，比如哪個(gè)goroutine應(yīng)該被運(yùn)行，它應(yīng)該運(yùn)行多久，什么時(shí)候?qū)⑺鼡Q出來。用前面的代碼來說明Go的調(diào)度會(huì)有一些小問題。Run函數(shù)會(huì)一直執(zhí)行，在它結(jié)束之前不會(huì)返回到調(diào)用器層面。那么假設(shè)上面的任務(wù)中Run進(jìn)入到一個(gè)阻塞的系統(tǒng)調(diào)用了，那么M也就跟著一起阻塞了，實(shí)際工作的線程就少了一個(gè)，無法充分利用CPU。

一個(gè)簡單的解決辦法是在進(jìn)入系統(tǒng)調(diào)用之前再制造一個(gè)M出來干活，這樣就填補(bǔ)了這個(gè)進(jìn)入系統(tǒng)調(diào)用的M的空缺，始終保證有GOMAXPROCS個(gè)工作線程在干活了。

func entersyscall() {
    go M()
}

那么出系統(tǒng)調(diào)用時(shí)怎么辦呢？如果讓M接著干活，豈不超過了GOMAXPROCS個(gè)線程了？所以這個(gè)M不能再干活了，要限制干活的M個(gè)數(shù)為GOMAXPROCS個(gè)，多了則讓它們閑置(物理線程比CPU多很多就沒意義了，讓它們相互搶CPU反而會(huì)降低利用率)。

func exitsyscall() {
    if len(allm) >= GOMAXPROCS {
        sched.lock.Lock()
        sched.allg = append(sched.allg, g)    //把g放回到隊(duì)列中
        sched.lock.Unlock()
        time.Sleep()    //這個(gè)M不再干活
    }
}

于是就變成了這樣子:

其實(shí)這個(gè)也很好理解，就像線程池做負(fù)載調(diào)節(jié)一樣，當(dāng)任務(wù)隊(duì)列很長后，忙不過來了，則再開幾條線程出來。而如果任務(wù)隊(duì)列為空了，則可以釋放一些線程。

協(xié)程與保存上下文

大家都知道阻塞于系統(tǒng)調(diào)用，會(huì)白白浪費(fèi)CPU。而使用異步事件或回調(diào)的思維方式又十分反人類。上面的模型既然這么簡單明了，為什么不這么用呢？其實(shí)上面的東西看上去簡單，但實(shí)現(xiàn)起來確不那么容易。

將一個(gè)正在執(zhí)行的任務(wù)yield出去，再在某個(gè)時(shí)刻再弄回來繼續(xù)運(yùn)行，這就涉及到一個(gè)麻煩的問題，即保存和恢復(fù)運(yùn)行時(shí)的上下文環(huán)境。

在此先引入?yún)f(xié)程的概念。協(xié)程是輕量級的線程，它相對線程的優(yōu)勢就在于協(xié)程非常輕量級，進(jìn)行切換以及保存上下文環(huán)境代價(jià)非常的小。協(xié)程的具體的實(shí)現(xiàn)方式有多種，上面就是其中一種基于線程池的實(shí)現(xiàn)方式。每個(gè)協(xié)程是一個(gè)任務(wù)，可以保存和恢復(fù)任務(wù)運(yùn)行時(shí)的上下文環(huán)境。

協(xié)程一類的東西一般會(huì)提供類似yield的函數(shù)。協(xié)程運(yùn)行到一定時(shí)候就主動(dòng)調(diào)用yield放棄自己的執(zhí)行，把自己再次放回到任務(wù)隊(duì)列中等待下一次調(diào)用時(shí)機(jī)等等。

其實(shí)Go語言中的goroutine就是協(xié)程。每個(gè)結(jié)構(gòu)體G中有一個(gè)sched域就是用于保存自己上下文的。這樣，這種goroutine就可以被換出去，再換進(jìn)來。這種上下文保存在用戶態(tài)完成，不必陷入到內(nèi)核，非常的輕量，速度很快。保存的信息很少，只有當(dāng)前的PC,SP等少量信息。只是由于要優(yōu)化，所以代碼看上去更復(fù)雜一些，比如要重用內(nèi)存空間所以會(huì)有g(shù)free和mhead之類的東西。

Go1.0

在前面的代碼中，線程與M是直接對應(yīng)的關(guān)系，這個(gè)解耦還是不夠。Go1.0中將M抽出來成為了一個(gè)結(jié)構(gòu)體，startm函數(shù)是線程的入口地址，而goroutine的入口地址是go表達(dá)式中的那個(gè)函數(shù)。總體上跟上面的結(jié)構(gòu)差不多，進(jìn)出系統(tǒng)調(diào)用的時(shí)候goroutine會(huì)跟M一起進(jìn)入到系統(tǒng)調(diào)用中，schedule中會(huì)匹配g和m，讓空閑的m來運(yùn)行g(shù)。如果檢測到干活的數(shù)量少于GOMAXPROCS并且沒有空閑著的m，則會(huì)創(chuàng)建新的m來運(yùn)行g(shù)。出系統(tǒng)調(diào)用的時(shí)候，如果已經(jīng)有GOMAXPROCS個(gè)m在干活了，則這個(gè)出系統(tǒng)調(diào)用的m會(huì)被掛起，它的g也會(huì)被掛到待運(yùn)行的goroutine隊(duì)列中。

在Go語言中m是machine的縮寫，也就是機(jī)器的抽象。它被設(shè)計(jì)成了可以運(yùn)行所有的G。比如說一個(gè)g開始在某個(gè)m上運(yùn)行，經(jīng)過幾次進(jìn)出系統(tǒng)調(diào)用之后，可能運(yùn)行它的m掛起了，其它的m會(huì)將它從隊(duì)列中取出并繼續(xù)運(yùn)行。

每次調(diào)度都會(huì)涉及對g和m等隊(duì)列的操作，這些全局的數(shù)據(jù)在多線程情況下使用就會(huì)涉及到大量的鎖操作。在頻繁的系統(tǒng)調(diào)用中這將是一個(gè)很大的開銷。為了減少系統(tǒng)調(diào)用開銷，Go1.0在這里做了一些優(yōu)化的。1.0版中，在它的Sched結(jié)構(gòu)體中有一個(gè)atomic字段，類型是一個(gè)volatile的無符32位整型。

// sched中的原子字段是一個(gè)原子的uint32，存放下列域
// 15位 mcpu  --正在占用cpu運(yùn)行的m數(shù)量 (進(jìn)入syscall的m是不占用cpu的)
// 15位 mcpumax  --最大允許這么多個(gè)m同時(shí)使用cpu
// 1位  waitstop  --有g(shù)等待結(jié)束
// 1位  gwaiting  --等待隊(duì)列不為空，有g(shù)處于waiting狀態(tài)
//    [15 bits] mcpu        number of m's executing on cpu
//    [15 bits] mcpumax    max number of m's allowed on cpu
//    [1 bit] waitstop    some g is waiting on stopped
//    [1 bit] gwaiting    gwait != 0

這些信息是進(jìn)行系統(tǒng)調(diào)用和出系統(tǒng)調(diào)用時(shí)需要用到的，它會(huì)決定是否需要進(jìn)入到調(diào)度器層面。直接用CAS操作Sched的atomic字段判斷，將它們打包成一個(gè)字節(jié)使得可以通過一次原子讀寫獲取它們而不用加鎖。這將極大的減少那些大量使用系統(tǒng)調(diào)用或者cgo的多線程程序的contention。

除了進(jìn)出系統(tǒng)調(diào)用以外，操作這些域只會(huì)發(fā)生于持有調(diào)度器鎖的時(shí)候，因此goroutines不用擔(dān)心其它goroutine會(huì)對這些字段進(jìn)行操作。特別是，進(jìn)出系統(tǒng)調(diào)用只會(huì)讀mcpumax，waitstop和gwaiting。決不會(huì)寫他們。因此，(持有調(diào)度器鎖)寫這些域時(shí)完全不用擔(dān)心會(huì)發(fā)生寫沖突。

總體上看，Go1.0調(diào)度設(shè)計(jì)結(jié)構(gòu)比較簡單，代碼也比較清晰。但是也存在一些問題。這樣的調(diào)度器設(shè)計(jì)限制了Go程序的并發(fā)度。測試發(fā)現(xiàn)有14%是的時(shí)間浪費(fèi)在了runtime.futex()中。

具體地看：

1. 單個(gè)全局鎖(Sched.Lock)用來保護(hù)所有的goroutine相關(guān)的操作(創(chuàng)建，完成，調(diào)度等)。
2. Goroutine切換。工作線程在各自之前切換goroutine，這導(dǎo)致延遲和額外的負(fù)擔(dān)。每個(gè)M都必須可以執(zhí)行任何的G.
3. 內(nèi)存緩存MCache是每個(gè)M的。而當(dāng)M阻塞后，相應(yīng)的內(nèi)存資源也被一起拿走了。
4. 過多的線程阻塞、恢復(fù)。系統(tǒng)調(diào)用時(shí)的工作線程會(huì)頻繁地阻塞，恢復(fù)，造成過多的負(fù)擔(dān)。

第一點(diǎn)很明顯，所有的goroutine都用一個(gè)鎖保護(hù)的，這個(gè)鎖粒度是比較大的，只要goroutine的相關(guān)操作都會(huì)鎖住調(diào)度。然后是goroutine切換，前面說了，每個(gè)M都是可以執(zhí)行所有的goroutine的。舉個(gè)很簡單的類比，多核CPU中每個(gè)核都去執(zhí)行不同線程的代碼，這顯然是不利于緩存的局部性的，切換開銷也會(huì)變大。內(nèi)存緩存和其它緩存是關(guān)聯(lián)到所有的M的，而事實(shí)上它本只需要關(guān)聯(lián)到運(yùn)行Go代碼的M(阻塞于系統(tǒng)調(diào)用的M是不需要mcache的)。運(yùn)行著Go代碼的M和所有M的比例可能高達(dá)1:100。這導(dǎo)致過度的資源消耗。

Go1.1

Go1.1相對于1.0一個(gè)重要的改動(dòng)就是重新調(diào)用了調(diào)度器。前面已經(jīng)看到，老版本中的調(diào)度器實(shí)現(xiàn)是存在一些問題的。解決方式是引入Processor的概念，并在Processors之上實(shí)現(xiàn)工作流竊取的調(diào)度器。

M代表OS線程。P代表Go代碼執(zhí)行時(shí)需要的資源。當(dāng)M執(zhí)行Go代碼時(shí)，它需要關(guān)聯(lián)一個(gè)P，當(dāng)M為idle或者在系統(tǒng)調(diào)用中時(shí)，它也需要P。有剛好GOMAXPROCS個(gè)P。所有的P被組織為一個(gè)數(shù)組，工作流竊取需要這個(gè)條件。GOMAXPROCS的改變涉及到stop/start the world來resize數(shù)組P的大小。

gfree和grunnable從sched中移到P中。這樣就解決了前面的單個(gè)全局鎖保護(hù)用有g(shù)oroutine的問題，由于goroutine現(xiàn)在被分到每個(gè)P中，它們是P局部的goroutine，因此P只管去操作自己的goroutine就行了，不會(huì)與其它P上的goroutine沖突。全局的grunnable隊(duì)列也仍然是存在的，只有在P去訪問全局grunnable隊(duì)列時(shí)才涉及到加鎖操作。mcache從M中移到P中。不過當(dāng)前還不徹底，在M中還是保留著mcache域的。

加入了P后，sched.atomic也從Sched結(jié)構(gòu)體中去掉了。

當(dāng)一個(gè)新的G創(chuàng)建或者現(xiàn)有的G變成runnable，它將一個(gè)runnable的goroutine推到當(dāng)前的P。當(dāng)P完成執(zhí)行G，它將G從自己的runnable goroutine中pop出去。如果鏈為空，P會(huì)隨機(jī)從其它P中竊取一半的可運(yùn)行的goroutine。

當(dāng)M創(chuàng)建一個(gè)新G的時(shí)候，必須保證有另一個(gè)M來執(zhí)行這個(gè)G。類似的，當(dāng)一個(gè)M進(jìn)入到系統(tǒng)調(diào)用時(shí)，必須保證有另一個(gè)M來執(zhí)行G的代碼。

2層自旋：關(guān)聯(lián)了P的處于idle狀態(tài)的的M自旋尋找新的G；沒有關(guān)聯(lián)P的M自旋等待可用的P。最多有GOMAXPROCS個(gè)自旋的M。只要有第二類M時(shí)第一類M就不會(huì)阻塞。