一、概述

1. 为什么在内核的线程调度器之外，Go 还需要实现一个自己的调度器

主要解决系统线程太重的问题：

  1. 创建与切换线程 太重：都需要在用户态和内核态之间切换，开销较大；
  2. 系统线程内存使用 太重：一方面，创建系统线程时会分配一段大部分情况下都用不完的栈内存，造成浪费；另一方面，栈内存空间创建后其大小不会再变化，有溢出的风险。

goroutine 是 Go 语言实现的用户态的线程，可以看做是对系统线程进行的一层抽象。有了这层抽象，Golang 程序员不会直接面对系统线程，直接使用 goroutine 就可以了，而操作系统不会 care 什么 goroutine，只是执行设定好的系统线程就好了。这层抽象，就是 Go 的调度器，后面会详细说明。Go 很精巧地解决了上述两个问题：

  1. goroutine 是用户态线程，其创建和切换等，都是在用户态完成而无需进入操作系统内核，其开销相比系统线程要小很多；
  2. goroutine 启动时默认栈大小只有 2k，可以根据实际情况进行自动伸缩。

2. Go scheduler

Go 程序的执行由两部分组成：Go Program 和 runtime，即 用户代码 和 运行时。这里的 runtime 和 Java、Python 中的不一样，Java 的是虚拟机，而Go 的 runtime 和用户代码一起编译到一个可执行文件中。用户代码和 runtime 除了代码组织上有界限之外，运行的时候并没有明显的界限，用户代码中，一些常用的关键字(如 go, new 等)被编译成 runtime 包下的一些函数调用。用户程序进行的系统调用都会被 runtime 拦截，以此来帮助 runtime 进行调度方面以及垃圾回收其他方面的工作。

一张关系图如下：

用户代码和runtime的关系

为什么需要 scheduler 呢？runtime 维护所有的 goroutine，就是通过 scheduler 来进行调度。goroutine 和系统线程是独立的，但是 goroutine 需要依赖系统线程才能执行。

可以用一句话概括 Go scheduler 的目标：

For scheduling goroutines onto kernel threads.

Go scheduler 的核心思想是：

  1. reuser 系统线程，限制同时运行(不包括阻塞的)的线程数为 N，其中 N 为 CPU 的核心数；
  2. 线程使用私有的本地运行队列，并且为了更高地使用 CPU，某个线程可以从其他线程偷 goroutine 来帮助运行，也可以在 goroutine 阻塞的时候将其传递给其他线程。

3. M:N 模型

goroutine 建立在操作系统线程之上，它与操作系统线程之间实现了一个多对多(M:N)的两级线程模型。M:N 是指 M 的 goroutine 运行在 N 的操作系统线程上，内核负责对这 N 的操作系统线程进行调度，而 Go runtime 则负责将这 M 个 goroutine 调度运用在这 N 个操作系统线程上。

简单理解，对 goroutine 的调度，是指程序代码按照一定的算法，在适当的时候挑选出合适的 goroutine 然后放到真正的线程上去执行的过程。其实并没有一个调度器实体，它只是一段代码的抽象化表示，具体来说是 需要发生调度时由操作系统线程执行runtime.schedule方法进行的。

Go runtime 负责 goroutine 的生老病死，从创建、切换、销毁都一手包办。runtime 在启动的时候，会创建 M 个操作系统线程(CPU 内核执行调度的基本单位)，之后创建的 N 个 goroutine 都会依附在这 M 个线程上执行。在同一时刻，一个系统线程上只能执行一个 goroutine，当 goroutine 发生阻塞时，runtime 会将当前 goroutine 调走，让其他的 goroutine 继续执行。这样做的目的是尽量提升性能，尽量让所有的系统线程上面都有代码在执行。

4. GPM 模型

我们观察调度过程的进化，从进程到线程再到协程，其实是一个不断共享、不断减少切换成本的过程。

要理解调度，需要理解两个概念：运行和阻塞。这里提供两个角度：我们觉得自己就是线程或者协程，运行就是在低头不断做事，阻塞就是我们目前做的事需要等待别人，然后就一直等着，等其他人做完了，我们接着做，这里我们是站在线程或者协程的角度去看的；另一个角度是，我们站在 CPU 的角度看，我正在敲代码写需求(一个线程或者协程)，发现依赖别人的函数还没有提交，那就把敲代码这事放在一边，最小化 IDE 然后点开钉钉沟通下一个需求，等依赖的函数提交了，又打开 IDE 继续敲代码——在 Linux 中，线程对应的是一个叫做task_struct的结构体，从本质上来说，线程并不是一个实体，线程只是代表一个执行流和其状态。真正驱动流程的是 CPU，CPU 根据 PC 寄存器从程序中取指令和操作数，从 RAM 中取数据,，进行计算、 处理、 跳转、 驱动执行流往前。 CPU 并不关注处理的是线程还是协程,，只需要设置 PC 寄存器， 设置栈指针等(这些称为上下文),，那么 CPU 就可以运行这个线程或者协程了。

所以，线程的运行，其实是被运行；线程的阻塞，其实是换出调度队列，不再去执行这个执行流。协程同理，协程也是一个类似于task_struct数据结构，其作用也是一个执行流或者状态，记录运行什么函数，运行到什么程度，也就是上下文。

Go 在用户态实现调度，所以 Go 也需要有代表协程这种执行体的数据结构，也要有保存和恢复上下文的处理过程以及调度队列。

