Golang Scheduler

最简单的调度模型是 1:1 模型，即“1 个线程对应执行 1 个 goroutine”。这种方式很简单，不过无法支持上百万的 goroutine，因为创建线程的代价相对比较高，在操作系统中在创建这么多的线程是不现实的。

M:N 模型是指“M 个线程执行 N 个 goroutine”。从操作系统角度，它只理解线程，对 goroutine 是一无所知的。Go runtime 需要维护 goroutine 的运行状态，以方便 Scheduler 进行调度。goroutine 的运行状态可简化为（省略了一些与调度关系不大的状态）下面 3 种：

1. Running – 这类 goroutine 正在线程上运行；
   
2. Runnable – 这类 goroutine 具体运行条件，但目前没有运行，正在等待线程来运行；
   
3. Blocked – 这类 goroutine 等待某些条件的发生，如阻塞在 channel 操作上、阻塞在系统调用上，阻塞在互斥锁上等等。
   

图 1 展示了 3 个线程执行 9 个 goroutine（其中 Running 状态 3 个，Runnable 状态 4 个，Blocked 状态 2 个）的情况。

Go 语言中的 G-M 模型和 G-P-M 模型都属于 M:N 模型，后文将介绍它们。

下面调度器相关源码摘自 Golang 1.0.1（注：没有找到 Golang 1.0 源码的 git tag）：

// Go scheduler
//
// The go scheduler's job is to match ready-to-run goroutines (`g's)
// with waiting-for-work schedulers (`m's).  If there are ready g's
// and no waiting m's, ready() will start a new m running in a new
// OS thread, so that all ready g's can run simultaneously, up to a limit.
// For now, m's never go away.

......

