【译】Golang中的调度（1）：OS调度器 - OS Scheduler

àì夳堔傛蜴生んèń 2023-06-21 07:29 2阅读 0赞

# 序 #

为了更好理解Go调度器的内在机制，我会以三个部分的内容分别进行阐述，链接如下：

1.  [Golang中的调度（1）：OS调度器 - OS Scheduler][Golang_1_OS_ - OS Scheduler]
2.  [Golang中的调度（2）：Go调度器 - Go Scheduler][Golang_2_Go_ - Go Scheduler]
3.  [Golang中的调度（3）：并发- Concurrency][Golang_3_- Concurrency]

本部分内容主要讨论操作系统层次的调度器工作机制。

# 引言 #

Go调度器能使你的多线程Go应用程序运行得更加有效率，这归功于Go调度器与OS(操作系统)调度器能与硬件上有效地协同工作（Mechanical Sympathy）。然而，如果你的多线程Go应用程序，其设计与运行不能和调度器在硬件上有效地协同，毫无疑问，这样的多线程是程序是失败的。对OS与Go调度器工作机制有一个大致的理解，这有助于你正确地设计多线程程序。

我们将以较高视角（higher-level）来解释调度器的内在机制。我会提供一些例子使你看清调度器的工作流程，这有助你设计更好的程序。尽管当你在设计多线程程序时，你需要考虑很多方面的东西，但调度器是一个非常重要的基础知识，这是你需要掌握的。

# OS调度器 #

操作系统的调度器是非常复杂的。它必须考虑其配套硬件的配置与性能，包括但不限于多处理器、多核、CPU高速缓存（cache memory）、NUMA（Non-Uniform Memory Access），没有这些，调度器无法尽可能的高效工作。值得高兴的是，你无需深入探讨这些主题，仍然可以就调度器的工作方式建立良好的思维模型。

你的程序最终只是一系列的机器指令，它们会被一条接一条的有序执行。为了做到这一点，操作系统使用了线程的概念。线程的工作是按序执行分配给它的指令集，直到没有指令可供这条线程执行，这就是为何我称一个线程为：“一条执行的路径（a path of execution）”

每个单独运行的应用程序都会创建一个进程，而每个进程都会有一个初始线程，线程可以创建更多的线程。所有的线程都是相互之间独立运行的，并且线程的调度是在线程级上，而非进程级。线程能够并发运行（每个线程都在一个内核上打开），或者并行运行（每个线程同时运行在不同的内核上）。线程同时维护着它的状态（用于安全与局部性）以及它独占的执行指令集。

OS调度器必须确保当有能被执行的线程时，内核不是空闲状态。它还会创造一种假象，即所有的线程能在同一时间内被执行。在创造这种假象的过程中，调度器会运行优先级更高的线程。但是，优先级相对较低的线程也不会被减少其执行时间。同时，调度器还需要尽可能快速地作出明智的决策来最大程度地减少调度延时（latency）。

要实现这一调度算法，需要考虑的因素很多，幸运地是，随着数十年行业经验的积累，我们所用的算法已很成熟。为了更好的理解调度算法，这里需要描述一些重要的概念。

## *执行指令* ##

程序计数器（Progarm counter-PC），有时又被称为指令指针（Instruction Pointer-IP），是使线程跟踪下一条要执行的指令。在大多数处理器中，程序计数器指的是下一条指令而非当前指令。

图 1 指令指针   [https://www.slideshare.net/JohnCutajar/assembly-language-8086-intermediate][https_www.slideshare.net_JohnCutajar_assembly-language-8086-intermediate]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70][]

如果你曾经看过Go程序的堆栈跟踪，你可能已经注意到在每行末尾有十六进制数字，正如表1输出中的+0x39和+0x72。

表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值偏移量。+0x39PC偏移量指的是若程序不发生panic，当前线程会执行位于example函数内的下一条指令位置。+0x72PC偏移量代表若程序运行返回main函数中，线程将要执行的位于main函数内的下一条指令位置。

现在查看产生上述堆栈输出的代码，如表2所示。

表2:

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 }

