[译] Scheduling In Go : Part II - Go Scheduler

序幕

这是一个由三部分组成的系列文章中的第二篇，它将提供对Go调度器背后的机制和语义的理解。这篇文章重点介绍Go调度器。

三个部分系列的索引：

  1. Go中的调度：第一部分-OS调度器
  2. Go中的调度：第二部分-Go调度器
  3. Go中的调度：第三部分-并发

介绍

在该调度系列的第一部分中，我解释了操作系统调度器的各个方面，我认为这些方面对于理解和欣赏Go调度器的语义很重要。在本文中，我将在语义级别上讲解Go调度器的工作方式，并着重于高级行为。Go调度器是一个复杂的系统，一些机械细节并不重要。重要的是要有一个良好的模型来说明事物的工作方式和行为方式。这将使您做出更好的工程决策。

您的程序开始

当您的Go程序启动时，会为主机上标识的每个虚拟核提供一个逻辑处理器（P）。如果您的处理器每个物理内核上具有多个硬件线程（Hyper-Threading），则每个硬件线程将作为虚拟核心呈现给您的Go程序。为了更好地理解这一点，请查看我的MacBook Pro的系统报告。

图1

+++

Hardware Overview:

Model Name: MacBook Pro

Model Identifier: MacBookPro13,3

Processor Name: Intel Core i7

Processor Speed: 2.9GHz

Number of Processors: 1

Total Number of Cores: 4

L2 Cache (per Core): 256 KB

L3 Cache: 8MB

Memory: 16GB

+++

您可以看到我有一个具有4个物理内核的处理器。该报告未公开的是我每个物理核心拥有的硬件线程数。英特尔酷睿i7处理器具有超线程功能，这意味着每个物理内核有2个硬件线程。这将向Go程序报告8个虚拟内核可用于并行执行OS线程。

要对此进行测试，请考虑以下程序：

清单1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

import (
	"fmt"
	"runtime"
)

