这是三部分系列中的第一篇文章,它将提供对Go中调度程序背后的机制和语义的理解。本文重点介绍操作系统调度程序。

三部分系列的索引：

1. Go中的调度：第I部分 - OS调度程序
2. Go中的调度：第II部分 - Go Scheduler
3. Go中的调度：第III部分 - 并发

介绍

Go调度程序的设计和行为使你的多线程Go程序更高效,更高效。这要归功于Go调度程序对操作系统（OS）调度程序的机械支持。但是,如果多线程Go软件的设计和行为与调度程序的工作方式没有机械上的支持,那么这一切都不重要。了解OS和Go调度程序如何正确设计多线程软件非常重要。

这篇由多部分组成的文章将重点介绍调度程序的更高级别的机制和语义。我将提供足够的详细信息,以便你可以看到工作原理,以便你做出更好的工程决策。尽管你需要为多线程应用程序做出很多工程决策,但是机制和语义构成了你所需的基础知识的关键部分。

OS Scheduler

操作系统调度程序是复杂的软件。他们必须考虑他们运行的硬件的布局和设置。这包括但不限于存在多个处理器和内核,CPU缓存和NUMA。没有这些知识,调度程序就不能尽可能高效。最棒的是,你仍然可以开发一个关于操作系统调度程序如何工作的良好心理模型,而无需深入研究这些主题。

你的程序只是一系列需要依次执行的机器指令。为了实现这一点,操作系统使用处理的概念。线程的工作是考虑并顺序执行它分配的指令集。执行继续,直到没有更多的线程执行指令。这就是我称之为“执行之路”的线程的原因。

你运行的每个程序都会创建一个处理器,并为每个处理器提供一个初始线程。线程可以创建更多的线程。所有这些不同的线程彼此独立地运行,并且调度决策在线程级别进行,而不是在进程级别。线程可以同时运行（每个线程在单个核心上转向）,也可以并行运行（每个线程在不同的核心上同时运行）。线程还保持自己的状态,以允许安全,本地和独立执行其指令。

如果存在可以执行的线程,则OS调度程序负责确保核心不空闲。它还必须创建一个错觉,即可以执行的所有线程同时执行。在创建这种错觉的过程中,调度程序需要运行优先级高于低优先级线程的线程。但是,具有较低优先级的线程不能缺乏执行时间。调度程序还需要通过快速而明智的决策尽可能地最小化调度延迟。

为实现这一目标,很多算法都要考虑到这一点,但幸运的是,该行业能够利用数十年的工作和经验。为了更好地理解所有这些,最好描述和定义一些重要的概念。

执行指令

该程序计数器（PC）,有时被称为指令指针（IP）,就是允许的线程来跟踪下一个执行指令的。在大多数处理器中,PC指向下一条指令而不是当前指令。

如果你曾经看过Go程序的堆栈跟踪,你可能已经注意到每行末尾的这些小十六进制数字。寻找+0x39和+0x72清单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值。该+0x39PC的偏移量代表的下一个指令线程将内部已经执行example的功能,如果该方法没有panic。在0+x72PC偏移值是内部的下一个指令main功能,如果控制正巧回到那个功能。更重要的是,该指针之前的指令会告诉你正在执行的指令。

查看清单2中的程序,该程序导致清单1中的堆栈跟踪。

清单2

1
2
3
4
5
6
7
8
9

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函数内部指令的PC偏移量,该指令比函数的起始指令低57（基数10）字节。在下面的清单3中,你可以看到一个objdump对的example从二元函数。找到第12条指令,它在底部列出。注意该指令上面的代码行是对它的调用panic。

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是下一条指令,而不是当前指令。清单3是基于amd64的指令的一个很好的例子,该Go程序的Thread负责顺序执行。

线程状态

另一个重要的概念是线程状态,它规定了调度程序对线程所采用的角色。线程可以处于以下三种状态之一：等待,可运行,执行。

• 等待：这意味着线程停止并等待某些东西才能继续。这可能是因为等待硬件（磁盘,网络）,操作系统（系统调用）或同步调用（原子,互斥）等原因。这些类型的延迟是性能不佳的根本原因。

• 可运行：这意味着线程需要时间在核心上,以便它可以执行其分配的机器指令。如果你有很多需要时间的线程,那么线程必须等待更长时间才能获得时间。此外,随着更多线程争用时间,缩短了任何给定线程获得的单独时间量。这种类型的调度延迟也可能是性能不佳的原因。

• 执行：这意味着线程已被放置在核心上并正在执行其机器指令。与应用程序相关的工作即将完成。这是每个人都想要的。

