Go語言 設計與演化

線程池

先看一些簡單點的吧。一個常規(guī)的 線程池+任務隊列 的模型如圖所示：

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

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

當然，這是最簡單的情形，但是一個很明顯的問題就是一個進入callback之后，就失去了控制權。因為沒有一個調(diào)度器層的東西，一個任務可以執(zhí)行很長很長時間一直占用的worker線程，或者阻塞于io之類的。

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

type G interface {
    Run() 
}

我們有一個全局的任務隊列，里面包含很多可運行的任務。線程池的各個線程從全局的任務隊列中取任務時，顯然是需要并發(fā)保護的，所以有下面這個結構體：

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

以及它的變量

var sched Sched

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

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

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

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

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

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

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

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

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

func entersyscall() {
    go M()
}

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

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

于是就變成了這樣子:

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

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

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

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

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

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

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

Go1.0

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

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

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

// sched中的原子字段是一個原子的uint32，存放下列域
// 15位 mcpu  --正在占用cpu運行的m數(shù)量 (進入syscall的m是不占用cpu的)
// 15位 mcpumax  --最大允許這么多個m同時使用cpu
// 1位  waitstop  --有g等待結束
// 1位  gwaiting  --等待隊列不為空，有g處于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

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

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

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

具體地看：

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

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

Go1.1

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

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

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

加入了P后，sched.atomic也從Sched結構體中去掉了。

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

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

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