浅谈Golang的Work Stealing机制

目录

• 基本工作原理
• 优点

Go的运行时系统使用了一种名为Work Stealing（工作窃取）的调度策略来分配Goroutine到可用线程（称为M，即MAChine）上执行。这样可以最大化CPU使用率，减少任务调度的开销。在这种机制下，任务队列和调度器通过动态平衡负载来提高并发性能和吞吐量。

Go的调度器使用了P（Processor）与M和Goroutine进行交互。每个P都维护了一个本地的Goroutine队列，新创建的Goroutine首先会被放入创建它的P的本地队列中。在这个系统中，P可以看作是可调度Goroutine的数量，每个P都可以关联一个M来执行Goroutine。

Work Stealing 机制的核心思想：每个操作系统线程（M）都有一个本地任务队列，它会尽可能地先执行自己队列中的协程。当某个M的P队列为空，而其他P仍有任务时，该M会尝试从其他P中"偷"一些协程来执行，以实现负载均衡

基本工作原理

• 任务队列：每个工作线程（或goroutine）都有自己的双端队列（deque），用于存储任务。当一个线程生成新任务时，它会将任务放入自己的队列。这种队列就是上述所讲的P处理器。

• 执行任务：M首先从自己对应P中获取任务并执行。如果它的任务队列为空，它就会尝试从其他线程的任务队列P中窃取任务。

• 窃取任务：当一个M发现自己的任务队列Pjs为空时，它会随机选择其他M的任务队列P，从队列的另一端窃取任务。这样可以避免竞争，因为线程对自己的任务队列使用一端，而其他线程只能从另一端窃取任务。

• 负载均衡：通过这种机制，系统能够动态地平衡负载。如果某个线程的任务较多，其他空闲线程可以帮助处理这些任务，从而避免某些线程过载而其他线程空闲的情况。

• 全局队列：如果所有本地队列P都为空，调度器会从全局队列中获取任务，全局队列存储的是所有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个线程，每个线程都关联了一个P，并且从其队列中取出Goroutine来执行。当M1完成了G1后，它会从P1的队列中取出G2来执行。如果P1的队列为空，M1就会尝试从P2或P3的队列中”窃取”一个Goroutine。

当从本线程M 从绑定 P 本地 队列、全局G队列、Netpoller 都找不到可执行的 G，会从其它 P 里窃取G并放到当前P上面

1)如果全局队列有G，从全局队列窃取的G数量：N = min(len(GRQ)/GOMAXPROCS + 1, len(GRQ/2)) （根据GOMAXPROCS数量负载均衡）

2)如果 Netpoller 有G（网络IO被阻塞的G），从Netpoller窃取的G数量：N = 1

3)如果从其它P里窃取G，从其它P窃取的G数量：N = len(LRQ)/2（平分负载均衡）

4)如果尝试多次一直找不到需要运行的goroutine则进入睡眠状态，等待被其它工作线程唤醒

从其它P窃取G的源码见runtime/proc.go stealWork函数，窃取流程如下：

1)选择要窃取的P

2)从P中偷走一半G

选择要窃取的P

窃取的实质就是遍历所有P，查看其运行队列是否有goroutine，如果有，则取其一半到当前工作线程的运行队列

为了保证公平性，遍历P时并不是按照数组下标顺序访问P，而是使用了一种伪随机的方式遍历allp中的每个P，防止每次遍历时使用同样的顺序访问allp中的元素

offset := uint32(random()) % nprocs
coprime := 随机选取一个小于nprocs且与nprocs互质的数
const stealTries = 4 // 最多重试4次
for i := 0; i < stealTries; i++ {
  // 随机访问所有 P
    for i := 0; i < nprocs; i++ {
        p := allp[offset]
        从p的运行队列偷取goroutine
        if 偷取成功 {
        break
        android}
        offset += coprime
        offset = offset % nprocs
     }
}

可以看到只要随机数不一样，遍历P的顺序也不一样，但可以保证经过nprocs次循环，每个P都会被访问到

从P中偷走一半G

挑选出盗取的对象P之后，则调用 runtime/ppythonroc.go 函数runqsteal 盗取P的运行队列中的goroutine，runqsteal函数再调用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     //取队列中gorphpoutine个数的一半
        if n == 0 {
            ......
            return ......
        }
        return n
    }
}

优点

• 高效利用资源：通过动态平衡负载，确保所有线程尽可能地保持忙碌状态，提高CPU利用率。

• 减少竞争：窃取任务时，只访问其他线程队列的一端，减少了竞争和锁的使用。

• 灵活性：能够自适应负载变化，当任务量不均时，自动进行负载均衡。

到此这篇关于浅谈golang的Work Stealing机制的文章就介绍到这了,更多相关Golang的Work Stealing机制内容www.devze.com请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！