工作类型

线程可以执行两种类型的工作。第一个称为CPU绑定,第二个称为IO绑定。

• CPU绑定：这是永远不会创建线程可能处于等待状态的情况的工作。这是不断进行计算的工作。计算Pi到第N位的线程将是CPU绑定的。

• IO绑定：这是导致线程进入等待状态的工作。这项工作包括请求通过网络访问资源或将系统调用进入操作系统。需要访问数据库的线程将是IO绑定。我将包括同步事件（互斥,原子）,导致线程等待此类别的一部分。

上下文切换

如果你在Linux,Mac或Windows上运行,则运行在具有抢占式调度程序的操作系统上。这意味着一些重要的事情。首先,它意味着调度程序在任何给定时间选择运行什么线程时都是不可预测的。线程优先级与事件一起（如在网络上接收数据）使得无法确定调度程序将选择执行什么操作以及何时执行操作。

其次,这意味着你必须永远不要根据你有幸经历的一些感知行为编写代码,但不能保证每次都能发生。很容易让自己思考,因为我已经看到过这种情况发生了1000次,这是有保障的行为。如果在应用程序中需要确定性,则必须控制线程的同步和编排。

在核心上交换线程的物理行为称为上下文切换。当调度程序从核心拉出执行中的线程并用可运行的线程替换它时,就会发生上下文切换。从运行队列中选择的线程进入执行状态。被拉出的线程可以移回可运行状态（如果它仍然具有运行能力）,或者进入等待状态（如果由于IO绑定类型的请求而被替换）。

上下文切换被认为是昂贵的,因为在核心上交换线程需要花费很多时间。在上下文切换期间存在的等待时间量取决于不同的因素,但是它在~1000和~1500纳秒之间花费是不合理的。考虑到硬件应该能够合理地执行（平均）每个核心每纳秒12条指令,上下文切换可能需要大约12k到18k的延迟指令。实质上,你的程序在上下文切换期间失去了执行大量指令的能力。

如果你有一个专注于IO绑定工作的程序,那么上下文切换将是一个优势。一旦线程进入等待中状态,另一个处于可运行状态的线程就可以取代它。这使得核心始终可以正常工作。这是调度的最重要方面之一。如果有工作（处于可运行状态的线程）,则不允许内核空闲。

如果你的程序专注于CPU绑定工作,那么上下文切换将成为性能的噩梦。由于Thead总是有工作要做,因此上下文切换正在停止这项工作的进展。这种情况与IO绑定工作负载的情况形成鲜明对比

少即是多

在处理器只有一个核心的早期阶段,调度并不过分复杂。因为你有一个单核处理器,所以在任何给定时间只能执行一个线程。我们的想法是定义一个调度程序周期并尝试在该段时间内执行所有Runnable线程。没问题：采用调度周期并除以需要执行的线程数。

例如,如果你将调度程序周期定义为10毫秒（毫秒）并且你有2个线程,则每个线程各获得5毫秒。如果你有5个线程,每个线程各获得2ms。但是,当你有100个线程时会发生什么？为每个线程提供10μs（微秒）的时间片不起作用,因为你将在上下文切换中花费大量时间。

你需要的是限制切片的短时间。在最后一种情况下,如果最小时间片是2ms并且你有100个线程,则调度程序周期需要增加到2000ms或2s（秒）。如果有1000个线程,现在你正在查看20秒的调度期间。如果每个线程使用其全时间片,则在此简单示例中所有线程运行一次需要20秒。

请注意,这是一个非常简单的世界观。在制定调度决策时,调度程序需要考虑和处理更多事情。您可以控制在应用程序中使用的线程数。当需要考虑更多的线程,并且发生IO-Bound工作时,会出现更多混乱和不确定行为。事情需要更长的时间来安排和执行。

这就是为什么游戏规则是“少即是多”。可运行状态中较少的线程意味着较少的调度开销和每个线程随时间推移的更多时间。处于可运行状态的更多线程意味着每个线程随时间变化的时间更短。这意味着你的工作也会随着时间的推移完成。

找到平衡点

你需要在你拥有的核心数量和获得应用程序最佳吞吐量所需的线程数之间找到平衡点。在管理这种平衡时,线程池是一个很好的答案。我将在第二部分告诉你,Go不再需要这个。我认为这是Go为使多线程应用程序开发更容易做的好事之一。

在Go编码之前,我用C ++编写代码,用NT编写C＃。在该操作系统上,使用IOCP（IO完成端口）线程池对于编写多线程软件至关重要。作为工程师,你需要确定所需的线程池数量和任何给定池的最大线程数,以最大化你给定的核心数量的吞吐量。