func main() {

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

当我在本地计算机上运行该程序时，NumCPU() 函数调用的结果将为8。我在计算机上运行的任何Go程序都将获得8处理器(P)。

每个P都分配有一个OS线程（“ M”）。“ M”代表机器。这个线程仍然是由操作系统管理，OS仍然负责将线程放到内核上的执行，如在最后博客解释的。这意味着，当我在计算机上运行Go程序时，我有8个线程可以执行我的工作，每个线程都单独连接到P。

每个Go程序还会获得一个初始Goroutine（“ G”），这是Go程序的执行路径。Goroutine本质上是一个协程，但这就是Go，因此我们将字母“ C”替换为“ G”，然后得到单词Goroutine。您可以将Goroutines视为应用程序级线程，并且它们在许多方面类似于OS线程。就像OS线程在内核中进行上下文切换一样，Goroutine在M时进行上下文切换。

最后一个难题是运行队列。Go调度器中有两个不同的运行队列：全局运行队列（GRQ）和本地运行队列（LRQ）。每个P都有一个LRQ，该LRQ管理分配给在P上下文中执行的Goroutine。这些Goroutine轮流被上下文切换到或切换出分配给该P的M。GRQ用于尚未分配给P的Goroutine。将Goroutines从GRQ转移到LRQ的过程，我们将在后面讨论。

图2提供了所有这些组件的图像。

图2 img

合作调度器

正如我们在第一篇文章中所讨论的，OS调度器是抢占式调度器。从本质上讲，这意味着您无法在任何给定时间预测调度器将要执行的操作。内核在做决定，而一切都是不确定的。运行在OS之上的应用程序无法通过调度来控制内核内部发生的事情，除非它们利用了诸如原子指令和互斥调用之类的同步原语。

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

Go合作调度器的出色之处在于它看起来和感觉都是抢先的。您无法预测Go调度器将要执行的操作。这是因为，此协作调度器的决策权不掌握在开发人员手中，而在于Go运行时。将Go调度器视为抢先式调度器很重要，并且由于该调度器是不确定的，因此这并不有更多的延伸。

Goroutine状态

就像线程一样，Goroutines具有相同的三个高级状态。这些决定了Go调度器在任何给定Goroutine中所扮演的角色。Goroutine可以处于以下三种状态之一：Waiting，Runnable或Executing。

Waiting：这意味着Goroutine已停止，正在等待某些东西才能继续。这可能是由于诸如等待操作系统（系统调用）或同步调用（原子和互斥操作）之类的原因。这些类型的延迟是导致性能下降的根本原因。

Runnable：这意味着Goroutine想要在M时间，以便可以执行其分配的指令。如果您有很多需要时间的Goroutine，那么Goroutine必须等待更长的时间才能获得时间。而且，随着更多Goroutine争夺时间，任何给定Goroutine所获得的时间都将缩短。这种类型的调度等待时间也可能是导致性能下降的原因。

Executing：这意味着Goroutine已放置在M上并正在执行其指令。与应用程序相关的工作已经完成。这就是每个人都想要的。

上下文切换

Go调度器需要定义明确的用户空间事件，这些事件发生在代码中的安全点处，以便从上下文进行切换。这些事件和安全点在函数调用中体现出来。函数调用对于Go调度器的运行状况至关重要。现在（使用Go 1.11或更低版本），如果运行任何未进行函数调用的紧密循环，则将导致调度器和垃圾回收中的延迟。在合理的时间范围内进行函数调用至关重要。

注意：有一个提案1.12已被接受，可以在Go调度器中应用非合作式抢占技术，以允许抢占紧密循环。

Go程序中发生了四类事件，这些事件使调度程序可以制定计划决策。这并不意味着它将总是在这些事件之一中发生。这意味着调度器有机会。

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

关键字的使用 go

关键字go是创建Goroutines的方式。一旦创建了新的Goroutine，它将为调度器提供做出调度决策的机会。

垃圾收集

由于GC使用自己的Goroutine集合运行，因此这些Goroutine需要M上的时间才能运行。这导致GC造成很多调度混乱。但是，调度器对于Goroutine所做的事情非常聪明，它将利用该情报做出明智的决策。一个明智的决定是上下文切换一个Goroutine，该Goroutine要与GC期间不接触堆的Goroutine接触。当GC运行时，将制定许多计划决策。

系统调用

如果Goroutine进行系统调用会导致Goroutine阻塞M，则调度器有时能够将Goroutine从M上下文切换出，并将使用上下文切换将新Goroutine切换到相同的M。但是，有时新的M是保持执行在P中排队的Goroutine。下一部分将详细说明其工作方式。

同步与编排

如果原子，互斥或通道操作调用将导致Goroutine阻塞，则调度器可以上下文切换运行新的Goroutine。一旦Goroutine可以再次运行，就可以对其重新排队，并最终在M上进行上下文切换。

异步系统调用

当您正在运行的OS能够异步处理系统调用时，可以使用称为网络轮询器的东西来更有效地处理系统调用。这是通过在各个操作系统中使用kqueue（MacOS），epoll（Linux）或iocp（Windows）来完成的。

我们今天使用的许多操作系统都可以异步处理基于网络的系统调用。这是网络轮询器名字的出处，这是因为它的主要用途是处理网络操作。通过使用网络轮询器进行网络系统调用，调度器可以防止Goroutine在进行这些系统调用时阻止M。这有助于使M保持可用以执行P的LRQ中的其他Goroutine，而无需创建新的M。这有助于减少OS上的调度负载。

看看它是如何工作的最好方法是看一个例子。

图3 img

图3显示了我们的基本调度图。Goroutine-1正在M上执行，还有3个Goroutine在LRQ中等待以获取其在M上的时间。网络轮询器闲置无事可做。

图4 img

在图4中，Goroutine-1希望进行网络系统调用，因此Goroutine-1被移至网络轮询器，并处理了异步网络系统调用。将Goroutine-1移至网络轮询器后，M现在可用于执行与LRQ不同的Goroutine。在这种情况下，Goroutine-2进行了上下文切换到M上。

图5 img

在图5中，网络轮询器完成了异步网络系统调用，并将Goroutine-1移回到P的LRQ中。一旦Goroutine-1可以在M上上下文切换回去，它负责的Go相关代码可以再次执行。这里最大的好处是，执行网络系统调用不需要额外的M。网络轮询器具有OS线程，并且正在处理有效的事件循环。

同步系统调用

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

注意：Windows OS确实具有异步进行基于文件的系统调用的功能。从技术上讲，在Windows上运行时，可以使用网络轮询器。

让我们逐一介绍同步系统调用（如文件I / O）会导致M阻塞的情况。

图6 img

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

图7 img

在图7中，调度器能够识别Goroutine-1导致M阻塞。此时，调度器将M1与P分离，而阻塞Goroutine-1仍处于连接状态。然后，调度器会引入一个新的M2来为P服务。此时，可以从LRQ中选择Goroutine-2，并在M2上进行上下文切换。如果由于先前的交换而已存在M，则此过渡比必须创建新的M更快。

图8 img

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

工作偷窃

调度器的另一个方面是它是一种窃取工作的调度器。这有助于在某些方面保持调度效率。首先，您想要的最后一个就是M进入等待状态，因为一旦发生这种情况，操作系统将上下文M切换出内核。这意味着，即使有一个Goroutine处于可运行状态，P也无法完成任何工作，直到在M上下文中将M切换回M为止。窃取工作还有助于在所有P上平衡Goroutine，从而更好地分配工作并更高效地完成工作。

让我们来看一个例子。

图9 img

在图9中，我们有一个多线程Go程序，其中有两个P，分别为四个Goroutine和GRQ中的一个Goroutine提供服务。如果P的服务之一迅速为其所有Goroutine提供服务，会发生什么情况？

图10 img

在图10中，P1没有更多的Goroutines要执行。但是在P2的LRQ和GRQ中都有可运行状态的Goroutine。这是P1需要窃取工作的时刻。窃取工作的规则如下。

清单2

1
2
3
4
5
6
7
8

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.
}

因此，根据清单2中的这些规则，P1需要在其LRQ中检查P2中的Goroutines，并取其发现结果的一半。

图11 img

