理解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

1
2
3
4
5
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

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$ 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),类似需要线程等待的情况y我也归为此类。
上下文切换(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之前,原作者在NT系统上使用C++和c#。在那个操作系统里,使用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系统必须要考虑在内。

调度决策场景

思考一下下面的调度场景。
应用程序启动,主线程已经在core1上启动。当线程正在执行,它为了访问数据需要去检索cache行。主线程现在为了某些并发处理创建一个新的线程。那么问题来了。
一旦线程创建好,并且准备要运行了,那么调度器是否应该:

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

以上都是调度器在做决定时需要考虑到的事情。
结论
这是第一部分,为你提供了一些多线程编程时要考虑到线程和OS调度器的一些理解。这同时也是golang调度器需要考虑的事情。下面一部分,会讲Go调度器的一些相关知识。

原文链接:www.ardanlabs.com/blog/2018/0…

-------------本文结束 感谢阅读-------------