6.5 调度器

各位读者朋友，很高兴大家通过本博客学习 Go 语言，感谢一路相伴！《Go语言设计与实现》的纸质版图书已经上架京东，有需要的朋友请点击 链接 购买。

Go 语言在并发编程方面有强大的能力，这离不开语言层面对并发编程的支持。本节会介绍 Go 语言运行时调度器的实现原理，其中包含调度器的设计与实现原理、演变过程以及与运行时调度相关的数据结构。

谈到 Go 语言调度器，我们绕不开的是操作系统、进程与线程这些概念，线程是操作系统调度时的最基本单元，而 Linux 在调度器并不区分进程和线程的调度，它们在不同操作系统上也有不同的实现，但是在大多数的实现中线程都属于进程：

process-and-threads

图 6-25 进程和线程

多个线程可以属于同一个进程并共享内存空间。因为多线程不需要创建新的虚拟内存空间，所以它们也不需要内存管理单元处理上下文的切换，线程之间的通信也正是基于共享的内存进行的，与重量级的进程相比，线程显得比较轻量。

虽然线程比较轻量，但是在调度时也有比较大的额外开销。每个线程会都占用 1M 以上的内存空间，在切换线程时不止会消耗较多的内存，恢复寄存器中的内容还需要向操作系统申请或者销毁资源，每一次线程上下文的切换都需要消耗 ~1us 左右的时间，但是 Go 调度器对 Goroutine 的上下文切换约为 ~0.2us，减少了 80% 的额外开销。

goroutines-on-thread

图 6-26 线程与 Goroutine

Go 语言的调度器通过使用与 CPU 数量相等的线程减少线程频繁切换的内存开销，同时在每一个线程上执行额外开销更低的 Goroutine 来降低操作系统和硬件的负载。

6.5.1 设计原理 #

今天的 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 ~ 至今
      • 实现基于信号的真抢占式调度；
      • 垃圾回收在扫描栈时会触发抢占调度；
      • 抢占的时间点不够多，还不能覆盖全部的边缘情况；
  • 非均匀存储访问调度器 · 提案
    • 对运行时的各种资源进行分区；
    • 实现非常复杂，到今天还没有提上日程；

除了多线程、任务窃取和抢占式调度器之外，Go 语言社区目前还有一个非均匀存储访问（Non-uniform memory access，NUMA）调度器的提案。在这一节中，我们将依次介绍不同版本调度器的实现原理以及未来可能会实现的调度器提案。

单线程调度器 #

runtime.scheduler:9682400

该函数会遵循如下的过程调度 Goroutine：

runtime.gosave:9682400runtime.nextgandunlock:9682400mruntime.gogo:9682400

虽然这个单线程调度器的唯一优点就是能运行，但是这次提交已经包含了 G 和 M 两个重要的数据结构，也建立了 Go 语言调度器的框架。

多线程调度器 #

pkg/runtime/proc.cruntime.schedule:go1.0.1
GOMAXPROCS
runtime.futex:go1.0.1
  1. 调度器和锁是全局资源，所有的调度状态都是中心化存储的，锁竞争问题严重；
  2. 线程需要经常互相传递可运行的 Goroutine，引入了大量的延迟；
  3. 每个线程都需要处理内存缓存，导致大量的内存占用并影响数据局部性；
  4. 系统调用频繁阻塞和解除阻塞正在运行的线程，增加了额外开销；

这里的全局锁问题和 Linux 操作系统调度器在早期遇到的问题比较相似，解决的方案也都大同小异。

任务窃取调度器 #

2012 年 Google 的工程师 Dmitry Vyukov 在 Scalable Go Scheduler Design Doc 中指出了现有多线程调度器的问题并在多线程调度器上提出了两个改进的手段：

  1. 在当前的 G-M 模型中引入了处理器 P，增加中间层；
  2. 在处理器 P 的基础上实现基于工作窃取的调度器；
runtime.schedule:779c45a
runtime.findrunnable:779c45a

运行时 G-M-P 模型中引入的处理器 P 是线程和 Goroutine 的中间层，我们从它的结构体中就能看到处理器与 M 和 G 的关系：

runq

golang-gmp

图 6-27 - G-M-P 模型

基于工作窃取的多线程调度器将每一个线程绑定到了独立的 CPU 上，这些线程会被不同处理器管理，不同的处理器通过工作窃取对任务进行再分配实现任务的平衡，也能提升调度器和 Go 语言程序的整体性能，今天所有的 Go 语言服务都受益于这一改动。

抢占式调度器 #

