共计 3196 个字符，预计需要花费 8 分钟才能阅读完成。
如果你已经阅读了前 2 篇文章：《调度起源》和《宏观看调度器》，你对 G、P、M 肯定已经不再陌生，我们这篇文章就介绍 Go 调度器的基本原理，本文总结了 12 个主要的场景，覆盖了以下内容：
G 的创建和分配。
P 的本地队列和全局队列的负载均衡。
M 如何寻找 G。
M 如何从 G1 切换到 G2。
work stealing，M 如何去偷 G。
为何需要自旋线程。
G 进行系统调用，如何保证 P 的其他 G ’ 可以被执行，而不是饿死。
Go 调度器的抢占。
12 场景
提示：图在前，场景描述在后。
上图中三角形、正方形、圆形分别代表了 M、P、G，正方形连接的绿色长方形代表了 P 的本地队列。
场景 1：p1 拥有 g1，m1 获取 p1 后开始运行 g1，g1 使用 go func()创建了 g2，为了局部性 g2 优先加入到 p1 的本地队列。
场景 2：g1 运行完成后(函数：goexit)，m 上运行的 goroutine 切换为 g0，g0 负责调度时协程的切换（函数：schedule）。从 p1 的本地队列取 g2，从 g0 切换到 g2，并开始运行 g2(函数：execute)。实现了线程 m1 的复用。
场景 3：假设每个 p 的本地队列只能存 4 个 g。g2 要创建了 6 个 g，前 4 个 g（g3, g4, g5, g6）已经加入 p1 的本地队列，p1 本地队列满了。
蓝色长方形代表全局队列。
场景 4：g2 在创建 g7 的时候，发现 p1 的本地队列已满，需要执行负载均衡，把 p1 中本地队列中前一半的 g，还有新创建的 g 转移到全局队列（实现中并不一定是新的 g，如果 g 是 g2 之后就执行的，会被保存在本地队列，利用某个老的 g 替换新 g 加入全局队列），这些 g 被转移到全局队列时，会被打乱顺序。所以 g3,g4,g7 被转移到全局队列。
场景 5：g2 创建 g8 时，p1 的本地队列未满，所以 g8 会被加入到 p1 的本地队列。
场景 6：在创建 g 时，运行的 g 会尝试唤醒其他空闲的 p 和 m 执行。假定 g2 唤醒了 m2，m2 绑定了 p2，并运行 g0，但 p2 本地队列没有 g，m2 此时为自旋线程（没有 G 但为运行状态的线程，不断寻找 g，后续场景会有介绍）。
场景 7：m2 尝试从全局队列 (GQ) 取一批 g 放到 p2 的本地队列（函数：findrunnable）。m2 从全局队列取的 g 数量符合下面的公式：
n = min(len(GQ)/GOMAXPROCS + 1, len(GQ/2))
公式的含义是，至少从全局队列取 1 个 g，但每次不要从全局队列移动太多的 g 到 p 本地队列，给其他 p 留点。这是从全局队列到 P 本地队列的负载均衡。
假定我们场景中一共有 4 个 P，所以 m2 只从能从全局队列取 1 个 g（即 g3）移动 p2 本地队列，然后完成从 g0 到 g3 的切换，运行 g3。
场景 8：假设 g2 一直在 m1 上运行，经过 2 轮后，m2 已经把 g7、g4 也挪到了 p2 的本地队列并完成运行，全局队列和 p2 的本地队列都空了，如上图左边。
全局队列已经没有 g，那 m 就要执行 work stealing：从其他有 g 的 p 哪里偷取一半 g 过来，放到自己的 P 本地队列。p2 从 p1 的本地队列尾部取一半的 g，本例中一半则只有 1 个 g8，放到 p2 的本地队列，情况如上图右边。
场景 9：p1 本地队列 g5、g6 已经被其他 m 偷走并运行完成，当前 m1 和 m2 分别在运行 g2 和 g8，m3 和 m4 没有 goroutine 可以运行，m3 和 m4 处于自旋状态，它们不断寻找 goroutine。为什么要让 m3 和 m4 自旋，自旋本质是在运行，线程在运行却没有执行 g，就变成了浪费 CPU？销毁线程不是更好吗？可以节约 CPU 资源。创建和销毁 CPU 都是浪费时间的，我们希望当有新 goroutine 创建时，立刻能有 m 运行它，如果销毁再新建就增加了时延，降低了效率。当然也考虑了过多的自旋线程是浪费 CPU，所以系统中最多有 GOMAXPROCS 个自旋的线程，多余的没事做线程会让他们休眠（见函数：notesleep()）。
场景 10：假定当前除了 m3 和 m4 为自旋线程，还有 m5 和 m6 为自旋线程，g8 创建了 g9，g8 进行了阻塞的系统调用，m2 和 p2 立即解绑，p2 会执行以下判断：如果 p2 本地队列有 g、全局队列有 g 或有空闲的 m，p2 都会立马唤醒 1 个 m 和它绑定，否则 p2 则会加入到空闲 P 列表，等待 m 来获取可用的 p。本场景中，p2 本地队列有 g，可以和其他自旋线程 m5 绑定。
场景 11：（无图场景）g8 创建了 g9，假如 g8 进行了非阻塞系统调用（CGO 会是这种方式，见 cgocall()），m2 和 p2 会解绑，但 m2 会记住 p，然后 g8 和 m2 进入系统调用状态。当 g8 和 m2 退出系统调用时，会尝试获取 p2，如果无法获取，则获取空闲的 p，如果依然没有，g8 会被记为可运行状态，并加入到全局队列。
场景 12：（无图场景）Go 调度在 go1.12 实现了抢占，应该更精确的称为请求式抢占，那是因为 go 调度器的抢占和 OS 的线程抢占比起来很柔和，不暴力，不会说线程时间片到了，或者更高优先级的任务到了，执行抢占调度。go 的抢占调度柔和到只给 goroutine 发送 1 个抢占请求，至于 goroutine 何时停下来，那就管不到了。抢占请求需要满足 2 个条件中的 1 个：1）G 进行系统调用超过 20us，2）G 运行超过 10ms。调度器在启动的时候会启动一个单独的线程 sysmon，它负责所有的监控工作，其中 1 项就是抢占，发现满足抢占条件的 G 时，就发出抢占请求。
场景融合
如果把上面所有的场景都融合起来，就能构成下面这幅图了，它从整体的角度描述了 Go 调度器各部分的关系。图的上半部分是 G 的创建、负债均衡和 work stealing，下半部分是 M 不停寻找和执行 G 的迭代过程。
如果你看这幅图还有些似懂非懂，建议赶紧开始看雨痕大神的 Golang 源码剖析，章节：并发调度。
总结，Go 调度器和 OS 调度器相比，是相当的轻量与简单了，但它已经足以撑起 goroutine 的调度工作了，并且让 Go 具有了原生（强大）并发的能力，这是伟大的。如果你记住的不多，你一定要记住这一点：Go 调度本质是把大量的 goroutine 分配到少量线程上去执行，并利用多核并行，实现更强大的并发。
下集预告
下篇会是源码层面的内容了，关于源码分析的书籍、文章可以先看起来了，先剧透一篇图，希望阅读下篇文章赶紧关注本公众号。
推荐阅读
Go 调度器系列（1）起源 Go 调度器系列（2）宏观看调度器
参考资料
在学习调度器的时候，看了很多文章，这里列一些重要的：
The Go scheduler: https://morsmachine.dk/go-sch…
Go’s work-stealing scheduler: https://rakyll.org/scheduler/，中文翻译版: https://lingchao.xin/post/gos…
Go 夜读：golang 中 goroutine 的调度: https://reading.developerlear…
Scheduling In Go : Part I、II、III: https://www.ardanlabs.com/blo…，中文翻译版: https://www.jianshu.com/p/cb6…
雨痕大神的 golang 源码剖析: github.com/qyuhen/book
也谈 goroutine 调度器: https://tonybai.com/2017/06/2…
kavya 的调度 PPT: https://speakerdeck.com/kavya…
抢占的设计提案，Proposal: Non-cooperative goroutine preemption: https://github.com/golang/pro…
如果这篇文章对你有帮助，请点个赞 / 喜欢，感谢。
本文作者：大彬
如果喜欢本文，随意转载，但请保留此原文链接：http://lessisbetter.site/2019/04/04/golang-scheduler-3-principle-with-graph/
