本文是 「Golang 并发编程」系列的第一篇，笔者水平有限，欢迎各位大佬指点～
## 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](https://xie.infoq.cn/article/a6948402be688dba530094e9b)）
翻译总结一下，即存在以下优化点：
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)` 全局可运行队列
如下图所示：
从 runtime 源码可知，整体的调度流程如下：
```go
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` 的实现，又可以扯一篇文章出来了，以后有空专门开一篇分析。
### Work-stealing 机制
`GMP`高性能的关键，在于引入了 `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 了：
```go
type p struct {
...
// Queue of runnable goroutines. Accessed without lock.
runqhead uint32
runqtail uint32
runq [256]guintptr
...
}
```
## 5. 小结
本文讲解了 go 语言调度器的发展及基于 GMP 的 work-stealing 策略，这个「偷」可以说是非常精妙啦～ 这是 「#Golang 网络编程」 系列的第一篇文章，如果对你有帮助，可以点个关注/在看来激励我写文章～
To be continued...
### 参考资料
- 《Head First of Golang Scheduler》https://zhuanlan.zhihu.com/p/42057783
- 《动图图解！GMP模型里为什么要有P？背后的原因让人暖心 | Go主题月》https://juejin.cn/post/6956008643456139301
- 《Golang 调度器 GMP 原理与调度全分析》https://learnku.com/articles/41728
- 《Go's work-stealing scheduler》https://rakyll.org/scheduler/
- 《Scheduling In Go : Part II - Go Scheduler》https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part2.html
- 《Go的隐秘世界：Goroutine调度机制概览》https://zhuanlan.zhihu.com/p/244054940
