理解golang调度之二 ：Go调度器

第一篇文章解释了关于操作系统层级的调度，我认为这对于理解 Go 的调度是很重要的。这一部分我会在语义层级解释Go调度器是如何工作的，并且着重关注它的一些高级行为。Go 调度器是一个十分复杂的系统，细节不重要，重要的是对于其工作和行为有一个好的理解,这会让你做出更好的工程方面的决定。

从一个程序开始

当你的go程序启动，主机上定义的每一个虚拟内核都会为它分配一个 逻辑处理器(P) ，如果你的处理器上每个物理内核有多个硬件线程（超线程），每个硬件线程对于你的go程序来说就是一个虚拟内核。为了理解这个事情，看一下我的MacBook Pro的系统配置。

图2.1

你可以看到一个单独处理器有4个物理核心。配置表没有显示每个物理核心有多少个硬件线程。Intel Core i7 处理器有自己的超线程，也就是每个物理内核上有两个硬件线程。因此Go程序知道并行执行操作系统线程的时候，会有8个虚拟内核可以用

为了测试这个事情，看一下下面的程序

L1

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代表机器(machine)。这个线程是OS来处理的并且OS还负责把线程放置到一个core上去执行。这意味着当我跑一个Go程序在我的机器上，我有8个可用的线程去执行我的工作，每个线程单独连到一个P上。

每个Go程序同时也会有一个初始的 Goroutine（G） 。一个Goroutine本质上是一个协程（Coroutine），但是在go里，把字面“C”替换为“G”所以我们叫Goroutine。你可以认为Goroutine是一个用户程序级别的线程而且它跟OS线程很多方面都类似。区别仅仅是OS线程在内核(Core)上进行上下文切换（换上和换下）,而Goroutines是在M上。

最后一个让人困惑的就是运行队列。在Go 调度器中有两种不同的运行队列：全局运行队列（ GRQ ）和本地运行队列( LRQ )。每个P会分配一个LRQ去处理P的上下文要执行的Goroutines 。这些Goroutines会在绑定到P的M上进行上下文的切换。GRQ会处理还没有分配到P上的Goroutines 。Goroutines从GRQ挪到LRQ的过程一会我们一会儿会说。

图2.2是包含了所有相关组件的一张图片

图2.2

协作调度

我们在第一部分的内容讲到了，OS调度器是一个抢占式调度器。也就是说你不知道调度器下一步会执行什么。内核所做的决定都是不确定的。运行在OS顶层的应用程序无法控制内核里面的调度，除非你使用同步的原始操作，例如 atomic 指令和 mutex 调用

Go调度器是Go runtime的一部分，Go runtime会编译到你应用程序里。这意味着Go调度器运行在内核之上的用户空间(user space)

当前Go调度器采用的不是抢占式调度器，而是协作试调度器。协作试调度器，意味着调度器需要代码中安全点处发生的定义好的用户空间事件去做出调度决策。

Go的协作调度有一个非常棒的地方就是，它看上去像是抢占式的。你没办法预测Go调度器将要做什么，这是因为协作试调度器的决策不是开发人员而是go runtime去做的。将Go调度器看做是一个抢占式调度器是很重要的，因为调度是不确定的，这里不需要再过多延伸。

Goroutine状态

和线程一样。Goroutine有三种相同的高级状态。Goroutine可以是任何一种状态：等待（Waiting）、可执行（Runnable）、运行中（Executing）.

等待：此时Goroutine已经停止并且等待事件发生来去再次执行。这可能是出于等待操作系统（系统调用）或同步调用（原子操作atomic和互斥操作mutex）等原因。 这些类型的延迟是性能不佳的根本原因。

可执行： 此时Goroutine想要在M上执行分配给它的指令。如果有很多Goroutines想要M上的时间片，那么Goroutines必须等待更长时间。而且，随着更多Goroutines争夺时间片，单独Goroutines分配的时间就会缩短，这种类型的调度延时也会导致性能很差。

运行中：这意味着Goroutines已经放置在M上并且执行它的指令。此时应用程序的工作即将完成，这是我们想要的状态。

上下文切换（Context Switching）

Go调度程序需要明确定义的用户空间事件，这些事件发生在代码中的安全点以进行上下文切换。这些事件和安全点在函数调用时发生。函数调用对Go调度器的运行状况至关重要。Go 1.11 或者更低版本中，如果你跑一个不做函数调用的死循环，会导致调度器延时和垃圾回收延时。合理的时机使用函数调用十分重要。

注意： 相关issue和建议 已经被提出来，并且应用到了1.12版本中。应用非协作的抢占式技术，使得在紧密循环中进行抢占。

Go程序中有4种类型的事件，允许调度器去做出调度决策。这不意味着某一个事件总是会发生，而是说调度器有机会去做出调度。

• 使用关键字 go
• 垃圾回收
• 系统调用
• 同步处理