// One round of scheduler: find a goroutine and run it.
// The argument is the goroutine that was running before
// schedule was called, or nil if this is the first call.
// Never returns.
static void
schedule(G *gp)
{
    ......
    schedlock();                          // 1.
    if(gp != nil) {
        ......
        switch(gp->status){
        case Grunnable:
        case Gdead:
            // Shouldn't have been running!
            runtime·throw("bad gp->status in sched");
        case Grunning:
            gp->status = Grunnable;       // 2.
            gput(gp);                     // 3.
            break;
    }
    ......
    // Find (or wait for) g to run.  Unlocks runtime·sched.
    gp = nextgandunlock();                // 4.
    gp->readyonstop = 0;
    gp->status = Grunning;                // 5.
    m->curg = gp;
    gp->m = m;

    ......
    runtime·gogo(&gp->sched, 0);          // 6.
}

上面源码中的核心操作如下：

1. 通过 schedlock() 拿到全局锁；
   
2. 把当前 goroutine 从 Running 状态改为 Runnable 状态；
   
3. 通过 gput(gp) 保存当前 goroutine 的执行信息；
   
4. 通过 nextgandunlock() 寻找下一个可运行 goroutine，并对全局锁进行解锁；
   
5. 把找到的下一个待运行 goroutine 的状态修改为 Running；
   
6. 通过 runtime·gogo 运行下一个 goroutine。
   

函数 schedule() 是永远不会返回的，因为 schedule() 中运行下一个 goroutine 时就把控制权交给了下一个 goroutine 代码。那么下一次的调度在什么时候发生呢？即由谁来再次调用 schedule() 函数呢？答案是由用户的 goroutine 代码来调用，详情请参考节 4.1。

结合上面的源码分析，之前介绍的图 1 可以更具体地表示为图 2 了。

如果 goroutine 发起了一个“阻塞的系统调用”，那么运行当前 gorountine 的线程会被操作系统放入到内核中某个队列中，等待内核调度，这不受 Go runtime 的控制。 这会导致在系统调用返回前，其他的 goroutine 都没有机会在这个线程上运行了。

为了使其它 goroutine 能被线程及时运行，在当前 gorountine 进入阻塞的系统调用时，Go 会唤醒另一个空闲线程来执行其它的 gorountine。 我们可以通过 SetMaxThreads 来设置最大的线程数（默认为 10000）。

2012 年 Google 工程师 Dmitry Vyukov 在 Scalable Go Scheduler Design Doc 一文中指出了当时调度器（G-M 模型）的可伸缩性（Scalability）不好，尤其是对那些有高吞吐或并行计算需求的服务程序。他提到了对 Vtocc（一个 Go 实现的服务程序）进行性能分析后发现有 14% 的 CPU 都消耗在拿锁操作 runtime.futex() 上。

具体来说，Dmitry Vyukov 指出当时调度器（G-M 模型）的实现有下面四点不足：

1. 存在单一全局互斥锁和集中状态。全局锁保护所有 goroutine 相关操作（如：创建、完成、重新调度等），导致锁竞争问题严重；
   
2. goroutine 传递问题：经常在 M 之间传递“可运行”的 goroutine，这导致调度延迟增大；
   
3. 每个线程 M 都需要做内存缓存（M.mcache），导致内存占用过高，且数据局部性较差；
   
4. 系统调用频繁地阻塞和解除阻塞正在运行的线程，导致额外的性能损耗。
   

增加 P 后的模型被称为 G-P-M 模型，如图 3 所示。

当 G（即 Goroutine）关联了 P（Logical Processor），且映射到 M（OS thread）后，G 才会被执行。

说明 1：每个 P 关联着一个“本地可运行队列”（Local Queue），这样把 G-M 模型中的全局可运行队列（Global Queue）去中心化了，对 Global Queue 的访问锁竞争会大大减少。
说明 2：如果 P 的 Local Queue 为空，则会从 Global Queue 及其它 P 的 Local Queue 中窃取任务（即可运行的 goroutine），这就是任务窃取算法（Work Stealing，节 3.4 中将详细介绍它）。
说明 3：P 的数量等于变量 GOMAXPROCS 所设置的值。
说明 4：M 的数量可能远大于 P 的数量（节 2.2 提到过 M 最大值为 10000），M2 关联着处于 syscall 状态的 goroutine（它们不会关联 P），细节参考节 3.3。

如果我们直接把“本地可运行队列”（Local Queue）关联到 M 上，这样也可以实现 Global Queue 的去中心化，也可以实现任务窃取算法。为什么要额外地增加逻辑处理器 P 呢？

我们知道 M 的数量往往大于 P 的数量，这是因为执行“阻塞的系统调用”时，M 会被操作系统内核阻塞，为了更快地为其它 goroutine 提供服务，不得不启动新的 M。如果每个 M 都关联着一个 Local Queue，那么下面问题会出现：

1. 当 M 执行“阻塞的系统调用”时，为了使 M 关联的 Local Queue 中的任务尽快地被处理，我们需要及时地分配它们到其它的 M 中去执行。这大大增加了“可运行”的 goroutine 在 M 之间的传递。
   
2. Local Queue 可能变得很多（回忆一下节 2.2 提到过 M 的默认最大值是 10000），这会导致任务窃取的效率变低。
   

引入 P 后，把 Local Queue 关联到 P 上，这些问题就不存在了。

节 2.2 中提到，如果 goroutine 要执行“阻塞的系统调用”，G-M 模型中它会唤醒另一个空闲线程； 在 G-P-M 模型中，goroutine 要执行“阻塞的系统调用”时，还会把当前的 M 和 P 分离，这样，唤醒的新线程可以接着执行被分离出来的 P 所关联的 Local Queue 中的任务了，相关的实现细节参考节 3.3.1。 系统调用是如此特别，Go runtime 专门为 goroutine 定义了一个名为 syscall 的状态，表示其正在执行系统调用。

执行系统调用的情况如图 4 所示。M3 是唤醒的新线程，它会关联以前属于 M2 的 P。图 4 的右边子图描述的是系统调用返回后的一种处理情况：G1 被放到了 Global Queue 中。不过，系统调用返回后如果有空闲的 P，M2 关联上这个空闲 P 后可以接着执行 G1（它没必要进入到 Global Queue 中了）。

参考：https://morsmachine.dk/go-scheduler

在介绍 Work Stealing 前，先介绍一下 Fork-Join 框架，因为 Work Stealing 算法是实现 Fork-Join 框架的主流方式。

Go 1.13 及以前的调度器采用的是一种“协作式抢占（Cooperative Preemption）”，它并不是基于定时器中断来实现抢占的。Go 在库函数、系统调用等等很多地方自动增加了一些 hook 点，在这些位置上会检测某个标记（即 P 结构上的 preempt 字段，这个标记可由 sysmon 线程来设置，比如发现 P 执行超过 10ms 就把 P 的 preempt 字段设置为 true），如果发现标记（preempt）被设置上，则调用 schedule() ，从而实现其它 goroutine 的抢占。

一般情况下，真实程序中的 goroutine 中往往都会包含引入 hook 点的代码，所以不用太担心某 goroutine 不执行 schedule() ，从而一直霸占资源的情况。当然，也有意外，请看下节。

协作式抢占可能导致 gorountine 一直霸占着某个线程，在节 4.1.1 中有一个“协作式抢占”导致 main 得不到执行的例子。在 Go 1.14 中引入了“基于信号”的抢占，以解决协作式抢占的不足。

基于信号的抢占的基本原理如下：程序启动时注册 SIGURG 信号的处理函数 runtime.doSigPreempt ；而 sysmon 线程在满足一定条件下会发送 SIGURG 信号，这样操作系统会中断线程的执行，去调用对应的信号处理函数 runtime.doSigPreempt 。需要说明的是，信号处理函数是由内核调用的，在其执行结束后，内核会返回用户态并继续执行信号发生时被中断的代码，这意味着我们无法直接在信号处理函数内去调用 schedule() 完成任务切换。怎么办呢？Go 的实现技巧是： 在信号处理函数中修改寄存器 SP（栈顶指针）和寄存器 PC（下一条机器指令的内存地址）的值，以确保内核返回用户态时执行另外一个函数 runtime.asyncPreempt （而不再是信号发生时被中断代码的下一条指令），而函数 runtime.asyncPreempt 会去调用 schedule() ，从而完成任务切换。

参考：https://github.com/golang/proposal/blob/master/design/24543-non-cooperative-preemption.md