十六进制数值+0x39代表的是在example函数内，相较函数起始位置相隔57（基于10进制）字节的指令位置。在表3中，你可以从二进制文件中看到example函数中的objdump。观察位于表3最下面的第12条指令，这条指令之上的代码是调用panic。

表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是指的下一条指令，而非当前指令。表三是运行在amd64之上的一个很好的例子，它表明了负责go程序运行的线程是按顺序执行的。

## *线程状态* ##

另外一个重要的概念是线程状态，它决定了调度器在线程中扮演的角色。一个线程可以是三种状态之一：等待、就绪和运行。

*  等待（waiting）：该状态表明了线程停止，并等待继续运行。这个状态可由以下情况引起：等待硬件响应（磁盘、网络），操作系统（系统调用），同步机制（原子操作，互斥操作）。这些类型的延迟是程序性能不佳的主要原因。
 *  就绪（runnable）：该状态表明线程想要从内核获取运行时间来执行分配其上的机器指令集。如果有大量的线程想要获取运行时间，那么这些线程需要等待更久。而且，随着更多线程争夺时间，任何给定线程获得的时间都将缩短。这种类型的调度延迟也是性能下降的原因。
 *  运行（executing）：该状态表明线程已置于内核上并正在执行其机器指令集。与程序相关的工作正在被执行，这是任何线程都想处于的状态。

## *任务类型* ##

线程所处理的任务可以分为两类。第一类为CPU密集型，第二类为IO密集型。

*  CPU密集型：这种类型的任务从不会造成使当前线程处于等待态的情况。这种任务是不断进行计算的工作，例如计算Pi的值到N位数的任务即是CPU密集型任务。
 *  IO密集型：这种类型的任务会使得线程进入等待态，例如请求某个网络资源或某系统调用。如果某个线程需要获取数据库资源，那么它是IO密集型。我也会将同步操作（原子，互斥）列入此类，因为它的某些策略也会使得线程进入等待态。

## *上下文切换* ##

如果你的程序运行在Linux、Mac或者Windows，那么其OS调度器是抢占式的。这表明了一些重要的特性。首先，这意味着在任何时候调度器会选择哪些线程来运行这是不可预测的。线程优先级和事件（例如从网络上获取数据）使得无法确定调度器将选择执行的线程以及何时执行。

其次，这意味着你不能仅凭一些感觉来进行多线程编程，尽管当前可能幸运的通过了测试，但是这并不能保证每次运行都如你预期的一样。因为这很容易造成一种假象，让自己相信这是一个可靠的程序：我已经以相同的方式运行了上千次。记住，在多线程编程时，你必须确保能有效地控制线程之间的同步与编排。

在一个内核上进行线程交换的行为被称做上下文切换。上下文切换发生在当调度器从内核中取下一个运行态的线程并将一个处于就绪态的线程置上的时候。这个从运行队列中选中并被置上的线程进入了执行状态。被取下的线程可能重新进入了就绪态（如果它还需要执行），或者进入了等待态（如果他是因为一个IO密集型任务而被置换）。

上下文切换的开销是昂贵的，因为它从一个内核上进行线程交换是耗时的。上下文切换期间的等待时间量取决于多种因素，但是它占了1000到1500纳秒，这是不合理的。从物理硬件上考虑，每个内核在每纳秒能够执行12条指令（平均地），一次上下文切换就占据了12k到18k指令集的时延。在本质上，你的程序在上下文切换期间失去了执行大量指令集的能力。

如果你的程序是集中在IO密集型任务，那么上下文切换将是一个优势。一旦某线程进入了等待态，另一个处于就绪态的线程就可接替它继续执行。这可以保证内核总是处于工作中的。这是调度最重要的方面之一：如果有任务需要做（线程处于就绪态），永远不要让内核空闲下来。

如果你的程序是集中在CPU密集型任务，那么上下文切换将会是性能的梦魇。因为线程总是有工作去做，而上下文切换正在阻止工作的进行。这种情况与IO密集型任务形成鲜明对比。