对 Go 语言并发模型的修改提升了调度器的性能，但是 1.1 版本中的调度器仍然不支持抢占式调度，程序只能依靠 Goroutine 主动让出 CPU 资源才能触发调度。Go 语言的调度器在 1.2 版本中引入基于协作的抢占式调度解决下面的问题：

  • 某些 Goroutine 可以长时间占用线程，造成其它 Goroutine 的饥饿；
  • 垃圾回收需要暂停整个程序（Stop-the-world，STW），最长可能需要几分钟的时间，导致整个程序无法工作；

1.2 版本的抢占式调度虽然能够缓解这个问题，但是它实现的抢占式调度是基于协作的，在之后很长的一段时间里 Go 语言的调度器都有一些无法被抢占的边缘情况，例如：for 循环或者垃圾回收长时间占用线程，这些问题中的一部分直到 1.14 才被基于信号的抢占式调度解决。

基于协作的抢占式调度 #

pkg/runtime/proc.c
cmd/internal/obj/x86.stacksplitruntime.morestackruntime.newstack
runtime.morestackStackPreemptruntime.morestackruntime.newstackstackguard0StackPreemptstackguard0StackPreempt

这种实现方式虽然增加了运行时的复杂度，但是实现相对简单，也没有带来过多的额外开销，总体来看还是比较成功的实现，也在 Go 语言中使用了 10 几个版本。因为这里的抢占是通过编译器插入函数实现的，还是需要函数调用作为入口才能触发抢占，所以这是一种协作式的抢占式调度。

基于信号的抢占式调度 #

基于协作的抢占式调度虽然实现巧妙，但是并不完备，我们能在 runtime: non-cooperative goroutine preemption 中找到一些遗留问题：

  • …

Go 语言在 1.14 版本中实现了非协作的抢占式调度，在实现的过程中我们重构已有的逻辑并为 Goroutine 增加新的状态和字段来支持抢占。Go 团队通过下面的一系列提交实现了这一功能，我们可以按时间顺序分析相关提交理解它的工作原理：

目前的抢占式调度也只会在垃圾回收扫描任务时触发，我们可以梳理一下上述代码实现的抢占式调度过程：

SIGURG
  1. 该信号需要被调试器透传；
  2. 该信号不会被内部的 libc 库使用并拦截；
  3. 该信号可以随意出现并且不触发任何后果；
  4. 我们需要处理多个平台上的不同信号；

STW 和栈扫描是一个可以抢占的安全点（Safe-points），所以 Go 语言会在这里先加入抢占功能。基于信号的抢占式调度只解决了垃圾回收和栈扫描时存在的问题，它到目前为止没有解决所有问题，但是这种真抢占式调度是调度器走向完备的开始，相信在未来我们会在更多的地方触发抢占。

非均匀内存访问调度器 #

非均匀内存访问（Non-uniform memory access，NUMA）调度器现在只是 Go 语言的提案。该提案的原理就是通过拆分全局资源，让各个处理器能够就近获取，减少锁竞争并增加数据的局部性。

在目前的运行时中，线程、处理器、网络轮询器、运行队列、全局内存分配器状态、内存分配缓存和垃圾收集器都是全局资源。运行时没有保证本地化，也不清楚系统的拓扑结构，部分结构可以提供一定的局部性，但是从全局来看没有这种保证。

go-numa-scheduler-architecture

图 6-28 - Go 语言 NUMA 调度器

如上图所示，堆栈、全局运行队列和线程池会按照 NUMA 节点进行分区，网络轮询器和计时器会由单独的处理器持有。这种方式虽然能够利用局部性提高调度器的性能，但是本身的实现过于复杂，所以 Go 语言团队还没有着手实现这一提案。

小结 #

Go 语言的调度器在最初的几个版本中迅速迭代，但是从 1.2 版本之后调度器就没有太多的变化，直到 1.14 版本引入了真正的抢占式调度才解决了自 1.2 以来一直存在的问题。在可预见的未来，Go 语言的调度器还会进一步演进，增加触发抢占式调度的时间点以减少存在的边缘情况。

6.5.2 数据结构 #

相信各位读者已经对 Go 语言调度相关的数据结构已经非常熟悉了，但是我们在一些还是要回顾一下运行时调度器的三个重要组成部分 — 线程 M、Goroutine G 和处理器 P：

golang-scheduler

图 6-29 Go 语言调度器

  1. G — 表示 Goroutine，它是一个待执行的任务；
  2. M — 表示操作系统的线程，它由操作系统的调度器调度和管理；
  3. P — 表示处理器，它可以被看做运行在线程上的本地调度器；

