Go Runtime 设计：计算资源调度

Posted on Edited on In

本文介绍了 Golang Runtime 中关于 goroutine 以及调度器的设计。

1. 为什么需要 GoRoutine？

1.1 多少个线程是最优的？

我们知道，计算机执行一项任务，通常情况下需要由计算、存储、I/O 等多个组件配合运转才能完成。由于 CPU 与其他设备之间速度的巨大差异，我们更倾向于利用多任务同时运行的方式，来最大化的利用 CPU 的计算能力，这也就是并发编程的意义所在。

而由于多核处理器的广泛普及，在多个 CPU 核心上 ”并行的“ 进行多任务 ”并发“，是编写高效程序的必经之路。从程序执行层次的角度看，”并行“ 更倾向于在底层语境下，指代多个 CPU 核心能同时执行代码片段，而 ”并发“ 更倾向于在高层语境下，指代多个任务能同时在计算机上运行。

OS 通过调度机制帮我们实现了将用户层面的多任务并发，映射到硬件层面的多核心并行。从最大化资源利用的角度讲（暂时抛开任务执行公平性不谈），其映射机制，是对 CPU 资源的一种 “超卖”：任务可能处于执行和等待（包括阻塞）两种状态，执行状态下需要 CPU 资源而等待状态下则可以出让 CPU 资源给其他任务使用。根据任务类型的不同，通常可能分成 CPU 密集型任务与 I/O 密集型任务。

那么理论上，到底要同时执行多少个任务（线程数），才能最大化的利用计算资源呢？《Java 并发编程实战》中给出了如下公式： \[ N_{threads}=N_{cpu}*U_{cpu}*(1+\frac{W}{C}) \] 其中： \[ N_{threads}=number\ of\ CPUs \] \[ U_{cpu}=target\ CPU\ utilization,\ 0\leqslant U_{cpu} \leqslant 1 \] \[ \frac{W}{C}=ratio\ of\ wait\ time\ to\ compute\ time \]

显然，基于资源最大化考虑，我们期望 \(U_{cpu} \to 1\)。

那么，对于计算密集型任务，随着计算占比的不断提高，其 \(\frac{W}{C} \to 0\)，因此 \(N_{threads} \to N_{cpu}\) ；而对于 I/O 密集型任务，随着 I/O 等待占比的不断提高，其 \(\frac{W}{C} \to ∞\) ，因此 \(N_{threads} \to ∞\)。

1.2 线程越多越好吗？

前面我们看到了，对于 I/O 占比较高的 I/O 密集型任务，理论公式中倾向于创建更多的线程来填补 CPU 的空闲，但这并不是零成本的。

关于线程所带来的开销，Eli Bendersky 在他的博文 Measuring context switching and memory overheads for Linux threads 中做了一些测量：

  • 线程上下文切换与启动的开销： 可以看到在线程绑核切换下，上下文切换的开销每次大约 2us，线程启动开销大约 5us。

  • 单个线程的内存开销：

    线程的内存开销主要体现在线程栈，他的代码示例表明，创建 10000 个线程，virtual memory 约为 80GiB（未实际分配），RSS 约为 80MiB。

Eli Bendersky 的文章主要想表达的是现代操作系统的线程开销已经非常小了，很多时候我们并不需要采用事件驱动等方式来增加复杂度，目前的操作系统支持数万个线程绰绰有余。

但假如我们想要数十万、上百万的线程呢？假如在不增加复杂度的前提下，能做到更低的开销呢？golang 用 goroutine 给出了它的解答。

在 Eli Bendersky 的文章中，测试线程切换的用例是让两个线程通过一个管道往复传递数据，结果是：在一秒内，大概能来回传递 40 万次。而后他又顺手用 go 重写了测试代码，得到的结果是：每秒 280 万次。

不论如何，无节制的创建新线程，最终一定会产生许多安全性问题，如过多的上下文切换，内存耗尽等等。

实际上谈论线程切换的开销时，涉及到的点比较多，也很难给出绝对正确的设计决策。

在 Google 的这个视频中，开发人员提到了明确的测试数据：

  1. 线程切换的开销在 1~6 us 之间，其差异主要在于，若在同一个 CPU 核心内切换，所花费的时间可以低至 1us，而在不同核心之间切换的开销可能会达到 6us。设置了 CPU Affinity 后的测试结果证明了这一点。
  2. 然而我们不能简单的将所有线程绑核了事。毕竟虽然绑核可以提升性能，但当存在 idle core 时，其他线程可能无法调度到该 core 上。
  3. 进一步的数据显示，线程切换中，进入内核态的开销只有最多 50ns （通常我们认为在用户态和内核态之间切换十分耗时），大部分开销都是由于现代调度器复杂的调度决策导致在不同的 core 之间发生线程调度。

