理解golang调度之一 ：操作系统调度

golang调度器的设计行为能够使你的多线程 go 程序更有效率、性能更好，这要归功于golang调度器对于操作系统调度器的支持。对于一个golang开发者来说，同时深刻理解操作系统调度和golang调度器工作原理，能够让你的golang程序设计和开发走到正确道路上。

操作系统调度器

操作系统调度器十分复杂，它必须要考虑到它所运行的底层硬件层级结构，包括但不限于处理器数和内核数，cpu cache和NUMA(非统一内存访问架构)。如果不考虑这些因素，调度器就没办法尽可能有效的工作。好事情是，你不必深入理解这些底层内容也能开发出好的程序。

你的程序其实就是一堆按顺序执行的机器指令。为了能让其正常干活，操作系统使用了线程的概念。线程会处理并执行分配给它的一系列的机器指令。线程会一直执行这些机器指令，直到没有指令再去给线程执行了。这也是为什么把线程称作"a path of execution"。

你运行的每个程序都会创建一个进程并且每个进程都会有一个初始线程。线程能够创建更多的线程。这些不同的线程独立运行并且调度行为是线程级别做决定的，而不是在进程级别。线程能够并发的执行(并发是说一个单独内核上每个线程会轮询占用一段cpu时间),而不是并行执行(在不同内核上同时执行)。线程同时会维持它自己的状态，并且能够在本地安全、独立地执行他自己的指令。这也说明了为什么线程是cpu调度的最小单位。

操作系统调度器，负责确保在有线程能够运行的时候内核不会空闲下来。它必须要制造出这样一种错觉——所有能够跑的线程此时都在同时执行。为了制造这种错觉，调度器需要优先执行高优先级的线程，但是它也必须保证低优先级的线程不会饿死(永远没有执行机会)。调度器也必须通过做出更聪明的决定将调度延时尽可能的压倒最少，。

幸运的是计算机发展了这么长时间，许多算法的应用使得调度器更加高效。为了能够理解上面的事情，需要解释一些重要的概念。

执行指令

程序计数器(PC)，有时候也叫做指令指针(IP)，能够让你找到下一个要执行的指令在哪。大部分的处理器里，PC指向下一个指令，而不是当前的指令。

如果你曾经注意到go程序的追踪栈，你会注意到这些每一行末尾的16进制数字。例如Listing 1里的+0x39和+0x72

Listing 1

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偏移量代表了程序在还未panic的时候，线程在 example 方法执行的下一条指令。+0x72 PC偏移量代表如果 example 函数回到main函数里， main 里的下一条指令。重要的是，指向指令的前一个指针告诉了你现正在执行什么指令

看一下导致Listing 1 panic的程序

Listing 2

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 }
复制代码

十六进制数+0x39代表了PC偏移量，在example函数里也就是距离函数开头57(10进制)bytes的位置。下面的Listing 3里，你可以通过二进制文件看到example函数的 objdump 。找到最下面的第12条指令，注意到是它上面一行的指令导致了 panic

Listing 3

$ 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)
复制代码

注意: PC始终是下一个指令，不是当前指令。Listing 3很好的说明了amd64下面，go线程是如何执行指令序列的。

线程状态

另一个重要概念就是“线程状态”，线程状态说明了调度器该如何处理此时的线程。线程有三个状态:等待、可运行、执行中。

等待(Waiting)：

此时意味着线程停止并且等待被唤醒。可能发生的原因有，等待硬件(硬盘、网络)，操作系统(系统调用) 或者是同步调用(atomic,mutexes)。这些情况是导致性能问题的根源

可运行(Runnable)：

此时线程想要占用内核上的cpu时间来执行分配给线程的指令。如果你有许多线程想要cpu时间，线程必须要等一段时间才能取到cpu时间。随着更多线程争用cpu时间，线程分配的cpu时间会更短。这种情况下的调度延时也会造成性能问题。

执行中(Executing):

此时线程已经置于内核中，并且正在执行它的机器指令。应用程序的相关内容正在被处理。这种状态是我们所希望的

工作类型

线程有两种工作类型。第一种叫CPU密集型，第二种叫IO密集型