在这些数据结果中，最主要的是一下几个(以下结构体均位于runtime包的runtime.go文件中)：

  • g: 它保存了 goroutine 的所有信息，该结构体的每一个实例对象都代表了一个goroutine。调度器代码会通过 g 对象来对 goroutine 进行调度——当 goroutine 被调离系统线程时，调度器负责把 CPU 相关寄存器值等上下文信息保存在 g 对象的成员变量中；当 goroutine 被重新拉起运行时，调度器又负责把 g 对象成员变量中所保存的上下文信息恢复到相关寄存器，也就是恢复了执行上下文。
  • schedt：一方面保存调度器本身的状态信息，另一方面它拥有一个用来保存 goroutine 的运行队列。因为每个 Go 程序只有一个调度器，所以在每个 Go 程序中 schedt 结构体只有一个实例对象，该实例对象在源代码中被定义成了一个共享的全局变量，这样每个工作线程都可以访问它以及它所拥有的 goroutine 运行队列，我们称这个运行队列为全局运行队列(GRQ)。
  • p：表示执行所需要的资源，其最大数量同时也是 Go 代码的最大并行度。每一个运行着 go 代码的工作线程都会与一个 p 结构体的实例对象关联在一起。全局运行队列是每一个工作线程都可以读写的，因此为了并发安全，访问时需要加锁，但加锁势必耗费性能进而称为瓶颈。于是调度器为每一个工作线程引入了一个 私有的 goroutine 运行队列，我们称之为“局部队列(LRQ)”，工作线程优先使用局部队列的 goroutine，只有必要时才会去访问全局队列(后面还会了解到，当一个 p 的局部队列使用完时，还会去别的 p 偷几个 g 过来运行)，这大大减少了锁冲突，提高了工作线程的并发性。
  • m：代表实际工作线程，每一个工作线程都有唯一的m与之对应。m 结构体对象除了记录着工作线程的诸如栈的起止位置、当前正在执行的 goroutine 以及是否空闲等等状态信息之外，还通过指针维持着与 p 结构体的实例对象之间的绑定关系。于是，通过 m 既可以找到与之对应的工作线程正在运行的 goroutine，又可以找到工作线程的局部运行队列等资源。

他们之间的关系，可以使用下图表示：

GPM关系

另有一张图可能更清晰形象：

GPM关系

Go scheduler 的职责就是将所有处于 可运行状态 的 goroutines 均匀分布到在 P 上运行的 M。

当一个 P 发现自己的 LRQ 已经没有 G 时，会从其他 P “偷” 一些 G 来运行。这被称为 Work-stealing，Go 从 1.1 开始实现。

Go scheduler 使用 M:N 模型，在任一时刻，M 个 goroutines（G） 要分配到 N 个内核线程（M），这些 M 跑在个数最多为 GOMAXPROCS 的逻辑处理器（P）上。每个 M 必须依附于一个 P，每个 P 在同一时刻只能运行一个 M。如果 P 上的 M 阻塞了，那它就需要其他的 M 来运行 P 的 LRQ 里的 goroutines。

实际上，Go scheduler 每一轮调度要做的工作就是找到处于 runnable 的 goroutines，并执行它。寻找的顺序如下：

runtime.schedule() {
    // 检查全局队列，防止全局队列中的G被饿死
    // if not found, 检查局部队列
    // if not found,
    //   尝试从其他的P偷一些G过来
    //   if not found, 从全局队列中去一些
    //      if not found, poll network
}

上述任何一步找到一个可执行的 goroutine 后，就会一直执行下去，直到被阻塞。当 P2 上的一个 G 执行结束，它就会去 LRQ 获取下一个 G 来执行。如果 LRQ 已经空了，就是说本地可运行队列已经没有 G 需要执行，并且这时 GRQ 也没有 G 了。这时，P2 会随机选择一个 P（称为 P1），P2 会从 P1 的 LRQ “偷”过来一半的 G。

这样做的好处是，有更多的 P 可以一起工作，加速执行完所有的 G。

5. goroutine 的状态

如下图：

goroutine状态转移

6. Go scheduler 的调度时机

在以下四种情况下，scheduler 可能会发生调度——“可能”意味着，scheduler 只是有机会调度，但并不一定会发生。

情形说明
使用关键字 go创建一个新的 goroutine，scheduler 会考虑调度
GC肯定会发生调度，因为 GC 必须要在 M 上运行。
发生系统调用当一个 goroutine 发生系统调用时，会阻塞 M，此时它会被调走，同时调用新的 goroutine 在 M 上运行
内存同步访问atomic，mutex，channel 操作等会使 goroutine 阻塞，因此会被调度走。等条件满足后（例如其他 goroutine 解锁了）还会被调度上来继续运行

7. 同步/异步系统调用概览

当一个正在执行的 G(goroutine)需要进行系统调用时，根据调用类型，它所依附的 M 有两种情况：同步(系统调用等) 和 异步(网络请求等)。

同步系统调用

同步情况下，M1 会被阻塞，进而从 P 上调度下来，此时 G1 依然依附在 M1 上执行，之后会有一个新的 M2 被调用到 P 上，接着执行 P 的本地运行队列 LRQ 中的 G。一旦系统调用完成，G1 会再次加入 P 的 LRQ 等待被调度，而之前的 M1 则会被隐藏，等到需要的时候再次被使用。

异步系统调用

异步情况下，M1 不会被阻塞，G1 的异步请求会被另一个组件Network Poller接手，而 G1 本身也会被绑定到Network Poller上，等到系统调用结束，G1 会再次回到 P 上。由于 M 没有被阻塞，它可以继续执行当前被绑定的 P 的 LRQ 里面的 G。

可以看到，在异步情况下，通过调度，Go scheduler 成功地将 IO 任务转变成了 CPU 任务，或者说将内核级别的线程切换转变成了用户级别的 goroutine 切换，极大地提高了效率。

二、具体实现

有时间再细究。

未完，待续…