Go 中的调度：第 I 部分 - OS 调度程序

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

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

线程状态

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

  • 等待：这意味着线程停止并等待某些东西才能继续。这可能是因为等待硬件（磁盘，网络）, 操作系统（系统调用）或同步调用（原子，互斥）等原因。这些类型的延迟是性能不佳的根本原因。
  • 可运行：这意味着线程需要时间在核心上，以便它可以执行其分配的机器指令。如果你有很多需要时间的线程，那么线程必须等待更长时间才能获得时间。此外，随着更多线程争用时间，缩短了任何给定线程获得的单独时间量。这种类型的调度延迟也可能是性能不佳的原因。
  • 执行：这意味着线程已被放置在核心上并正在执行其机器指令。与应用程序相关的工作即将完成。这是每个人都想要的。

工作类型

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

  • CPU 绑定：这是永远不会创建线程可能处于等待状态的情况的工作。这是不断进行计算的工作。计算 Pi 到第 N 位的线程将是 CPU 绑定的。
  • IO 绑定：这是导致线程进入等待状态的工作。这项工作包括请求通过网络访问资源或将系统调用进入操作系统。需要访问数据库的线程将是 IO 绑定。我将包括同步事件（互斥，原子）, 导致线程等待此类别的一部分。

上下文切换

如果你在 Linux,Mac 或 Windows 上运行，则运行在具有抢占式调度程序的操作系统上。这意味着一些重要的事情。首先，它意味着调度程序在任何给定时间选择运行什么线程时都是不可预测的。线程优先级与事件一起（如在网络上接收数据）使得无法确定调度程序将选择执行什么操作以及何时执行操作。
其次，这意味着你必须永远不要根据你有幸经历的一些感知行为编写代码，但不能保证每次都能发生。很容易让自己思考，因为我已经看到过这种情况发生了 1000 次，这是有保障的行为。如果在应用程序中需要确定性，则必须控制线程的同步和编排。
在核心上交换线程的物理行为称为上下文切换。当调度程序从核心拉出执行中的线程并用可运行的线程替换它时，就会发生上下文切换。从运行队列中选择的线程进入执行状态。被拉出的线程可以移回可运行状态（如果它仍然具有运行能力）, 或者进入等待状态（如果由于 IO 绑定类型的请求而被替换）。
上下文切换被认为是昂贵的，因为在核心上交换线程需要花费很多时间。在上下文切换期间存在的等待时间量取决于不同的因素，但是它在～1000 和～1500 纳秒之间花费是不合理的。考虑到硬件应该能够合理地执行（平均）每个核心每纳秒 12 条指令，上下文切换可能需要大约 12k 到 18k 的延迟指令。实质上，你的程序在上下文切换期间失去了执行大量指令的能力。
如果你有一个专注于 IO 绑定工作的程序，那么上下文切换将是一个优势。一旦线程进入等待中状态，另一个处于可运行状态的线程就可以取代它。这使得核心始终可以正常工作。这是调度的最重要方面之一。如果有工作（处于可运行状态的线程）, 则不允许内核空闲。
如果你的程序专注于 CPU 绑定工作，那么上下文切换将成为性能的噩梦。由于 Thead 总是有工作要做，因此上下文切换正在停止这项工作的进展。这种情况与 IO 绑定工作负载的情况形成鲜明对比

Go 中的调度：第 II 部分 - Go Scheduler

当你的 Go 程序启动时，它会为主机上标识的每个虚拟核心提供一个逻辑处理器（P）

GPM代表了三个角色，分别是Goroutine、Processor、Machine。

  • Goroutine：就是咱们常用的用go关键字创建的执行体，它对应一个结构体g，结构体里保存了goroutine的堆栈信息
  • Machine：表示操作系统的线程
  • Processor：表示处理器，有了它才能建立G、M的联系


Go 调度程序中有两个不同的运行队列：全局运行队列（GRQ）和本地运行队列（LRQ）。每个 P 都有一个 LRQ, 用于管理指定在 P 的上下文中执行的 Goroutines。这些 Goroutines 轮流在上下文中切换到分配给 P 的 M。GRQ 用于尚未分配给的 Goroutines。还没有。有一个过程将 Goroutines 从 GRQ 转移到 LRQ, 我们将在后面讨论。