CPU密集型(cpu-bound):

这种工作下，线程永远不会被置换到等待(waiting)状态。这种一般是进行持续性的cpu计算工作。比如计算Pi这种的就是cpu密集型工作

IO密集型(io-bound)

这种工作会让线程进入到等待(waiting)状态。这种情况线程会持续的请求资源（比如网络资源）或者是对操作系统进行系统调用。线程需要访问数据库的情况就是IO密集型工作。同时我会把同步事件(例如mutexes、atomic)，这种需要线程等待的情况归入此类工作。

上下文切换(Context Switch)

如果你的程序运行在 Linux 、Mac或者是Windows上面，你的调度器则是抢占式的。这意味着一些重要的事情。第一、它意味着调度器不会预先知道此时此刻会运行哪个线程。线程优先级加上事务(例如接受网络数据)让调度器无法确定哪个时间执行哪个线程。

第二、你永远不能按照历史经验去看，你之前幸运跑出来的代码其实不能保证每次都按你所想去执行。如果你的代码1000次都是按照同样方式执行，你很容易以为下次也保证按照一样方式执行。如果你的程序需要确定性的话，你一定要控制线程的同步和编排。

在内核上切换线程的物理行为叫做上下文切换(context switch)。上下文切换发生在这样的情况，调度器从内核换下正在执行的线程，替换上可执行的线程。线程是从运行队列中取出，并设置成执行中(Executing)的状态。从内核上下来的线程会置成可运行状态,或者是等待状态。

上下文切换的代价是昂贵的，因为它需要花时间去交换线程，从内核上拿下来再放上去。上下文切换的延时受到很多因素影响，但是通常情况下，它会有1000--1500纳秒的延时。考虑到硬件上每个内核上平均每纳秒执行12个指令，一次上下文切换会花费你12k--18k个指令延时。这本质上来说，你的程序在上下文切换过程中失去了执行大量指令的机会。

如果你的程序集中于IO密集型(cpu-bound)的工作，上下文切换会相对有利。一旦一个线程进入到等待(waiting)状态。另一个处于可运行(Runnable)状态的线程会取代它的位置。这会使得内核始终是处于工作状态。这是调度器调度的一个重要方面，如果有事做(有线程处于可运行状态)就不允许内核闲下来。

如果你的程序集中于cpu密集型(cpu-bound)的工作，那么上下文切换会是性能的噩梦。因为线程要一直做事情，上下文切换会停止正在处理的工作。这种情况和IO密集型形工作成鲜明对比。

少即是多(Less Is More)

在早期时候，处理器仅仅只有一个内核，调度器并不十分复杂。因为你有一个单独的处理器，一个单独的内核，所以任何时间只能跑一个线程。方法是定义一个调度期(scheduler period) 然后尝试在一个调度期内去执行所有可运行(Runnable)的线程。这样没问题:把调度期按照需要执行的线程数量去分每一小段。

举例，如果你定义了你的调度期是10ms 并且你有两个线程，那每个线程会分到5ms。5个线程的话，每个线程就是2ms。但是如果你有100个线程会怎么样？每个线程时间片是10us(微秒), 这就会无法工作，因为你需要大量时间去进行上下文切换(context switches)。

在最后一个场景，如果最小的时间切片是2ms 并且你有100个线程，调度期需要增加到2000ms也就是2s。要是如果你有1000个线程呢，现在调度期需要20s，也就是你要花20s才能跑完所有的线程如果每个线程都能跑满它的时间切片。

上面发生的是显而易见的事情。调度器在做决定的时候还要考虑到更多的因素。你控制了应用程序里的线程数量，当有更多线程的时候，并且是IO密集(IO-Bound)工作，就会有更多的混乱和不确定行为发生，调度和执行就花费更多时间。

这也是为什么说游戏规则就是“少即是多(Less is More)”，可运行线程越少意味着调度时间越少，线程得到的时间越多。更多的线程就意味着每个线程获得的时间就越少，分配的时间内做的事情也就越少。

找到平衡点

你需要在内核数量和你的线程数量两者间，找到一个能够让你的程序获得最好吞吐量的平衡点。想要去找到这样的平衡点，线程池是一个很好的选择。

