Go语言在2016年再次拿下TIBOE年度编程语言称号，这充分证明了Go语言这几年在全世界范围内的受欢迎程度。如果要对世界范围内的gopher发起一次“你究竟喜欢Go的哪一点”的调查，我相信很多Gopher会提到：goroutine。

Goroutine是Go语言原生支持并发的具体实现，你的Go代码都无一例外地跑在goroutine中。你可以启动许多甚至成千上万的goroutine，Go的runtime负责对goroutine进行管理。所谓的管理就是“调度”，粗糙地说调度就是决定何时哪个goroutine将获得资源开始执行、哪个goroutine应该停止执行让出资源、哪个goroutine应该被唤醒恢复执行等。goroutine的调度是Go team care的事情，大多数gopher们无需关心。但个人觉得适当了解一下Goroutine的调度模型和原理，对于编写出更好的go代码是大有裨益的。因此，在这篇文章中，我将和大家一起来探究一下goroutine调度器的演化以及模型/原理。

一、Goroutine调度器

提到“调度”，我们首先想到的就是操作系统对进程、线程的调度。操作系统调度器会将系统中的多个线程按照一定算法调度到物理CPU上去运行。传统的编程语言比如C、C++等的并发实现实际上就是基于操作系统调度的，即程序负责创建线程(一般通过pthread等lib调用实现)，操作系统负责调度。这种传统支持并发的方式有诸多不足：

  • 复杂
    • 创建容易，退出难：做过C/C++ Programming的童鞋都知道，创建一个thread(比如利用pthread)虽然参数也不少，但好歹可以接受。但一旦涉及到thread的退出，就要考虑thread是detached，还是需要parent thread去join？是否需要在thread中设置cancel point，以保证join时能顺利退出？
    • 并发单元间通信困难，易错：多个thread之间的通信虽然有多种机制可选，但用起来是相当复杂；并且一旦涉及到shared memory，就会用到各种lock，死锁便成为家常便饭；
    • thread stack size的设定：是使用默认的，还是设置的大一些，或者小一些呢？
  • 难于scaling

为此，Go采用了用户层轻量级thread或者说是类coroutine的概念来解决这些问题，Go将之称为”goroutine“。goroutine占用的资源非常小(Go 1.4将每个goroutine stack的size默认设置为2k)，goroutine调度的切换也不用陷入(trap)操作系统内核层完成，代价很低。因此，一个Go程序中可以创建成千上万个并发的goroutine。所有的Go代码都在goroutine中执行，哪怕是go的runtime也不例外。将这些goroutines按照一定算法放到“CPU”上执行的程序就称为goroutine调度器或goroutine scheduler。

不过，一个Go程序对于操作系统来说只是一个用户层程序，对于操作系统而言，它的眼中只有thread，它甚至不知道有什么叫Goroutine的东西的存在。goroutine的调度全要靠Go自己完成，实现Go程序内goroutine之间“公平”的竞争“CPU”资源，这个任务就落到了Go runtime头上，要知道在一个Go程序中，除了用户代码，剩下的就是go runtime了。

于是Goroutine的调度问题就演变为go runtime如何将程序内的众多goroutine按照一定算法调度到“CPU”资源上运行了。在操作系统层面，Thread竞争的“CPU”资源是真实的物理CPU，但在Go程序层面，各个Goroutine要竞争的”CPU”资源是什么呢？Go程序是用户层程序，它本身整体是运行在一个或多个操作系统线程上的，因此goroutine们要竞争的所谓“CPU”资源就是操作系统线程。这样Go scheduler的任务就明确了：将goroutines按照一定算法放到不同的操作系统线程中去执行。这种在语言层面自带调度器的，我们称之为原生支持并发。

二、Go调度器模型与演化过程

1、G-M模型

2012年3月28日，Go 1.0正式发布。在这个版本中，Go team实现了一个简单的调度器。在这个调度器中，每个goroutine对应于runtime中的一个抽象结构：G，而os thread作为“物理CPU”的存在而被抽象为一个结构：M(machine)。这个结构虽然简单，但是却存在着许多问题。前Intel blackbelt工程师、现Google工程师Dmitry Vyukov在其《Scalable Go Scheduler Design》一文中指出了G-M模型的一个重要不足： 限制了Go并发程序的伸缩性，尤其是对那些有高吞吐或并行计算需求的服务程序。主要体现在如下几个方面：

  • 单一全局互斥锁(Sched.Lock)和集中状态存储的存在导致所有goroutine相关操作，比如：创建、重新调度等都要上锁；
  • goroutine传递问题：M经常在M之间传递”可运行”的goroutine，这导致调度延迟增大以及额外的性能损耗；
  • 每个M做内存缓存，导致内存占用过高，数据局部性较差；
  • 由于syscall调用而形成的剧烈的worker thread阻塞和解除阻塞，导致额外的性能损耗。