image.png

协作调度程序

Go 调度程序是 Go 运行时的一部分，Go 运行时内置在应用程序中。这意味着 Go 调度程序在内核之上的用户空间中运行。Go 调度程序的当前实现不是抢占式调度程序，而是协作调度程序。作为协作调度程序意味着调度程序需要在代码中的安全点处发生的明确定义的用户空间事件以做出调度决策。

Go 合作调度程序的优点在于它的表现和感觉先发制人。你无法预测 Go 调度程序将要执行的操作。这是因为这个合作调度程序的决策不是由开发人员掌握，而是在 Go 运行时。将 Go 调度程序视为抢占式调度程序非常重要，并且由于调度程序是非确定性的，因此这并不是一件容易的事。

Goroutine 并发

就像线程一样，Goroutines 拥有相同的三个高级状态。这些决定了 Go 调度程序在任何给定的 Goroutine 中所起的作用。Goroutine 可以处于以下三种状态之一：Waiting,Runnable 或 Executing。

  • 等待：这意味着 Goroutine 已停止并等待某些事情继续进行。这可能是出于等待操作系统（系统调用）或同步调用（原子操作和互斥操作）等原因。这些类型的延迟是性能不佳的根本原因。
  • 可运行：这意味着 Goroutine 需要时间在 M 上，因此它可以执行其指定的指令。如果你有很多想要时间的 Goroutines, 那么 Goroutines 必须等待更长时间才能得到时间。此外，随着更多 Goroutines 争夺时间，任何给定的 Goroutine 获得的个人时间缩短了。这种类型的调度延迟也可能是性能不佳的原因。
  • 执行：这意味着 Goroutine 已被置于 M 并正在执行其指令。与应用程序相关的工作即将完成。这是每个人都想要的。

上下文切换

Go 调度程序需要明确定义的用户空间事件，这些事件发生在代码中的安全点以进行上下文切换。这些事件和安全点在函数调用中表现出来。函数调用对 Go 调度程序的运行状况至关重要。

Go 程序中发生了四类事件，允许调度程序做出调度决策。这并不意味着它总是会发生在其中一个事件上。这意味着调度程序获得了机会。

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

使用关键字 go

关键字 go 是你创建 Goroutines 的方式。一旦创建了新的 Goroutine, 它就为调度程序提供了做出调度决策的机会。

垃圾收集

由于 GC 使用自己的 Goroutines 运行，因此那些 Goroutines 需要时间在 M 上运行。这会导致 GC 产生大量的调度混乱。但是，调度程序非常聪明地了解 Goroutine 正在做什么，它将利用这些智能做出明智的决策。一个聪明的决定是上下文切换一个 Goroutine, 它想要在 GC 期间接触那些没有接触堆的堆。当 GC 运行时，正在做出许多调度决策。

系统调用

如果 Goroutine 进行系统调用会导致 Goroutine 阻塞 M, 有时调度程序能够将 Goroutine 从 M 上下文切换并将新的 Goroutine 上下文切换到相同的 M. 但是，有时新的 M 是需要继续执行在 P 中排队的 Goroutines。如何工作将在下一节中更详细地解释。

同步和编排

当你运行的操作系统具有异步处理系统调用的能力时，可以使用称为网络轮询器的内容来更有效地处理系统调用。这是通过在这些相应的操作系统中使用 kqueue（Mac 操作系统）,epoll（Linux）或 iocp（Windows）来实现的。
基于网络的系统调用可以由我们今天使用的许多操作系统异步处理。这是网络轮询器获得其名称的地方，因为它的主要用途是处理网络操作。通过使用网络轮询器进行网络系统调用，调度程序可以防止 Goroutines 在进行系统调用时阻止 M. 这有助于保持 M 可用于在 P 的 LRQ 中执行其他 Goroutines 而无需创建新的 Ms. 这有助于减少操作系统上的调度负载。