使用go之前，作者使用C++和c#在NT上。在那个操作系统里，使用IOCP(IO Completion Ports) 线程池对于写多线程软件十分重要。作为一个工程师，你需要计算出你要用多少个线程池，以及每个线程池的最大线程数，从而在确定了内核数的系统里最大化你的吞吐量。

当写web服务时候，你需要和数据库通信。3是一个魔法数字，每个内核设置3个线程似乎在NT上有最好的吞吐量。换句话说，每内核3线程能够最小化上下文切换的延时，最大化在内核上的执行时间。当你创建一个IOPC线程池，我知道我可以在主机上设置每个内核1--3个线程数量。

如果我使用2个线程每个内核，完成工作的时间会变长，因为本来需要有工作去做的内核会有空闲时间。如果我每个内核用4个线程，也会花更长时间，因为我需要花更多时间进行上下文切换。平衡数字3，不管是什么原因，似乎在NT上都是一个神奇的数字。

当你的服务需要处理许多不同类型的工作会如何呢。那会有不同并且不一致的延迟。可能它会产生许多需要去处理的不同系统级别的事件。这种情况，你不可能去找到一个魔法数字，能让你在所有时间所有不同的工作情况下都有优秀的性能。当你使用线程池的时候，找到一个合适的配置会十分复杂。

缓存行(Cache Lines)

从主存访问数据有很高的延迟（大概100~300个时钟周期），因此处理器和内核会有缓存，能够让线程访问到更近的数据。从缓存访问数据的延迟非常低(大概3~40个时钟周期) 根据不同的缓存访问方式。衡量性能的一个方面就是，处理器通过减少数据访问延时而获取数据的效率。编写多线程的应用程序需要考虑到机器的缓存系统。

处理器和主存使用缓存行(cache lines)进行数据交换。一个缓存行是一个64 byte的内存块，它在内存和缓存系统之间进行交换。每个内核会分配它自己需要的cache副本，也就是意味着硬件使用的是值语义(区别于指针语义)。这也是为什么多线程中的内存突变会造成严重的性能问题。

当多线程并行运行，正在访问相同数据，甚至是相邻的数据单元，他们会访问相同的缓存行。任何内核上运行的任何线程能够从相同的缓存行获取各自的拷贝。

如果给一个内核，他上面的线程修改它的cache行副本，然后会通过硬件的神奇操作，同一cache行的所有其他副本都会被标记为无效。当一个线程尝试读写无效cache行，主存需要去访问去获取新的cache行副本(大约要100~300个时钟周期)

也许在2核的处理器上这不是大问题，但是如果是一个32核处理器并行跑32个线程，并且同时访问和修改一个相同的cache行呢？由于处理器到处理器之间的通信延迟增加，情况会更糟。程序内存会发生颠簸，并且性能很差，而且很可能你也不知道为什么会这样。

这就是cache的一致性问题（ cache-coherency problem ）或者是说是共享失败（false sharing）。当编写改变共享状态的多线程应用时，cache系统必须要考虑在内。

调度决策场景

想象一下，我已经要求你根据我给你的高级信息编写OS调度程序。 想想你必须考虑的这种情况。

你启动了你的应用程序，主线程已经在core1上启动。当线程正在执行，他需要去检索cache行因为需要访问数据。这个Thread现在决定为了某些并发处理创建一个新的线程。那么问题来了。

一旦线程创建好，并且准备要运行了，那么调度器是否应该:

1. 从core1上换下main主线程？这样做有助于提高性能，因为这个新线程需要的相同数据被缓存的可能性非常大。但是主线程并没有得到它的全部时间片。
2. 线程是否要一直等待直到main主线程完成它的时间后core1可用？线程并没有在运行，但是一旦运行它获取数据的延时将会消除。
3. 线程等待下一个可用的core？这意味着所选择的core的cache行会经历冲刷、检索、复制，从而导致延迟。但是线程会更快的启动，并且主线程会完成它的时间片。

这些都是调度器在做决定时需要考虑到的一些有趣问题。我能告诉你的事情就是，如果有空闲的内核，它将会被使用。你希望当线程能够运行的时候它就会运行。