## *少即是多* ##

在早期的时候，处理器只有一个内核，那时的调度还并不是过于复杂。因为你只有单内核的单处理器，在任何时刻只能有一条线程能被执行。那时的做法是定义一个调度周期（scheduler period），并尝试在一个调度周期内执行所有的就绪态线程。方法：将调度周期除以需要执行的线程数。

举个例子，如果你定义你的调度周期为10ms（milliseconds）并且你有2个线程需要执行，那么每个线程可获取5ms，如果你有5个线程需要执行，那么每个线程获取2ms。但是，如果有100个线程呢，那怎么办？如果分配给每个线程10μs（microseconds）的时间片，那将不能工作，因为你会耗费大量的时间在上下文切换上面。

你需要做的事是限制时间片的长度。在上例中，如果最小时间片是2ms而有100个线程需要执行，那么调度周期就需要增加到2000ms，即2s（seconds）。倘使是1000个线程呢，则你需要将调度周期调到20s。在这个简单的例子中，如果每个线程都执行一次，并且每个线程的这次执行都用完了分配给它的时间片，那么让所有线程都执行一次就花费了20s。

请注意，在调度问题上，这只是非常简单的一个情况。调度器在做调度决策时，存在更多的因素需要去考虑与处理。你需要控制的是你程序中的线程数。当需要考虑更多的线程数，或者正在做IO密集型任务，会发生更混乱与不确定的情况。线程需要更长的时间来被调度与执行。

这就是为什么这个游戏的规则叫“少即是多（Less is More）”。少的就绪态线程意味着少的调度开销，每个线程能够获得多的执行时间。多的就绪态线程意味着每个线程获得少的执行时间，这意味着同样的时间开销下，你能完成的工作变得更少。

## *寻找平衡* ##

你需要在拥有的内核数量和为程序获得最佳通量所需的线程数量之间找到一个平衡点。处理这种平衡问题，线程池是一个不错的方案。我会在第二部分的内容中提到线程池，但这并不是Go中所需要的。Go使得开发多线程应用变得更简单，我认为这是Go所做的最酷的事情之一。

在使用Go之前，我在WindowsNT上用C++和C\#编程。在这个操作系统上，使用IOCP（IO Completion Ports）线程池来进行多线程程序的编写是至关重要的。作为一个工程师，你需要评估所需线程池的数量，以及所给线程池的最大线程数，根据当前内核数量，使其通量最大化。

当写一个与数据库打交道的web服务，魔法数字3，是每个内核之上的线程数量，总是能使得在NT上得到最佳通量。换句话说，每个内核上3个线程，能在最大化在内核上执行时间的同时，最小化上下文切换的延时开销。当建立一个IOCP线程池时，我知道在确定的主机上，我会在每个内核上以最小1个线程最大3个线程来执行。

如果在每个内核上2个线程，要完成所有的工作会花费更长的时间，因为有些本来可以用来完成任务的时间却变成了空闲时间。如果我使用4个线程，它同样会花费更长的时间，因为存在了更多的上下文切换的延时开销。每个内核的3个线程变成了一个平衡数据，不管原因到底是啥，它在NT系统上似乎已是一个具有魔法意味的数字。

倘使你的服务正在做大量不同类型的任务呢？这可能会导致差异性与不一致的延时。或许它正在生成大量不同的需要处理的系统级事件，因此在所有不同的任务流中，可能并不能找到一个魔法数字去适应所有的情况。当涉及到使用线程池来调整服务的性能时，找到正确的一致性配置会变得非常复杂。

## *快取线/缓存线（Cache lines）* ##

从主存中直接获取数据有高的延时开销（100-300个时钟周期），因此处理器和内核具有局部缓存（local caches），以使数据保持在需要它的硬件线程附近。从缓存中获取数据延时开销明显变小（3-40个时钟周期），具体大小取决于要获取数据的缓存级别上。在现今，性能优化的一个方面是如何有效地将数据放入处理器以减少数据访问延迟。写多线程程序需要考虑缓存系统的内在机制。

