引言

在传统的编程语言中，并发实现多是基于线程模型。以pthread为例，应用程序创建线程，虽然这个过程是在用户态，但实际的创建和调度都由内核态完成，操作系统调度器将软件线程调度到不同的硬件线程上运行。在 Go 的并发实现中，使用 goroutine 代替了线程，不再依赖操作系统调度器，在用户态实现将goroutine放到不同的内核态线程中运行。

跨处理器调度策略

调度通常意味着为完成某个过程分配有限的资源。如何在调度的过程兼顾公平（不能导致饥饿）和效率，同时考虑到负载均衡，资源利用和优先级处理，是伴随计算机硬件发展和应用场景拓展而不断变化的课题。在具体介绍 Go 所使用的工作窃取策略之前，先从朴素策略开始介绍一些调度策略。

朴素公平策略

为了使CPU各核心（以下简称处理器）之间负载尽可能平衡，自然地想到在各处理器之间平均分配。处理器有 n 个核心，有 x 个任务需要执行，在朴素的公平调度策略中，每个处理器都会得到x / n个任务。

但是在Go语言的并发模型使用的是fork-join模型，任务可能相互依赖，平均分配任务可能会导致其中一个利处理器用率不足，还可能导致缓存和TLB失效。如：

其中T1在执行时调用T4并依赖T4的结果，T3依赖T1的结果。在时间n+a时，P1可以执行T4来解除自己的阻塞。

工作窃取策略

可以在以上的基础上增加一个FIFO队列用于调度，这是最基础的工作窃取策略，在处理器有空闲的时候将任务出队。

这种最基础的策略解决了未充分利用处理器的问题，比简单地在处理器之间分配任务要好，但是因为引入了一个集中化的队列，所有的处理器都需要使用这个数据结构，反复进入和退出临界区的代价非常高，缓存偏移问题也会更加突出，对于细粒度的goroutine来说，集中队列不太适合。

在工作队列的基础上做一些优化，拆分工作队列，为每个处理器构造一个双端队列和一个计算资源的抽象-线程。这样解决了临界区的效率损耗问题，但是还没有解决利用缓存局部性和处理器利用率。因为Go遵循fork-join的并发模型，如果从T1开始fork出的任务都放在P1中，那么什么时候使用P2执行？任务在工作队列之间移动的时候，上下文切换会出现问题吗？

因此分布式队列工作窃取算法遵循了一些基本原则：

1. 在fork点，将任务添加到与线程关联的双端队列的尾部
2. 如果线程空闲，则选取一个随机的线程，从它的双端队列头部窃取任务
3. 如果是在未准备好的join点，则将任务从双端队列的尾部出队
4. 如果线程的双端队列是空的，则：
   a. 暂停加入
   b. 从随机线程的双端队列中窃取工作

Goroutine调度器

以上的工作窃取策略已经接近了Goroutine的具体实现，但是还需要了解更多关于真正实现的细节和优化。

Goroutine调度器的实现不是一蹴而就的，从最初的G-M模型到G-P-M模型，从不支持抢占到支持协作式抢占，Goroutine调度器也经过了不断的优化。

G、P和M

• G：代表 Goroutine，存储了 Goroutine 的执行栈信息、Goroutine 状态以及 Goroutine 的任务函数等。
• P：代表逻辑 processor，P 的数量决定了系统内最大可并行的 G 的数量，拥有工作窃取中的工作队列。
• M：代表着真正的执行计算资源，也就是内核态线程。在绑定有效的 P 后，进入一个调度循环，而调度循环的机制大致是从 P 的本地运行队列以及全局队列中获取 G，切换到 G 的执行栈上并执行 G 的函数，调用 goexit 做清理工作并回到 M，如此反复。M 并不保留 G 状态，这是 G 可以跨 M 调度的基础。

在Go的运行时中，首先启动M，然后是P，最后是调度运行G。

G 抢占调度

Go 程序启动时，运行时会去启动一个名为 sysmon 的 M（监控线程），sysmon 每 20us~10ms 启动一次，完成以下工作：

• 释放闲置超过 5 分钟的 span 内存；
• 如果超过 2 分钟没有垃圾回收，强制执行；
• 将长时间未处理的 netpoll 结果添加到任务队列；
• 向长时间运行的 G 任务发出抢占调度；
• 收回因 syscall 长时间阻塞的 P；

如果如果一个 G 任务运行 10ms，sysmon 就会认为它的运行时间太久而发出抢占式调度的请求。一旦 G 的抢占标志位被设为 true，那么等到这个 G 下一次调用函数或方法时，运行时就可以将 G 抢占并移出运行状态，放入队列中，等待下一次被调度。

channel阻塞或网络IO情况下的调度

如果 G 被阻塞在某个 channel 操作或网络 I/O 操作上时，G 会被放置到等待队列中，M 会尝试运行 P 的下一个可运行的 G。如果这时 P 没有可运行的 G 供 M 运行，那么 M 将解绑 P，并进入挂起状态。

当 I/O 操作完成或 channel 操作完成，在等待队列中的 G 会被唤醒，标记为可运行（runnable），并被放入到某 P 的队列中，绑定一个 M 后继续执行。

系统调用阻塞情况下的调度。

如果一个 G 被阻塞在系统调用上，执行它的 M 也会进入挂起状态并解绑 P 。此时，如果有空闲线程，P 会绑定到它上，继续执行其他协程；如果没有，Go运行时将创建新 M。当系统调用结束，G会尝试重新获取P，如果无可用P，G标记为可运行，其 M 再次挂起。

引用

Katherine Cox-Buday. Go语言并发之道
Tony Bai. "并发：聊聊Goroutine调度器的原理".极客时间 小徐先生1212. "Golang GMP 原理". https://mp.weixin.qq.com/s/jIWe3nMP6yiuXeBQgmePDg