go语言调度器实现(一)---os调度

go语言最大的卖点在于并发编程,尤其是现在免费的午餐已经结束,这意味着要挖掘硬件的高性能,软件越来越重要.

而易于编写并发程序的go语言,调度器的实现是一关键因素.因此本系列文章希望探索go语言的调度器实现.

将分3篇文章进行讲述,分别是OS调度器,GO调度器以及如何进行并发编程.

介绍

Go调度器的设计和行为能够让Go多线程程序的编写更加高效和具有更高的性能。这要得益于Go调度器的设计深谙OS调度器的工作机制。即使你不了解这些调度机制，对于你设计的Go多线程程序也没有影响，但是，对OS和Go调度器，以及如何编写多线程程序有一个全面和深刻和理解，是十分重要的。

这3篇文章将会关注调度器高层次的工作机制和语义。将通过展示足够的细节让你看到事情是如何进行的，进而让你在设计程序时能够做出更好的决定。尽管在设计多线程程序时你需要做出许多工程上的抉择，但底层的工作机制和语义是基础的关键部分。

OS调度器

操作系统调度器是很复杂的软件模块。它必须考虑其运行的硬件布局和设置。包括多处理器和多核心，CPU缓存和NUMA等等。不了解这些内容，调度器不可能设计的高效。即使你不深入地了解这些主题，你也可以对OS调度器模型有一个好的了解。

你的程序是一系列需要顺序执行的指令。为了执行这些指令，OS使用了线程这个概念。顺序执行分配给它的指令是线程的任务。线程执行指令直到没有更多的指令为止。因此也可以将线程看作“执行的一条路径”。

你运行的每个程序创建一个进程，每个进程创建一个初始线程。线程有能力创建更多的线程。所有这些线程独立的运行，调度发生在线程级别，而不是进程级别（还记得操作系统课本上讲的吗？线程是系统调度的基本单位）。

线程能够并发执行（每个线程在同一个核上各自运行一段时间），也可以并行执行（每个线程运行在不同的核上）。线程持有它们各自的状态用于安全，独立的执行它们的指令。

OS调度器的职责是确保在有线程需要执行时CPU核心不能够空闲。它也必须让人们感觉到所有要执行的线程都在同时执行，同时调度器需要优先运行高优先级的线程。但是，低优先级的线程也不能被“饿死”。调度器还必须快速和聪明的做出决策以保证最小的延迟。

为了做到上述这些，需要用到很多算法，幸运地是，我们能够利用过去几十年行业的相关工作和经验。为了更好地理解这些内容，我们需要描述和定义一些重要的概念。

执行指令

PC寄存器，有时也称为IP，是用于跟踪线程要执行的下一条指令。在大多数处理器上，PC指向下一条指令而不是当前指令。

如果你看过GO程序的栈，你可能会注意到每行结尾处的十六进制数。比如下面的0x39,0x72.

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

这些数值代表了从当前函数顶PC的偏移量。

+0x39代表example函数里如果没有panic将要执行的下一条指令。

+0x72代表了main函数如果从example函数返回将要执行的下一条指令。更重要的是，前一条指令指出了正在执行的指令。

下面是造成产生这个栈的代码:

https://github.com/ardanlabs/gotraining/blob/master/topics/go/profiling/stack_trace/example1/example1.go

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

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

通过objdump查看二进制程序的指令，可以看到下面的第12条指令(最后一条指令)就是距函数头+0x39处的指令。