1.3 限制最大线程数

既然我们不能容忍无限制创建线程，那么最直接想到的自然是设定一个线程数上限，当线程超限后，拒绝再创建新的线程。

线程池是最通用的解决方案。

池化是资源复用的常见方式，线程池可以最多持有 n 个工作线程（当然根据工作负载的变化，n 可以是动态的），同时持有一个任务队列。工作线程执行如下的循环：从队列获取任务 -> 执行任务 -> 再次从队列获取任务，因此如果没有空闲的工作线程，任务就必须在队列等待。

线程池不仅能限制线程的最大数量，同时也能降低线程反复创建、销毁产生的开销。对于突发的大规模任务也能比较优雅的实现降级、削峰填谷等措施。

不过，简单使用线程池，一个任务对应一个线程的这种同步并发编程模型没有改变。

对于同步并发模式，显然有其固有的优势：

  • 程序清晰简单，易于实现
  • 线程本地变量易于分配和回收

但除了可能创建过多线程产生的资源问题以外，还有额外的劣势：

  • 由于粒度较粗，任务内嵌套的可并行部分（如多个 I/O 操作等），难以并行化。本质上是无法真正将 CPU 操作和 I/O 操作分开，CPU 操作和 IO 操作交替执行，会导致同一个线程被反复的换入换出产生许多切换开销
  • 此外，同一个线程在反复切换时，有可能调度到不同的 CPU 上，这种跨 CPU 的切换开销大得多

1.4 换种思路

对于 I/O 密集型的任务，执行过程中有很大一部时间都在等待，当 I/O 返回时任务才能继续工作。也正是这种等待的特点，给了我们创建多线程来提高 CPU 利用率的理由：阻塞等待中的线程不需要 CPU 时间。

设想假如我们将这种机制反过来，线程不是阻塞等待被唤醒，而是主动询问所有正在等待的 I/O，检查某个（或某些） I/O 是不是返回了。如果返回了，就处理与之关联的任务，而如果没有返回，线程就继续检查下一个等待中的 I/O，或者处理其他任务。

与阻塞唤醒的被动式相比，询问的方式会更加主动。原先的 “执行任务 -> I/O 阻塞 -> 继续执行” 的流程，变成了 “执行任务 -> 注册 I/O 事件 -> 回调任务” 。

这种模式称之为事件驱动的并发编程模型，线程进行轮询（poll）的动作，称为事件循环。

从工作原理上我们就能发觉，事件驱动模型有如下的特点：

  • 不需要很多线程：与多线程通过阻塞出让 CPU 相比，主动切换任务继续使用 CPU 资源，实际上是绕过了系统调度器，在用户侧传递任务上下文，比在内核侧切换线程上下文的开销小得多
  • 需要通过回调函数来保持事件与任务的关联关系：通过事件回调来继续执行先前被中断的任务
  • 主线程不允许存在阻塞：
    • 在多线程模型下对资源的阻塞等待式访问，需要全部替换成非阻塞式访问，否则一旦出现阻塞，将导致事件轮询线程无法继续轮询。
    • 对于阻塞 I/O 实际上还是需要引入线程池，但此时的 I/O 线程只负责 I/O 操作，不再负责处理计算或协调逻辑

1.5 Callback Hell

在事件驱动模型里，将耗费时间的 I/O 阻塞调用交给线程池进行异步化，在阻塞调用返回后，通过调用 callback 函数来恢复执行任务逻辑。

这种方式在简单的任务逻辑中运行的很好，然而当存在一个任务，其整个逻辑链条中包含了多个相互依赖的阻塞 I/O，这时 callback 函数的注册链路会不断加深，最后形成难以理解的 “Callback Hell” 。

产生 Callback Hell 的本质是什么？需要通过参数传递上下文。

注册回调函数时，将回调函数地址作为参数传递给事件注册器，是为了能够在合适的时机被调用。回调函数内访问的外部变量，是由编译器默默地通过闭包传递（不支持闭包的语言需要在堆上分配对象，并通过参数传递其地址）。

因为没有外部协助，所以我们需要在应用代码中通过回调函数进行上下文传递，随着传递次数的增多，就导致了回调地狱。

另外要注意的一点是，这里的 “上下文传递”，如果不做特殊处理，会丢失一部分上下文。假如在 callback 内抛出了错误，我们是无法追踪到这个 callback 是在哪里传入的：callerFunc 传入 callback，而调用栈信息在 callerFunc 返回的那一刻就丢失了。

1.6 协程

