Go里的GMP协程调度

概述

Go调度器的详细调度过程是什么？

GMP

M个协程绑定1个线程，模型大概如下：

G（Goroutine）

G 取自Goroutine的首字母，一个G代表一个Goroutine，Goroutine是一个与其他Goroutines并行运行在同一地址空间的go函数或方法。当 Goroutine 被调离 CPU 时，调度器代码负责把 CPU 寄存器的值保存在 G 对象的成员变量之中，当 Goroutine 被调度起来运行时，调度器代码又负责把 G 对象的成员变量所保存的寄存器的值恢复到 CPU 的寄存器。

协程之于Go调度器好比内核线程之于OS调度器，也是有着多种状态的，但因为它不可见底层核心线程的状态，因此会有更细致和复杂的状态迁移图，如下图所示：

不同状态的描述如下图所示：

Go协程状态图相比进程状态图多了收缩/扩展栈和执行系统调用两个更加细分的状态，而且同时runnable和running状态和OS的状态不是一一对应的，其实用户态无法感知到OS的就绪态、运行态和阻塞态。

M（Machine）

OS 底层线程的抽象，它本身就与一个内核线程进行绑定，每个工作线程都有唯一的一个 M 结构体的实例对象与之对应，它代表着真正执行计算的资源，由操作系统的调度器调度和管理。M 结构体对象除了记录着工作线程的诸如栈的起止位置、当前正在执行的 Goroutine 以及是否空闲等等状态信息之外，还通过指针维持着与 P 结构体的实例对象之间的绑定关系。

最多只会有 GOMAXPROCS 个活跃线程能够正常运行，因为M需要和P绑定才能运行G，而P的个数取决于设置的GOMAXPROCS，一个M阻塞了就会创建新的M。

P（Processor）

表示逻辑处理器。对 G 来说，P 相当于 CPU 核，G 只有绑定到 P(在 P 的 local runq 中)才能被调度。对 M 来说，P 提供了相关的执行环境(Context)，如内存分配状态(mcache)，任务队列(G)等。它维护一个局部 Goroutine 可运行 G 队列，工作线程优先使用自己的局部运行队列，只有必要时才会去访问全局运行队列，这可以大大减少锁冲突，提高工作线程的并发性，并且可以良好的运用程序的局部性原理。

GMP概述

1. 全局队列（Global Queue）：存放等待运行的G。
2. P的本地队列：同全局队列类似，存放的也是等待运行的G，存的数量有限，不超过256个。新建G’时，G’优先加入到P的本地队列，如果队列满了，则会把本地队列中一半的G移动到全局队列。
3. P列表：所有的P都在程序启动时创建，并保存在数组中，最多有GOMAXPROCS(可配置)个。
4. M：线程想运行任务就得获取P，从P的本地队列获取G，P队列为空时，M也会尝试从全局队列拿一批G放到P的本地队列，或从其他P的本地队列偷一半放到自己P的本地队列。M运行G，G执行之后，M会从P获取下一个G，不断重复下去。

Goroutine调度器和OS调度器是通过M结合起来的，每个M都代表了1个内核线程，OS调度器负责把内核线程分配到CPU的核上执行。对于本地运行队列，每个逻辑处理器有一个本地运行队列。如果创建一个goroutine并准备运行，这个goroutine首先会被放到调度器的全局运行队列中。之后，调度器会将全局运行队列中的goroutine分配给一个逻辑处理器，并放到这个逻辑处理器的本地运行队列中。本地运行队列中的goroutine会一直等待直到被分配的逻辑处理器执行。下图展示了操作系统线程、逻辑处理器和本地运行队列之间的关系：