2、G-P-M模型

于是Dmitry Vyukov亲自操刀改进Go scheduler，在Go 1.1中实现了G-P-M调度模型和work stealing算法，这个模型一直沿用至今：

有名人曾说过：“计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决”，我觉得Dmitry Vyukov的G-P-M模型恰是这一理论的践行者。Dmitry Vyukov通过向G-M模型中增加了一个P，实现了Go scheduler的scalable。

P是一个“逻辑Proccessor”，每个G要想真正运行起来，首先需要被分配一个P（进入到P的local runq中，这里暂忽略global runq那个环节）。对于G来说，P就是运行它的“CPU”，可以说：G的眼里只有P。但从Go scheduler视角来看，真正的“CPU”是M，只有将P和M绑定才能让P的runq中G得以真实运行起来。这样的P与M的关系，就好比Linux操作系统调度层面用户线程(user thread)与核心线程(kernel thread)的对应关系那样(N x M)。

3、抢占式调度

G-P-M模型的实现算是Go scheduler的一大进步，但Scheduler仍然有一个头疼的问题，那就是不支持抢占式调度，导致一旦某个G中出现死循环或永久循环的代码逻辑，那么G将永久占用分配给它的P和M，位于同一个P中的其他G将得不到调度，出现“饿死”的情况。更为严重的是，当只有一个P时(GOMAXPROCS=1)时，整个Go程序中的其他G都将“饿死”。于是Dmitry Vyukov又提出了《Go Preemptive Scheduler Design》并在Go 1.2中实现了“抢占式”调度。

这个抢占式调度的原理则是在每个函数或方法的入口，加上一段额外的代码，让runtime有机会检查是否需要执行抢占调度。这种解决方案只能说局部解决了“饿死”问题，对于没有函数调用，纯算法循环计算的G，scheduler依然无法抢占。

4、NUMA调度模型

从Go 1.2以后，Go似乎将重点放在了对GC的低延迟的优化上了，对scheduler的优化和改进似乎不那么热心了，只是伴随着GC的改进而作了些小的改动。Dmitry Vyukov在2014年9月提出了一个新的proposal design doc：《NUMA‐aware scheduler for Go》，作为未来Go scheduler演进方向的一个提议，不过至今似乎这个proposal也没有列入开发计划。

5、其他优化

Go runtime已经实现了netpoller，这使得即便G发起网络I/O操作也不会导致M被阻塞（仅阻塞G），从而不会导致大量M被创建出来。但是对于regular file的I/O操作一旦阻塞，那么M将进入sleep状态，等待I/O返回后被唤醒；这种情况下P将与sleep的M分离，再选择一个idle的M。如果此时没有idle的M，则会新创建一个M，这就是为何大量I/O操作导致大量Thread被创建的原因。

Ian Lance Taylor在Go 1.9 dev周期中增加了一个Poller for os package的功能，这个功能可以像netpoller那样，在G操作支持pollable的fd时，仅阻塞G，而不阻塞M。不过该功能依然不能对regular file有效，regular file不是pollable的。不过，对于scheduler而言，这也算是一个进步了。

三、Go调度器原理的进一步理解

1、G、P、M

关于G、P、M的定义，大家可以参见$GOROOT/src/runtime/runtime2.go这个源文件。这三个struct都是大块儿头，每个struct定义都包含十几个甚至二、三十个字段。像scheduler这样的核心代码向来很复杂，考虑的因素也非常多，代码“耦合”成一坨。不过从复杂的代码中，我们依然可以看出来G、P、M的各自大致用途（当然雨痕老师的源码分析功不可没），这里简要说明一下：

  • G: 表示goroutine，存储了goroutine的执行stack信息、goroutine状态以及goroutine的任务函数等；另外G对象是可以重用的。
  • P: 表示逻辑processor，P的数量决定了系统内最大可并行的G的数量（前提：系统的物理cpu核数>=P的数量）；P的最大作用还是其拥有的各种G对象队列、链表、一些cache和状态。
  • M: M代表着真正的执行计算资源。在绑定有效的p后，进入schedule循环；而schedule循环的机制大致是从各种队列、p的本地队列中获取G，切换到G的执行栈上并执行G的函数，调用goexit做清理工作并回到m，如此反复。M并不保留G状态，这是G可以跨M调度的基础。