那么，假设：

  1. 如果能通过一些手段更优雅的维护任务的全部上下文，就不需要在参数中层层嵌套传递回调函数
  2. 如果不需要嵌套回调函数，就能像写同步阻塞的多线程代码一样写事件驱动的异步代码，进而方便的实现任务间的交互协作

基于上述讨论，我们自然会发现，只要想办法把完整的函数逻辑拆分成一个个小的异步任务，作为进行挂起/恢复（yield/resume）的最小单元，并且通过合理的手段维护任务上下文，确保挂起后能正确的找到恢复位置，我们就能实现任务间的切换和调度。

这已经覆盖了系统调度器的绝大部分工作内容（除了抢占，事件循环类似于协作式调度），任务可以类比为线程，不同点在于任务之间切换是协作式的（等待资源时主动挂起，出让 CPU），假如一个任务不主动出让 CPU，他就能永久的拥有该 CPU。对于这种执行协作式任务的模型，我们可以称之为协程（co-routine）模型。

这里需要注意的是，协程模型的提出相比线程模型更早。线程通过抢占式调度解决了协程的协作式调度对资源使用的的非公平性。

对于维护上下文的问题，协程模型的解决方式有两种：

  • 有栈式：通过保存、恢复现场，将协程的调用栈保存在协程结构内部
  • 无栈式：将协程之间的上下文保存在外部，常见的办法是有限状态机

1.7 用户级调度器

前面讨论完后，我们发现通过事件驱动 + 异步 I/O + 优雅切换上下文的办法，可以比较高效且友好的将应用逻辑中的 CPU 处理部分和 I/O 处理部分分开来执行，同时还不降低代码逻辑的完整性。

此时此刻，只剩下如下的两个问题未能解决：

  1. 饥饿问题：某些任务由于各种原因，长时间占据 CPU 时间，导致其他任务饥饿，可能产生严重的不公平。
  2. 线程管理问题：I/O 线程池如何分配更合理；并行的任务之间，如何通信和处理数据竞争。

对于问题 1，需要引入抢占式调度，在合适的时机对任务触发抢占，强制该任务出让 CPU。对于问题 2，可以抽象线程管理层，向下管理系统线程，向上提供任务之间的并发原语。

最终，我们就能得到一个构建在操作系统线程之上的用户级调度器。

它：

  • 将任务作为调度基本单元
  • 支持并发的任务协作与抢占，妥善处理数据竞争
  • 向任务屏蔽阻塞的系统调用
  • 能够基于任务编写同步风格的代码

以上就是 golang 调度器的大致特性，golang 中的任务正是 goroutine。

由于引入了完整的调度器抽象，golang 便有能力将 goroutine 与 channel 结合，实现 CSP 并发模型，将任务之间的通信和数据竞争转化为对象所有权的传递，优雅的解决了并发通信的问题（Do not communicate by sharing memory. Instead, share memory by communicating.）。

2. 什么是 G-P-M 模型？

2.1 基本调度理论

调度，就是分配资源（resource）用以执行任务（task）的动作。

这里的资源，可以是计算资源如 CPU，存储资源如内存空间，网络资源如带宽、端口等。任务是基于资源所执行的动作，它依赖资源并通过操作资源来产生价值。

调度目标

根据不同的资源、任务以及业务目标，调度器的设计目标是多样的：

  • 最大化吞吐量：效率优先，目的是让任务能尽可能充足的利用资源，而不是把资源花费在调度或等待上。
  • 最小化等待时间：体验优先，目的是让尽可能多的任务开始执行，效率和任务的实际完成时间次要考虑。
  • 最小化延迟和响应时间：体验优先，目的是尽可能让每一个任务都等待相对较少的时间，且能相对较快的执行。
  • 最大化公平：公平优先，目的是结合任务的任务优先级，以及单位资源的负载率，尽可能公平的将资源和任务匹配。

显然，上述目标之间非但不相辅相成，反而很可能相互掣肘（比如最大吞吐和最小延迟），因此选定调度器的设计目标必须结合实际的业务目标。

调度原理

之所以需要调度，是基于这种假设：资源通常是有限的，而需要执行的任务比资源多得多。假如任务比资源还少，那么就没有调度的必要了。

因此调度器的工作原理就是根据当下任务、资源的状态，基于特定的调度策略，做出调度决策：接下来哪些 task 将会拥有哪些资源。

我们可以得出，调度器在逻辑层面的样子：

映射到 Go

上述调度器原理，如果映射到 Go，显然 goroutine 是 task，操作系统线程是 resource。因此调度过程就是将选中的 goroutine 放到选中的线程上执行。

