观golang作者分享go scheduler有感 -- GMP模型浅析

golang 核心开发人员，goroutine 调度的设计者 Dmitry Vyukov，在 2019 的一个 公开演讲《Go scheduler: Implementing language with lightweight concurrency》里面里阐述了 goroutine 调度的设计思想以及一些优化的细节。(youtube地址:https://www.youtube.com/watch?v=-K11rY57K7k) , 本文是笔者结合自身经验和认知的一点观后感，采用从零开始层层递进的方法，总结剖析了其背后的软件设计思想，希望能够帮助大家更好的了解GMP的演进和设计思路。

零、术语

简写	含义
G	goroutine，go中的协程
M	一个实际的线程(thread of a core)
P	协程调度器的抽象
GMP	go scheduler模型的抽象

一、如何设计go scheduler

1. goroutine的设计目标

goroutine 调度的设计目标，其实就是设计一种高效的并发编程模型

• 从开发的角度只需要一个关键词（go）就能创建一个执行会话，很方便使用，即开发效率是高效的。
• 从运行态的角度，上述创建的会话也能高效的被调度执行，即运行效率也是高效的。
  我们可以近似将 goroutine 看待为协程（一些代码逻辑 + 一个栈上下文）
• 为了降低开发者的开发心智，最好能支持无线大小的栈
• 能保证goroutine之间能够进行公平的调度

1.2 朴素实现,M:G = 1:n

​ 想要实现并发的执行流，最直截了当的，自然就是多线程。由此便得出初始思路：每个 goroutine 对应一个线程。

​ 从并发的功能角度来讲，该方案固然可以实现并发，但性能方面却很不堪，尤其是在并发很重的时候，成千上万个线程的资源占用、创建销毁、抢占调度带来的开销会很巨大。

1.3 线程池方案，M:G=n:m

既然线程太多不好，那我们可以很轻易地做出一点改善，控制一下线程数量，如此便得到更进一步的方案：线程池，限定只启动 N 个线程。

由于该方案下，可能是 M 个 goroutine，N 个线程，因而显然需要考虑一个问题：对于一个 goroutine，它到底该由哪个线程去执行？我们可以简单地采用一个全局的 Global Run Queue，然后让所有线程主动去获取 goroutine 来执行，如下图：

这样做在线程少的时候，如果调度行为不是很频繁，可能问题不大。但当线程较多时，就会有 scalable 的问题，mutex 的互斥竞争会非常激烈（考虑到基于时间片的抢占行为，实际上调度必然是很频繁的）,称为调度器的性能瓶颈。

1.4 朴素线程分治

在多线程编程领域中，互斥处理可以称得上是“名声在外”，需极其小心地去应对。最常见的解决方案，并不是如何精妙地去 lock free(本人最讨厌的设计之一)，而是直接通过 “数据分治” 和 “逻辑分治” 来避免做复杂的加锁互斥，将各个线程按横向（负载分组）或纵向（逻辑划分）进行切分来处理工作。

通过数据分治的思想，我们就可以得到改进的方案：每个线程分别处理一批 G， 进行线程分治,将所有 G 分开放到各线程自己的存储中，即所谓的 Local Run Queue 中，如下图：

这样不仅避免了频繁的线程切换，同一个G，因为只会在同一个M中执行，能够极大的利用CPU cachelocality。

1.5 朴素GMP模型–Processor的设计

让我们继续分析确认一下，该模型是否真的解决了 scalable 的问题。上述模型下，为了充分利用 CPU，每个线程要按一定的策略去 Steal 其他线程 Local Run Queue 里面的 G 来执行，以免线程之间存在 load balance 问题（有些太闲，有些又太忙）。

因此在线程很多的时候，存在大量的无意义加锁 Steal 操作，因为其他线程的 Local Run Queue 可能也常常都是空的。还有另一个问题，由于现在的一些内存资源是绑定在线程上面的，会导致线程数量和资源占用规模紧耦合。当线程数量多的时候，资源消耗也会比较大。

注：在 N 核的机器环境下，假如我们设定线程池大小为 N，由于系统调用的存在（关于系统调用的处理见后文），实际的线程数量会超过 N。

上面这么多方案，都只提到了GMP中的G和M，那么P是如何设计和抽象出来的呢？

既然每个线程一份资源也不合适，那么我们可以仿照线程池的思路，单独做一个资源池，做计算存储分离：把 Local Run Queue 及相关存储资源都挪出去，并依然限定全局一共 N 份，即可实现资源规模与系统中的真实线程数量的解耦。线程每次从对应的数据结构（Processor）中获取 goroutine 去执行，Local Run Queue 及其他一些相关存储资源都挂在 Processor 下。这样加一层 Processor 的抽象之后，便得到初步的GMP方案：

1.6 final方案–真正的GMP

到1.5，其实基本的GMP方案已经完成了，但是为了

• 更加高效的处理网络调用(大多数网络调用会导致线程阻塞)，go中会有一个独立的网络管理模块Net Poller,Net Poller 独享一个(可能多个)P和G，这个Processor所有的goroutine都是网络调用相关的请求和处理，当某个P已经处理完所有G，则会检查Net Poller是否有goroutine待处理，然后steal过来处理。
• 提高线程利用率，既能避免线程频繁调度切换，也防止有线程处于空耗/自旋

设计了一套Work-Stealing机制，流程如下

1. 只有 1/61 的情况下，会检查 GRQ 来获取一个 G 来运行
2. 如果没找到，则检查 LRQ
3. 如果 LRQ 也为空，则尝试从其它 P 上偷 G
4. 如果偷不到，就再检查 GRQ
5. 如果还是没事干，就会从 Network Poller 上拿一个

因此最终的方案如下：

二、go scheduler如何保证调度的公平性以及抢占

​ 前面我们主要侧重讲的是如何高效，还未讨论到调度的另一个关键问题：公平性与抢占，接下来我们看看如何实现抢占。

​ 参考操作系统 CPU 的调度策略，通常各进程会分时间片，时间片用完了就轮到其他进程。在 golang 里也可以如此，不能让一些 goroutine 长期霸占着运行资源不退出，必须实现基于时间片的 “抢占”。

那怎么抢占呢，需要监测 goroutine 执行时间片是否用完了。如果要检查系统中的各种状态变化、事件发生情况，通常会有中断与轮询两种思路，中断是由一个中控方来做检查与控制，而轮询则是各个参与方按一定的策略主动 check 询问。因此对于 goroutine 抢占而言，有以下两种解决方案：

1）Signals，通过信号来中断原来的线程执行。

2）Cooperative checks，通过线程间歇性轮询自己 check 运行的时间片情况来主动暂停。

二者的优劣对比如下：

signals	cooperative checks
依赖os	与os独立
快	慢(1~10%)
不可抢占时间较多	不可抢占时间较少

​ 因为 golang 其实是有 runtime 的，而且代码编译生成也都是 golang 编译器控制的，综合优劣分析，选择后者会比较合理。

​ 对于 Cooperative checks 的方案，从代码编译生成的角度看，很容易做 check 指令的埋点。且因为 golang 本来就要做动态增长栈，在函数入口处会插入检查是否该扩栈的指令，正好利用这一点来做相关的检查实现（这里有一些优化细节，可以使得基于时间片的抢占开销也较小）。

插入 check 指令的做法，会导致该方案存在一个理论缺陷：若有一个死循环，里面的所有代码都不包含 check 指令，那依然会无法抢占，不过现实中基本不存在这种情况，总会做函数调用、访问 channel 等类似操作，因此不足为虑（实际上有个场景无法忽略，那就是 GC 的 STW(stop the world)，如果那个时候要停住所有 goroutine，而有一个处于死循环中，那就会导致 GC 卡住，所以后续版本的 golang 还是又通过 signal 抢占解决了这个问题）。

除此以外还有一个系统调用的问题，当线程一旦进入系统调用后，也会脱离 runtime 的控制。试想万一系统调用阻塞了呢，基于 Cooperative checks 的方案，此时又无法进行抢占，是不是整个线程也就罢工了。所以为了维持整个调度体系的高效运转，必然要在进入系统调用之前要做点什么以防患未然。 这里采用的办法也很直接，对于即将进入系统调用的线程，不做抢占，而是由它主动让出执行权。线程 A 在系统调用之前 handoff 让出 Processor 的执行权，唤醒一个 idle 线程 B 来做交接。当线程 A 从系统调用返回时，不会继续执行，而是将 G 放到 run queue，然后进入 idle 状态等待唤醒，这样一来便能确保活跃线程数依然与 Processor 数量相同。

references:

https://www.youtube.com/watch?v=-K11rY57K7k

https://www.mo4tech.com/golang-gmp-model-for-concurrent-scheduling.html