image.png
上图显示了我们的基本调度图。Goroutine-1 正在 M 上执行，并且还有 3 个 Goroutines 等待 LRQ 在 M 上等待。网络轮询器无所事事。

image.png

Goroutine-1 想要进行网络系统调用，因此 Goroutine-1 被移动到网络轮询器并处理异步网络系统调用。一旦 Goroutine-1 移动到网络轮询器，M 现在可以从 LRQ 执行不同的 Goroutine。在这种情况下，Goroutine-2 在 M. 上下文切换。

image.png

异步网络系统调用由网络轮询器完成，Goroutine-1 被移回到 L 的 LRQ 中。一旦 Goroutine-1 可以在 M 上进行上下文切换，Go 负责的 Go 相关代码可以再次执行。这里的最大优势是，要执行网络系统调用，不需要额外的 Ms。网络轮询器具有操作系统线程，它正在处理有效的事件循环。

同步系统调用

当 Goroutine 想要进行无法异步完成的系统调用时会发生什么？在这种情况下，网络轮询器不能被使用，并且进行系统调用的 Goroutine 将阻止 M. 这是不幸的，但是没有办法防止这种情况发生。不能异步进行的系统调用的一个示例是基于文件的系统调用。如果你正在使用 CGO, 则可能还有其他情况，调用 C 函数也会阻止 M.

image.png

再次显示了我们的基本调度图，但这次 Goroutine-1 将进行同步系统调用以阻止 M1。

image.png

调度程序能够识别 Goroutine-1 已导致 M 阻塞。此时，调度程序将 M1 与 P 分离，同时仍然附加阻塞 Goroutine-1。然后调度器引入新的 M2 来为 P 服务。此时，可以从 LRQ 中选择 Goroutine-2 并且在 M2 上进行上下文切换。如果由于之前的交换而已经存在 M, 则此切换比必须创建新 M 更快。

image.png

由 Goroutine-1 完成的阻塞系统调用完成。此时，Goroutine-1 可以移回 LRQ 并再次由 P 服务。如果需要再次发生这种情况，则将 M1 放在侧面以备将来使用。

工作窃取

调度程序的另一个方面是它是一个工作窃取调度程序。这有助于在一些领域保持有效的调度。首先，你想要的最后一件事就是 M 进入等待状态，因为一旦发生这种情况，操作系统就会将 M 从核心上下文切换。这意味着即使有一个 Goroutine 处于可运行状态，P 也无法完成任何工作，直到 M 在核心上进行上下文切换。窃取工作也有助于平衡所有 P 的 Goroutines, 从而更好地分配工作并更有效地完成工作。
让我们来看一个例子。

image.png

我们有一个多线程 Go 程序，其中两个 P 服务四个 Goroutines, 每个服务 GRQ 中有一个 Goroutine。如果 P 的所有 Goroutines 中的一个服务很快就会发生什么？

image.png

P1 没有更多的 Goroutines 来执行。但是 Goroutines 处于可运行状态，无论是在 LRQ 中还是在 GRQ 中。这是 P1 需要偷工作的时刻。窃取工作的规则如下。

  1. runtime.schedule () {
  2.     // 只有 1/61 的时间，检查 G 的全局可运行队列 
  3.     // 如果找不到，请检查本地队列。
  4.     // 如果没找到，
  5.     // 试图从其他 Ps 窃取 
  6.     // 如果没有，请检查全局可运行队列。
  7.     // 如果找不到，轮询网络。
  8. }

基于清单 2 中的这些规则，P1 需要在其 LRQ 中检查 P2 for Goroutines 并获取其发现的一半。

image.png

Goroutines 的一半来自 P2, 现在 P1 可以执行那些 Goroutines。

如果 P2 完成为其所有 Goroutines 提供服务并且 P1 的 LRQ 中没有任何东西会发生什么？

image.png

P2 完成了所有工作，现在需要窃取一些。首先，它将查看 P1 的 LRQ, 但它不会找到任何 Goroutines。接下来，它将查看 GRQ。那里会发现 Goroutine-9。

image.png