有时，正在运行的goroutine需要执行一个阻塞的系统调用，如打开一个文件。当这类调用发生时，线程和goroutine会从逻辑处理器上分离，该线程会继续阻塞，等待系统调用的返回。与此同时，这个逻辑处理器就失去了用来运行的线程。所以，调度器会创建一个新线程，并将其绑定到该逻辑处理器上。之后，调度器会从本地运行队列里选择另一个goroutine来运行。一旦被阻塞的系统调用执行完成并返回，对应的goroutine会放回到本地运行队列，而之前的线程会保存好，以便之后可以继续使用。

如果一个goroutine需要做一个网络I/O调用，流程上会有些不一样。在这种情况下，goroutine会和逻辑处理器分离，并移到集成了网络轮询器的运行时。一旦该轮询器指示某个网络读或者写操作已经就绪，对应的goroutine 就会重新分配到逻辑处理器上来完成操作。

调度

调度器设计策略

复用线程：避免频繁的创建、销毁线程，而是对线程的复用。

• 1）work stealing机制

  当本线程无可运行的G时，尝试从其他线程绑定的P偷取G，而不是销毁线程。

• 2）hand off机制

  当本线程因为G进行系统调用阻塞时，线程释放绑定的P，把P转移给其他空闲的线程执行。

利用并行：GOMAXPROCS设置P的数量，最多有GOMAXPROCS个线程分布在多个CPU上同时运行。GOMAXPROCS也限制了并发的程度，比如GOMAXPROCS = 核数/2，则最多利用了一半的CPU核进行并行。

抢占：在coroutine中要等待一个协程主动让出CPU才执行下一个协程，在Go中，一个goroutine最多占用CPU 10ms，防止其他goroutine被饿死，这就是goroutine不同于coroutine的一个地方。

全局G队列：在新的调度器中依然有全局G队列，但功能已经被弱化了，当M执行work stealing从其他P偷不到G时，它可以从全局G队列获取G。

全局goroutine队列

当创建一个新的G之后优先加入本地队列，如果本地队列满了，会将本地队列的G移动到全局队列里面，当M执行work stealing从其他P偷不到G时，它可以从全局G队列获取G。

我们创建一个协程 go func()经历过程如下图：

说明：

这里有两个存储G的队列，一个是局部调度器P的本地队列、一个是全局G队列。新创建的G会先保存在P的本地队列中，如果P的本地队列已经满了就会保存在全局的队列中；处理器本地队列是一个使用数组构成的环形链表，它最多可以存储 256 个待执行任务。

G只能运行在M中，一个M必须持有一个P，M与P是1：1的关系。M会从P的本地队列弹出一个可执行状态的G来执行，如果P的本地队列为空，就会想其他的MP组合偷取一个可执行的G来执行；一个M调度G执行的过程是一个循环机制；会一直从本地队列或全局队列中获取G

M缓冲池

上面说到P的个数默认等于CPU核数，每个M必须持有一个P才可以执行G，一般情况下M的个数会略大于P的个数，这多出来的M将会在G产生系统调用时发挥作用。类似线程池，Go也提供一个M的池子，需要时从池子中获取，用完放回池子，不够用时就再创建一个。

调度例外

如果一切正常，调度器会以上述的那种方式顺畅地运行，但这个世界没这么美好，总有意外发生，以下分析goroutine在两种例外情况下的行为。

Go runtime会在下面的goroutine被阻塞的情况下运行另外一个goroutine：

用户态阻塞/唤醒

当goroutine因为channel操作或者network I/O而阻塞时（实际上golang已经用netpoller实现了goroutine网络I/O阻塞不会导致M被阻塞，仅阻塞G，这里仅仅是举个栗子），对应的G会被放置到某个wait队列(如channel的waitq)，该G的状态由_Gruning变为_Gwaitting，而M会跳过该G尝试获取并执行下一个G，如果此时没有可运行的G供M运行，那么M将解绑P，并进入sleep状态；当阻塞的G被另一端的G2唤醒时（比如channel的可读/写通知），G被标记为，尝试加入G2所在P的runnext（runnext是线程下一个需要执行的 Goroutine。）， 然后再是P的本地队列和全局队列。