使用关键字 go

使用关键字go来创建Goroutine。一旦一个新的Goroutine创建好，调度器便有机会去做出调度决定

垃圾回收

GC时候会有它自己的Goroutines，这些Goroutines也需要M上的时间片。这会导致GC产生很多调度混乱。但是调度器很聪明，它知道Goroutines在做什么，然后会做出合理的调度决策。一个聪明的决定就是对那些想要触及到堆的Goroutine和GC时候不会触及堆的Goroutine进行上下文切换。GC发生的时候会产生很多调度决策。

系统调用

如果一个Goroutine做出了会导致M阻塞的系统调用，调度器有时候会用一个新的Goroutine从M上替换下这个Goroutine。但是有时候会需要一个新的M去执行挂在P队列上的Goroutine，这种情况我会在下一部分讲解。

同步处理

如果atomic、mutex或者是channel操作的调用导致了Goroutine的阻塞，调度器会切换一个新的Goroutine去执行。一旦那个Goroutine又可以重新执行了，他会被挂到队列上并最终在M上会上下文切换回去。

异步系统调用

当OS有能力去处理异步的系统调用时候，使用 网络轮询器(network poller) 去处理系统调用会更加高效。不同的操作系统分别使用了kqueue (MacOS)、epoll (Linux) 、 iocp (Windows) 对此作了实现。

今天许多操作系统都能处理基于网络(Networking-based)的系统调用。这也是网络轮询器(network poller)这一名字的由来，因为它的主要用途就是处理网络操作。网络系统上通过使用network poller，调度器可以防止Goroutines在系统调用的时候阻塞M。这可以让M能够去执行其他在P的 LRQ上面的其他Goroutines而不是再去新建一个M。这可以减少OS上的调度加载。

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

图2.3

图2.3展示了基本的调用图例。Goroutine-1正在M上面执行并且有3个Goroutine在LRQ上等待想要获取M的时间片。network poller此时空闲没事做。

图2.4

图2.4中 Goroutine-1想要进行network system调用，因此Goroutine-1移到了network poller上面然后处理异步调用，一旦Goroutine-1从M上移到network poller，M便可以去执行其他LRQ上的Goroutine。此时 Goroutine-2切换到了M上面。

图2.5

图2.5中，network poller的异步网络调用完成并且Goroutine-1回到了P的LRQ上面。一旦Goroutine-1能够切换回M上，Go的相关代码便能够再次执行。很大好处是，在执行network system调用时候，我们不需要其他额外的M。network poller有一个OS线程能够有效的处理事件循环。

同步系统调用

当Goroutine想进行系统调用无法异进行该怎么办呢？这种情况下，无法使用 network poller并且Goroutine产生的系统调用会阻塞M。很不幸但是我们无法阻止这种情况发生。一个例子就是基于文件的系统调用。如果你使用CGO，当你调用C函数的时候也会有其他情况发生会阻塞M。

注意：Windows操作系统确实有能力去异步进行基于文件的系统调用。从技术上讲，在Windows上运行时可以使用network poller。

我们看一下同步系统调用(比如file I/O)阻塞M的时候会发生什么。

图2.6

图2.6又一次展示了我们的基本调度图例。但是这一次Goroutine-1的同步系统调用会阻塞M1

图2.7

图2.7中，调度器能够确定Goroutine-1已经阻塞了M。这时，调度器会从P上拿下来M1，Goroutine-1依旧在M1上。然后调度器会拿来一个新的M2去服务P。此时LRQ上的Goroutine-2会上下文切换到M2上。如果已经有一个可用的M了，那么直接用它会比新建一个M要更快。

图2.8

图2.8中，Goroutine-1的阻塞系统调用结束了。此时Goroutine-1能够回到LRQ的后面并且能够重新被P执行。M1之后会被放置一边供未来类似的情况使用。

工作窃取（Work Stealing）

调度器的另一个层面，它其实也是一个work-stealing的调度器。这在一些情况下能够让调度更有效率。你最不想看到的事情是一个M进入了等待状态，因为这一旦发生，OS将会把M从core上切换下来。这意味着即使有可执行的Goroutine， P此时也没法干活了，直到M重新切换回core上。Work stealing同时也会平衡P上的所有Goroutines从而能够使工作更好的分配，更有效率。

让我们看一个例子

图2.9

图2.9里，我们有个多线程的Go程序。两个P分别服务4个Goroutines。并且一个单独的Goroutine在GRQ上。那么如果其中一个P很快执行完它所有的Goroutines会怎么样？

图2.10

P1没有更多Goroutine去执行了，但是在GRQ和P2的LRQ中都有可执行的Goroutines。这种情况P1会去窃取工作，Work Stealing的规则如下

L2

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.
}
复制代码

所以基于L2的规则，P1需要去看P2的LRQ上的Goroutines并且拿走一半。

