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

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

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

基本工作原理

• 任務(wù)隊(duì)列：每個(gè)工作線程（或goroutine）都有自己的雙端隊(duì)列（deque），用于存儲(chǔ)任務(wù)。當(dāng)一個(gè)線程生成新任務(wù)時(shí)，它會(huì)將任務(wù)放入自己的隊(duì)列。這種隊(duì)列就是上述所講的P處理器。

• 執(zhí)行任務(wù)：M首先從自己對應(yīng)P中獲取任務(wù)并執(zhí)行。如果它的任務(wù)隊(duì)列為空，它就會(huì)嘗試從其他線程的任務(wù)隊(duì)列P中竊取任務(wù)。

• 竊取任務(wù)：當(dāng)一個(gè)M發(fā)現(xiàn)自己的任務(wù)隊(duì)列P為空時(shí)，它會(huì)隨機(jī)選擇其他M的任務(wù)隊(duì)列P，從隊(duì)列的另一端竊取任務(wù)。這樣可以避免競爭，因?yàn)榫€程對自己的任務(wù)隊(duì)列使用一端，而其他線程只能從另一端竊取任務(wù)。

• 負(fù)載均衡：通過這種機(jī)制，系統(tǒng)能夠動(dòng)態(tài)地平衡負(fù)載。如果某個(gè)線程的任務(wù)較多，其他空閑線程可以幫助處理這些任務(wù)，從而避免某些線程過載而其他線程空閑的情況。

• 全局隊(duì)列：如果所有本地隊(duì)列P都為空，調(diào)度器會(huì)從全局隊(duì)列中獲取任務(wù)，全局隊(duì)列存儲(chǔ)的是所有P都無法處理的goroutine。

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

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

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

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

1)如果全局隊(duì)列有G，從全局隊(duì)列竊取的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

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

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

offset := uint32(random()) % nprocs
coprime := 隨機(jī)選取一個(gè)小于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)行隊(duì)列偷取goroutine
        if 偷取成功 {
        break
        }
        offset += coprime
        offset = offset % nprocs
     }
}

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

從P中偷走一半G

挑選出盜取的對象P之后，則調(diào)用 runtime/proc.go 函數(shù)runqsteal 盜取P的運(yùn)行隊(duì)列中的goroutine，runqsteal函數(shù)再調(diào)用runqgrap從P的本地隊(duì)列尾部批量偷走一半的 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        //計(jì)算隊(duì)列中有多少個(gè)goroutine
        n = n - n/2     //取隊(duì)列中g(shù)oroutine個(gè)數(shù)的一半
        if n == 0 {
            ......
            return ......
        }
        return n
    }
}

優(yōu)點(diǎn)

• 高效利用資源：通過動(dòng)態(tài)平衡負(fù)載，確保所有線程盡可能地保持忙碌狀態(tài)，提高CPU利用率。

• 減少競爭：竊取任務(wù)時(shí)，只訪問其他線程隊(duì)列的一端，減少了競爭和鎖的使用。

• 靈活性：能夠自適應(yīng)負(fù)載變化，當(dāng)任務(wù)量不均時(shí)，自動(dòng)進(jìn)行負(fù)載均衡。

到此這篇關(guān)于淺談Golang的Work Stealing機(jī)制的文章就介紹到這了,更多相關(guān)Golang的Work Stealing機(jī)制內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！ 

最新評(píng)論