Go 调度器

Dec 18, 2020 23:00 · 4314 words · 9 minute read Golang

译文

介绍

在这个调度器系列的第一篇，我之所以解释了操作系统调度器是因为我相信有助于理解 Go 调度器的机制。在这篇博客中，我会进一步从语义的层面解释 Go 调度器是如何在更上一层工作的。Go 调度器是一个复杂的系统，撇开细枝末节，重要的是对其工作原理心里有数，这有助于你做出更好的工程决策。

启动你的程序

当你的 Go 程序启动，会给苏注解的每个虚拟核心分配一个逻辑处理器（P）。如果处理器支持超线程，每个硬件线程对你的 Go 程序来说就是一个虚拟核心。打个比方，看一眼我电脑的系统信息：

这是个八核处理器，报告上没写每个物理核心的硬件线程数。Intel Core i9 处理器支持超线程，意味着每个物理核心有两个硬件线程。Go 程序认为这就有 16 个虚拟核心来并行跑操作系统的线程。

写个小程序来测试下：

package main

import (
    "fmt"
    "runtime"
)

func main() {
    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    fmt.Println(runtime.NumCPU())
}

在我本地运行这个程序，NumCPU() 函数的结果是 16，所有在我机器上跑的 Go 程序会被分配 16 个 P。

每个 P 分配一条操作系统线程（M），M 代表机器（machine）。这个线程由操作系统管理，操作系统负责将线程调度至 CPU 核心，上一篇有解释过。也就是说在我的机器上运行 Go 程序，有 8 条可用线程来作业，每条都绑定一个 P。

每个 Go 程序都以一个初始的 Goroutine（G）启动，这就是 Go 程序的执行体。Goroutine 就是 Go 的协程（Coroutine），我们用 G 取代 C 创造了 Goroutine 这个词。你可以把 Goroutine 当作是应用级的线程因为它们很多方面非常相似。正如操作系统线程在 CPU 核心做上下文切换，Goroutine 在 M 做上下文切换。

最后一个难题是运行队列。Go 调度器中有两个不同的运行队列：全局运行队列（GRQ）和局部运行队列（LRQ）。每个 P 都有 LRQ，在 P 的上下文中管理 Goroutine 的分配。这些 Goroutine 轮流通过上下文切换分配给该 P 的 M。Goroutine 的 GRQ 还没有被分配给 P。我们稍后讨论将 Goroutine 从 GRQ 转移至 LRQ。

调度器

正如前文所说，操作系统调度器是竞态的。本质上你没法预测调度器的行为。内核在拍板，一切都是不确定的。在操作系统上层运行的应用程序无法控制内核中进行的调度，除非使用原语和互斥锁等同步能力。

Go 调度器是 Go 运行时的一部分，而 Go 运行时内置在你的应用程序中。也就是说 Go 调度器在用户态运行而不是内核空间。Go 调度的当前实现不是竞态的而是协作式。作为一个协作式调度器就要定义好用户空间的事件，这些事件发生在代码中的安全点，以便决策调度。

Go 调度器的厉害之处在于它能够感知竞争，而你却无法预知它要做啥。这是因为调度器的决策权不在开发者手中，而是 Go 运行时。Go 调度器也是竞争型调度器，因此是不确定的。

Goroutine 状态

就像线程，Goroutine 同样有三种状态，指示了 Go 调度器为 Goroutine 赋予的角色。

等待：表示 Goroutine 已经停止了，可能在等待操作系统（系统调用）或同步操作（原子操作和互斥锁）。这些类型的延迟是导致性能不好的罪魁祸首。
可运行：Goroutine 想要在 M 上获得一些时间来执行分配给它的指令。如果很多 Goroutine 都这样，那大家都要等更久。此外，每个 Goroutine 分到的时间都会缩短因为大家都在争抢。这种类型的调度延迟也是性能不好的原因。
运行中：Goroutine 已经占据 M 执行指令了。应用程序的作业正在完成，这是众望所归。

上下文切换

Go 调度器需要明确定义用户空间的事件，这些事件发生在代码中的安全点来做上下文切换。这些事件和安全点体现在函数调用中，对 Go 调度器的健康发展至关重要。如今（Go 1.11 或更低版本）如果循环中没有函数调用，将会在调度器内造成延迟和垃圾收集。在合理的时间内发生函数调用至关重要。

注意，1.12 有个建议被接受，就是在 Go 调度器内部应用非合作性的抢占技术，允许抢占紧缩循环。

