深入学习 Golang GMP 调度器

1. 前言

Go 语言最大的魅力就是只需要 go 关键字即可快速创建一个 goroutine ，无需关注操作系统的调度细节，即可利用上多核轻松开发出高并发的服务器应用。理解了 Golang 调度器的机制，能让我们写出高性能的并发程序，也可以提升我们的问题定位、性能优化的能力。

2. 进程、线程、协程

任何并发程序，无论在应用层是何形式，最终都要被操作系统所管理。由此涉及到以下几个概念：

• 进程 (Process)：操作系统分配资源的基本单位
• 线程 (Thread)：CPU 调度的基本单位，一个核上同时只能运行一个线程，单线程的栈内存大小约 1MB
• 协程 (Coroutine)：轻量级、用户态线程。在 Go 语言中，有 goroutine的概念。当一个 goroutine 被创建出来时，分配的栈大小是 2KB，可见其「轻量」

3. 早期的调度模型：GM 模型

系统的设计往往都不是一蹴而就的，伴随着演进和优化，Golang scheduler 也不例外。1.1 版本前的 go，使用的是相对简单的 GM 模型来处理 goroutine 的调度，GM 实际是两个结构体，即：

• G(Goroutine): 协程结构体，使用 go func() 时，就会创建一个 G
• M(machine): 处理线程操作的结构体，与操作系统直接交互

GM 模型包含一个全局协程队列，即所有新建的 G 对象都会排队等待 M 的处理。如图：

这样的设计在高并发下会带来以下问题：

What’s wrong with current implementation:

1. Single global mutex (Sched.Lock) and centralized state. The mutex protects all goroutine-related operations (creation, completion, rescheduling, etc).
2. Goroutine (G) hand-off (G.nextg). Worker threads (M’s) frequently hand-off runnable goroutines between each other, this may lead to increased latencies and additional overheads. Every M must be able to execute any runnable G, in particular the M that just created the G.
3. Per-M memory cache (M.mcache). Memory cache and other caches (stack alloc) are associated with all M’s, while they need to be associated only with M’s running Go code (an M blocked inside of syscall does not need mcache). A ratio between M’s running Go code and all M’s can be as high as 1:100. This leads to excessive resource consumption (each MCache can suck up up to 2M) and poor data locality.
4. Aggressive thread blocking/unblocking. In presence of syscalls worker threads are frequently blocked and unblocked. This adds a lot of overhead.

（原文见 Scalable Go Scheduler Design Doc）

翻译总结一下，即存在以下优化点：

1. 全局锁、中心化状态带来的锁竞争导致的性能下降
2. M 会频繁交接 G，导致额外开销、性能下降。每个 M 都得能执行任意的 runnable 状态的 G
3. 对每个 M 的不合理的内存缓存分配，进行系统调用被阻塞住的 M 其实不需要分配内存缓存
4. 强线程阻塞/解阻塞。频繁的系统调用导致的线程阻塞/解阻塞带来了大量的系统开销。

由此演进出经典的 GMP 调度模型

4. 高效的 GMP 调度模型

为了解决 G 和 M 调度低效的问题，中间层 P(Processor) 被引入了。

• P(Processor) 即管理 goroutine 资源的处理器

由此得以将原先的系统线程资源管理 M 与 goroutine 对象 G 解耦。

除此之外，GMP 还引入了几个新概念：

• LRQ (Local Runnable Queue) 本地可运行队列，这个「本地」，是针对 P 而言的，是指挂载在一个 P 上的可运行 G 队列
• GRQ (Global Runnable Queue) 全局可运行队列

如下图所示：


LRQ 与 GRQ

从 runtime 源码可知，整体的调度流程如下：

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll .NETwork.
}

翻译一下，即

• 只有 1/61 的情况下，会检查 GRQ 来获取一个 G 来运行
• 如果没找到，则检查 LRQ
• 如果 LRQ 也为空，则尝试从其它 P 上偷 G
• 如果偷不到，就再检查 GRQ
• 如果还是没事干，就会从 Network Poller 上拿一个。这里的 Network Poller 是 go 管理网络调用的模块，如下图，当出现网络 IO 时，就会将当前的 G 移交到 Network Poller 处理。P.S. Network Poller 的实现，又可以扯一篇文章出来了，以后有空专门开一篇分析。

src="https://www.isolves.com/d/file/p/2023/09-18/a9690b348185cead9640fed0eb650bd3.jpg" />

Work-stealing 机制

GMP高性能的关键，在于引入了 work-stealing 机制，如下图所示：


work-stealing 机制

当一个新的 G 被创建时，它会被追加到它当前 P 的 LRQ 队尾。当一个 G 被执行完时，它当前的 P 会先尝试从自己的 LRQ 中 pop 一个 G 出来执行，如果此时队列为空，则会随机选取一个 P 并偷走它一半的 G ，对应图中，也就是 3 个 G

这就好比公司里的卷王，自己的需求做完了，还要悄悄把摸鱼大王的需求清单里一半的需求都挂到自己名下，囧

最后一个疑问：GRQ 什么时候被写入呢？

这又涉及到 G 创建时的分配流程了，我们知道，goroutine 都是由老的 goroutine 分配出来的，mAIn 函数也不例外，因此每个 G 被分配的时候已经有一个老 G 和对应的老 P 了，在挂载 G 到 P 上时，也会优先挂在到老 P 的 LRQ 上去。但是老 P 的 LRQ 其实是有限的，当挂满的时候，这个新 G 就只能挂到 GRQ 上，等待被调度了。可以参考源码中 P 的定义，其中 runq 就是 GRQ 了：

type p struct {
   ...
    // Queue of runnable goroutines. Accessed without lock.
   runqhead uint32
   runqtail uint32
   runq     [256]guintptr
    ...
}

5. 小结

本文讲解了 go 语言调度器的发展及基于 GMP 的 work-stealing 策略，这个「偷」可以说是非常精妙啦～ 这是 「Golang 并发编程」 系列的第一篇文章，如果对你有帮助，可以点个关注/在看来激励我继续写文章～