此外还需要考虑几个细节问题：

  1. 如何组织待执行的 goroutine ?
    • 平衡查找树：提高查找效率，适用于经常需要取出特定的 goroutine
    • 堆：用堆来实现优先级队列，适用于 goroutine 区分优先级的场景
    • 链表：链表实现的普通队列，适用于每一个 goroutine 都是相对平等的
  2. 如何组织线程资源？
    • 无界线程池：可能会经常创建或销毁大量线程，类似于 1：1 的映射关系，不适用 M:N 的场景
    • 有界线程池，容量等于 CPU 核数，绑核：线程与 CPU 核数 1：1，可以最大限度降低操作系统的线程切换，但假如 goroutine 触发系统调用，会阻塞整个线程
    • 有界线程池，灵活调整容量：根据 goroutine 数量灵活调整线程数，对于执行 goroutine 的线程保持最多与 CPU 核数一致，当进行系统调用时创建新线程，这样不会阻塞其他 goroutine，但线程管理更复杂
  3. 何时触发切换？
    • 系统调用：系统调用会阻塞线程，因此当有任务执行系统调用时，触发切换，并将系统调用的执行放到专门的线程中
    • 协作：多个 goroutine 间协作，类似前面提到的相互抛球，在一方等待时触发切换
    • 抢占：为了避免单个 goroutine 占据过多的 CPU 时间，需要定期扫描，将执行时间过久的 goroutine 换出
    • 主动触发：将触发调度权交给 goroutine，业务上可以选择主动放弃 CPU
  4. 如何实现切换？
    • 保存上下文：保存 PC、SP 以及其他通用寄存器，保存 goroutine 私有栈
    • 恢复上下文：恢复待换入的 goroutine 的 PC、SP 以及通用寄存器，和其私有栈

2.2 集中式调度器

基于前文所述，我们应该很容易的就能想象出一个 go 调度器的雏形（g 指代 goroutine，m 指代 os 线程，下同）：

显然，在 go 语言演进的初期，其调度器也是类似这个样子的。其特点有：

  1. 所有 goroutine 都进入一个全局队列，用 g 表示
  2. 线程分为执行 goroutine、执行 Syscall、空闲三种，用 m 表示
  3. 在 m 上执行调度逻辑，触发调度，从全局队列中获取新 g，替换 curg

这种调度方式很直接的反映了调度器需要做的事情：把任务（g）分配到资源（m）上。我们也称这种方式为集中式调度。

如果看 runtime/proc.go 的代码，在文件顶部注释中，引用了 go 调度器的设计文档，在设计文档中提到了上述集中式调度器存在的问题：

  1. 由于中心化存储所有状态，多线程调度时需要抢锁，需要锁保护的操作包括creation、completion、rescheduling 等，文中的测算数据是有大约 14% 的开销花在了对 futex 的锁竞争上
  2. 由于调度决策导致的同一个 g 在多个 m 之间往复执行（handoff），可能产生额外的延迟和开销（回顾 1.2 节的多核线程切换开销）
  3. 在 g 运行过程中的栈、小对象等等，都会存放在 m.mcache 缓存中，每当创建新的 m 时都会分配 mcache，但当 m 在执行 syscall 的时候，并不需要 mcache。在某些情况下执行 g 的 m 与其他 m 的比例可能高达 1：100，这导致：
    • 没用的 mcache 产生额外的资源消耗
    • 当 g 切换到不同的 m 上时，在 mcache 上加载关联的栈、对象等，会降低 data locality
  4. 由于系统调用导致 g 频繁的在不同的 m 上切换，产生大量开销

在抢锁问题上，我们可以用 lock-free 的方式降低开销吗？

不能。lock-free 的优势在于利用对内存位置的 atomic 操作来显著降低抢锁动作的开销，但这是建立在竞争不激烈的前提下。如果竞争本来就很激烈，所有线程一股脑的去执行 atomic 操作，效率可能反而不如排队，因为大量无效的抢锁动作也会耗费 CPU。

2.3 P 来了

根据前面提到的影响性能的场景，我们期望能做出如下的改变：

  • 尽量减少调度器抢锁，改善调度等待
  • 尽量降低同一个 g 在不同 m 之间切换的概率，提升 data locality
  • 尽量剥离非 m 必须的属性（如 mcache），降低资源浪费

为了达成上述目标，Dmitry Vyukov 在他的设计文档里，引入了 p 的概念。

P 代表 processor，从 go 调度器的角度看，可以理解为逻辑处理器。即将 m、syscall、I/O 等等概念屏蔽到 p 以下，逻辑上只有 g，g 只在 p 上运行，类比线程在 CPU 上运行。

