今天的 Go 语言调度器有着优异的性能，但是如果我们回头看 Go 语言的 0.x 版本的调度器会发现最初的调度器不仅实现非常简陋，也无法支撑高并发的服务。调度器经过几个大版本的迭代才有今天的优异性能，历史上几个不同版本的调度器引入了不同的改进，也存在着不同的缺陷:
- 单线程调度器 · 0.x
- 只包含 40 多行代码；
- 程序中只能存在一个活跃线程，由 G-M 模型组成；
- 多线程调度器 · 1.0
- 允许运行多线程的程序；
- 全局锁导致竞争严重；
- 任务窃取调度器 · 1.1
- 引入了处理器 P，构成了目前的 G-M-P 模型；
- 在处理器 P 的基础上实现了基于工作窃取的调度器；
- 在某些情况下，Goroutine 不会让出线程，进而造成饥饿问题；
- 时间过长的垃圾回收（Stop-the-world，STW）会导致程序长时间无法工作；
- 抢占式调度器 · 1.2 ~ 至今
- 基于协作的抢占式调度器 – 1.2 ~ 1.13
- 通过编译器在函数调用时插入抢占检查指令，在函数调用时检查当前 Goroutine 是否发起了抢占请求，实现基于协作的抢占式调度；
- Goroutine 可能会因为垃圾回收和循环长时间占用资源导致程序暂停；
- 基于信号的抢占式调度器 – 1.14 ~ 至今
- 实现基于信号的真抢占式调度；
- 垃圾回收在扫描栈时会触发抢占调度；
- 抢占的时间点不够多，还不能覆盖全部的边缘情况；
- 基于协作的抢占式调度器 – 1.2 ~ 1.13
- 非均匀存储访问调度器 · 提案
- 对运行时的各种资源进行分区；
- 实现非常复杂，到今天还没有提上日程；
G-M模型
单线程调度器
0.x 版本调度器只包含表示 Goroutine 的 G 和表示线程的 M 两种结构，全局也只有一个线程。我们可以在 clean up scheduler 提交中找到单线程调度器的源代码，在这时 Go 语言的调度器还是由 C 语言实现的，调度函数 runtime.scheduler:9682400 也只包含 40 多行代码 ：
static void scheduler(void) {
G* gp;
lock(&sched);
if(gosave(&m->sched)){
lock(&sched);
gp = m->curg;
switch(gp->status){
case Grunnable:
case Grunning:
gp->status = Grunnable;
gput(gp);
break;
...
}
notewakeup(&gp->stopped);
}
gp = nextgandunlock();
noteclear(&gp->stopped);
gp->status = Grunning;
m->curg = gp;
g = gp;
gogo(&gp->sched);
}
该函数会遵循如下的过程调度 Goroutine：
- 获取调度器的全局锁；
- 调用
runtime.gosave:9682400保存栈寄存器和程序计数器； - 调用
runtime.nextgandunlock:9682400获取下一个需要运行的 Goroutine 并解锁调度器； - 修改全局线程
m上要执行的 Goroutine； - 调用
runtime.gogo:9682400函数运行最新的 Goroutine；
虽然这个单线程调度器的唯一优点就是能运行，但是这次提交已经包含了 G 和 M 两个重要的数据结构，也建立了 Go 语言调度器的框架。
多线程调度器
Go 语言在 1.0 版本正式发布时就支持了多线程的调度器，与上一个版本几乎不可用的调度器相比，Go 语言团队在这一阶段实现了从不可用到可用的跨越。我们可以在 pkg/runtime/proc.c 文件中找到 1.0.1 版本的调度器，多线程版本的调度函数 runtime.schedule:go1.0.1 包含 70 多行代码，我们在这里保留了该函数的核心逻辑：
static void schedule(G *gp) {
schedlock();
if(gp != nil) {
gp->m = nil;
uint32 v = runtime·xadd(&runtime·sched.atomic, -1<<mcpuShift);
if(atomic_mcpu(v) > maxgomaxprocs)
runtime·throw("negative mcpu in scheduler");
switch(gp->status){
case Grunning:
gp->status = Grunnable;
gput(gp);
break;
case ...:
}
} else {
...
}
gp = nextgandunlock();
gp->status = Grunning;
m->curg = gp;
gp->m = m;
runtime·gogo(&gp->sched, 0);
}
整体的逻辑与单线程调度器没有太多区别，因为我们的程序中可能同时存在多个活跃线程，所以多线程调度器引入了 GOMAXPROCS 变量帮助我们灵活控制程序中的最大处理器数，即活跃线程数。
多线程调度器的主要问题是调度时的锁竞争会严重浪费资源，Scalable Go Scheduler Design Doc 中对调度器做的性能测试发现 14% 的时间都花费在 runtime.futex:go1.0.1 上3，该调度器有以下问题需要解决：
- 调度器和锁是全局资源，所有的调度状态都是中心化存储的，锁竞争问题严重；
- 线程需要经常互相传递可运行的 Goroutine，引入了大量的延迟；
- 每个线程M都需要处理内存缓存，导致大量的内存占用且数据局部性差；
- 系统调用频繁阻塞和解除阻塞正在运行的线程，增加了额外性能开销；
逻辑处理器P和任务窃取调度器的提出
2012 年 Google 的工程师 Dmitry Vyukov 在 Scalable Go Scheduler Design Doc 中指出了现有多线程调度器的问题并在多线程调度器上提出了两个改进的手段：
- 在当前的 G-M 模型中引入了处理器 P，增加中间层；
- 在处理器 P 的基础上实现基于工作窃取的调度器；
基于任务窃取的 Go 语言调度器使用了沿用至今的 G-M-P 模型，我们能在 runtime: improved scheduler 提交中找到任务窃取调度器刚被实现时的源代码，调度器的 runtime.schedule:779c45a 在这个版本的调度器中反而更简单了：
static void schedule(void) {
G *gp;
top:
if(runtime·gcwaiting) {
gcstopm();
goto top;
}
gp = runqget(m->p);
if(gp == nil)
gp = findrunnable();
...
execute(gp);
}
- 如果当前运行时在等待垃圾回收，调用
runtime.gcstopm:779c45a函数； - 调用
runtime.runqget:779c45a和runtime.findrunnable:779c45a从本地或者全局的运行队列中获取待执行的 Goroutine； - 调用
runtime.execute:779c45a在当前线程 M 上运行 Goroutine；
当前处理器本地的运行队列中不包含 Goroutine 时，调用 runtime.findrunnable:779c45a 会触发工作窃取，从其它的处理器的队列中随机获取一些 Goroutine。
运行时 G-M-P 模型中引入的处理器 P 是线程和 Goroutine 的中间层，我们从它的结构体中就能看到处理器与 M 和 G 的关系：
struct P {
Lock;
uint32 status;
P* link;
uint32 tick;
M* m;
MCache* mcache;
G** runq;
int32 runqhead;
int32 runqtail;
int32 runqsize;
G* gfree;
int32 gfreecnt;
};
处理器持有一个由可运行的 Goroutine 组成的环形的运行队列 runq，还反向持有一个线程m。调度器在调度时会从处理器的队列中选择队列头的 Goroutine 放到线程 M 上执行。如下所示的图片展示了 Go 语言中的线程 M、处理器 P 和 Goroutine 的关系。
G-P-M模型
基于工作窃取的多线程调度器将每一个线程绑定到了独立的 CPU 上，这些线程会被不同处理器管理，不同的处理器通过工作窃取对任务进行再分配实现任务的平衡，也能提升调度器和 Go 语言程序的整体性能，今天所有的 Go 语言服务都受益于这一改动。
抢占式调度器
对 Go 语言并发模型的修改提升了调度器的性能，但是 1.1 版本中的调度器仍然不支持抢占式调度，程序只能依靠 Goroutine 主动让出 CPU 资源才能触发调度。
基于协作的抢占式调度(~1.13)
Go 语言的调度器在 1.2 版本4中引入基于协作的抢占式调度解决下面的问题5：
- 某些 Goroutine 可以长时间占用线程，造成其它 Goroutine 的饥饿；
- 垃圾回收需要暂停整个程序（Stop-the-world，STW），最长可能需要几分钟的时间6，导致整个程序无法工作；
我们可以在 pkg/runtime/proc.c 文件中找到引入基于协作的抢占式调度后的调度器。
基于协作的抢占式调度的工作原理：
- 编译器会在调用函数前插入
runtime.morestack； - Go 语言runtime会在垃圾回收暂停程序、系统监控发现 Goroutine 运行超过 10ms 时发出抢占请求
StackPreempt； - 当发生函数调用时，可能会执行编译器插入的
runtime.morestack，它调用的runtime.newstack会检查 Goroutine 的stackguard0字段是否为StackPreempt； - 如果
stackguard0是StackPreempt，就会触发抢占让出当前线程；
具体描述：
Go 语言在分段栈的机制上实现基于协作的抢占调度：编译器在分段栈上插入的函数morestack，所有 Goroutine 在函数调用时都有机会从被插入的函数中进入runtime检查是否需要执行抢占。Go 语言runtime也会在垃圾回收STW、系统监控中检查运行超过 10ms 的 Goroutine 并发出抢占请求 StackPreempt，Goroutine 收到信号后主动让出CPU(当前线程)。
这种实现方式虽然增加了运行时的复杂度，但是实现相对简单，也没有带来过多的额外开销，总体来看还是比较成功的实现，也在 Go 语言中使用了 10 几个版本。因为这里的抢占是通过编译器插入函数实现的，还是需要函数调用作为入口才能触发抢占，所以这是一种协作式的抢占式调度。
1.2 版本的抢占式调度虽然能够缓解这个问题，但是它实现的抢占式调度是基于协作的，在之后很长的一段时间里 Go 语言的调度器都有一些无法被抢占的边缘情况，例如：没有任何函数调用的 for 循环或者垃圾回收长时间占用线程，这些问题中的一部分直到 1.14 才被基于信号的抢占式调度解决。
基于信号的抢占式调度(1.14~)
基于协作的抢占式调度虽然实现巧妙，但是并不完备，我们能在 runtime: non-cooperative goroutine preemption 中找到一些遗留问题：
- runtime: tight loops should be preemptible #10958
- An empty for{} will block large slice allocation in another goroutine, even with GOMAXPROCS > 1 ? #17174
- runtime: tight loop hangs process completely after some time #15442
- …
Go 语言在 1.14 版本中实现了非协作的抢占式调度，目前的抢占式调度也只会在垃圾回收扫描任务时触发，我们可以梳理一下抢占式调度过程：
- 程序启动时，在
runtime.sighandler中注册SIGURG信号的处理函数runtime.doSigPreempt； - 在触发垃圾回收的栈扫描时会调用
runtime.suspendG挂起 Goroutine，该函数会执行下面的逻辑：- 将
_Grunning状态的 Goroutine 标记成可以被抢占，即将preemptStop设置成true； - 调用
runtime.preemptM触发抢占；
- 将
runtime.preemptM会调用runtime.signalM向线程发送信号SIGURG；- 操作系统会中断正在运行的线程并执行预先注册的信号处理函数
runtime.doSigPreempt； runtime.doSigPreempt函数会处理抢占信号，获取当前的 SP 和 PC 寄存器并调用runtime.sigctxt.pushCall；runtime.sigctxt.pushCall会修改寄存器并在程序回到用户态时执行runtime.asyncPreempt；- 汇编指令
runtime.asyncPreempt会调用运行时函数runtime.asyncPreempt2； runtime.asyncPreempt2会调用runtime.preemptPark；runtime.preemptPark会修改当前 Goroutine 的状态到_Gpreempted并调用runtime.schedule让当前函数陷入休眠并让出线程，调度器会选择其它的 Goroutine 继续执行；
上述 9 个步骤展示了基于信号的抢占式调度的执行过程，屏蔽掉具体的函数名，可以这样表述：
- M 启动时注册一个 SIGURG 信号的处理函数：sighandler。
- 系统监控sysmon 线程检测到执行时间过长的 goroutine、以及GC stw 时，会向相应的 M（或者说线程，每个线程对应一个 M）发送 SIGURG 信号。
- 收到信号后，内核执行 sighandler 函数，通过 pushCall 向当前goroutine的执行流插入 asyncPreempt 函数调用。
- 回到当前 goroutine 执行 asyncPreempt 函数，通过 mcall 切到 g0 栈执行 gopreempt_m。
- gopreempt_m会将当前 goroutine 从running切换到runable状态，并将其重新放入到全局可运行队列，空出来的M 则继续寻找其他 goroutine 来运行。
- 被抢占的 goroutine 再次调度过来执行时，会执行现场恢复工作。
除了分析抢占的过程之外，我们还需要讨论一下抢占信号的选择，提案根据以下的四个原因选择 SIGURG 作为触发异步抢占的信号7；
- 该信号需要被调试器透传；
- 该信号不会被内部的 libc 库使用并拦截；
- 该信号可以随意出现并且不触发任何后果；
- 我们需要处理多个平台上的不同信号；
STW 和栈扫描是一个可以抢占的安全点（Safe-points），所以 Go 语言会在这里先加入抢占功能8。基于信号的抢占式调度只解决了垃圾回收和栈扫描时存在的问题（因为只在这些时候检查抢占），它到目前为止没有解决所有问题，但是这种真抢占式调度是调度器走向完备的开始，相信在未来我们会在更多的地方触发抢占。
数据结构
回顾一下运行时调度器的三个重要组成部分 — 线程 M、Goroutine G 和处理器 P：
- G — 表示 Goroutine，它是一个待执行的任务；
- M — 表示操作系统的线程，它由操作系统的调度器调度和管理；
- P — 表示处理器，它可以被看做运行在线程上的本地调度器；
G – Goroutine
Goroutine 是 Go 语言调度器中待执行的任务，它在运行时调度器中的地位与线程在操作系统中差不多，但是它占用了更小的内存空间，也降低了上下文切换的开销。
Goroutine 只存在于 Go 语言的运行时，它是 Go 语言在用户态提供的线程，作为一种粒度更细的资源调度单元，如果使用得当能够在高并发的场景下更高效地利用机器的 CPU。
Goroutine的主要成员变量
Goroutine 在 Go 语言运行时使用私有结构体 runtime.g 表示。这个私有结构体非常复杂，总共包含 40 多个用于表示各种状态的成员变量，这里也不会介绍所有的字段，仅会挑选其中的一部分。
栈相关
首先是与栈相关的两个字段：
type g struct {
stack stack
stackguard0 uintptr
}
抢占相关
其中 stack 字段描述了当前 Goroutine 的栈内存范围 [stack.lo, stack.hi)，另一个字段 stackguard0 可以用于调度器抢占式调度。除了 stackguard0 之外，Goroutine 中还包含另外三个与抢占密切相关的字段：
type g struct {
preempt bool // 抢占信号
preemptStop bool // 抢占时将状态修改成 `_Gpreempted`
preemptShrink bool // 在同步安全点收缩栈
}
defer 和 panic相关
Goroutine 与我们在前面章节提到的 defer 和 panic 也有千丝万缕的联系，每一个 Goroutine 上都持有两个分别存储 defer 和 panic 对应结构体的链表：
type g struct {
_panic *_panic // 最内侧的 panic 结构体
_defer *_defer // 最内侧的延迟函数结构体
}
线程记录、Goroutine状态、调度相关和其它
最后，我们再节选一些作者认为比较有趣或者重要的字段：
type g struct {
m *m
sched gobuf
atomicstatus uint32
goid int64
}
m— 当前 Goroutine 占用的线程，可能为空；atomicstatus— Goroutine 的状态；sched— 存储 Goroutine 的调度相关的数据，用于保存和恢复现场；goid— Goroutine 的 ID，该字段对开发者不可见，Go 团队认为引入 ID 会让部分 Goroutine 变得更特殊，从而限制语言的并发能力10；
上述四个字段中，我们需要展开介绍 sched 字段的 runtime.gobuf 结构体中包含哪些内容：
type gobuf struct {
sp uintptr
pc uintptr
g guintptr
ret sys.Uintreg
...
}
sp— 栈指针；pc— 程序计数器；g— 持有runtime.gobuf的 Goroutine；ret— 系统调用的返回值；
这些内容会在调度器保存或者恢复上下文的时候用到，其中的栈指针和程序计数器会用来存储或者恢复寄存器中的值，改变程序即将执行的代码。
Goroutine的9种状态
结构体 runtime.g 的 atomicstatus 字段存储了当前 Goroutine 的状态。除了几个已经不被使用的以及与 GC 相关的状态之外，Goroutine 可能处于以下 9 种状态：
| 状态 | 描述 |
|---|---|
_Gidle | 刚刚被分配并且还没有被初始化 |
_Grunnable | 没有执行代码，没有栈的所有权，存储在运行队列中 |
_Grunning | 可以执行代码，拥有栈的所有权，被赋予了内核线程 M 和处理器 P |
_Gsyscall | 正在执行系统调用，拥有栈的所有权，没有执行用户代码，被赋予了内核线程 M 但是不在运行队列上 |
_Gwaiting | 由于运行时而被阻塞，没有执行用户代码并且不在运行队列上，但是可能存在于 Channel 的等待队列上 |
_Gdead | 没有被使用，没有执行代码，可能有分配的栈 |
_Gcopystack | 栈正在被拷贝，没有执行代码，不在运行队列上 |
_Gpreempted | 由于抢占而被阻塞，没有执行用户代码并且不在运行队列上，等待唤醒 |
_Gscan | GC 正在扫描栈空间，没有执行代码，可以与其他状态同时存在 |
虽然 Goroutine 在运行时中定义的状态非常多而且复杂，但是我们可以将这些不同的状态聚合成三种：等待中、可运行、运行中，运行期间会在这三种状态来回切换：
- 等待中：Goroutine 正在等待某些条件满足，例如：系统调用结束等，包括
_Gwaiting、_Gsyscall和_Gpreempted几个状态； - 可运行：Goroutine 已经准备就绪，可以在线程运行，如果当前程序中有非常多的 Goroutine，每个 Goroutine 就可能会等待更多的时间，即
_Grunnable； - 运行中：Goroutine 正在某个线程上运行，即
_Grunning；
M – Machine Thread
Go 语言并发模型中的 M 是操作系统线程。调度器最多可以创建 10000 个线程，但是其中大多数的线程都不会执行用户代码（可能陷入系统调用），最多只会有 GOMAXPROCS 个活跃线程能够正常运行。
在默认情况下，运行时会将 GOMAXPROCS 设置成当前机器的核数，我们也可以在程序中使用 runtime.GOMAXPROCS 来改变最大的活跃线程数。
图 6-32 CPU 和活跃线程
在默认情况下，一个四核机器会创建四个活跃的操作系统线程，每一个线程都对应一个运行时中的 runtime.m 结构体。
在大多数情况下，我们都会使用 Go 的默认设置，也就是线程数等于 CPU 数，默认的设置不会频繁触发操作系统的线程调度和上下文切换，所有的调度都会发生在用户态，由 Go 语言调度器触发，能够减少很多额外开销。
g0和curg
Go 语言会使用私有结构体 runtime.m 表示操作系统线程，这个结构体也包含了几十个字段，这里先来了解几个与 Goroutine 相关的字段：
type m struct {
g0 *g
curg *g
...
}
其中 g0 是持有调度栈的 Goroutine，curg 是在当前线程上运行的用户 Goroutine，这也是操作系统线程唯一关心的两个 Goroutine。
图 6-33 调度 Goroutine 和运行 Goroutine
g0 是一个运行时中比较特殊的 Goroutine，它会深度参与运行时的调度过程，包括 Goroutine 的创建、大内存分配和 CGO 函数的执行。
P – Processor
调度器中的处理器 P 是线程和 Goroutine 的中间层，它能提供线程需要的上下文环境，也会负责调度线程上的等待队列，通过处理器 P 的调度，每一个内核线程都能够执行多个 Goroutine，它能在 Goroutine 进行一些 I/O 操作时及时让出计算资源，提高线程的利用率。
因为调度器在启动时就会创建 GOMAXPROCS 个处理器，所以 Go 语言程序的处理器数量一定会等于 GOMAXPROCS，这些处理器会绑定到不同的内核线程M上。
runtime.p 是处理器的运行时表示，作为调度器的内部实现，它包含的字段也非常多，其中包括与性能追踪、垃圾回收和计时器相关的字段，这些字段也非常重要，但是在这里就不展示了，我们主要关注处理器中的线程和运行队列：
type p struct {
m muintptr
runqhead uint32
runqtail uint32
runq [256]guintptr //g队列
runnext guintptr
...
}
反向存储的线程维护着线程与处理器之间的关系，而 runqhead、runqtail 和 runq 三个字段表示处理器持有的运行队列，其中存储着待执行的 Goroutine 列表，runnext 中是线程下一个需要执行的 Goroutine。
p的5种状态
runtime.p 结构体中的状态 status 字段会是以下五种中的一种：
| 状态 | 描述 |
|---|---|
_Pidle | 处理器没有运行用户代码或者调度器，被空闲队列或者改变其状态的结构持有，运行队列为空 |
_Prunning | 被线程 M 持有，并且正在执行用户代码或者调度器 |
_Psyscall | 没有执行用户代码，当前线程陷入系统调用 |
_Pgcstop | 被线程 M 持有，当前处理器由于垃圾回收被停止 |
_Pdead | 当前处理器已经不被使用 |
表 7-4 处理器的状态
通过分析处理器 P 的状态，我们能够对处理器的工作过程有一些简单理解，例如处理器在执行用户代码时会处于 _Prunning 状态，在当前线程执行 I/O 操作时会陷入 _Psyscall 状态。
