Go语言调度器

译序

本文翻译 Daniel Morsing 的博文 The Go scheduler，个人觉得这篇文章把Go Routine和调度器的知识讲的浅显易懂，作为一篇介绍性的文章，很不错。

译文

介绍

Go 1.1版本最大的特性之一就是一个新的调度器，由Dmitry Vyukov贡献。这个新的调度器为并行Go程序带来了令人激动、无以后继的性能提升，我觉得我应该为之写点什么东西。

这篇博客的大部分内容都已经在这篇原始设计文档中描述过了，这是一份相当好理解的文章，但是略显技术性。

虽然该设计文档已经包含了关于新调度器你所需要知道的一切，但本篇博文包含图片，所以很明显它略胜一筹。

为什么Go运行时需要一个调度器

在我们研究这个新调度器之前，我们需要搞清楚为什么需要它，为什么要制造一个用户空间的调度器，即使操作系统已经能为你调度线程。

POSIX线程API很大程度上是现有UNIX进程模型的逻辑扩展，线程拥有许多与进程相同的控制。线程有自己的信号掩码，可以设置CPU亲和力，可以被分组到cgroups，也可以查询它们使用了哪些资源。所有这些控制因为一些Go语言使用Goroutine时并不需要的特性而增加了开销，并且当你的程序有10万个线程时这些开销就快速叠加起来。

另一个问题是操作系统无法做出通知的调度决策，基于Go的模型。比如，Go的垃圾收集器需要在收集时所有线程都停止，并且内存需要处于一致的状态。这涉及到等待运行中的线程达到我们所知的内存一致的点。

当你有很多线程需要随机调度的时候，很大的可能性你需要等待许多线程已达到一致的状态。Go的调度器可以做出决策，只在当他知道内存已经一致的时候进行调度。这意味着当我们因为垃圾收集而停下来时，我们只需要等待那些正在CPU内核中运行的线程。

我们的角色

线程通常有3种模型：一个是N:1模型，该模型中多个用户线程运行在一个内核线程中，这种模型的好处在于上下文切换非常快，但是无法充分利用多核线程。另一个是1:1模型，其中一个执行线程对应一个系统线程，该模型充分利用机器上的多个核心，但是上下文切换很慢，因为需要陷入内核。

Go采用M:N的模型，尝试取两者的长处。它在任意数量的系统线程上调度任意数量的用户线程，这样你不仅可以获得很快的上下文切换，也可以充分利用你系统的多核。这种方式的主要缺点是给调度器带来的复杂性。

为了完成调度的任务，Go调度器使用到了3个实体：

三角形表示系统线程，它由操作系统管理的，行为很像POSIX线程。在运行时代码中，它被称为M（Machine，机器）。
圆圈表示一个goroutine。它包含了栈，指令指针，以及其他对调度goroutine很重要的信息，例如其阻塞的channel。在运行时代码中，称作G。
矩形表示调度的上下文。你可以把它看成是在单个线程中运行Go代码的调度器的本地版本。它是让我们从N:1调度到M:N调度的重要部分。在运行时代码中，称作P（Processor，处理器）。

图中我们看到有2个线程（M），每个线程都持有一个上下文（P），每个上下文都运行着一个goroutine（G）。为了运行goroutines，每个线程都必须持有一个上下文。

上下文的数量是在启动时被设置为环境变量GOMAXPROCS的值，或者通过运行时调用函数GOMAXPROCS()进行设置。一般来说，这个值在程序运行过程中不会改变。上下文数量固定意味着任意时刻只有GOMAXPROCS个线程在运行go代码。我们可以利用这一点根据不同机器调节go进程的调用，例如在4核的CPU上用4个线程运行go代码。

灰色的goroutine是没在运行中的，但等待着被调度。它们被安排在一个称为runqueues的列表中，当一个goroutine执行go表达式时，goroutines被添加到列表的末尾。当一个上下文运行goroutine到调度点时，它从它的runqueues中弹出一个goroutine，设置栈和指令指针，然后开始执行这个goroutine。

为了打破互斥，每个上下文有自己的本地runqueues。前一个版本的go调度器只有一个全局的runqueues以及一个互斥锁来保护它。线程经常被阻塞，等待互斥锁释放接触阻塞。如果你的机器有32个核心，这将变得非常低效。

只要所有上下文都有goroutine可以执行，go的调度器就会按照这种稳定的状态进行调度。然而，存在几种例外的情况。

你要（系统）调用谁？

现在你可能会好奇，到底为什么要上下文？难道我们不能抛弃上下文，直接把runqueues放在线程上吗？不尽然。我们之所以需要上下文，是因为我们可以在当前运行中的线程需要阻塞时把上下文交给其他线程。
需要阻塞的一个例子是我们进行系统调用。由于线程不能既执行代码又阻塞于系统调用，我们需要交接上下文，以继续进行调度。

上图我们可以看到，一个线程放弃了它的上下文，好让其他线程可以运行之。调度器保证有足够的线程来运行所有上下文。插图中的M1可能刚刚被创建，用于处理这个系统调用，或者它来自于线程缓存。执行系统调用的线程会继续持有产生系统调用的goroutine，因为从技术上讲它扔在执行，只是阻塞在操作系统中了。

当系统调用返回时，线程必须尝试获得上下文，才得以继续运行返回的goroutine。通常的操作模式从其他线程那偷取一个上下文。如果偷取失败，它会把goroutine放到全局的runqueue，将自己进入线程缓存然后睡眠。

当上下文的本地runqueue为空时，就会到全局的runqueue去拉取。上下文也会定期检查全局runqueue，否则全局runqueue中的goroutine可能永远都不能执行最终饿死。

偷取工作

系统的稳定状态改变的另一种情况是当其中一个上下文的runqueue为空，没有goroutine可以调度。这在上下文之间的runqueues不平衡的情况下可能发生。这可能导致上下文耗尽其runqueue而系统仍然有工作要完成。为了继续执行go代码，上下文可以从全局runqueue中获取goroutine，但是如果其中没有goroutines，上下文就需要从别的地方获取。

所谓别的地方即是其他的上下文。当一个上下文耗完其goroutines时，它会从另外一个上下文偷取一半的goroutine。这保证了每个上下文总是有活儿可以干，从而保证了所有线程都以其最大的能力工作着。