Press "Enter" to skip to content

Go: Go 调度器的任务窃取(Work-Stealing)

ℹ️ 本文基于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数量(分别为P0P1)。当本地队列满了,积压了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

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据