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。

这保证了每一个上下文总是有活儿能够干，从而保证了全部线程都以其最大的能力工作着。