快捷導(dǎo)航

淺談Golang的Work Stealing機(jī)制

更新時間：2025年03月04日 10:25:17 作者：Lzww0608

Go的運(yùn)行時系統(tǒng)使用了一種名為Work Stealing的調(diào)度策略來分配Goroutine到可用線程上執(zhí)行,本文主要介紹了淺談Golang的Work Stealing機(jī)制,具有一定的參考價值,感興趣的可以了解一下

Go的運(yùn)行時系統(tǒng)使用了一種名為Work Stealing（工作竊取）的調(diào)度策略來分配Goroutine到可用線程（稱為M，即Machine）上執(zhí)行。這樣可以最大化CPU使用率，減少任務(wù)調(diào)度的開銷。在這種機(jī)制下，任務(wù)隊列和調(diào)度器通過動態(tài)平衡負(fù)載來提高并發(fā)性能和吞吐量。

Go的調(diào)度器使用了P（Processor）與M和Goroutine進(jìn)行交互。每個P都維護(hù)了一個本地的Goroutine隊列，新創(chuàng)建的Goroutine首先會被放入創(chuàng)建它的P的本地隊列中。在這個系統(tǒng)中，P可以看作是可調(diào)度Goroutine的數(shù)量，每個P都可以關(guān)聯(lián)一個M來執(zhí)行Goroutine。

Work Stealing 機(jī)制的核心思想：每個操作系統(tǒng)線程（M）都有一個本地任務(wù)隊列，它會盡可能地先執(zhí)行自己隊列中的協(xié)程。當(dāng)某個M的P隊列為空，而其他P仍有任務(wù)時，該M會嘗試從其他P中"偷"一些協(xié)程來執(zhí)行，以實現(xiàn)負(fù)載均衡

基本工作原理

任務(wù)隊列：每個工作線程（或goroutine）都有自己的雙端隊列（deque），用于存儲任務(wù)。當(dāng)一個線程生成新任務(wù)時，它會將任務(wù)放入自己的隊列。這種隊列就是上述所講的P處理器。
執(zhí)行任務(wù)：M首先從自己對應(yīng)P中獲取任務(wù)并執(zhí)行。如果它的任務(wù)隊列為空，它就會嘗試從其他線程的任務(wù)隊列P中竊取任務(wù)。
竊取任務(wù)：當(dāng)一個M發(fā)現(xiàn)自己的任務(wù)隊列P為空時，它會隨機(jī)選擇其他M的任務(wù)隊列P，從隊列的另一端竊取任務(wù)。這樣可以避免競爭，因為線程對自己的任務(wù)隊列使用一端，而其他線程只能從另一端竊取任務(wù)。
負(fù)載均衡：通過這種機(jī)制，系統(tǒng)能夠動態(tài)地平衡負(fù)載。如果某個線程的任務(wù)較多，其他空閑線程可以幫助處理這些任務(wù)，從而避免某些線程過載而其他線程空閑的情況。
全局隊列：如果所有本地隊列P都為空，調(diào)度器會從全局隊列中獲取任務(wù)，全局隊列存儲的是所有P都無法處理的goroutine。

以下是一個簡化的示意圖，展示了P, M和Goroutine的交互：

     P1       P2       P3
     |        |        |
     v        v        v
    [G1,G2] [G3]   [G4,G5,G6] 
     ^        ^        ^
     |        |        |
     M1       M2       M3

在這個圖中，我們有3個P（P1、P2和P3），每個P都有一個本地的Goroutine隊列。M1、M2和M3是3個線程，每個線程都關(guān)聯(lián)了一個P，并且從其隊列中取出Goroutine來執(zhí)行。當(dāng)M1完成了G1后，它會從P1的隊列中取出G2來執(zhí)行。如果P1的隊列為空，M1就會嘗試從P2或P3的隊列中”竊取”一個Goroutine。

當(dāng)從本線程M 從綁定 P 本地隊列、全局G隊列、Netpoller 都找不到可執(zhí)行的 G，會從其它 P 里竊取G并放到當(dāng)前P上面

1)如果全局隊列有G，從全局隊列竊取的G數(shù)量：N = min(len(GRQ)/GOMAXPROCS + 1, len(GRQ/2)) （根據(jù)GOMAXPROCS數(shù)量負(fù)載均衡）

2)如果 Netpoller 有G（網(wǎng)絡(luò)IO被阻塞的G），從Netpoller竊取的G數(shù)量：N = 1

3)如果從其它P里竊取G，從其它P竊取的G數(shù)量：N = len(LRQ)/2（平分負(fù)載均衡）

4)如果嘗試多次一直找不到需要運(yùn)行的goroutine則進(jìn)入睡眠狀態(tài)，等待被其它工作線程喚醒

從其它P竊取G的源碼見runtime/proc.go stealWork函數(shù)，竊取流程如下：

1)選擇要竊取的P

2)從P中偷走一半G

選擇要竊取的P

竊取的實質(zhì)就是遍歷所有P，查看其運(yùn)行隊列是否有g(shù)oroutine，如果有，則取其一半到當(dāng)前工作線程的運(yùn)行隊列

為了保證公平性，遍歷P時并不是按照數(shù)組下標(biāo)順序訪問P，而是使用了一種偽隨機(jī)的方式遍歷allp中的每個P，防止每次遍歷時使用同樣的順序訪問allp中的元素

offset := uint32(random()) % nprocs
coprime := 隨機(jī)選取一個小于nprocs且與nprocs互質(zhì)的數(shù)
const stealTries = 4 // 最多重試4次
for i := 0; i < stealTries; i++ {
  // 隨機(jī)訪問所有 P
    for i := 0; i < nprocs; i++ {
        p := allp[offset]
        從p的運(yùn)行隊列偷取goroutine
        if 偷取成功 {
        break
        }
        offset += coprime
        offset = offset % nprocs
     }
}

可以看到只要隨機(jī)數(shù)不一樣，遍歷P的順序也不一樣，但可以保證經(jīng)過nprocs次循環(huán)，每個P都會被訪問到

從P中偷走一半G

挑選出盜取的對象P之后，則調(diào)用 runtime/proc.go 函數(shù)runqsteal 盜取P的運(yùn)行隊列中的goroutine，runqsteal函數(shù)再調(diào)用runqgrap從P的本地隊列尾部批量偷走一半的 G

func runqgrab(_p_ *p, batch *[256]guintptr, batchHead uint32, stealRunNextG bool) uint32 {
    for {
        h := atomic.LoadAcq(&_p_.runqhead) // load-acquire, synchronize with other consumers
        t := atomic.LoadAcq(&_p_.runqtail) // load-acquire, synchronize with the producer
        n := t - h        //計算隊列中有多少個goroutine
        n = n - n/2     //取隊列中g(shù)oroutine個數(shù)的一半
        if n == 0 {
            ......
            return ......
        }
        return n
    }
}