Go 程序中的四类事件会使调度器进行决策，不过也不一定会发生，有一定的几率：

使用了 go 关键字
垃圾回收
系统调用
同步

使用 `go` 关键字

go 关键字创建 Goroutine，当新的 Goroutine 创建时，调度器就得到一个决策的机会。

垃圾回收

GC 使用它自己的 Goroutine 运行，他们需要 M 上的时间片。这导致了 GC 搞出来不少混乱的调度。但是调度器对 Goroutine 都在干些啥门儿清，它会做出漂亮的决策：在垃圾回收期间，将想要访问堆的 Goroutine 与那些不与堆接触的 Goroutine 上下文切换。GC 运行时，调度器时刻都在思考。

系统调用

Goroutine 进行系统调用会导致 M 被阻塞，有时候调度器会将 Goroutine 切出 M，把一个新的 Goroutine 切到 M 上。但有时候又需要一个新的 M 来继续执行在 P 排队的 Goroutine，下一节我们再详细讲。

同步

如果原子操作、互斥锁或者管道操作导致 Goroutine 阻塞了，调度器就切进一个新的 Goroutine 来执行。当那个 Goroutine 又可以跑了，会重新入队，最终切回 M。

异步系统调用

当操作系统有异步处理系统调用的能力，可以使用一种叫做网络轮询器的东西来更高效地处理系统调用，通过在各种操作系统中使用 kqueue（macOS）、epoll（Linux）或 iocp（Windows）来实现。

现代操作系统都可以异步处理基于网络的系统调用，这也是网络轮询器这一名称的由来，因为它主要用于处理网络操作。通过网络轮询器，调度器可以防止 Goroutine 在进行网络系统调用时阻塞 M。尽量复用 M 来执行 P 上的 LRQ 的其他 Goroutine 而非创建新的 M，有助于减轻系统的调度负担。

如图 3 所示，Goroutine-1 正在 M 上执行，还有 3 个 Goroutine 在 LRQ 中等待他们的机会，网络轮询器无所事事中。

Goroutine-1 想要系统调用，所以就被挂到网络轮询器下，开始异步系统调用。只要 Goroutine-1 被挂到网络轮询器下，M 就空出来了，可以执行在 LRQ 中排队的 Goroutine 了。在这个例子中，Goroutine-2 被切换至 M。

图 5 中，异步网络系统调用完成了，Goroutine-1 回到了 LRQ 队列中。一旦 Goroutine-1 可以被切回 M，相关的 Go 代码会继续执行。这里最大的胜利在于，不需要额外的 M 来执行网络系统调用。网络轮询器是一个高效处理事件循环的 OS 线程。

同步系统调用

要是 Goroutine 既想系统调用又不想异步呢？这种情况不能使用网络轮询器，而系统调用的 Goroutine 只能阻塞 M，很不幸无法避免。这种不能异步的系统调用和文件系统调用相关。如果你用 CGO，还有其他调用 C 函数阻塞 M 的情况。

注意：Windows 倒是能够异步基于文件的系统调用，从技术上讲，在 Windows 上跑可以使用网络轮询器。

来走一遍同步系统调用导致 M 阻塞时发生了什么。

这次 Goroutine-1 将要进行同步系统调用，会阻塞 M。

图 7 中，调度器可以识别出 Goroutine-1 导致 M 阻塞，这时调度器会将 P 和 M1 断开。然后调度器为 P 带来一个新的 M2，从 LRQ 中挑出 Goroutine-2 并切换上去。如果因为之前的交换而已经有 M 存在，这种转换比创建一个新的要快。

当 Goroutine-1 进行的阻塞系统调用结束。此时 Goroutine-1 可以放回 LRQ 中，再次由 P 来服务。M1 被扔到一边以备将来这种情况需要再次发生时使用。

任务窃取

另一方面 Go 调度器是任务窃取型的，有助于保持调度的效率。首先大家都最不希望 M 进入等待状态，一旦出现，操作系统会将 M 从核心上切换下来，这意味着 P 无法继续下去了，即使还有处于运行中的 Groutine，直到 M 被切换回核心。任务窃取还有助于平衡所有 P 的 Goroutine，从而更好更有效地分配工作。

图 9 中，我们有个多线程的 Go 程序，两个 P 分别为四条 Goroutine 和一条 GRQ 中的 Goroutine服务。如果其中一个 P 快速地服务于所有的 Goroutine ，会发生什么？