2、G被抢占调度

和操作系统按时间片调度线程不同，Go并没有时间片的概念。如果某个G没有进行system call调用、没有进行I/O操作、没有阻塞在一个channel操作上，那么m是如何让G停下来并调度下一个runnable G的呢？答案是：G是被抢占调度的。

前面说过，除非极端的无限循环或死循环，否则只要G调用函数，Go runtime就有抢占G的机会。Go程序启动时，runtime会去启动一个名为sysmon的m(一般称为监控线程)，该m无需绑定p即可运行，该m在整个Go程序的运行过程中至关重要：

sysmon每20us~10ms启动一次，按照《Go语言学习笔记》中的总结，sysmon主要完成如下工作：

  • 释放闲置超过5分钟的span物理内存；
  • 如果超过2分钟没有垃圾回收，强制执行；
  • 将长时间未处理的netpoll结果添加到任务队列；
  • 向长时间运行的G任务发出抢占调度；
  • 收回因syscall长时间阻塞的P；

我们看到sysmon将“向长时间运行的G任务发出抢占调度”，这个事情由retake实施：

可以看出，如果一个G任务运行10ms，sysmon就会认为其运行时间太久而发出抢占式调度的请求。一旦G的抢占标志位被设为true，那么待这个G下一次调用函数或方法时，runtime便可以将G抢占，并移出运行状态，放入P的local runq中，等待下一次被调度。

3、channel阻塞或network I/O情况下的调度

如果G被阻塞在某个channel操作或network I/O操作上时，G会被放置到某个wait队列中，而M会尝试运行下一个runnable的G；如果此时没有runnable的G供m运行，那么m将解绑P，并进入sleep状态。当I/O available或channel操作完成，在wait队列中的G会被唤醒，标记为runnable，放入到某P的队列中，绑定一个M继续执行。

4、system call阻塞情况下的调度

如果G被阻塞在某个system call操作上，那么不光G会阻塞，执行该G的M也会解绑P(实质是被sysmon抢走了)，与G一起进入sleep状态。如果此时有idle的M，则P与其绑定继续执行其他G；如果没有idle M，但仍然有其他G要去执行，那么就会创建一个新M。

当阻塞在syscall上的G完成syscall调用后，G会去尝试获取一个可用的P，如果没有可用的P，那么G会被标记为runnable，之前的那个sleep的M将再次进入sleep。

四、调度器状态的查看方法

Go提供了调度器当前状态的查看方法：使用Go运行时环境变量GODEBUG。

GODEBUG这个Go运行时环境变量很是强大，通过给其传入不同的key1=value1,key2=value2… 组合，Go的runtime会输出不同的调试信息，比如在这里我们给GODEBUG传入了”schedtrace=1000″，其含义就是每1000ms，打印输出一次goroutine scheduler的状态，每次一行。每一行各字段含义如下：

我们还可以输出每个goroutine、m和p的详细调度信息，但对于Go user来说，绝大多数时间这是不必要的：

关于go scheduler调试信息输出的详细信息，可以参考Dmitry Vyukov的大作：《Debugging performance issues in Go programs》。这也应该是每个gopher必读的经典文章。当然更详尽的代码可参考$GOROOT/src/runtime/proc.go中的schedtrace函数。

基础

Go运行时管理调度、垃圾收集和goroutines的运行时环境。在这里，我将只关注调度程序。

运行时调度器通过将它们映射到操作系统线程来运行goroutines。Goroutines是线程的轻量级版本，启动成本非常低。每一个goroutine都是由一个名为G的结构体描述的，它包含了跟踪其堆栈和当前状态所必需的字段。所以,G = goroutine。

运行时跟踪每个G，并将它们映射到逻辑处理器上，命名为P。P可以被看作是一个抽象的资源或上下文，需要被获取，因此OS线程（称为M或机器）可以执行G。你可以通过调用 runtime.GOMAXPROCS(numLogicalProcessors) 来控制运行时的逻辑处理器，如果你打算调整这个参数（或许不应该），设置一次并忘记它，因为它需要“停止一切”GC暂停。

从本质上讲，操作系统运行线程，执行你的代码。Go的诀窍是，编译器在不同的地方插入调用到Go运行时，例如通过通道发送一个值，对运行时包进行调用），这样就可以通知调度程序并采取行动。