在 m 的层面，除了原本的 m 执行 g 不变以外，要求 m 想要执行 g，必须先和某一个 p 绑定，g 相关的状态、上下文、对象等等都保存在 p 内。

如此可以引出完整的 G-M-P 模型图：

p 的数量默认与 CPU 核数保持一致，每个 p 里面都保存有一个自己的私有 g 队列，当 m 要执行 g 时，需要先绑定 p，并且从 p 的私有队列中获取 g。

这样一来，前面的目标悉数实现：

  • 每一个 g 在需要被调度时，m 都会尝试在绑定的 p 上调度，调度参与方只有单线程 m、 p 的私有队列，不需要加锁（实际上由于 p 可能会在 m 之间传递，还是需要用 cas 操作队列，但争抢概率大大降低）
  • 当 m 与 p 绑定后，调度所依赖的数据和操作大都在当前 m 上（p 的私有队列甚至是一个 ring），这可以有效利用 CPU 的缓存、预取等优化手段
  • 原本的 mcache，现在放在了 p 处，这样数据随 p 移动，与 m 彻底脱钩了

那么这里有一个新问题：g 都保存在 p 的本地队列中，由于调度不均衡，导致有的 p 空闲，有的 p 负担过重怎么办？

引入全局队列。

当出现某个 p 的私有队列空/满，导致无法取出/存入 g 时，将从全局队列中批量取/存一部分 g。全局队列用链表实现，无界，一般不会塞满。此外，因为通常 p 不会从全局队列中拿 g，为了保证一定的公平性（不至于全局队列中的 g 饥饿），每经过一定的调度次数后，就会强制从全局队列获取一个 g（实际是 61 次，为什么选 61？请见文末拓展阅读）。

假如全局队列也空了呢？

工作窃取。（这里省略了一些检查 gc、定时器、netpoll 等等动作，通常工作窃取是最后的选择）

从其他 p 的队列尾部，窃取一半的工作，转移到当前 p。

要是实在没有任务了呢？就只能让当前 m 陷入睡眠，p 进入 idle 队列，共同等待新任务到来。

3. 如何实现调度？

3.1 G 的生命周期

上图表示了一个 g 里面包含相对关键的内容，主要有三部分：

  • stack：golang 实现的 goroutine 是有栈的，也就是说一个任务的私有上下文都会保存在 g 的 stack 中。同时，golang 通过栈的扩缩容，实现了初始栈很小（大约 2KiB），同时确保随着代码执行栈能逐步的扩张而不会产生栈溢出（除非超过 64bit 平台下最大栈容量 1GB）
  • gobuf：可以看到里面包含有 sp、pc、ret 等等，显然 gobuf 是为了保存在 g 被换出前的代码执行位置以及相关上下文；此外，ctxt 保存的是 DX 寄存器的值，用于存储闭包中对外部对象的引用。
  • status：当前 g 的状态，用于表示当前的 g 处于什么样的过程中。

3.1.1 创建 G

最常见的：go func() 会在编译期被翻译为调用 runtime.newproc()，g 实际执行的函数会通过指针形式的参数传递到 newproc 函数中。

可见 g 结构可能从 free list 中获取，也可能在 free list 为空的时候申请新的，当有了新的 g （即 newg） 后，由于和当前 g （即 curg）分属不同的栈，因此要把在 curg 存储的 fn 参数复制到 newg 的栈内。

之后，对 newg 的 sp、pc、status 等进行初始化后，将 newg 塞入当前 p 的私有队列中。

注意这里对 sp 的初始化比较有趣：先是给 sp 写入了 goexit 函数的地址，之后又对 sp 减 8，这是为什么？

在聊 sp 存 goexit 地址之前，我们需要先看一看，go 函数调用中，栈结构是怎么分配的：

由一个简单的函数调用过程，得到汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
  p, q := cal(123, 456)
  print(p+q)
}

func cal(x, y int) (sum int, z int) {
  m := x + y
  n := m*2
  print(m + n)
  return m, n
}