图2.11

图2.11中，一半的Goroutines从P2上偷走，P1现在可以执行那些Goroutines

如果P2完成了所有Goroutines的执行，并且P1的LRQ上已经空了会怎么样？

图2.12

图2.12中，P2完成了它所有的工作，现在想要偷点什么。首先，它会去看P1的LRQ却发现什么也没有了。接下来他会去看GRQ。他会找到Goroutine-9

图2.13

图2.13中，P2从GRQ上偷走了Goroutine-9并且开始执行它的工作。这种work stealing的很大好处是，它让M一直有事情做而不是闲下来。这种work stealing 可以看做内部的M的轮转，这种轮转的好处在这篇博客里做了很好的解释。

实际例子

我想让你看一下Go调度器为了在同一时间里做更多事情，这一切是如何一块发生的。首先想象这样一个多线程的 C语言 应用，程序需要处理两个OS线程，他们俩互相进行通信。

图2.14

图2.14中，有两个线程，相互通信。线程1上下文切换到Core1上并且现在正在执行，这允许线程1向线程2发送消息。

注意：通信方式不重要。重要的是这个过程里的线程状态。

图2.15

在图2.15中，一旦线程1完成发送消息，它就需要等待响应。这会导致线程1从Core1切换下来并处于等待状态。一旦线程2收到消息通知，它就会进入可执行的状态。现在OS进行上下文切换然后线程2在一个Core2上面执行。接下来线程2处理消息然后给线程1发送一个新消息。

图2.16

图2.16里。随着线程1收到线程2的消息，又一次发生了上下文切换。现在线程2从执行中的状态切换为等待的状态。并且线程1从等待状态切换到了可执行状态，最终回到运行状态。现在线程1可以处理并发送一个新消息回去。

所有的上下文切换(context switches)和状态的改变都需要花费时间去处理，这就限制了工作速度。每一次上下文切换 会导致50ns的潜在延迟，硬件执行指令的期望时间是每ns 12个指令，你会看到上下文切换的时候就少执行600个指令。因为这些线程在不同的core之前切来切去，cache-line未命中导致的延迟也会增加。

我们来看一下相同例子，使用Goroutines和Go调度器做替换。

图2.17

图2.17中，有两个Goroutines相互传递消息。G1上下文切换到M1上进行工作处理，之前这都是在Core1上发生的事情。现在是G1向G2发送消息。

图2.18

图2.18中，一旦G1发送完消息，它就会等待响应返回。这会让G1从M1上切换下来，并且进入到等到状态。一旦G2收到消息通知，它会进入可执行状态。现在Go调度器会把G2切换到M1上去执行，M1依旧在Core1上跑着。接下来G2处理消息然后给G1发送一个新消息。

图2.19

在图2.19中，随着G1收到G2发送来的消息，又一次发生上下文切换。现在G2从执行中的状态切换到等待状态并且G1从等待中切换到可执行状态，最终回到运行的状态，G1又能够处理并向G2发送新的消息了。

表面上事情并没有什么不同。不论你使用线程还是Goroutines都有上下文切换和状态改变的过程。但是线程和Goroutines之间有一个重要的差别可能不会被明显注意到。

在使用Goroutines的场景，整个过程一直使用的是相同的OS线程和Core。这也就意味着，从OS的视角，OS线程从来没有进入到waiting状态，一次也没有。结果就是我们在线程中上下文切换丢失的指令在Goroutines中不会丢失。

本质上讲，在OS层级go把io/blocking类型的工作转变成了cpu密集型的工作。由于所有上下文切换的过程都发生在应用程序的级别，上下文切换不会像线程一样丢掉600个指令（平均来说）。Go调度器还有助于提高cache-line的效率和NUMA。这也是为什么我们不需要比虚拟内核数更多的线程。在Go里，随着时间推移更多事情会被处理，因为Go调度器会尝试用更少的线程并且每个线程去做更多事情，这有助于减少OS和硬件层级的加载延迟。

结论

Go调度程序的设计在考虑操作系统和硬件工作复杂性方面确实令人惊讶。 在操作系统级别将IO /blocking工作转换为CPU密集型工作，是在利用更多CPU容量的过程中获得巨大成功的地方。 这就是为什么你不需要比虚拟内核数更多的OS线程。 每个虚拟内核一个OS线程情况下，你可以合理的期望你的所有工作(CPU密集、IO密集)都能够完成。对于网络程序和那些不需要系统调用阻塞OS线程的程序，也能够完成。

作为开发人员，你依旧需要理解在处理不同类型工作的时候你的程序正在做什么。你不能为了想要更好性能去无限制创建goroutine。Less is always more，但是通过理解了go调度器，你可以更好的做出决定。下一部分，我会探讨以保守的方式利用并发来提升性能的方法，但是对于代码的复杂性还是要做出平衡。