Go 语言调度（一）: 系统调度

调度相关的一系列文章主要参考 Scheduling In Go : Part I - OS Scheduler 翻译来的。
因为在学习的过程中偶然发现，感觉总结得蛮好的，就不造轮子了，干脆直接翻译过来作为自己的学习笔记了，英文好的建议直接阅读原文。

Go 调度器使你编写的 Go 程序并发性更好，性能更高。这主要是因为 Go 调度器很好的运用了系统调度器的机制原理。但是，如果你不了解调度器基本的工作原理，那你写的 Go 服务很可能对调度器很不友好，使得 Go 调度器发挥不出它的优势。想要正确的设计一个优秀的高并发服务，对操作系统和 Go 的调度机制的一定的理解是很重要的。
这一系列的文章主要专注在调度器的一些宏观机制上。我会形象化的详细解释它是如何工作的，使你可以在编码时做出更好的工程判断。尽管在并发编程中你还有很多其他知识点要了解，但在调度器的机制是其中比较基础的一部分。。

操作系统调度

操作系统调度器是软件开发中很复杂的一块。他们必须考虑硬件设施的布局和设计。这其中就包括了多处理器和多核的存在，CPU 缓存和 NUMA。没有这些知识，调度器就无法达到高效。庆幸的是，你仍然可以通过构造一个宏观的心理模型来理解操作系统调度程序的工作原理，而无需深入研究这一主题。

你的程序其实就是一堆需要按照顺序一个接一个执行的机器指令。为此，操作系统使用了一个线程的概念。线程的工作就是按顺序执行分配给它的指令集，直到没有指令可以执行了为止。

你运行的每一个程序都会创建一个进程，并且每一个进程都会有一个初始线程。线程拥有创建更多线程的能力。这些不同的线程都是独立运行的，调度策略都是在线程这一级别上的，而不是进程级别（或者说调度的最小单元是线程而不是进程）。线程是可以并发执行的（轮流使用同一个核），或并行（每个线程互不干扰的同时在不同的核上跑）。线程还维护这他们自己状态，好保证安全、隔离、独立的执行自己的指令。

系统调度器负责保证当有线程可以执行时，CPU 是不能处于空闲状态的。它还必须创建一个所有线程同时都在运行的假象。在创造这个假象的过程中，调度器需要优先运行优先级更高的线程。但是低优先级的线程又不能被饿死（就是一直不被运行）。调度器还需要通过快速、明智的决策尽可能的最小化调度延迟。

这方面有很多种算法，不过幸运的是，这方面有行业里数十年的工作经验可以参考。

Program counter(PC)，有时候也被叫做指令指针(instruction pointer, 简称IP)，线程用它来跟踪下一个要执行的指令。在大多数处理器中，PC 指向的是下一个指令，而不是当前指令。

如果你曾经看过 Go 程序的 stack trace，你可能注意到了每行的最后都有一个 16 进制数字。比如 +0x39和0x72。

goroutine 1 [running]:
   main.example(0xc000042748, 0x2, 0x4, 0x106abae, 0x5, 0xa)
       stack_trace/example1/example1.go:13 +0x39                 <- LOOK HERE
   main.main()
       stack_trace/example1/example1.go:8 +0x72                  <- LOOK HERE

这些数字表示的是 PC 值距离所在函数的顶部的偏移量。0x39 这个 PC 偏移量代表了线程要执行的在 example 函数中的下一个指令（如果程序没有崩溃）。0x72 代表的是程序返回到 main 后，要执行的下一个指令。更重要的是，在这个指针之前的那个指令，表示的是正在执行的指令。

来看一下上述 stack trace 的源代码。

func main() {
    example(make([]string, 2, 4), "hello", 10)
}

func example(slice []string, str string, i int) {
   panic("Want stack trace")
}