func print(p int) {
  fmt.Println(p)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
## main()
TEXT	"".main(SB), ABIInternal, $40-0
## ... ...
SUBQ	$40, SP            # SP-40，申请 40 bytes 栈空间
MOVQ	BP, 32(SP)         # 保存原 BP 到栈底（SP+32）
LEAQ	32(SP), BP         # 新 BP 设置为当前栈底 （SP+32）
 ## ... ...
MOVQ	$123, (SP)         # 栈顶 SP 写入入参 x=123
MOVQ	$456, 8(SP)        # SP+8 写入入参 y=456
## ... ...
CALL	"".cal(SB)         # 调用 cal()，会自动将 cal 的返回位置存入 SP-8，并设置新 SP=SP-8
MOVQ	16(SP), AX         # SP+16 存放 cal 的返回值 1：p，存入 AX
ADDQ	24(SP), AX         # SP+24 存放 cal 的返回值 2：q，这里将 q 与 AX 之和存入 AX，即 p+q
MOVQ	AX, (SP)           # p+q 存入栈底 SP
CALL	"".print(SB)       # 调用 print()
MOVQ	32(SP), BP         # 恢复原 BP
ADDQ	$40, SP            # 释放栈空间
RET
## ... ...

## cal()
TEXT	"".cal(SB), ABIInternal, $24-32
## ... ...
SUBQ	$24, SP            # SP-24，申请 24 bytes 栈空间
MOVQ	BP, 16(SP)         # 保存main BP 到栈底（SP+16）
LEAQ	16(SP), BP         # 新 BP 设置为当前栈底 （SP+16）
## ... ...
MOVQ	"".x+32(SP), AX    # 入参 x，存入 AX，此时 SP 已经在 CALL 处被 -8，因此是 SP+32（SP+24+8）
MOVQ	"".y+40(SP), CX    # 入参 y，存入 CX
ADDQ	CX, AX             # x+y，存入 AX
MOVQ	AX, "".m+8(SP)     # AX 存入 SP+8，即局部变量 m
LEAQ	(AX)(AX*2), CX     # AX + AX*2，存入 CX，即 m+n
MOVQ	CX, (SP)           # CX 存入 SP，局部变量 n 被优化掉，直接将 m+n 作为 print() 的入参
## ... ...
CALL	"".print(SB)       # 调用 print()
MOVQ	"".m+8(SP), AX     # 取出 m 存入 AX
MOVQ	AX, "".sum+48(SP)  # AX 存入返回值 1：sum
SHLQ	$1, AX             # AX 左移一位，即 n = m*2
MOVQ	AX, "".z+56(SP)    # AX 存入返回值 2：z
MOVQ	16(SP), BP         # 恢复main BP
ADDQ	$24, SP            # 回收 24 bytes 栈空间
RET
## ... ...

## 省略 print()

可以看到，在 go 中，参数和返回值都通过栈传递（从 1.17 开始 amd64 平台已经转为寄存器传递，见：issue#40724）。

因此我们能绘制出上面汇编代码所反映出的栈结构来：

可见函数的入参和返回值是由调用方预留的，函数的局部变量放在自己的栈内，而同时也会给调用的其他函数预留参数和返回值。这里函数自己的栈空间，称为函数的栈帧。此外，CALL 指令会将调用方的返回地址存入 SP-8，并自动设置 SP=SP-8，而只有当函数栈帧大于零时（需要用到栈空间，才需要自己的 BP），才会保存调用者的 BP。

通用表示如下图（图源）：

上面提到，CALL 会自动保存返回地址，这里就对应了为什么创建 g 时，将 SP-8 = goexit。

原因是，给 SP-8 存入 goexit，会让 fn 返回后，由 CPU 直接跳转到 goexit，执行 g 的退出动作，包括释放空间等，并在退出的最后一步调用调度函数，重新进入调度。这种做法十分巧妙，不需要为 fn 插入额外的跳转逻辑。

3.1.2 切换 G

g 可能会在执行过程中被换出，那么整个换出、换入的动作，需要执行什么操作呢？为了尽可能的减少切换成本，go 将切换的过程组织的十分简练，归纳起来流程如下：

  1. 将待换出 curg 的 status 从 running 改为 runnable（如果是从 goexit 调度的，则状态改为 dead），并将 curg 的 pc、sp、bp 等寄存器保存入 curg.shed（即 gobuf ）
  2. 待换入 newg 的 status 从 runnable 改为 running，并将 newg 的 pc、sp、bp 等寄存器从 gobuf 中取出，恢复回寄存器
  3. PC 已经指向 newg 的恢复位置，下一条指令就开始执行 newg，完成切换

不过这里仍存在一个小问题：从 g 的视角看，g 在自己的的运行函数 fn 中，并不知道自己的 gobuf、stack、status 等等属性，这些对 g 本身来讲是透明的。那么，前面流程中改状态、保存、恢复寄存器是谁来干的呢？

答案是 g0。

g0 本身也是一个 g，他拥有 g 所拥有的所有属性，唯独是他没有自己的 fn，g0 的工作，就是在上帝视角执行调度相关逻辑。

在执行这些调度逻辑时，其各种函数调用所需要的栈空间就都从 g0 的栈中分配，g0 的栈比较特殊，它不支持扩缩容，而是在创建的时候就限定了其栈空间是8 KiB，这个空间确保所有调度相关的逻辑都够用而不会产生溢出。正因为在特殊的栈上执行特殊的工作，因此 g0 的栈也称为系统栈（systemstack，同样的 gsignal 的栈也叫系统栈）。

所以实际上的 g 切换过程为：

3.1.3 销毁 G

当一个 g 执行完毕后，如前文所述，会通过 ret addr 跳转到 goexit 函数。

goexit 函数是用 go 汇编写的一个包装函数，实际上最终是切换到 g0 后调用 runtime.goexit0()。

销毁一个 g，主要流程如下：

主要工作是改变状态、清理标志位等属性、释放栈空间，将该 deadg 放入 free list 队列，待下次 newproc() 时复用，最后重新执行调度。

3.2 调度

3.2.1 调度触发点

经过前文的描述，我们已经知道，goroutine 的调度，不是由专门的线程全程进行调度的。实际上在需要调度的时候，是由各种条件而触发，在 m 执行 g 的间隙进行调度（当然在 sysmon 中的抢占式调度除外，详见后文）。

首先，所有的调度意图，最终都会通过在系统栈上调用 schedule() 函数实现。那么，调度触发点都有哪些呢？

上述触发点从设计上讲是十分合理的，比如：

  • 创建了新的 m 后，自然需要触发调度来将 g 调度到新的 m 上
  • 在 g 之间存在依赖和等待时（比如等锁，等 channel，等 gc，等网络），也需要放弃当前执行，触发调度
  • g 执行结束了，通过触发调度出让 m 资源
  • 从阻塞的系统调用返回时，应该触发调度，恢复执行
  • 抢占

3.2.2 调度循环

在触发了调度之后，就正式进入调度循环。

调度循环的唯一目的就是找到一个合适的 g，并将之切换到 m 上执行。

调度循环流程如下：

在整个流程中，任一环节拿到了 g，就直接返回并切换。

首先会检查是否需要执行 gc 标记，之后分别从本地队列、全局队列、net poller 处检查，还没有就尝试任务窃取，如果任务窃取也偷不到任何 g，则休眠，等待被唤醒（在调度过程中、创建新的 g、抢占、netpoll 等很多时机都会尝试唤醒）。

3.3 M 与系统调用

3.3.1 M 生命周期

从 m 的结构来看，m 上可以运行 g、g0、gsignal，也可以脱离 g 运行 start_fn。在前面提到的调度流程中，当 m 在执行 schedule() 时，如果找不到 g，m 的状态会被设置为 spining，代表此时的 m 正在自旋寻找任务。而经过一系列动作后，还是无任务可做，那么 m 就会被 block，等待有任务的时候再被唤醒。

golang 为了支持多平台，在线程、内存、网络等操作上都抽取了抽象函数，对 m 的操作也一样。m 与 os 线程一一绑定，其整个生命周期的动作如下：

可以看到，对 m 的操作是通过clone()、futex()等等系统调用操作 os 线程实现的。有趣的是，在目前的 golang 版本中，只有当进程退出时 os 线程才会被释放（通过exit()系统调用）。其他时刻，不论有多少个 m 在休眠，都不会将其对应的 os 线程关掉，相关讨论可见 #issue14592。

3.3.2 系统调用

goroutine 在执行用户代码的过程中，必定会遇到需要操作系统协助的相关动作，以最简单的文件操作为例：如open()、read()、write() 等的基本操作，都需要操作系统的支持。

golang 将这些系统调用操作，都进行了封装和整理，当尝试执行系统调用时，会进行一系列的处理：

如图所示，在执行 syscall 之前，保存当前 g，并通过 handoffp() 将 g 所在的 p 换出到其他 m 上执行（这一步是通过 sysmon 间接完成的）。之后原先的 m 开始正式执行系统调用，在执行完毕后，将原 g 恢复，入队（无论是插入某个空闲的 p，还是直接插入全局队列），之后再次调度。最后原先的 m 会休眠，等待被唤醒。

3.3.3 Net Poller

为了能高效的处理网络事件，各类操作系统都会采用一些方法，如 linux 下通过内核事件轮询实现的 epoll，其他类似的有 kqueue、IOCP 等。

golang 通过 net poller 将不同 os 对处理网络事件的动作进行了抽象：

以 linux 系统为例，进行网络动作时会初始化 epoll（只做一次），之后每当需要等待网络 I/O 时，就会将携带着 g 的事件注册到 epoll，之后 g 阻塞换出（gopark），直到调用 epoll_wait() 得到了 ready 的 fd 后，取出关联的 g，将其放入调度队列等待调度。

对 epoll_wait() 的调用不是由专门的线程做的，而是在调度过程中、sysmon、退出 STW 等等很多地方都会尝试检查，一旦发现有 ready 的 g，就将之放入调度队列。

3.3.4 Timer

我们经常使用 time.Sleep() 来让 g 休眠一段时间，并在时间到了之后醒来。显然，获取时间也需要涉及到系统调用，那么完整的休眠、唤醒的流程是怎样的？

整个流程十分简单，调用 time.Sleep() 的 g 会创建一个设定了唤醒时间的 timer，并将自身与之绑定，之后将这个 timer 注册到 p 上，然后进入休眠。在每一次调度的时候，调度逻辑都会检查 p 上所有的 timer，如果超过了唤醒时间，就将绑定的 g 唤醒，放入调度队列。整个流程里只有获取系统时间的部分，需要与系统交互。

正因为是在每一次调度的时候才会检查 timer，那么就存在一个问题，如果当前系统没有调度需求，那么只有当超过一定时间强制抢占时才会真正检查 timer，所以可以得出 time.Sleep() 的实际休眠时间是不会太准确的。

3.4 抢占

3.4.1 触发

在前面所述的绝大多数场景下，g 之间的调度都是协作式（cooperative）的，比如等锁时换出，系统调用时换出等等。然而很多时候我们需要从外部抢占 goroutine，为了解决：

  • 某一个 g 可能会持续运行，导致其他 g 饥饿，或是难以切换到 g0 去执行一些底层工作

  • 当需要 STW 时，通常是等待所有的 g 执行到某个 safe point 后暂停。在实现抢占之前是通过编译器在函数调用前插入检查逻辑实现的，在某些特殊情况下这可能导致长时间的等待

因此，golang 通过如下触发抢占的手段解决上述问题：

  1. sysmon 线程：前面提到了，sysmon 不依赖 g，直接绑定在 m 上执行。类似守护线程定期执行一些维护工作，当它发现某个 g 执行时间过久时，就会触发抢占信号
  2. GC：当 gc 要扫描 g 的栈时，就会触发抢占，让当前 g 暂停配合扫描
  3. STW：在 stw 时抢占所有 g

如上图所示，触发抢占后，会尝试进行两个动作，一是将被抢占 g 的 preempt 标志置为 true，触发同步抢占，相关抢占逻辑会检查该状态判断是否实施抢占；二是发出抢占信号 sigPreempt，这是基于操作系统信号实现的异步抢占逻辑。

3.4.2 实施

抢占分两种：

  1. 直接将当前 g 换出，加入全局队列后执行调度
  2. 将当前 g 休眠，直接执行调度，并在之后唤醒。这种抢占方式主要用于 GC 栈扫描。休眠再唤醒的方式可以更准确的控制 g。

同步抢占

同步抢占的逻辑比较简单，主要在栈伸缩、gc 标记等处检查 preempt 标记（栈伸缩时是通过 stackguard0 标记），如果为 true 则实施抢占。

异步抢占

异步抢占通过信号机制实现。整个抢占流程如图所示：

抢占信号发出后，系统内核会将对应的线程信号表置位，当下一次该线程被系统调度器调度时，会处理 pending 的信号。由于这个过程不是同步的，因此称之为异步抢占（由图可见，在做信号处理时，用到了 m 中保存的 gsignal 用作系统栈）。

在多数情况下，同步抢占通过函数调用时对抢占标志的检查就可以完成，但异步抢占可以解决某些极端场景，如某个 g 执行了 for {} ，如果没有通过内核发送的信号机制，仅仅靠 go scheduler，是无法打断死循环流程的。

4 总结

本文主要介绍了 golang 中 goroutine、调度器等的实现，用来解释 golang runtime 是如何分配和调度计算资源的。

首先通过介绍 I/O 密集型并发编程中遇到的问题与挑战，来描述 golang 为什么要构造一个用户级调度器；

其次简要讨论了分布式调度器对集中式调度器的性能改善；

最后解释了 golang 是如何实现 goroutine 的调度的。

Reference

  1. 《Java 并发编程实战》§8.2 设置线程池大小
  2. Measuring context switching and memory overheads for Linux threads
  3. User-level threads....... with threads. - Paul Turner - Google
  4. Concurrent Servers: Part 2 - Threads
  5. Concurrent Servers: Part 3 - Event-driven
  6. Concurrent Servers: Part 6 - Callbacks, Promises and async/await
  7. 《Go 语言设计与实现》 §6.5 调度器
  8. 《Go语言高级编程》§3 Go汇编语言
  9. Go Source Code

拓展阅读

Go scheduler: Implementing language with lightweight concurrency