在图11中，一半的Goroutine取自P2，现在P1可以执行这些Goroutine。

如果P2完成其所有Goroutine的服务并且P1的LRQ中没有剩余，该怎么办？

图12 img

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

图13 img

在图13中，P2从GRQ窃取了Goroutine-9，并开始执行工作。所有这些偷窃工作的最大好处是，它可以让 M 保持忙碌而不会闲着。在内部，这种窃取工作被认为是在旋转M。这种旋转还有其他好处，JBD在其窃取工作的博客文章中很好地解释了这一点。

实际例子

通过适当的机制和语义，我想向您展示如何将所有这些结合在一起以使Go计划程序随着时间的推移执行更多的工作。想象一下用C编写的多线程应用程序，其中程序正在管理两个OS线程，它们相互之间来回传递消息。

图14 img

在图14中，有2个线程来回传递消息。线程1在Core 1上进行了上下文切换，并且现在正在执行，这允许线程1将其消息发送到线程2。

注意：如何传递消息并不重要。重要的是随着编排的进行，线程的状态。

图15 img

在图15中，线程1完成发送消息后，现在需要等待响应。这将导致线程1被上下文从Core 1切换到另一状态，并进入等待状态。线程2收到有关该消息的通知后，便进入可运行状态。现在，操作系统可以执行上下文切换，并使线程2在恰好是内核2的Core上执行。接下来，线程2处理该消息并将新消息发送回Thread 1。

图16 img

在图16中，线程1再次接收到线程2发出的消息后，线程又进行了上下文切换，现在线程2的上下文从执行状态切换到了等待状态，线程1的上下文从等待状态切换到了可运行状态。最终返回到执行状态，这使其可以进行处理并将新消息发送回去。

所有这些上下文切换和状态更改都需要执行时间，这限制了工作可以完成的速度。每个上下文切换潜在的潜在延迟约为1000纳秒，并且希望硬件每纳秒执行12条指令，因此您正在查看的是大约12k条指令，或多或少地不在这些上下文切换期间执行。由于这些线程也在不同的内核之间反弹，因此由于高速缓存行未命中而导致额外延迟的机会也很高。

让我们以相同的示例为例，但是使用Goroutines和Go调度器。

图17 img

在图17中，有两个相互协调的Goroutine来回传递消息。G1在M1上进行了上下文切换，而M1恰好在Core 1上运行，这使G1可以执行其工作。G1的工作是将其消息发送到G2。

图18 img

在图18中，G1完成发送消息后，现在需要等待响应。这将导致G1被上下文切换出M1，并进入等待状态。一旦G2收到有关该消息的通知，它将进入可运行状态。现在，Go调度器可以执行上下文切换，并使G2在内核1上运行的M1上执行。接下来，G2处理该消息并将新消息发送回G1。

图19 img

在图19中，当G2发送的消息被G1接收时，事物再次上下文切换。现在，G2上下文从执行状态切换到等待状态，G1上下文从等待状态切换到可运行状态，最后回到执行状态，这使它可以处理并发送新消息。

表面上的东西似乎没有什么不同。无论使用线程还是Goroutine，都会发生所有相同的上下文切换和状态更改。但是，使用线程和Goroutines之间的主要区别乍一看可能并不明显。

在使用Goroutines的情况下，所有处理都使用相同的OS Thread和Core。从操作系统的角度来看，这意味着操作系统线程永远不会进入等待状态。不止一次。结果，在使用线程时我们丢失给上下文切换的所有这些指令在使用Goroutines时不会丢失。

从本质上讲，Go在OS级别将IO /阻塞工作变成了CPU密集型工作。由于所有上下文切换都是在应用程序级别进行的，因此每个上下文切换不会损失与使用线程时相同的（平均）约12k指令。在Go中，这些相同的上下文切换使您花费约200纳秒或约2.4k的指令。调度器还有助于提高缓存行效率和NUMA。这就是为什么我们不需要的线程多于虚拟内核。在Go中，随着时间的推移，有可能完成更多的工作，因为Go调度器尝试使用更少的线程，并在每个线程上执行更多操作，这有助于减少OS和硬件上的负载。

结论

Go调度器在设计如何考虑到OS和硬件如何工作的复杂性方面确实非常了不起。在操作系统级别上，将IO /阻塞工作转变为CPU密集型工作的能力是我们在随着时间的推移利用更多CPU容量方面获得的巨大胜利。这就是为什么您不需要比拥有的虚拟内核更多的OS线程。您可以合理地期望通过每个虚拟内核只有一个OS线程来完成所有工作（CPU密集型和IO 密集型）。对于网络应用程序和其他不需要阻止操作系统线程的系统调用的应用程序而言，这样做是可能的。

作为开发人员，您仍然需要根据您正在处理的工作类型来了解您的应用程序在做什么。您无法创建无限数量的Goroutine，并期望获得惊人的性能。少即是多，但有了这些Go-Scheduler语义的理解，您就可以做出更好的工程决策。在下一篇文章中，我将探讨以保守的方式利用并发以获得更好的性能，同时仍然平衡可能需要添加到代码中的复杂性的想法。