[toc]

原文:Scheduling In Go : Part II - Go Scheduler

前言

这是本系列的第二篇文章，本文重点介绍Go中的调度机制

简介

在本系列的第一篇文章中，主要介绍了操作系统的系统调度的部分内容，我认为那部分内容对于理解Go调度器的语义非常重要。在本篇文章中，我会从语义层面解释Go调度器是如何工作的，并重点介绍它的高级特性。Go调度器是个非常复杂的系统，可以不用过分关注小的细节，重要的是有一个好的调度器如何工作以及如何表现的概念，这有助于你在工程化开发过程中进行更好的决策。

你的程序启动

当你的Go程序启动时，它会为主机上每个有标识的虚拟内核分配一个逻辑处理器（P），如果你的处理器运行在一个可以执行多硬件线程的物理内核上（超线程），那么每个硬件线程会变为虚拟内核供你的Go程序使用。为了更好的理解这点，请看下一我的MacBook Pro的系统报告。

图1

94_figure1.png

你可以看见，我有一个四核的处理器，报告中无法体现每个核的硬件线程数。英特尔酷睿i7处理器具有超线程功能，因此每个核拥有2个硬件线程，对于Go程序而言，意味着有8个虚拟核心可以并行执行OS线程。

为了测试这点，参考下面这段代码

代码1

package main

import (
    "fmt"
    "runtime"
)