图 2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70 1][]

处理器与主存交换数据是通过快取线完成的。一条快取线是64字节大小的内存块，它用来在主存和缓存系统进行数据交换。每个内核都得到了它所需快取线的副本，这意味着硬件使用的是值语义（value semantics）。这就是在多线程程序中内存突变（mutations to memory）是性能梦魇的原因。

当多线程以并行的形式运行，并且它们要拿相同的数据或数据值相近的数据，那么它们会在同一条快取线上获取数据。运行在任意内核上的任意线程都会从这条快取线上得到它的副本。

图 3

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70 2][]

如果某内核上的某线程要对一条快取线的副本做某个更改，那么通过硬件操作，所有其他对这同一条快取线上的副本会被标记为脏副本。当某个线程尝试通过一个脏副本来进行读写操作，主内存访问（main memory acces）（100-300时钟周期）需要得到一个针对该快取线新的副本。

或许在双核处理器上，这并不是一个大问题。但是，如果是32个线程并行地运行在32核处理器上面，且它们都要在同一个快取线上做访问和更改数据的操作呢？如果系统是两个物理独立的处理器且每个处理器有16个内核呢？由于处理器与处理器之间需要通信所至的额外延时，这会使得问题变得更加糟糕。应用程序会内存崩溃，性能变得十分糟糕，更可能地是，你并不知道为什么会这样。

这个问题被称为缓存一致性问题（cache-coherency problem），并且会引起像错误共享之类的问题。当多线程程序会改变共享状态时，必须考虑上缓存系统机制。

# 调度决策场景 #

假设我让你写一个OS调度器，就基于上述以较高视角给你的信息。思考一个你必须考虑的情况，请记住，这是调度器在做出调度决策时必须考虑的许多有趣的事情之一。

你启动应用程序，创建了主线程且在内核1上执行。主线程开始执行它的指令集，因为需要数据所以取得了快取线。这时，主线程决定创建一个新线程用于并发处理，那么问题来了。

一旦新线程被创建且处于就绪态，这个时候调度器应该考虑：

1.  是否要通过上下文切换将主线程从内核1上取下？这样做可以提高性能，因为这个新线程需要的相同的数据已经在缓存中了，这个时机是非常完美的。但是这样做，主线程就不能得到它全部的时间片了。
2.  是否让这个新线等待主线程时间片的完成？这时内核1变得可用，新线程并未运行，但是一旦启动，获取数据的时延将会消除。
3.  是否让新线程等待下一个可用的内核？这意味着从所选内核的快取线，将进行刷新，获取和复制，从而产生了时延。但是，线程将启动得更快，并且主线程可以完成其时间片。

玩的开心吗？在OS调度器做调度决策时，有很多有趣的问题需要考虑。幸运的是，我们不需要做这些事情。我只能告诉你的是，如果有一个空闲的内核，它将被使用，你希望线程可以在能被运行时运行。

# 结论 #

第一部分的内容，提供了在写多线程程序时必须考虑的有关线程和OS调度器的见解。这些也是Go调度器需要考虑的事项。在下一部分内容中，我将描述Go调度器的机制以及它们如何与该机制相关。最后，运行几个程序，你将看到所有的秘密。

英文原文连接：

[Scheduling In Go : Part I - OS Scheduler][Scheduling In Go _ Part I - OS Scheduler]

[Golang_1_OS_ - OS Scheduler]: https://blog.csdn.net/slphahaha/article/details/103499048
[Golang_2_Go_ - Go Scheduler]: https://blog.csdn.net/slphahaha/article/details/103515573
[Golang_3_- Concurrency]: https://blog.csdn.net/slphahaha/article/details/103886865
[https_www.slideshare.net_JohnCutajar_assembly-language-8086-intermediate]: https://www.slideshare.net/JohnCutajar/assembly-language-8086-intermediate
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191211220831468.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191212153426744.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191212160430743.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ==,size_16,color_FFFFFF,t_70
[Scheduling In Go _ Part I - OS Scheduler]: https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part1.html