Ms，Ps&Gs之间的互动

Ms、Ps和Gs之间的交互有点复杂。看一下这个工作流程图：

在这里我们可以看到，对于G来说有两种类型的队列：在“schedt”结构中有一个全局队列（很少使用），并且每个P维护一个可运行的G队列。

为了执行一个goroutine，M需要保存上下文P.机器，然后弹出它的goroutines，执行代码。

当你安排一个新的goroutine（做一个go func（）调用）时，它被放置到P的队列中。这里有一个有趣的偷工调度算法，当M完成了某个G的执行，然后它试图从队列中取出另一个G，它是空的，然后它随机地选择另一个P并试图从它中偷取一半的可运行的G！

当你的goroutine做一个阻塞的系统调用时，会发生一些有趣的事情。阻塞系统调用将被拦截，如果要运行Gs，运行时将从P中分离出线程并创建一个新的OS线程（如果空闲线程不存在的话）来服务该处理器。

当一个系统调用恢复时，goroutine被放回一个本地运行队列，线程会自动放置（意味着线程不会运行），并将自己插入到空闲线程列表中。

如果goroutine进行网络调用，运行时也会执行类似的操作。这个调用将被拦截，但是因为Go有一个集成的网络轮询器，它有自己的线程，它将被分配给它。

如果当前的goroutine被阻塞，那么运行时将运行一个不同的goroutine：

  • 阻塞系统调用（例如打开一个文件），
  • 网络输入，
  • 通道操作，
  • 同步包中的原语。

调度程序跟踪

Go允许跟踪运行时调度程序。这是通过GODEBUG环境变量完成的：

下面是它给出的输出示例：

注意，它使用了与G、M和P以及它们的状态相同的概念，比如P的队列大小。通常，你不需要那么多的细节，所以你可以使用：

此外，还有一个名为go tool trace的高级工具，它有一个UI，允许我们探索，程序运行时正在做什么。

MPG画图示意

调度模型简介

groutine能拥有强大的并发实现是通过GPM调度模型实现，下面就来解释下goroutine的调度模型。

Go的调度器内部有四个重要的结构：M，P，S，Sched，如上图所示（Sched未给出） M:M代表内核级线程，一个M就是一个线程，goroutine就是跑在M之上的；M是一个很大的结构，里面维护小对象内存cache（mcache）、当前执行的goroutine、随机数发生器等等非常多的信息 G:代表一个goroutine，它有自己的栈，instruction pointer和其他信息（正在等待的channel等等），用于调度。 P:P全称是Processor，处理器，它的主要用途就是用来执行goroutine的，所以它也维护了一个goroutine队列，里面存储了所有需要它来执行的goroutine Sched：代表调度器，它维护有存储M和G的队列以及调度器的一些状态信息等。

调度实现

从上图中看，有2个物理线程M，每一个M都拥有一个处理器P，每一个也都有一个正在运行的goroutine。 P的数量可以通过GOMAXPROCS()来设置，它其实也就代表了真正的并发度，即有多少个goroutine可以同时运行。 图中灰色的那些goroutine并没有运行，而是出于ready的就绪态，正在等待被调度。P维护着这个队列（称之为runqueue）， Go语言里，启动一个goroutine很容易：go function 就行，所以每有一个go语句被执行，runqueue队列就在其末尾加入一个 goroutine，在下一个调度点，就从runqueue中取出（如何决定取哪个goroutine？）一个goroutine执行。

当一个OS线程M0陷入阻塞时（如下图)，P转而在运行M1，图中的M1可能是正被创建，或者从线程缓存中取出。

当MO返回时，它必须尝试取得一个P来运行goroutine，一般情况下，它会从其他的OS线程那里拿一个P过来， 如果没有拿到的话，它就把goroutine放在一个global runqueue里，然后自己睡眠（放入线程缓存里）。所有的P也会周期性的检查global runqueue并运行其中的goroutine，否则global runqueue上的goroutine永远无法执行。 另一种情况是P所分配的任务G很快就执行完了（分配不均），这就导致了这个处理器P很忙，但是其他的P还有任务，此时如果global runqueue没有任务G了，那么P不得不从其他的P里拿一些G来执行。一般来说，如果P从其他的P那里要拿任务的话，一般就拿run queue的一半，这就确保了每个OS线程都能充分的使用，如下图：

参考地址：

http://morsmachine.dk/go-scheduler

https://www.cnblogs.com/zkweb/p/7815600.html