[笔记] Go 调度器

操作系统调度器

执行指令

程序计数器(PC),有时称为指令指针(IP),线程利用它来跟踪下一个要执行的指令。在大多数处理器中,PC指向的是下一条指令,而不是当前指令。

线程状态

  • 等待中(Waiting):这意味着线程停止并等待某件事情以继续。这可能是因为等待硬件(磁盘、网络)、操作系统(系统调用)或同步调用(原子、互斥)等原因。这些类型的延迟是性能下降的根本原因。
  • 待执行(Runnable):这意味着线程需要内核上的时间,以便执行它指定的机器指令。如果有很多线程都需要时间,那么线程需要等待更长的时间才能获得执行。此外,由于更多的线程在竞争,每个线程获得的单个执行时间都会缩短。这种类型的调度延迟也可能导致性能下降。
  • 执行中(Executing):这意味着线程已经被放置在一个核心上,并且正在执行它的机器指令。与应用程序相关的工作正在完成。这是每个人都想要的。

工作类型

  • CPU-Bound:这种工作类型永远也不会让线程处在等待状态,因为这是一项不断进行计算的工作。比如计算 π 的第 n 位,就是一个 CPU-Bound 线程。
  • IO-Bound:这是导致线程进入等待状态的工作类型。比如通过网络请求对资源的访问或对操作系统进行系统调用。

上下文切换

在核心上交换线程的物理行为称为上下文切换。当调度器将一个正在执行的线程从内核中取出并将其更改状态为一个可运行的线程时,就会发生上下文切换。

寻找一个平衡

你需要在 CPU 核心数和为应用程序获得最佳吞吐量所需的线程数之间找到平衡。当涉及到管理这种平衡时,线程池是一个很好的解决方案。

CPU 缓存

从主存访问数据有很高的延迟成本(大约 100 到 300 个时钟周期),因此处理器核心使用本地高速缓存来将数据保存在需要的硬件线程附近。从缓存访问数据的成本要低得多(大约 3 到 40 个时钟周期),这取决于所访问的缓存。

屏幕快照 2018-10-09 下午4.54.50

cache line是在主存和高速缓存系统之间交换的 64 字节内存块。

当并行运行的多个线程正在访问相同的数据值,甚至是相邻的数据值时,它们将访问同一cache line上的数据。在任何核心上运行的任何线程都将获得同一cache line的副本。

Go 调度剖析

当 Go 程序启动时,它会为主机上标识的每个虚拟核心提供一个逻辑处理器(P)。

每个 P 都被分配一个系统线程 M 。M 代表机器(machine),它仍然是由操作系统管理的,操作系统负责将线程放在一个核心上执行。这意味着当在我的机器上运行 Go 程序时,有 8 个线程可以执行我的工作,每个线程单独连接到一个 P。

每个 Go 程序都有一个初始 G。G 代表 Go 协程(Goroutine),它是 Go 程序的执行路径。Goroutine 本质上是一个 Coroutine,但因为是 Go 语言,所以把字母 “C” 换成了 “G”,我们得到了这个词。你可以将 Goroutines 看作是应用程序级别的线程,它在许多方面与系统线程都相似。正如系统线程在物理核心上进行上下文切换一样,Goroutines 在 M 上进行上下文切换。

最后一个重点是运行队列。Go 调度器中有两个不同的运行队列:全局运行队列(GRQ)本地运行队列(LRQ)。每个 P 都有一个LRQ,用于管理分配给在P的上下文中执行的 Goroutines,这些 Goroutine 轮流被和P绑定的M进行上下文切换。GRQ 适用于尚未分配给P的 Goroutines。其中有一个过程是将 Goroutines 从 GRQ 转移到 LRQ。

协作式调度器

Go 协作式调度器的优点在于它看起来和感觉上都是抢占式的。你无法预测 Go 调度器将会执行的操作。这是因为这个协作调度器的决策不掌握在开发人员手中,而是在 Go 运行时。将 Go 调度器视为抢占式调度器是非常重要的,并且由于调度程序是非确定性的,因此这并不是一件容易的事。

Goroutine 状态

  • Waiting:这意味着 Goroutine 已停止并等待一些事情以继续。这可能是因为等待操作系统(系统调用)或同步调用(原子和互斥操作)等原因。这些类型的延迟是性能下降的根本原因。
  • Runnable :这意味着 Goroutine 需要M上的时间片,来执行它的指令。如果同一时间有很多 Goroutines 在竞争时间片,它们都必须等待更长时间才能得到时间片,而且每个 Goroutine 获得的时间片都缩短了。这种类型的调度延迟也可能导致性能下降。
  • Executing :这意味着 Goroutine 已经被放置在M上并且正在执行它的指令。与应用程序相关的工作正在完成。这是每个人都想要的。

上下文切换

在 Go 程序中有四类事件,它们允许调度器做出调度决策:

  • 使用关键字 go
  • 垃圾回收
  • 系统调用
  • 同步和编配

使用关键字 go

关键字 go 是用来创建 Goroutines 的。一旦创建了新的 Goroutine,它就为调度器做出调度决策提供了机会。

垃圾回收

由于 GC 使用自己的 Goroutine 运行,所以这些 Goroutine 需要在 M 上运行的时间片。这会导致 GC 产生大量的调度混乱。但是,调度程序非常聪明地了解 Goroutine 正在做什么,它将智能地做出一些决策。

系统调用

如果 Goroutine 进行系统调用,那么会导致这个 Goroutine 阻塞当前M,有时调度器能够将 Goroutine 从M换出并将新的 Goroutine 换入。然而,有时需要新的M继续执行在P中排队的 Goroutines。这是如何工作的将在下一节中更详细地解释。

同步和编配

如果原子、互斥量或通道操作调用将导致 Goroutine 阻塞,调度器可以将之切换到一个新的 Goroutine 去运行。一旦 Goroutine 可以再次运行,它就可以重新排队,并最终在M上切换回来。

异步系统调用

当你的操作系统能够异步处理系统调用时,可以使用称为网络轮询器的东西来更有效地处理系统调用。这是通过在这些操作系统中使用 kqueue(MacOS),epoll(Linux)或 iocp(Windows)来实现的。

基于网络的系统调用可以由我们今天使用的许多操作系统异步处理。这就是为什么我管它叫网络轮询器,因为它的主要用途是处理网络操作。通过使用网络轮询器进行网络系统调用,调度器可以防止 Goroutine 在进行这些系统调用时阻塞M。这可以让M执行P的 LRQ 中其他的 Goroutines,而不需要创建新的M。有助于减少操作系统上的调度负载。

同步系统调用

如果 Goroutine 要执行同步的系统调用,会发生什么?在这种情况下,网络轮询器无法使用,而进行系统调用的 Goroutine 将阻塞当前M。这是不幸的,但是没有办法防止这种情况发生。需要同步进行的系统调用的一个例子是基于文件的系统调用。如果你正在使用 CGO,则可能还有其他情况,调用 C 函数也会阻塞M。

任务窃取(负载均衡思想)

调度器的另一个方面是它是一个任务窃取的调度器。这有助于在一些领域保持高效率的调度。首先,你最不希望的事情是M进入等待状态,因为一旦发生这种情况,操作系统就会将M从内核切换出去。这意味着P无法完成任何工作,即使有 Goroutine 处于可运行状态也不行,直到一个M被上下文切换回核心。任务窃取还有助于平衡所有P的 Goroutines 数量,这样工作就能更好地分配和更有效地完成。

线程和 Goroutine区别

使用线程和 Goroutine 之间有一个主要区别:
在使用 Goroutine 的情况下,会复用同一个系统线程和核心。这意味着,从操作系统的角度来看,操作系统线程永远不会进入等待状态。因此,在使用系统线程时的开销在使用 Goroutine 时就不存在了。

资源:

https://segmentfault.com/a/1190000016038785
https://segmentfault.com/a/1190000016611742