系统调用阻塞

当M执行某一个G时候如果发生了阻塞操作，M会阻塞，如果当前有一些G在执行，调度器会把这个线程M从P中摘除，然后再创建一个新的操作系统的线程(如果有空闲的线程可用就复用空闲线程)来服务于这个P。当M系统调用结束时候，这个G会尝试获取一个空闲的P执行，并放入到这个P的本地队列。如果获取不到P，那么这个线程M变成休眠状态， 加入到空闲线程中，然后这个G会被放入全局队列中。

队列轮转

可见每个P维护着一个包含G的队列，不考虑G进入系统调用或IO操作的情况下，P周期性的将G调度到M中执行，执行一小段时间，将上下文保存下来，然后将G放到队列尾部，然后从队列中重新取出一个G进行调度。

除了每个P维护的G队列以外，还有一个全局的队列，每个P会周期性地查看全局队列中是否有G待运行并将其调度到M中执行，全局队列中G的来源，主要有从系统调用中恢复的G。之所以P会周期性地查看全局队列，也是为了防止全局队列中的G被饿死。

除了每个P维护的G队列以外，还有一个全局的队列，每个P会周期性地查看全局队列中是否有G待运行并将其调度到M中执行，全局队列中G的来源，主要有从系统调用中恢复的G。之所以P会周期性地查看全局队列，也是为了防止全局队列中的G被饿死。

全局队列与公平性

• 由于在G1中创建的新协程会优先放到当前P上，因此容易发生P的runqueue满的情况，这种情况下会尝试将该P上的一部分G放到别的P上或者放到全局队列中
• 为了保证公平，当全局运行队列中有待执行的Goroutine 时，通过schedtick 保证有一定几率（1/61）会从全局的运行队列中查找对应的Goroutine
• 从处理器本地的运行队列中查找待执行的Goroutine
• 如果前两种方法都没有找到Goroutine，会通过runtime.findrunnable 进行阻塞地查找Goroutine，寻找的路径有以下几种，包括：
  1. 从全局运行队列中查找。
  2. 从网络轮询器中查找是否有Goroutine 等待运行。
  3. 通过runtime.runqsteal 尝试从其他随机的处理器中窃取待运行的Goroutine。

示例

正常情况下

所有的goroutine运行在同一个M系统线程中，每一个M系统线程维护一个Processor，任何时刻，一个Processor中只有一个goroutine，其他goroutine在runqueue中等待。一个goroutine运行完自己的时间片后，让出上下文，回到runqueue中。 多核处理器的场景下，为了运行goroutines，每个M系统线程会持有一个Processor。

协程创建与更替

P 拥有 G1，M1 获取 P 后开始运行 G1，G1 使用go func()创建了 G2，为了局部性 G2 优先加入到 P1 的本地队列。G1运行完之后会按照runqueue的顺序继续运行G2。

协程阻塞

当正在运行的goroutine（G0）阻塞的时候，例如进行系统调用，会再创建一个系统线程（M1)，当前的M0线程放弃了它的Processor（P），P转到新的线程中去运行。

特殊的 M0 和 G0

M0

M0是启动程序后的编号为0的主线程，这个M对应的实例会在全局变量rutime.m0中，不需要在heap上分配，M0负责执行初始化操作和启动第一个G，在之后M0就和其他的M一样了

G0

G0是每次启动一个M都会第一个创建的goroutine，G0仅用于负责调度G，G0不指向任何可执行的函数，每个M都会有一个自己的G0，在调度或系统调用时会使用G0的栈空间，全局变量的G0是M0的G0

那么一个G由于调度被中断，此后如何恢复？中断的时候将寄存器里的栈信息，保存到自己的G对象里面。当再次轮到自己执行时，将自己保存的栈信息复制到寄存器里面，这样就接着上次之后运行了。

延伸阅读