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 资源，但是它们最小化了操作系统线程的抢占。一个线程正在旋转，如果:
- 一个拥有线程的处理器正在寻找一个可执行的 goroutine。
- 一个没有所属处理器的线程正在寻找一个可以依附的处理器
- 当它准备一个 goroutine 时，如果有一个空闲的处理器并且没有其他的旋转线程，调度程序会取消一个额外的线程，然后旋转这个线程。
在任何时候，都有最多 GOMAXPROCS 个线程在旋转。当一个旋转的线程找到工作后，它就会脱离自旋状态。
如果空闲的线程没有处理器可分配，则已分配到处理器上的空闲线程不会阻塞。当新的 goroutine 被创建或者一个线程被阻塞时，调度程序将确保至少有一个旋转的线程，这确保了当没有可运行的 goroutine 时程序仍可以运行，也避免过多的线程 block/unblock。
Go调度程序做了很多工作，以避免对操作系统线程的过度抢占，通过将它们调度到正确的和未充分利用的处理器上，并实现了“旋转”线程，以避免出现阻塞/未阻塞的转换。
调度事件可以通过执行跟踪程序跟踪。如果你认为你的处理器利用率很低，那么你可以排查一下正在发生什么。
作者：谢烟客
链接：http://www.jianshu.com/p/20c49ce02175
來源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。