Go: Go 调度器的任务窃取（Work-Stealing）

 关注
发布于: 2020 年 06 月 06 日
ℹ️ 本文基于Go 1.13 
﻿
在Go中创建goroutine既方便又快捷。但是go在同一时间单核只能运行一个goroutine, 因此需要一种方式来停放其他goroutine来确保处理器负载均衡。
Goroutine队列Go使用两级队列来管理处于等待中的goroutine，分别是本地队列和全局队列。每个处理器有一个本地队列，而全局队列是唯一的并且可以被所有处理器共享：
﻿
全局和本地队列
﻿
每个本地队列最大容量是256，容量满了之后新产生的goroutine将会被存放到全局队列。下面的程序中生产了上千个goroutine：
﻿
func main() {
   var wg sync.WaitGroup
 
   for i := 0;i < 2000 ;i++ {
      wg.Add(1)
      go func() {
         a := 0
 
         for i := 0; i < 1e6; i++ {
            a += 1
         }
 
         wg.Done()
      }()
   }
 
   wg.Wait()
}
﻿
下面是拥有两个处理器的调度器trace信息：
﻿
 本地和全局队列详情
﻿
trace信息trace信息通过 runqueue 展示了全局队列中 goroutine 的数量，以及方括号中 [3 256] 的本地队列goroutine数量（分别为P0和P1）。当本地队列满了，积压了256个等待中的 goroutine后，下一个 goroutine 会被压到全局队列中，正如我们从 runqueue 看到的数量增长一样。
﻿
仅当本地队列满载时，goroutine才进入全局队列。 当Go往调度器注入goroutine列表时，goroutine也会被推送到全局队列，例如 网络轮询器（network poller） 或者在垃圾回收期间等待的 goroutine。
﻿
下面图说明了上面的例子：
﻿
本地队列最多有256个goroutine
﻿
然而，我们还想知道为什么上面 P0的本地队列在上面trace图里不是空的，因为Go使用了其他策略来保证每个处理器保持忙碌。
﻿
任务窃取如果处理器没有任务可处理，它会按照以下规则来执行，直到满足某条规则：
﻿
从本地队列获取
从全局队列获取
从网络轮询器（network poller）获取
从其他处理器的本地队列窃取
﻿
在我们之前例子里，main函数在P1 上运行并创建goroutine。当第一批goroutine进入P1的本地队列时候，P0 正在寻找任务。然而，它的本地队列，全局队列和网络轮询器都是空的。最后的方案就是从P1 中窃取任务：
﻿
 P0 的任务窃取
﻿
这是P0 任务窃取前后的调度器trace信息：
P0 的任务窃取
﻿
trace信息展示了，处理器是如何从其它处理器中窃取任务的。它从其他处理器的本地队列中取走一半的 goroutine；在七个 goroutine 中，偷走了四个 ，其中一个立马在 P0 执行，剩下的放到本地队列。现在多处理器处于负载均衡的状态。这能通过执行 tracing 来确认：
﻿
goroutine被良好的分发，因为没有 I/O, goroutine被链式执行而不需要切换。让我们现在来看下如果涉及到文件操作等I/O时会发生什么。
﻿
I/O 和全局队列让我们看一个涉及到文件操作的例子：
﻿
func main() {
   var wg sync.WaitGroup
 
   for i := 0;i < 20 ;i++ {
      wg.Add(1)
      go func() {
         a := 0
         for i := 0; i < 1e6; i++ {
            a += 1
            if i == 1e6/2 {
               bytes, _ := ioutil.ReadFile(`add.txt`)
               inc, _ := strconv.Atoi(string(bytes))
               a += inc
            }
         }
         wg.Done()
      }()
   }
 
   wg.Wait()
}
﻿
变量 a 在循环中根据文件中的数值不断累加。下面是新的trace信息：
﻿
﻿
在这个例子中，我们可以发现每个goroutine 并不是只被一个处理器处理。因为系统调用（ system call）,Go使用网络轮询器在系统调用结束后将goroutine放进全局队列。这里是goroutine #35的说明：
﻿
 I/O 操作后将任务放到全局队列
﻿
因为处理器在本地任务跑完后可以从全局队列获取任务，P0会执行G35。这种行为也解释了为什么一个 goroutine可以跑在不同的处理器上并显示了如何在资源空闲时让其他goroutine运行来优化系统调用。
﻿
编译整理自  Go: Work-Stealing in Go Scheduler
博客地址：https://www.chenjie.info/2407
﻿
本文首发于我的公众号：
﻿