P2 从 GRQ 窃取了 Goroutine-9 并开始执行工作。所有这些偷窃工作的好处在于它允许女士保持忙碌而不会闲着。这项工作窃取在内部被视为旋转 M. 这种旋转具有 JBD 在她的 工作窃取 博客文章中解释得很好的其他好处。

实际例子

有了相应的机制和语义，我想向你展示如何将所有这些结合在一起，以便 Go 调度程序随着时间的推移执行更多工作。想象一下用 C 编写的多线程应用程序，其中程序管理两个操作系统线程，它们相互传递消息。

image.png

有 2 个线程来回传递消息。线程 1 在 Core 1 上进行上下文切换，现在正在执行，这允许线程 1 将其消息发送到线程 2。
注意：消息的传递方式并不重要。当业务流程继续进行时，重要的是线程的状态。

image.png

一旦线程 1 完成发送消息，它现在需要等待响应。这将导致线程 1 从 Core 1 上下文关闭并进入等待状态。一旦线程 2 收到有关该消息的通知，它就会进入可运行状态。现在操作系统可以执行上下文切换并在 Core 上执行线程 2, 它恰好是 Core 2. 接下来，线程 2 处理消息并将新消息发送回线程 1。

image.png

线程上下文切换再次由线程 2 接收线程 2 的消息。现在线程 2 上下文 - 从执行状态切换到等待状态和线程 1 上下文 - 从等待状态切换到可运行状态最后回到执行状态，允许它处理并发回新消息。
所有这些上下文切换和状态更改都需要时间来执行，这限制了工作的完成速度。由于每个上下文切换可能会产生约 1000 纳秒的延迟，并且希望硬件每纳秒执行 12 条指令，因此你可以查看 12k 指令，或多或少，在这些上下文切换期间不执行。由于这些线程也在不同的核心之间弹跳，因高速缓存行未命中而导致额外延迟的可能性也很高。
让我们采用相同的例子，但使用 Goroutines 和 Go 调度程序。

image.png

有两个 Goroutine 正在编排，彼此之间来回传递消息。G1 在 M1 上进行上下文切换，这恰好在 Core 1 上运行，这允许 G1 执行其工作。G1 的工作是将其消息发送给 G2。

image.png

一旦 G1 完成发送消息，它现在需要等待响应。这将导致 G1 上下文关闭 M1 并进入等待状态。一旦 G2 收到有关该消息的通知，它就会进入可运行状态。现在，Go 调度程序可以执行上下文切换并在 M1 上执行 G2,M1 仍然在 Core 1 上运行。接下来，G2 处理消息并将新消息发送回 G1。

image.png

当 G2 接收到由 G2 发送的消息时，事物再次上下文切换。现在 G2 上下文 - 从执行状态切换到等待状态，G1 上下文 - 从等待状态切换到可运行状态，最后返回到执行状态，这允许它处理并发回新消息。

从本质上讲，Go 已将 IO / Blocking 工作转变为操作系统级别的 CPU 限制工作。由于所有上下文切换都是在应用程序级别进行的，因此在使用 Threads 时，每个上下文切换都不会丢失相同的～12k 指令（平均）。在 Go 中，那些相同的上下文切换花费大约 200 纳秒或～2.4k 指令。调度程序还有助于提高缓存线效率和 NUMA。这就是为什么我们不需要比虚拟核心更多的线程。在 Go 中，随着时间的推移，可以完成更多的工作，因为 Go 调度程序尝试使用更少的线程并在每个线程上执行更多操作，这有助于减少操作系统和硬件的负载。

Go 调度程序在设计如何考虑操作系统和硬件如何工作的复杂性方面确实令人惊讶。在操作系统级别将 IO / 阻塞工作转换为 CPU 限制工作的能力是我们在利用更多 CPU 容量的过程中获得巨大成功的地方。这就是为什么你不需要比虚拟核心更多的操作系统线程。你可以合理地期望每个虚拟核心只需一个操作系统线程即可完成所有工作（CPU 和阻塞 IO 绑定）。对于不需要阻止操作系统线程的系统调用的网络应用程序和其他应用程序，可以这样做。

Go 中的调度：第 III 部分 - 并发

哎、不懂的好多