我们会在这一节中分别介绍不同的结构体，详细介绍它们的作用、数据结构以及在运行期间可能处于的状态。

G #

Goroutine 是 Go 语言调度器中待执行的任务，它在运行时调度器中的地位与线程在操作系统中差不多，但是它占用了更小的内存空间，也降低了上下文切换的开销。

Goroutine 只存在于 Go 语言的运行时，它是 Go 语言在用户态提供的线程，作为一种粒度更细的资源调度单元，如果使用得当能够在高并发的场景下更高效地利用机器的 CPU。

runtime.g
stackstackguard0stackguard0
deferpanicdeferpanic

最后，我们再节选一些作者认为比较有趣或者重要的字段：

matomicstatusschedgoid
schedruntime.gobuf
sppcgruntime.gobufret

这些内容会在调度器保存或者恢复上下文的时候用到，其中的栈指针和程序计数器会用来存储或者恢复寄存器中的值，改变程序即将执行的代码。

runtime.gatomicstatus
_Gidle_Grunnable_Grunning_Gsyscall_Gwaiting_Gdead_Gcopystack_Gpreempted_Gscan

表 7-3 Goroutine 的状态

_Grunnable_Grunning_Gsyscall_Gwaiting_Gpreempted

goroutine-status

图 6-30 Goroutine 的状态

虽然 Goroutine 在运行时中定义的状态非常多而且复杂，但是我们可以将这些不同的状态聚合成三种：等待中、可运行、运行中，运行期间会在这三种状态来回切换：

_Gwaiting_Gsyscall_Gpreempted_Grunnable_Grunning

golang-goroutine-state-transition

图 6-31 Goroutine 的常见状态迁移

上图展示了 Goroutine 状态迁移的常见路径，其中包括创建 Goroutine 到 Goroutine 被执行、触发系统调用或者抢占式调度器的状态迁移过程。

M #

GOMAXPROCS
GOMAXPROCSruntime.GOMAXPROCS

scheduler-m-and-thread

图 6-32 CPU 和活跃线程

runtime.m

在大多数情况下，我们都会使用 Go 的默认设置，也就是线程数等于 CPU 数，默认的设置不会频繁触发操作系统的线程调度和上下文切换，所有的调度都会发生在用户态，由 Go 语言调度器触发，能够减少很多额外开销。

runtime.m
curg

g0-and-g

图 6-33 调度 Goroutine 和运行 Goroutine

g0 是一个运行时中比较特殊的 Goroutine，它会深度参与运行时的调度过程，包括 Goroutine 的创建、大内存分配和 CGO 函数的执行。在后面的小节中，我们会经常看到 g0 的身影。

runtime.mpnextpoldp
runtime.m

P #

调度器中的处理器 P 是线程和 Goroutine 的中间层，它能提供线程需要的上下文环境，也会负责调度线程上的等待队列，通过处理器 P 的调度，每一个内核线程都能够执行多个 Goroutine，它能在 Goroutine 进行一些 I/O 操作时及时让出计算资源，提高线程的利用率。

GOMAXPROCSGOMAXPROCS
runtime.p
runqheadrunqtailrunqrunnext
runtime.pstatus
_Pidle_Prunning_Psyscall_Pgcstop_Pdead

表 7-4 处理器的状态

_Prunning_Psyscall

小结 #

我们在这一小节简单介绍了 Go 语言调度器中常见的数据结构，包括线程 M、处理器 P 和 Goroutine G，它们在 Go 语言运行时中分别使用不同的私有结构体表示，我们在下面会深入分析 Go 语言调度器的实现原理。

6.5.3 调度器启动 #

runtime.schedinit
maxmcountGOMAXPROCS
GOMAXPROCSruntime.procresizeruntime.procresize
allpnewruntime.p.initallp[0]runtime.p.destroyallpallp[0]_Pidle
runtime.procresize

6.5.4 创建 Goroutine #

gocmd/compile/internal/gc.state.stmtcmd/compile/internal/gc.state.callruntime.newproc
runtime.newprocfuncvalruntime.newproc1runtime.wakep
runtime.newproc1g
  1. 获取或者创建新的 Goroutine 结构体；
  2. 将传入的参数移到 Goroutine 的栈上；
  3. 更新 Goroutine 调度相关的属性；

首先是 Goroutine 结构体的创建过程：

gFreeruntime.malg
runtime.memmovefnargpnarg
runtime.newproc1_Grunnable
runtime.newprocruntime.gfgetruntime.malgruntime.runqput

初始化结构体 #