16 进制数字 +0x39 代表了距离 example 函数第一条指令后面 57(0x39的10进制值) 字节的那个指令。下面我们通过对二进制文件执行 objdump，来看看这个 example 函数。从下面的汇编代码中找到第 12 条指令。注意上面代码中调用 panic 的那条指令。

$ go tool objdump -S -s "main.example" ./example1
TEXT main.example(SB) stack_trace/example1/example1.go
func example(slice []string, str string, i int) {
  0x104dfa0     65488b0c2530000000  MOVQ GS:0x30, CX
  0x104dfa9     483b6110        CMPQ 0x10(CX), SP
  0x104dfad     762c            JBE 0x104dfdb
  0x104dfaf     4883ec18        SUBQ $0x18, SP
  0x104dfb3     48896c2410      MOVQ BP, 0x10(SP)
  0x104dfb8     488d6c2410      LEAQ 0x10(SP), BP
    panic("Want stack trace")
  0x104dfbd     488d059ca20000  LEAQ runtime.types+41504(SB), AX
  0x104dfc4     48890424        MOVQ AX, 0(SP)
  0x104dfc8     488d05a1870200  LEAQ main.statictmp_0(SB), AX
  0x104dfcf     4889442408      MOVQ AX, 0x8(SP)
  0x104dfd4     e8c735fdff      CALL runtime.gopanic(SB)
  0x104dfd9     0f0b            UD2              <--- LOOK HERE PC(+0x39)

另一个重要的概念就是线程状态，它决定了线程在调度器中的角色。一个线程有 3 中状态：阻塞态、就绪态和运行态。

译者注：实际情况中不止这 3 个，阻塞也分可中断和不可中断 2 种，此外还有僵尸态、初始化状态等。
但如作者所说，我们只是在宏观上建立一个简单心理模型来理解调度原理，不深入细节。

阻塞态：表示线程已经停止，需要等待一些事情发生后才可继续。这有很多种原因，比如需要等待硬件（磁盘或网络），系统调用，或者互斥锁（atomic, mutexes）。这类情况导致的延迟，往往是性能不佳的根本原因。

译者注：如果你发现，机器的 CPU 利用率很低，同时程序的 QPS 还很低，待处理的请求还有很多堆在后面，速度就是上不去。那说明你的线程都处于阻塞态等待被唤醒，没有干活。

就绪态：这代表线程想要一个 CPU 核来执行被分配的机器指令。如果你有很多个线程需要 CPU，那么线程就不得不等待更长时间。此时，因为许多的线程都在争用 CPU，每个线程得到的运行时间也就缩短了。

运行态：这表示线程已经被分配了一个 CPU 核，正在执行它的指令。与应用相关的工作正在被完成。这是每个人都想要的状态。

线程的工作有 2 种类型的负荷。第一种叫做 CPU密集型，第二种叫 IO密集型。

CPU密集：处理这种工作的线程从来不会主动进入阻塞态。它一直都需要使用 CPU。这种工作通常都是数学计算。比如计算圆周率的第 n 位的工作就属于 CPU密集型的工作。

IO密集：这种工作会使得线程进入阻塞态。常见于通过网络请求资源，或者进行了系统调用。一个需要访问数据库的线程属于 IO密集的。互斥锁的使用也属于这种。

上下文切换

Linux，Mac 或者 Windows 系统上都拥有抢占式调度器。这表明了很重要的几点。

第一，线程何时被调度器选中，被分配 CPU 时间片是不可预测的。线程的优先级和事件同时都会对调度结果有影响，这导致你不可能确定调度去什么时候能调度你的线程。

译者注：你动一下鼠标，敲一下键盘，这些动作都会触发 CPU 的中断响应，也就是事件。这都会对调度器的结果产生影响的，所以说它是不可预测的。

第二，这表明了，你绝不能凭感觉来写代码，因为你的经验不能保证总是应验。人是很容易平感觉下定论的，同样的事情反复出现了上千次，就认为它是百分百的。如果你想要有百分百的确定性，必须在线程中使用互斥锁。

在同一个 CPU 核上交换线程的行为过程，称为上下文切换。上下文切换发生时，调度器把一个线程从核上拿下来，把另一个就绪态的线程放到核上。从就绪队列中选中的这个线程，就这样被置成了运行态。而被从核上拿来下的那个线程，被置为就绪态（如果它仍然可以被执行），或者进入阻塞态（如果它是因为执行了 IO 操作才被替换的）。

上下文切换是昂贵的，因为在一个核上交换线程需要时间片。上下文切换造成的计算损失受很多因素影响，一般是 50 到 100 纳秒左右。
假设一个 CPU 核平均每纳秒可执行 12 个机器指令，一次上下文切换要执行 600 到 1200 条指令，那么本质上，你的程序在上下文切换期间丢失了可以执行大量指令的机会。

如果你有一个 IO 密集的工作，那么上下文切换会有一定的优势。一旦一个线程进入了阻塞态，另一个就绪态的线程就可以立马执行。这使得 CPU 一直都在工作。这是调度中最重要的目标，就是如果有线程可执行（处于就绪态），就不能让 CPU 闲着。

如果你的程序是 CPU 密集的，那么上下文切换将会是性能的噩梦。因为线程总是有指令要执行，而上下文切换中断了这个过程。这与 IO 密集型的工作形成了鲜明的对比。

在早期，CPU 只有单核的。调度也就没那么复杂。因为你只有一个单核 CPU。在任意一个时间点，只有一个线程可以运行。有一种轮询调度的方法，它尝试对每个就绪态的线程都执行一段时间。使用调度周期，除以线程总数，就是每个线程应该执行的时间。

比如，如果你定义你的调度周期是 10 毫秒，现在有 2 个线程，那么在一个调度周期内，每个线程可以执行 5 毫秒。如果你有 5 个线程，那么每个线程可以执行 2 毫秒。但是，如果你有 1000 个线程呢？每个线程执行 10 微妙是没有意义的，因为你大部分时间都花在了上下文切换上。

这时你就需要限制最短的执行时间应该是多少。在上面的那个场景中，如果最短的执行时间是 2 毫秒，同时你有 100 个线程，那么调度周期就需要增加到 2000 毫秒（2秒）。如果你有 1000 个线程，调度周期就要变成 20 秒。这个简单的例子中，一个线程要等 20 秒才能执行一次。

要知道这我们只是举了最简单调度场景。实际上调度器在做调度策略时需要考虑很多事情。这是你应该会想到一个常见并发手段，就是线程池的使用。让线程的数量在控制之内。

所以游戏规则就是『少即是多』，越少的就绪态线程意味着越少的调度工作，每个线程就会得到更多的时间。越多的就绪态线程意味着每个线程会得到越少的时间，也就意味着同一时间你能完成的工作越少（其他的 CPU 时间都被操作系统拿去做调度用了）。

你需要在 CPU 核数和线程数量上寻找一个平衡，来使你的应用能够拥有最高的吞吐。当需要维持这个平衡时，线程池是一个最好的解决方案。在下一篇文章中我会想你展示，在 Go 语言中根本不需要线程池。我认为 Go 语言最优秀的一点就是，它使得并发编程更简单了。

在写 Go 之前，我使用 C++ 和 C# 在 NT 上开发。在那个操作系统上，主要是使用 IOCP 线程池来完成并发编程的。作为一个工程师，你需要指定需要多少线程池，每个线程池的最大线程数是多少，来保证在固定核上达到最高的性能。

当写 web 服务的时候，需要和数据库打交道，每核 3 个线程的配置，似乎总能在 NT 平台上德奥最高的吞吐量。换句话说，就是每核 3 个线程可以使上下文切换的代价最小，从而最大化线程的执行时间。

如果配置每核只用 2 个线程，它会花费更多时间把工作完成，因为 CPU 会经常处在空闲状态。如果我一个核创建 4 个线程，它也会花费更长时间，因为上下文切换的代价会升高。每核 3 个线程的平衡，总是能得到最好的结果，不知道什么原因，它就是个魔法数字。

那如果你的服务的即有 CPU 密集的工作也有 IO 密集的工作呢？这可能会产生不同类型的延迟。这种情况就不太可能找到一个魔法数字来适用于所有情况。当使用线程池来调整服务的性能时，找到一个正确的一致配置是很复杂的。

Cache Line

访问主内存中的数据是有很高延迟的。大约 100 ~ 300 个时钟周期。所以 CPU 往往都会有一个本地 cache，使得数据距离需要它的线程所在的核更近。访问 cache 中的数据是很快的，和访问寄存器差不多。今天，性能优化中很重要的一部分就是怎么才能让 CPU 更快的得到数据，来减少数据访问的延迟。写多线程应用时面对状态异变问题时，需要考虑 cache 系统的机制。

cache line 是 cache 与主内存交换数据的最小单位。一个 cache line 是一块 64 字节的内存，用以在主内存和 cache 系统之间交换数据。每个核都有一份它自己所需要数据的拷贝。这就是为什么在多线程应用中，内存异变是导致性能问题的噩梦。因为 CPU Core 上运行的线程变了，不同的线程需要访问的数据不同，cache 里的数据也就失效了。

当多线程并行时，如果他们访问同样的数据，或者相邻很近的数据。他们将会访问同一个 cache line 中的数据。运行这些线程的任何一个核，都会在自己的 cache 上对数据做一份拷贝。也就是说，每个 CPU 核的 cache 中都有同样的一份数据拷贝，这些拷贝对应于内存中的同一块地址。

如果一个核上的线程，对拷贝数据进行了修改，那么硬件会将其他所有核上的 cache line 拷贝都标记为『脏』。当其他核上的线程试图访问或修改这个数据时，需要重新从主内存上拷贝最新的数据到自己的 cache 中。

也许 2 核的 CPU，不会出大问题，但如果是 32 核的 CPU 并行的运行着 32 个线程呢？如果系统有 2 个 CPU ，每个 CPU 有 16 核呢？这更糟糕，因为增加了 CPU 之间的的通信延迟。这个应用将会出现内存颠簸现象，性能会急剧下降，然而你可能都不知道为什么。

调度决策场景

假如现在要求你在以上给出信息的基础上，设计一个系统调度器了。想象一下你需要解决的这种场景。记住，上面所描述的，只是做调度决策时，需要考虑的众多情况之一。

现在假设机器只有一个单核CPU。你启动了应用，线程被创建了并且在一个 CPU 核上运行。随着线程开始执行它的指令，cache line 也开始检索数据，因为指令需要数据。现在线程要创建一个新的线程做一些并发处理。现在的问题是。

线程一旦创建并进入了就绪态，调度器有以下几种选择：

1. 直接进行上下文切换，把主线程从 CPU 上拿掉？
   这是对性能有益的，因为新线程需要同样的数据，而这些数据之前已经存在与 cache 上了。但主线程就不得不把时间片分给子线程了。
2. 让新线程等待主线程执行完它的所有时间片？
   线程没执行，执行时不必从主内存中同步数据到 local cache 了。
3. 让线程等待其他可用核？
   这就意味着被选中的核，要拷贝一份 cache line 中的数据，这会导致一定的延迟。但是新线程会立刻开始执行，主线程也能继续完成自己的工作。

用哪种方式呢？这就是系统调度在做调度决策时需要考虑的一个有趣的问题。答案是，如果有空闲的核，那就直接用。我们的目标是，如果有工作要做，就决不让 CPU 闲着。

文章带你了解了，当编写多线程应用时，关于线程和系统调度器需要考虑的一些事情。这些也是 Go 语言调度器需要考虑的事情。下一篇文章中，我会描述狗语言调度程序的实现，以及它与本篇所述内容的关系。