图 10 中，P1 已经没有 Goroutine 执行了，但是 P2 的 LRQ 和 GRQ 上还可运行状态的 Goroutine，这时 P1 就要“偷窃”了，偷窃的规则如下：

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

根据这些规则，P1 要检查 P2 的 LRQ 队列中的 Goroutine 并拿走一半。

现在 P1 有 Goroutine 来执行了。

如果 P2 完成了它自己所有 Goroutine，而 P1 的 LRQ 已经所剩无几，会发生啥？

图 12 中，P2 要开始偷东西了。它先看看 P1 的 LRQ 还有没有 Goroutine 了，然后再看看 GRQ，在那它找到了 Goroutine-9。

P2 从 GRQ 偷了 Goroutine-9 并开始作业了。任务偷窃的好处是让 M 保持忙碌而不是无所事事。任务偷窃在内部被认为是 M 自旋。

实际案例

有了机制和语义，我将向你展示这些东西是怎么结合在一起，让 Go 调度器高效工作的。想象一下用 C 写一个多线程应用，管理两个 OS 线程，相互传递消息。

如图 14，两个线程来回传递消息。线程 1 切换至核心 1，正在执行，向线程 2 发消息。

注意：消息如何传递并不重要，重要的是这个过程中线程的状态。

线程 1 发完消息要等待响应，这将导致它被切出核心 1 并进入等待状态。一旦线程 2 收到消息，会进入可运行状态。现在操作系统将线程 2 切换至核心 2 上。接着线程 2 处理消息并应答。

线程 2 的消息被线程 1 接收时上下文切换又来了。线程 2 从执行状态切换至等待状态，线程 1 从等待状态进入可运行状态最后回到执行中状态，处理并应答消息。

上下文和状态的切换都要花时间的，限制了作业的速度。每次上下文切换会产生约 1000 纳秒的延迟，这期间硬件少执行了 1.2W 条指令。由于这些线程在不同的核心之间辗转腾挪，因此无法命中缓存导致额外的延迟也很多。

同一个案例，这次换成 Goroutine 和 Go 调度器。

G1 切换至 M1，M1 在核心 1 上跑，G1 向 G2 发送消息。

图 18 中，一旦 G1 发完消息就要等待应答，这将导致 G1 被切出 M1 并进入等待状态。当 G2 收到消息，进入可运行状态，Go 调度器开始上下文切换，让 G2 到 M1 上执行，而 M1 仍在核心 1 上。接下来 G2 处理消息并回复 G1。

当 G2 发的消息被 G1 接收时，又要上下文切换了。现在 G2 从运行中切换至等待状态，G1 从等待切换至可执行状态最终到运行中，处理并应答消息。

表面上并没有什么不同，无论使用线程还是 Goroutine ，上下文该切换切换状态改变的变。但是有一个主要的区别，乍一看可能并不明显。

使用 Goroutine 的案例中，所有操作都是同一核心上的同一条操作系统线程处理的。从操作系统的角度来看，线程从未进入等待状态，一次都没有。因此，就不存在操作系统线程上下文切换造成的指令停滞了。

本质上，Go 将 IO 阻塞上升到了操作系统级别的 CPU 绑定。既然所有上下文切换都是在应用级别发生的，就不会浪费使用线程时上下文切换造成的 1.2W 条指令时间。在 Go 中，上下文切换差不多耗费 200 纳秒或 2.4k 条指令。调度器也在帮助提高缓存命中率和 NUMA 的效率。这就是为什么不需要比虚拟核心更多的线程，Go 调度器尽可能使用更少的线程，充分利用好每条线程，有助于减少操作系统和硬件的负载。

总结

Go 调度器在设计上如何考虑到操作系统和硬件工作方式的复杂性令人惊叹。在操作系统层面将 IO 阻塞转化为 CPU 绑定作业的能力，在高效利用 CPU 取得了重大进步。用每个虚拟核心的操作系统线程来完成所有的工作（CPU 和 IO 阻塞绑定）。对于不需要系统调用阻塞操作系统线程的应用程序来说倒是有可能的。

作为开发者，你还是要知道自己的应用程序在干啥。不能无限创建 Goroutine 还指望性能很好。少即是多，但是理解了 Go 调度器的机制你能够做出更合理的工程决策。下一篇博客，我将讨论如何利用并发获取更好的性能且保持代码的可读性。

原文

https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html

译文

介绍