runtime.gfgetruntime.g

golang-newproc-get-goroutine

图 6-34 获取 Goroutine 结构体的三种方法

runtime.gfgetgFree
gFree
gFreegFreeruntime.malgruntime.gruntime.stackalloc
runtime.malgallgs
runtime.newproc1runtime.malg

运行队列 #

runtime.runqput
nexttruerunnextnextfalseruntime.runqputslow

处理器本地的运行队列是一个使用数组构成的环形链表，它最多可以存储 256 个待执行任务。

golang-runnable-queue

图 6-35 全局和本地运行队列

简单总结一下，Go 语言有两个运行队列，其中一个是处理器本地的运行队列，另一个是调度器持有的全局运行队列，只有在本地运行队列没有剩余空间时才会使用全局队列。

调度信息 #

runtime.goexit
schedruntime.gostartcallfnruntime.gostartcall
spruntime.goexitpcpcpcspruntime.goexit

6.5.5 调度循环 #

runtime.mstartruntime.mstart1stackguard0stackguard1runtime.schedule
runtime.schedule
schedtickruntime.findrunnable
runtime.findrunnable
runtime.runqsteal

因为函数的实现过于复杂，上述的执行过程是经过简化的，总而言之，当前函数一定会返回一个可执行的 Goroutine，如果当前不存在就会阻塞等待。

runtime.executeruntime.gogo
runtime.gogo
runtime.gobufruntime.goexit
runtime.goexit
CALL
runtime.gogoCALL

golang-gogo-stack

图 6-36 runtime.gogo 栈内存

JMPruntime.goexit
runtime.goexit0_Gdeadruntime.gfputgFree
runtime.goexit0runtime.scheduleruntime.scheduleruntime.schedule

golang-scheduler-loop

图 6-36 调度循环

这里介绍的是 Goroutine 正常执行并退出的逻辑，实际情况会复杂得多，多数情况下 Goroutine 在执行的过程中都会经历协作式或者抢占式调度，它会让出线程的使用权等待调度器的唤醒。

6.5.6 触发调度 #

runtime.schedule

schedule-points

图 6-37 调度时间点

runtime.mstartruntime.goexit0
runtime.schedule

主动挂起 #

runtime.gopark
runtime.mcallruntime.park_m
runtime.park_m_Grunning_Gwaitingruntime.dropgruntime.schedule
runtime.goreadyruntime.gopark
runtime.ready_Grunnable

系统调用 #

_Gsyscallsyscall.Syscallsyscall.RawSyscallsyscall.Syscall
INVOKE_SYSCALLruntime.entersyscallruntime.exitsyscall

golang-syscall-and-rawsyscal

图 6-38 Go 语言系统调用

syscall.RawSyscall
系统调用类型
SYS_TIMERawSyscall
SYS_GETTIMEOFDAYRawSyscall
SYS_SETRLIMITRawSyscall
SYS_GETRLIMITRawSyscall
SYS_EPOLL_WAITSyscall
……

表 7-5 系统调用的类型

RawSyscallSYS_EPOLL_CREATESYS_EPOLL_WAITSYS_TIME

正常的系统调用过程相对比较复杂，下面将分别介绍进入系统调用前的准备工作和系统调用结束后的收尾工作。

准备工作 #

runtime.entersyscallruntime.reentersyscall
_Gsyscall_Psyscall
runtime.reentersyscall

恢复工作 #

runtime.exitsyscall
runtime.exitsyscallfast
_Psyscallwirepruntime.acquirep
runtime.exitsyscall0_Grunnable
runtime.pidleget
runtime.schedule

协作式调度 #

runtime.Gosched
runtime.goschedImpl_Grunnableruntime.schedule

6.5.7 线程管理 #

runtime.LockOSThreadruntime.UnlockOSThreadruntime.LockOSThread
runtime.LockOSThread
runtime.dolockOSThreadlockedglockedm
runtime.UnlockOSThread
runtime.LockOSThread

线程生命周期 #

runtime.startmruntime.newm
runtime.newosprocclone
cloneexitruntime.mstartruntime.mstartruntime.newmfn

6.5.8 小结 #

Goroutine 和调度器是 Go 语言能够高效地处理任务并且最大化利用资源的基础，本节介绍了 Go 语言用于处理并发任务的 G - M - P 模型，我们不仅介绍了它们各自的数据结构以及常见状态，还通过特定场景介绍调度器的工作原理以及不同数据结构之间的协作关系，相信能够帮助各位读者理解调度器的实现。

6.5.9 延伸阅读 #

上一节 下一节