（译）Go 语言的工作窃取调度器

作者: 谢烟客 | 来源:发表于2017-08-31 07:19 被阅读966次

（译）Go 语言的工作窃取调度器
【译】GO的工作窃取调度程序
[译] Go语言调度器 by povilas
高伸缩性Go调度器设计(译)
Go语言调度器
go 调度器实现
Golang后端面试汇总-001
Go 语言调度（二）: goroutine 调度器
Go 的并发性与调度器
golang调度器学习

原文链接：Go's work-stealing scheduler

Go 调度程序的任务是在多个运行在一个或多个处理器上的系统线程上分发出可运行的 goroutine。在多线程计算中，调度已经出现了两种模式：工作共享与工作窃取。

工作共享：当一个处理器创建新的线程时，它试图将一部分线程迁移到其他的处理器上执行，期望更充分的利用那些 IDLE 状态的处理器。
工作窃取：未被充分利用的处理器会主动寻找其他处理器上的线程，并“窃取”一些线程。

与工作共享模式相比，工作窃取模式线程的迁移发生的频率更低。当所有的处理器都有工作要运行时，没有任何线程被迁移。一旦有了空闲处理器，就会考虑迁移。

Go 从 1.1 版本开始就有了一个工作窃取模式的调度程序，它是由 Dmitry Vyukov 贡献的。这篇文章将深入地解释什么是工作窃取的调度程序，以及如何实现一个。

调度的基础

Go有一个 M:N 的调度程序，它可以使用多核处理器。在任何时候，M 个 goroutine 都需要被分发在最多 GOMAXPROCS 个处理器上运行的 N 个系统线程上。Go调度程序使用以下术语来描述 goroutines、线程和处理器:

G：goroutine
M：系统线程(Machine)
P：处理器

有一个特定于处理器的本地 goroutine 队列和一个全局的 goroutine 队列。每个系统线程都应该被分配给一个处理器，如果处理器被阻塞或被系统调用，那么可能处理器上会没有线程。在任何时候，最多有
GOMAXPROCS 个处理器被用于分配。任何时候，一个线程都只能运行在一个处理器上。如果有需要调度器也可以创建更多的线程。

image.png

每一轮的调度都只是找到一个可运行的 goroutine 并执行它。在每一轮的调度中，搜索都按照以下顺序进行:

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

一旦找到一个可运行的 goroutine ，它就会被执行，直到被阻塞。

注意：看起来全局队列比局部队列优先级更高，但是偶尔检查全局队列只是为了避免系统线程在局部队列中的 goroutine 用尽前只调用局部 goroutine 队列中的 goroutine。

窃取

当一个 goroutine 被创建或一个已经存在的 goroutine 变为可以运行状态，它被推送到当前处理器上的一个可运行的 goroutines 队列中，当处理器执行完一个 goroutine，它将试图从自己的局部可运行 goroutine 队列中弹出这个 goroutine。如果队列为空，处理器会随机选择一个其他处理器，并试图从这个处理器的局部可运行 goroutine 队列中偷取一半数量的可运行 goroutine。

image.png

在上面的例子中，P2 这个处理器无法找到任何可执行的 goroutines。因此，它随机选择另一个处理器 P1，并将 3 个 goroutines 偷到自己的局部队列中。P2 将执行这些 goroutines，而调度器也将在多个处理器之间更均衡的调度。

旋转线程

调度程序总是希望将可运行的 goroutines 分发到线程中，以便充分利用处理器，但同时我们又需要限制过多的任务来节省 CPU 资源。与此相矛盾的是，调度器还需要能够扩展到高吞吐量和CPU密集的程序中。

如果性能很关键，那么经常性的抢占将显得十分的昂贵，并且对高吞吐量的程序来说这也是个严重的问题。操作系统线程之间不应该频繁的传递可运行的 goroutine，因为这将导致延迟的增加。另外，在有系统调用的情况下，系统线程需要不断的 block 与 unblock，这也是非常昂贵的同时也增加了很多额外的开销。

为了减少线程间传递，调度器实现了“旋转线程”。旋转线程虽然消耗了额外的 CPU 资源，但是它们最小化了操作系统线程的抢占。一个线程正在旋转，如果: