Goroutine 调度模型

总结一下 goroutine 的原理和调度器。

首先我们先来看一下进程、线程、协程三者的区别:

  • 进程:进程是系统进行资源分配的基本单位,每一个进城都有一个独立的内存空间。
  • 线程:线程是 CPU 调度的基本单位,一个进程可以有多个线程,每个线程可以共享父进程的资源(比如内存)。
  • 协程:协程是一种用户态的轻量级线程,协程间切换只需要保存任务的上下文,没有内核态的开销更轻量级。

当一个线程在执行时,CPU 的所有寄存器中的值、以及线程栈中的内容被称为该线程的上下文。当内核需要切换到另一个线程时,它需要保存当前线程的所有状态,即保存当前线程的上下文,以便在再次执行线程时,能够必得到切换时的状态执行下去。

上下文切换的代价是很高的。上下文切换的延迟取决于不同的因素,大概在在 50 到 100 纳秒之间。考虑到硬件应该能够合理地(平均)在每个核心上每纳秒执行 12 条指令,那么一次上下文切换可能会花费 600 到 1200 条指令的延迟时间。实际上,上下文切换占用了大量程序执行指令的时间。

如果存在跨核上下文切换(Cross-Core Context Switch),可能会导致 CPU 缓存失效。从主存访问数据有很高的延迟成本(大约 100 到 300 个时钟周期),因此处理器核心使用本地高速缓存来将数据保存在需要的硬件线程附近。从缓存访问数据的成本要低得多(大约 3 到 40 个时钟周期)。

Goroutine 非常轻量,Goroutine 上下文切换只涉及到三个寄存器(PC / SP / DX)的值修改。线程的上下文切换则需要涉及模式切换(从用户态切换到内核态)、以及多个寄存器的刷新。Goroutine 内存占用少,线程栈空间通常是 2M,Goroutine 栈空间最小 2K。

GPM

goroutine

  1. 当 Go 程序启动时,默认每个虚拟核心提供一个逻辑处理器(P)。比如检测到 4 核 8 线程的处理器这将告诉 Go 程序有 8 个虚拟核心可用于并行执行系统线程。
  2. 每个 P 都被分配一个系统线程 M 。M 代表机器(machine),它仍然是由操作系统管理的,操作系统负责将线程放在一个核心上执行。这意味着当在我的机器上运行 Go 程序时,有 8 个线程可以执行我的工作,每个线程单独连接到一个 P。
  3. 每个 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,下面将进行分析。

调度器

调度器提供了如下四种调度策略,下面将主要分析一下第三种和第四种策略:

  1. atomic、mutex、channel 调用将导致 Goroutine 阻塞,调度器可以安排一个新的 Goroutine 去运行。而一旦 Goroutine 可以再次运行,它就可以重新排队,并最终在 M 上切换回来。
  2. 如果在 Goroutine 执行 sleep 操作,导致 M 被阻塞了,Go 程序后台有一个监控线程 sysmon,它监控那些长时间运行的 G 任务然后设置可以强占的标识符,别的 Goroutine 就可以抢先进来执行。只要下次这个 Goroutine 进行函数调用,那么就会被强占,同时也会保护现场,然后重新放入 P 的 LRQ 等待下次执行。
  3. 由于网络请求和 IO 操作导致的 Goroutine 阻塞。
  4. 由于同步的系统调用导致的阻塞。

异步调用

Go 程序提供了 NetPoller 来处理网络请求和 IO 操作的问题,通过 kqueue(MacOS),epoll(Linux)或 iocp(Windows)来实现 IO 多路复用。通过使用 NetPoller 进行网络系统调用,调度器可以防止 Goroutine 在进行这些系统调用时阻塞 M。这可以让 M 轮流执行 P 的 LRQ 中其他的 Goroutines,而不需要创建新的 M,有助于减少操作系统上的调度负载。

比如 G1 正在 M 上执行,LRQ 上还有 3 个 Goroutine 等待执行,NetPoller 出于空闲状态。

upload successful

接下来 G1 想要进行网络调用,它被移动到 NetPoller 并且处理异步网络系统调用。然后,M 可以从 LRQ 执行另外的 Goroutine。此时,G2 就被上下文切换到 M 上了。

upload successful

异步网络系统调用由 NetPoller 完成,G1 被移回到 P 的 LRQ 中等待被调用。最大优势是,执行网络系统调用不需要占用 M,NetPoller 使用系统线程执行。

upload successful

同步调用

如果 Goroutine 要执行同步的系统调用比如文件 io 操作,这个时候 NetPoller 无法使用,而进行系统调用的 Goroutine 将阻塞当前 M。使用 CGO 也会阻塞 M。

ps: Windows 确实能够异步进行基于文件的系统调用,从技术上讲,在 Windows 上运行时,可以使用和 Netpool 类似的机制。

下图中 G1 进行文件 io 操作阻塞了 M1。

upload successful

调度器发现 G1 已导致 M1 阻塞,此时,调度器将 M1 与 P 分离,同时也将 G1 带走。然后调度器引入新的 M2 来服务 P。此时,可以从 LRQ 中选择 G2 并在 M2 上进行上下文切换。

upload successful

阻塞的系统调用完成后,G1可以移回 LRQ 并再次由 P 执行。

goroutine-sync

work-stealing

Go 的调度器是一个任务窃取的调度器。我们最不希望的事情是 M 进入等待状态,因为一旦发生这种情况,操作系统就会将 M 从内核切换出去分配给其他线程。这意味着 P 无法完成任何工作,即使队列里有 Goroutine 处于可运行状态也不行,直到 M 被上下文切换回核心。同时任务窃取还有助于平衡所有 P 的 Goroutines 数量,这样工作就能更好地分配和更有效地完成。

看下面的一个例子:这是一个多线程的 Go 程序,其中有两个P,每个P都服务着四个 Goroutine,另在 GRQ 中还有一个单独的 Goroutine。如果其中一个P的所有 Goroutines 很快就执行完了会发生什么?

upload successful

根据规则,P1将窃取P2中一半的 Goroutines,窃取完成后的样子如下:

upload successful

我们再来看一种情况,如果P2完成了对所有 Goroutine 的服务,而 P1 的 LRQ 也什么都没有,会发生什么?

upload successful

P2 完成了所有任务,现在需要窃取一些 Goroutine。首先,它将查看 P1 的 LRQ,但找不到任何 Goroutines。接下来,它将查看 GRQ 在这里它会找到 G9,P2 从 GRQ 手中抢走了 G9 并开始执行。

upload successful

任务窃取的好处在于它使 M 不会闲着,在窃取任务时,M 是自旋的。

参考资料

  1. https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part1.html
  2. https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html
  3. https://rakyll.org/scheduler/
  4. https://segmentfault.com/a/1190000015464889
  5. https://www.cnblogs.com/lxmhhy/p/6041001.html