在编写与数据库通信的Web服务时,每个核心3个线程的神奇数量似乎始终在NT上提供最佳吞吐量。换句话说,每个内核3个线程最小化了上下文切换的延迟成本,同时最大化了内核上的执行时间。在创建IOCP线程池时,我知道在主机上识别出的每个核心都至少有1个线程和最多3个线程。

如果我每个核心使用2个线程,则需要更长时间才能完成所有工作,因为我有空闲时间可以完成工作。如果我每个核心使用4个线程,它也需要更长的时间,因为我在上下文切换中有更多的延迟。无论出于何种原因,每个核心3个线程的平衡似乎总是在NT上的神奇数字。

如果你的服务正在进行许多不同类型的工作,该怎么办？这可能会产生不同且不一致的延迟。也许它还会创建许多需要处理的不同系统级事件。可能无法找到一直适用于所有不同工作负载的幻数。当使用线程池来调整服务的性能时,找到正确的一致配置会变得非常复杂。

缓存行

从主存储器访问数据具有如此高的延迟成本（约100至约300个时钟周期）,处理器和内核具有本地高速缓存以使数据保持接近需要它的硬件线程。从高速缓存访​​问数据的成本要低得多（约3到约40个时钟周期）,具体取决于所访问的高速缓存。今天,性能的一个方面是关于如何有效地将数据导入处理器以减少这些数据访问延迟。编写改变状态的多线程应用程序需要考虑缓存系统的机制。

使用高速缓存行在处理器和主存储器之间交换数据。高速缓存行是在主存储器和高速缓存系统之间交换的64字节内存块。每个核心都有自己需要的任何缓存行的副本,这意味着硬件使用值语义。这就是为什么多线程应用程序中的内存突变会造成性能噩梦的原因。

当并行运行的多个线程访问相同的数据值或甚至是彼此接近的数据值时,它们将访问同一缓存线上的数据。在任何核心上运行的任何线程都将获得其自己的同一缓存行的副本。

如果给定核心上的一个线程对其高速缓存行的副本进行了更改,那么通过硬件的能力,同一高速缓存行的所有其他副本都必须标记为脏状态。当线程尝试对脏缓存行进行读或写访问时,需要主存储器访问（约100到约300个时钟周期）来获取缓存行的新副本。

也许在2核处理器上这不是什么大问题,但是并行运行32个线程的32核处理器在同一个缓存线上访问和改变数据呢？具有两个物理处理器的系统如何,每个处理器有16个核心？由于处理器到处理器通信的延迟增加,情况会更糟。该应用程序将通过内存进行颠簸,性能将变得非常糟糕,而且很可能,你将无法理解为什么。

这称为缓存一致性问题,并且还引入了诸如错误共享之类的问题。在编写将改变共享状态的多线程应用程序时,必须考虑缓存系统。

调度决策场景

想象一下,我已经要求你根据我给你的高级信息编写OS调度程序。想想你必须考虑的这种情况。请记住,这是调度程序在做出调度决策时必须考虑的许多有趣的事情之一。

启动应用程序并创建主线程并在核心1上执行。当线程开始执行其指令时,正在检索缓存行,因为需要数据。Thread现在决定为某些并发处理创建一个新的Thread。这是个问题。

一旦创建了Thread并准备好了,调度程序应该是：

1. 上下文切换核心1的主线程？这样做有助于提高性能,因为这个新线程需要相同的数据已经被缓存的可能性非常大。但主线程没有得到它的全部时间片。

2. 是否等待核心1在主线程的时间片完成之前可用？线程未运行,但一旦启动,将取消获取数据的延迟。

3. 让线程等待下一个可用的核心？这将意味着将刷新,检索和复制所选核心的高速缓存行,从而导致延迟。但是线程会更快地启动,主线程可以完成其时间片。

玩得开心吗？这些是OS调度程序在做出调度决策时需要考虑的有趣问题。对每个人来说幸运的是,我不是那个制作它们的人。我可以告诉你的是,如果有空闲核心,它将会被使用。你希望线程在运行时运行。

结论

这篇文章的第一部分提供了在编写多线程应用程序时对线程和OS调度程序必须考虑的内容的见解。这些是Go调度程序也考虑到的事情。在下一篇文章中,我将描述Go调度程序的语义以及它们如何与此信息相关。最后,你将通过运行几个程序来看到所有这些。

原文:

1) Scheduling In Go : Part I - OS Scheduler
2) Scheduling In Go : Part II - Go Scheduler
3) Scheduling In Go : Part III - Concurrency