func main() {

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

在我的本地运行这段代码，运行结果输出的是8，也就是说任何在我这台机器上运行的Go程序都会分配8个P。

每个P会被分配一个OS线程（M），这个‘M’代表的是机器（machine）。这个线程依然由操作系统进行管理，也会如上一篇文章所述，操作系统会负责将线程放到核心上执行。这意味着当我的机器运行Go程序的时候，我有8个线程可以工作，每个线程会分配一个独立的P。

在Go程序的运行过程中，每个Go程序会初始化一个Goroutine(G)，Goroutine本质上是协程（Coroutine），因为我们用的是Go语言，所以把字母C替换成了G，于是得到了一个词Goroutine。你可以把Goroutine理解为应用程序级别的线程，它和OS线程有很多相似之处。正如OS线程在内核上进行上线文切换一样，Goroutines在M上进行上下文切换。

最后一个难题是运行队列(run queue)。在Go的调度器中有两种运行队列：全局运行队列（GRQ）和本地运行队列（LRQ）。每个P都有一个LRQ，用于管理分配在这个P上的上下文中执行的Goroutine。这些Goroutine轮流在这个P分配的M上进行上下文切换。GRQ用来管理尚未分配给P的Goroutine，有一个过程是把GRQ上的goroutine移动到LRQ上，这个我们稍后讨论。

图二描述了全部上面提到的组件。

图二

94_figure2.png

协同调度

在第一篇文章中我们讨论过，操作系统调度是一个抢占式调度，本质上你无法预测调度程序在什么时间执行了什么操作，内核做决策的时候一切都是不可控的，运行在操作系统上的应用程序无法控制内核中发生的事情，除非使用了比如“atomic”和“mutex”这类同步原语。

Go调度器是Go程序运行的一部分，并内置在你的应用程序中，这就说明Go调度器是运行在内核之上的用户空间。Go调度器的当前实现不是抢占式，而是协同调度，也就意味着，调度程序需要在代码中明确定义用户空间事件，并在安全的地方进行调度决策。

这种设计的亮点在于看起来调度器是抢占式的，你无法预测Go调度器要做什么，因为这个调度决策是并不是由开发者决定的，而是在Go运行过程中进行的。因此以抢占式调度器的方式去思考就变的很重要，因为它具有不确定性，这不是一件容易的事。

Goroutine的状态

与线程一样，Goroutine也拥有三个状态，可以是三种状态中的一种：Waiting,Runnable或者Executing

Waiting:这个状态表示Goroutine目前已经停止并等待一些东西再继续运行。这可能是在等待系统的操作（系统调用）或同步调用（原子操作和互斥操作）等。这些类型的延迟是性能不佳的根本原因。

Runnable:这个状态表示，Goroutine需要在M上的时间片来运行指令，如果同时有很多Goroutine需要时间片，那么这个等待时间就会变长，同样的，每个Goroutine获取的每个时间片就更短。这种类型的延迟也是性能不佳的原因。

Executing:这个状态表示，Goroutine已被置于M并正在执行其指令，与应用程序相关的工作即将完，这是每个人都期望的结果。

上下文切换

Go调度器需要明确定义的用户空间事件，并在代码中的安全点进行上下文切换，这些事件和安全点在方法调用中体现。函数调用对Go调度器的运行状况至关重要。今天（使用Go 1.11或更低版本），如果你运行一段没有任何方法调用的tight loop，那么将会因为调度器和垃圾回收器而出现延迟，函数调用在合理的时间范围内发生是至关重要的。

注意：在Go的1.12版本有一项提议被采纳，Go的调度器允许在执行tight loop时应用非协作抢占的技术。

Go程序中有四类事件可能触发调度决策。

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

使用关键词go

关键字go是你创建Goroutine的方式。一旦创建了新的Goroutine，调度器就有可能进行一次调度决策。

垃圾回收

由于GC在运行过程中会使用自己的Goroutine，这些Goroutine都需要M上的时间片，因此这会导致GC产生大量的调度混乱。但是调度器非常了解Goroutine在做什么，会作出明智的调度决策，其中一项是决策是，当一个Goroutine要接触一个没有被使用的堆时，会对它进行一次上下文切换（PS：原文是“One smart decision is context-switching a Goroutine that wants to touch the heap with those that don’t touch the heap during GC”，不知道这么理解对不对）。当GC运行时，会有许多决策。

系统调用

Goroutine进行系统调用会导致Goroutine阻塞M，有时调度器会进行上线文切换，将这个Goroutine换下，并将一个新的Goroutine换到这个M上。然而有的时候，需要新的M来继续执行在P中排队的Goroutine，这是如何工作的的将在下一章详细解释。

同步和编排治理

如果调用了原子操作，互斥或者通道，会导致Goroutine阻塞，调度器会上线文切换一个新的Goroutine运行，一旦这个Goroutine可以再次运行了，它会重新排队并最终通过上下文切换回到M上。

异步系统调用

当你运行的操作系统能够异步执行系统调用的时候，可以使用称为网络轮询器("network poller")""的东西来更有效地处理系统调用。这是通过在这些相应的OS中使用kqueue（MacOS），epoll（Linux）或iocp（Windows）来实现的。

基于网络的系统调用可以使用操作系统的异步处理，今天我们使用的很多操作系统都可以实现。network poller这个名字的由来正是因为它主要用来处理网络请求。通过使用network poller来进行网络系统调用，调度器就可以防止Goroutine在进行系统调用时阻塞M。这有助于保持M执行P的LRQ中的Goroutine时可用，且无需创建新的M，这也有助于减少OS上的调度负载。

查看其工作原理的最佳方法是运行示例。

图3

94_figure3.png

图3显示了基本调度图。Goroutine-1正在M上执行，还有3个Goroutine在LRQ上等待获取M时间片。网络轮询器此时空闲。

图4

94_figure4.png

在图4中，Goroutine-1想要进行网络系统调用，因此Goroutine-1被移动到网络轮询器并且发起异步网络系统调用。一旦Goroutine-1移动到网络轮询器，M现在可以执行LRQ上的其他Goroutine。在这种情况下，Goroutine-2被上下文切换到了M上。

图5

94_figure5.png

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

同步系统调用

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

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

让我们来看看将导致M阻塞的同步系统调用（如文件I / O）所发生的情况。

图6

94_figure6.png

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

图7

94_figure7.png

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

图8

94_figure8.png

在图8中，由Goroutine-1产生的阻塞系统调用完成。此时，Goroutine-1移回LRQ并再次由P服务。M1会放在侧面以备将来再次使用。

工作窃取

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

让我们来看一个例子。

图9

94_figure9.png

在图9中，我们有一个多线程Go程序，其中有两个P，每个服务于四个Goroutine，GRQ中有一个Goroutine。如果一个P的所有Goroutine很快执行完毕会发生什么？

图10

94_figure10.png

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

代码2

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需要检测在P2的LRQ上的 Goroutine并获取它找到的一半。

图11

94_figure11.png

在图11中，Goroutine的一半来自P2，现在P1可以执行那些Goroutine。
如果P2完成为其所有Goroutine并且P1的LRQ中没有任何东西会发生什么？

图12

94_figure12.png

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

图13

94_figure13.png

在图13中，P2从GRQ窃取了Goroutine-9并开始执行工作。所有这些偷窃工作的好处在于它允许M保持忙碌而不会空闲。这项工作窃取在内部被视为旋转操作。这种自旋还有其他好处，在JBD（一个女工程师）的一篇博客work-stealing里有很好的解释

实例

有了相应的机制和语义，我们来看看如何将所有这些结合在一起，以便Go调度器能够执行更多的工作。想象一下用C编写的多线程应用程序，其中程序管理两个OS线程，它们相互传递消息。

图14

94_figure14.png

在图14中，有2个线程来回传递消息。线程1在Core1上进行上下文切换，线程1将其消息发送到线程2。

注意：消息的传递方式并不重要。重要的是运行过程中线程的状态。

图15

94_figure15.png

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

图16

94_figure16.png

在图16中，T2的消息被T1接受，再次进行上线文切换。现在T2从执行状态切换到等待状态和T1从等待状态切换到可运行状态最后回到执行状态，允许它处理并发回新消息。

所有这些上下文切换和状态更改都需要时间来执行，这限制了工作的完成速度。由于每个上下文切换可能会产生50纳秒的延迟，并且理论上硬件每纳秒执行12条指令，因此大约会有600条指令在此期间没有执行。由于这些线程也在不同的内核之间切换，因缓存未命中引起额外延迟的可能性也很高。

相同的例子，这次使用Goroutine和Go调度器。

图17

94_figure17.png

在图17中，有两个Goroutine正在相互协调，来回传递消息。G1在M1上进行上下文切换，M1在Core 1上运行，因此G1可以执行操作将消息发送给G2。

图18

94_figure18.png

在图18中，一旦G1完成发送消息，它需要等待回复，这让G1在M1上进行上下文切换进入等待状态。一旦G2收到这个消息，它将进入可执行状态，现在Go调度器可以进行上线文切换，将G2切换到M1上执行，此时仍然在core 1上运行。接下来，G2处理消息并将消息发送回G1。

图19

94_figure19.png

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

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

在使用Goroutines的情况下，全程使用相同的OS线程和核心。这意味着，从操作系统的角度来看，操作系统线程永远不会进入等待状态;我们使用Threads时因为上下文切换造成的指令损失，在使用Goroutine时不会丢失。

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

结论

Go调度器在设计方面充分考虑到了操作系统与硬件工作的复杂性，这方面确实令人惊讶。在操作系统级别，将IO/Blocking工作转换为CPU-bound工作，这一点在充分利用CPU方面取得了巨大的成功，这也是为什么你不需要更多的虚拟内核，你可以合理的认为每个虚拟内核上只需要一个操作系统线程，就可以完成所有工作。这样对于网络应用程序和其他应用程序可以不必对OS线程造成阻塞。

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