$ 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) {
  0x104dfa065488b0c2530000000MOVQ GS:0x30, CX
  0x104dfa9483b6110CMPQ 0x10(CX), SP
  0x104dfad762cJBE 0x104dfdb
  0x104dfaf4883ec18SUBQ $0x18, SP
  0x104dfb348896c2410MOVQ BP, 0x10(SP)
  0x104dfb8488d6c2410LEAQ 0x10(SP), BP
panic("Want stack trace")
  0x104dfbd488d059ca20000LEAQ runtime.types+41504(SB), AX
  0x104dfc448890424MOVQ AX, 0(SP)
  0x104dfc8488d05a1870200LEAQ main.statictmp_0(SB), AX
  0x104dfcf4889442408MOVQ AX, 0x8(SP)
  0x104dfd4e8c735fdffCALL runtime.gopanic(SB)
  0x104dfd90f0bUD2              <---这里就是PC(+0x39)

记住：PC是下一条指令，而不是当前的指令。上面的例子是基于amd64架构的GO程序线程的指令序列。

线程状态

另一个重要的概念是线程状态，这是调度器分配给线程的状态。

线程可以处于3种状态：Waiting,Runnable,Executing.

Waiting:线程由于等待一些条件而处于停止状态。比如等待硬件（磁盘，网络），等待系统调用或同步调用（原子操作，锁）。这些类型的延迟是造成低性能的根本原因。

Runnable: 线程期望在某个核上获得CPU时间片以运行分配给它的指令。如果你有许多线程需要获得时间片，线程必须等待更长的时间。同样，当有更多的线程竞争CPU时，每个线程获得的时间片就会减少。这种类型的调度延迟也是造成低性能的原因。

Executing: 这意味着线程已经在某个CPU上执行指令。这是我们都期望的状态。

工作类型

线程有2种类型的工作，一种是CPU密集型，另一种是IO密集型。

CPU密集型: 这种任务从不进入等待状态，处于持续地计算状态，典型的如计算PI值。

IO密集型: 这种任务会导致任务进入等待状态。这种任务通过网络发送请求或通过系统调用陷入内核。需要访问数据库的线程是IO密集型的。另外，需要等待同步事件（锁，原子操作）等的线程也属于这一类。

上下文切换

如果你在Linux,Mac或者Windows上运行程序，那么这些系统的OS是可抢占的。这意味着

• 调度器选择哪个线程在任何时间运行是不可预知的。线程优先级和事件发生的时机（比如网络数据的达到）使预测调度器的行为更加不可能。

• 你的代码不能依赖一些经验来预测调度器的行为，因此这不总是能保证的。如果你需要你的程序有确定的行为你需要编排线程并控制线程的同步。

在CPU核上切换另一个线程执行称为“上下文切换”。当调度器将一个正在执行的线程替换为另外一个可运行的线程时发生“上下文切换”。这时从运行队列里选择一个线程并使之处于执行状态。换下来的线程可能被重新放放运行队列（如果它仍然可以继续运行），也可能处于等待状态（因为I/O请求而被替换）。

“上下文切换”是昂贵的，因为这需要耗费CPU时间。“上下文切换”造成的延时是由不同因素决定的，是不可能预知的。但是平均大约需要1000–1500 ns,如果每个CPU核心每ns能够执行12条指令，那么上下文切换会造成12K到18K的指令延迟。根本上，在上下文切换期间你的程序将损失大量指令执行的能力。

如果你的程序是IO密集型的，那么上下文切换是有利的。一旦一个线程处于等待状态，另外一个处于可运行状态的线程可以执行。这可以使CPU始终处于工作状态。这是调度器一方面的任务，不要让CPU处于空闲状态。

如果你的程序是CPU密集型的，那么上下文切换是性能的噩梦。因为线程总是有工作要做，而线程切换打断了线程。这与IO密集型的任务形成了鲜明的对比。

少即是多

早期的CPU只有一个核心，这时的调度器还不十分复杂。因为一个CPU只有一个核心，同时只有一个线程可能执行。调度器需要定义调度周期，在调度周期内需要执行所有处于运行状态的线程。这很简单：将调度周期除以需要执行的线程数量。

举个例子，如果将调度周期定义10ms而你有2个线程，那么每个线程执行5ms.如果你有5个线程，每个线程执行2ms.但是，如果有100个线程呢？简单的给每个线程10us是不行的，因为你在上下文切换上将会消耗大量的时间。

你需要限制时间片的下限。如果最小时间片限制为2ms，那么调度周期就会变为2000ms，也就是2s.如果有1000个线程，调度周期将会变为20s.那么就需要20s才能将所有线程执行一次，假设所有的线程都需要消耗完时间片。

上面的例子只是一个很简化的例子。真实的调度器需要考虑更多的因素。你需要控制程序中使用的线程数量。当有更多的线程和I/O发生时，就会有更多混乱和不确定的行为发生，就需要更长的时间执行调度。

这就是”少即是多”原则。更少的线程意味着更少的调度开销，每个线程获得的运行时间就更多。越多的线程意味着每个线程获得的运行时间越少，也就意味着你的任务需要更多的时间才能完成。

找到平衡

为了使你的应用程序达到最高吞吐量你需要在CPU个数和线程个数之间找到平衡。这时，线程池是一个很好的选择。我将会在第2篇文章中告诉你GO不需要这个了。我认为这是GO为了使多线程编程更容易而做的一件好事。

使用C++和C#在NT系统上进行开发，使用IOCP线程池是开发多线程软件的关键能力。你需要通过CPU个数来给线程池设置合适的最大线程数量。

当编写与数据库打交道的WEB服务器时，在NT系统上每个CPU核3个线程通常是一个最好的选择。换句话说，每个CPU核3个线程能够最小化“上下文切换”带来的延迟，同时保证每个CPU核有最大的执行时间。当创建一个IOCP线程时，通常为每个CPU核设置最小线程数量为1，最大线程数量为3.

如果每个CPU核使用2个线程，那么完成任务需要花费更多的时间，因为CPU有空闲时间。如果每个CPU核使用4个线程，那么完成任务也需要花费更多的时间，因为“上下文切换”带来了更多的延迟。每个CPU核3个线程是一个平衡点，无论是什么原因，在NT系统上3看起来个是“魔术字”。

如果你的服务在做很多不同种类的工作，那应该如何？可能会产生许多不同和不确定的延时，也可能需要处理很多系统级的事件。这种情况下不太可能找到一个合适的魔术字。当使用线程池来提高系统性能时，找到一个合适固定的配置十分困难和复杂。

Cache Lines

从主存访问数据有很高的延迟（大约100300个时钟周期）。处理器用本地缓存来缓存线程所需的数据。从缓存访问数据消耗较低（约340个时钟周期）。如今，如何提高处理器访问数据的效率来减少延迟是性能优化的重要方面。编写拥有可变状态的多线程程序需要考虑缓存系统的相关机制。

下图是i7处理器的缓存系统示意图

主存和处理器之间通过缓存行来交换数据。一个缓存行是64字节的内存块。每个CPU核心都拥有所需缓存行的拷贝。这就是为什么在多线程程序中可变状态是性能的噩梦。

当多个线程并行访问同样的数据时，或者访问相邻的数据时，它们会访问同一个内存行。在任一CPU核心上的任一线程都会获得同样的缓存行拷贝。这就会产生“伪共享”问题。

如果其中一个线程修改了其内存行拷贝，缓存系统会将所有其它核上的相同内存行拷贝标记为“脏”。当另外的线程要读取或写“脏”的缓存行时，就需要访问主存获取新的内存行拷贝(参考我之前的文章<<SMP缓存一致性>>.
如果其中一个线程修改了其内存行拷贝，缓存系统会将所有其它核上的相同内存行拷贝标记为“脏”。当另外的线程要读取或写“脏”的缓存行时，就需要访问主存获取新的内存行拷贝(参考我之前的文章<<SMP缓存一致性>>.

如果上述情况只发生在2个CPU核心上可能问题还不大，但是如果运行在32个CPU核心上的32线程并行地访问同样的缓存行呢？这时情况就很糟糕了，因此处理器之间的通信会增加大量的延迟。应用程序会在内存上激烈地冲突，性能可能会很差，同时，你可能都无法理解为什么会这样。

这就是“缓存一致性”问题，还有相关的“伪共享”问题。当编写涉及可变状态的多线程程序时，必须考虑缓存系统。

调度决策场景

相像一下，如果你要基于上述知识涉及一个OS调度器。有一种你必须要考虑的场景。记住，这是调度器做出调度决策时需要考虑的很多有趣的问题的其中之一。

你的程序开始运行，主线程被创建并在核1上运行。线程在执行指令，由于数据访问缓存行被填充并使用。这时线程准备创建一个新线程来处理并发问题。那么，问题来了。

新线程创建成功之后，调度器该如何调度它？

1. 将主线程切换出核1？这样做有利于性能提升，因为新线程需要访问同样的数据已经在缓存中了。但是主线程的时间片还未消耗完。
2. 将新线程放到核1的运行队列中等待调度。这样主线程能够用完时间片，新线程所需的数据也在缓存中，但是需要等待。
3. 挑选另外一个可用的核来运行新线程。这意味着缓存行需要重新建立。但是线程可以尽快的运行，同时主线程也可以运行完自己的时间片。

是不是越来越有趣了？OS调度器再做出调度决策时有很多有趣的问题需要考虑。幸运地是，我们不需要考虑这些。我们要知道的就是，如果有CPU核空闲，就要利用它。

总结

这篇文章告诉了你在写多线程程序时如何从线程和OS调度器的视角来考虑问题。这些问题GO调度器也同样也需要考虑。下一篇将介绍GO调度器所提供的语义，届时会和本篇文章介绍的知识有所关联。最后，你将通过编写一系列程序来实际理解这些知识。