信马由缰操作系统-闲聊 Golang 协程

本篇主要介绍 Go 的 GM 与 GMP 模型相关内容。

1 GM 模型

在12年的go1.1版本之前用的都是GM模型。

1.1 Go1 的调度源码

下面是 Go 1 版本中暂停一个 Goroutine 并寻找下一个可运行 Goroutine 的关键调度过程。

static void  
schedule(G *gp)  
{  
    int32 hz;  
    uint32 v;  
  
    schedlock();  
    if(gp != nil) {  
       // Just finished running gp.  
       gp->m = nil;  
       runtime·sched.grunning--;  
  
       // atomic { mcpu-- }  
       v = runtime·xadd(&runtime·sched.atomic, -1<<mcpuShift);  
       if(atomic_mcpu(v) > maxgomaxprocs)  
          runtime·throw("negative mcpu in scheduler");  
  
       switch(gp->status){  
       case Grunnable:  
       case Gdead:  
          // Shouldn't have been running!  
          runtime·throw("bad gp->status in sched");  
       case Grunning:  
          gp->status = Grunnable;  
          gput(gp);  
          break;  
       case Gmoribund:  
          gp->status = Gdead;  
          if(gp->lockedm) {  
             gp->lockedm = nil;  
             m->lockedg = nil;  
          }  
          gp->idlem = nil;  
          unwindstack(gp, nil);  
          gfput(gp);  
          if(--runtime·sched.gcount == 0)  
             runtime·exit(0);  
          break;  
       }  
       if(gp->readyonstop){  
          gp->readyonstop = 0;  
          readylocked(gp);  
       }  
    }
    // ... 
  
    // Find (or wait for) g to run.  Unlocks runtime·sched.  
    gp = nextgandunlock();  
    gp->readyonstop = 0;  
    gp->status = Grunning;  
    m->curg = gp;  
    gp->m = m;  
  
    // Check whether the profiler needs to be turned on or off.  
    hz = runtime·sched.profilehz;  
    if(m->profilehz != hz)  
       runtime·resetcpuprofiler(hz);  
  
    if(gp->sched.pc == (byte*)runtime·goexit) {    // kickoff  
       runtime·gogocall(&gp->sched, (void(*)(void))gp->entry);  
    }  
    runtime·gogo(&gp->sched, 0);  
}

通过源码可知，对于一个正在运行的 Goroutine ：

1. 首先通过 schedlock(); 方法全局加锁，这个锁很多地方会用到，比如涉及垃圾回收时调用 runtime·stoptheworld 暂停程序及相关调度的工作，即gc中常说的STW。
2. 通过gp->m = nil;解绑 m，结束当前运行的 Goroutine。
3. 获得锁后，将该 Goroutine 的运行状态由 Running （正在运行）状态改成 Runnable （可运行）状态。
4. 使用gput 保存当前 Goroutine 的堆栈等信息
5. 调用nextgandunlock() 寻找或等待下一个可用 Goroutine，并通过schedunlock(); 释放全局锁给其他调度使用。
6. 将新 Goroutine 的状态改为 Running 状态
7. 通过 m->curg = gp; 和 gp->m = m;将新 Goroutine 与 M 绑定
8. 最后调用runtime·gogo 运行新 Goroutine

1.2 浅谈GM模型

我们再结合相关图片来说一下GM模型。首先明确几个概念：

1. KSE ：Kernel Scheduling Entity 调度的实体，即轻量级进程，也就是线程。
2. G : Goroutine ，一个协程，即通过执行 go func() 创建个 struct ，即 runtime 中的一个抽象结构 G （struct runtime.g），每个 Goroutine 都有自己的栈空间、定时器等。初始化的栈空间在2k左右，随着需求等增长而增长。
3. M ： Machine，工作线程，相当于抽象化的内核线程，记录内核线程信息，有自己的线程栈。每个工作线程对应 runtime 中的一个抽象结构 M （ struct runtime.m） 。
   1. 当执行 Goroutine 时，该M线程栈指向该 Goroutine 的线程栈即M.stack->G.stack，M的寄存器指向G提供的函数，然后去执行。
   2. 如果不为此工作线程分配内存，则由操作系统自主提供（操作系统不同提供的大小也不同）。

在该模型中：

1. 每当有一个 Goroutine 执行时，都有一个 M 与一个 KSE 绑定后执行 Goroutine。
2. Go 中维护着一个 Goroutine 全局队列，M 从该全局队列中获取可运行的 Goroutine 并执行，该过程需要加锁schedlock()。
3. 当运行的 Goroutine 因为调度等原因需要 M 放回全局队列的过程也需要加锁schedlock()。
4. 当运行的 Goroutine 调用了一个阻塞的系统调用时，运行这个 Goroutine 的工作线程也会被阻塞。
5. 一个线程 M 被阻塞应该创建/唤醒另一个线程来运行其他未被阻塞的 Goroutine 。这里线程可以创建不止一个，但活跃线程（即活跃 M ）的最大值存储在 MAXGOPROCS 中。

1.3 GM模型的缺点

在 2012 年时 Dmitry Vyukov 发表了文章《Scalable Go Scheduler Design Doc》，提到这样的设计在高并发下会带来以下问题：

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.

翻译总结来说，问题如下：

1. 单一全局互斥锁（mutex，Sched.Lock）和集中状态管理 ：M 每次从全局队列中捞取 G 都需要加锁，导致 goroutine 所有操作（如创建、结束、重新调度等）都需要重新加锁。
2. Goroutine 传递问题 ：工作线程 M 之间经常交换 可运行的 Goroutine ，导致调度延迟增大以及额外的性能损耗。刚创建的 G 被放进全局队列中，而不是由当前 M 直接运行，从而产生不必要的开销和延迟。
3. Per-M 持有内存缓存(（M.mcache） ：
   1. 每个 M 都持有mcache和stackalloc，但只有运行 G 的代码时才需要内存（每个mcache可高达2mb）。
   2. 在 M 处于系统调用 syscall 时并不需要，但运行 G 代码 和 阻塞在 syscall 的 M 的比例高达1：100，造成很大的资源浪费。
   3. 这种方式的内存亲缘性也很差，因为 G 在 M 中运行会对当前M的内存进行预热，但现在 G 调度到同一个 M 的概率不高，导致预热的内存复用率不高，所以数据局部性不好。
4. 频繁地线程阻塞/解阻塞 ：系统调度下，工作线程 M 经常被阻塞和取消阻塞，从而增加了很多开销。比如当 M 找不到 G 时，就会进入频繁阻塞/唤醒进行的检查逻辑，以便及时发现新的 G 来执行。

2 GMP 模型

2.1 基础

为了解决 GM 的上述问题，Dmitry Vyukov 在 Go 1.1 中引入了一个结构 P ( Processor )。P 是一个抽象概念，代表调度器，但不是真正的物理CPU，它既是 M 所需的上下文环境，也是用户级代码逻辑的处理器。

至此，我们再看下这阶段的三者关系：

1. G ：Goroutine ，一个协程，与之前无变化。
2. M ：Machine，工作线程。这里的 M 不再有自己的线程栈，这些资源分割给了 P。 M 绑定有效 P 后，才能调度/执行 G。 M的数量有限制，默认数量限制是 10000，可以通过 debug.SetMaxThreads()方法进行设置，如果有 M 空闲，那么就会回收或者睡眠。
3. P ：Processor，调度器，也称虚拟处理器。
   1. 管理着 M 执行 G 所需的资源和上下文，即 mcache/stackalloc 从 M 移到了P。当 P 中有 G 需要执行，将创建或者唤醒一个 M 来执行，所以 P 与 M 绑定才构成一个执行单元。
   2. 在保留 G 全局队列的情况下，每个P中有一个本地的G队列 local queue ，简称 LRQ，对应的全局可运行 G 队列简称 GRQ。
      1. 因为 P 的存在，runtime 不再需要做一个集中式的 Groutine 调度。
      2. 为了降低全局锁的影响，每个 M 都会在 P 的本地队列、全局队列或者其他 P 的本地队列中寻找 G 执行。这也是 GMP Work-stealing （工作窃取）算法的核心。
      3. 为了避免加锁，P 的本地队列是一个 Lock-Free 的队列，窃取 G 时基于 CAS 原子操作来完成。
   3. P 决定了并行任务的数量，，可通过runtime.GOMAXPROCS 来设定。
      1. Go 1.5 之后 GOMAXPROCS 被默认设置为可用核数，即 CPU 核心数，之前默认为 1 。
      2. Docker 中以前读取到的是物理机的 CPU核心数（涉及 /proc 文件系统的问题，可考虑基于 lxcfs 等方案解决，具体情况后续容器部分再详细讨论），导致创建的 P 的数量过多。 P 多了，创建的线程就会变多，从而上下文切换过多，上下文切换又会浪费 CPU。在网络 I/O 密集或者 CPU 密集的情况下，Docker 可能通过 Cgroup 限制 CPU ，从而可能触 CFS 的一些节流 （ throttle ），最终影响延迟（ Latency ）。
   4. Goroutine 会被设置到处理器 P 的 runnext 作为处理器下一个执行的任务。

Go1.21 中基于 CAS 原子操作从P 的本地队列获取可运行 G 的源码如下：

// Get g from local runnable queue.
// If inheritTime is true, gp should inherit the remaining time in the
// current time slice. Otherwise, it should start a new time slice.
// Executed only by the owner P.
func runqget(pp *p) (gp *g, inheritTime bool) {
	// If there's a runnext, it's the next G to run.
	next := pp.runnext
	// If the runnext is non-0 and the CAS fails, it could only have been stolen by another P,
	// because other Ps can race to set runnext to 0, but only the current P can set it to non-0.
	// Hence, there's no need to retry this CAS if it fails.
	if next != 0 && pp.runnext.cas(next, 0) {
		return next.ptr(), true
	}

	for {
		h := atomic.LoadAcq(&pp.runqhead) // load-acquire, synchronize with other consumers
		t := pp.runqtail
		if t == h {
			return nil, false
		}
		gp := pp.runq[h%uint32(len(pp.runq))].ptr()
		if atomic.CasRel(&pp.runqhead, h, h+1) { // cas-release, commits consume
			return gp, false
		}
	}
}

2.2 工作窃取

GMP 模型同时引入了 GMP Work-stealing （工作窃取）算法用来解决关于 G 的调度问题。正常情况下逻辑如下：

1. 当一个 P 执行完自己本地队列 LRQ 中所有 G 并且全局队列（本小节中全局队列均默认说的是 GRQ） 为空时，会尝试中另一个 P 的本地队列的尾部窃取一半的 G 。
2. 反之若全局队列 GRQ 不为空，则从 GRQ 中获取 （GRQ中的当前总数/GOMAXPROCS）个 G 。

关于 P 的选择，为了保证公平性，从随机位置上的 P 开始，选一个小于 GOMAXPROCS 且和它互为质数的步长，从而保证遍历的顺序也随机化了。

关于从全局队列中获取 G ，如果只在窃取失败时才去获取是不够的，很容易导致全局队列饥饿。为解决该问题， P 的调度算法还是会在每 N 轮调度之后去 GRQ 中取一个 G。在Go1.18及之前 先判断schedtick从全局队列获取，再从本地获取获取，最后执行findrunnable 获取，从1.19 开始全部集中在了findrunnable 中 获取G，我们这里以 Go 1.21 的 findrunnable 源码来讲解 ：

1. 如果 P 的本地队列一直有任务 G ，相当于全局队列中的 G 没人管了，所以通过 schedtick 保证有一定概率（ 1/61 ）去全局的运行队列中查找 G ，即每调度61次就会拿一个过来。
2. 如果获取失败，先通过 runqget从 P 的本地队列获取可用的 G 。
3. 如果本地队列没有，则通过 globrunqget 从全局队列中获取可用的 G 。
4. 如果以上都没有，则从网络轮询器 netpoll(0) 中查找是否有 Goroutine 等待运行。
5. 最后通过在stealWork 中调用 runqsteal 尝试从其他随机的处理器 P 中窃取一半待运行的 Goroutine 。

2.3 G 所处的位置

1. 进程都会有一个全局可运行 G 队列 GRQ 。
   1. 新建 G 时，P 的本地队列已满（256），就会将当前队列的一部分 G 以及待加入的 G 通过 runqputslow 一起放入该调度器持有的全局可运行队列。
   2. 阻塞的系统调用返回时，如果找不到空闲的 P ，也会被放入全局可运行队列中。
2. 每个 P 拥有一个自己的本地可执行队列 LRQ 。
3. 有一些 G 不在可运行队列中
   1. 处于 channel 阻塞态的 G 被放在阻塞队列 sudog 。
   2. 为了复用，结束后进入 P 的全局自由G列表 gFree 中 G 。
   3. 因为系统调用等原因脱离了 P，但绑定在 M 上的 G 。

2.4 Syscall 系统调度相关

1. 调用系统调用后，P 与 M 解绑，M 与 G 进入阻塞，P 此时的状态就是syscall，这时的 P 是不能被调度给别的 M 的。
2. 如果短时间内阻塞的 M 被唤醒，M 会优先重新获取这个 P，能或得到则继续绑定回去，从而保证之前的上下文等资源继续使用，有利于数据局部性。

调度中的系统监视器(system monitor)称为 sysmon ，负责定时扫描。

1. 在执行 syscall 时，如果某个 P 的 G 执行时间超过一个 sysmon tick（10ms）,就会把它设置为idle，将 P 重新调度给需要的 M，强制解绑。而此时可能会有其它 M 正在寻找可用的 P ，从而将该 P 与其绑定。
2. P 与 M 脱离后进入 idle list （即全局空闲P列表，pidle）中等待被绑定。syscall 结束后 M 按如下规则执行，直到满足条件为止。
   1. 尝试获取同一个 P ，恢复执行 G
   2. 尝试获取 idle list 中的另一个空闲的 P ，恢复执行 G
   3. 找不到空闲的 P ，将 G 放回全局可运行 G 队列，M 放回 M 的 idle list 中。与 P 相对应， M 也有 M 的全局空闲队列。

有些地方说当执行 syscall 时，Go 无法限制 Blocked OS Thread 数量，所以使用syscall写程序要认真考虑 pthread exhaust 问题，因为可能创建大量线程都阻塞，最终导致爆掉。说无法限制应该是由于 GOMAXPROCS 控制的是 P 的数量，无法限制与 P 脱离的 M 的数量。目前一个Go 进程中的 M 的数量是可以控制的，默认数量限制是 10000，可以通过 debug.SetMaxThreads()方法进行设置。当然创建大量线程导致阻塞的问题还是需要注意的。

2.5 Spining Thread 线程自旋

线程自旋是相对线程阻塞而言的，表象是循环执行一个指定逻辑，在这里指的是调度逻辑，目的是不停的寻找 G。这样做的问题是如果 G 迟迟不来，CPU 会白白浪费在这无意义的计算上。对应的好处是降低了 M 上下文切换成本，提高了性能。可以在两个地方引入：

1. M 不带 P 的，找 P 挂载，一有 P 释放就与之结合。
2. M 带 P 的，找 G 运行，一有可运行的 G 就立即执行。

为了避免浪费 CPU，自旋 M 最多允许 GOMAXPROCS 个（即与 P 数量相同）。当有类型1的自旋 M 存在时，类型2的 M 就不阻塞，阻塞就会释放 P ，一旦释放 P 就会立即被类型1的 M 获取并绑定，这是没必要的。

在新 G 被创建、M 进入系统调用、M 从空闲被激活这三种状态变化前，调度器会通过创建或唤醒一个 M 确保至少有一个自旋 M 存在，除非没有空闲 P 。

1. 当新 G 被创建，如果有可用的 P，就意味着 G 可以被立即执行，即使不在同一个 P 也无防。所以此时保留一个自旋的 M 就可以保证新 G 被很快的运行。这种情况下应该不存在类型1的自旋，只有类型2的自旋。
2. 当 M 进入系统调用，意味着 M 不知道什么时候能醒来，那么 M 对应的 P 中剩下的 G 就需要有一个新的 M 来执行，所以保留一个自旋 M 来执行剩下的 G。此时应该不存在类型2的自旋，只有类型1的自旋。
3. 如果 M 从空闲被激活变成活跃，意味着一个自旋 M 进入工作状态了，这时要检查并确保有一个自旋 M 的存在，以防还有 G 或者 P 空闲着。

2.6 GMP解决问题的方式小结

最后，针对开始时提出的 GM 模型中的问题，总结一下 GMP 模型给出了解决方案：

1. 单一全局互斥锁（mutex，Sched.Lock）和集中状态管理 ：全局队列依旧使用全局锁，但通过引入 P 及 P 的本地G队列，明显减少使用场景。而且 P 的本地队列使用无锁队列，基于 CAS 原子操作来面对可能的并发场景。
2. Goroutine 传递问题 ：除非遇上 P 本地队列已满或者其他的P做工作窃取，一般情况下 G 创建后就放在当前 P 的队列中，尽量避免 G 的传递问题。执行系统调用后 M 会优先获取之前的 P 并恢复 G 执行。这些都保证了良好的数据局部性。
3. Per-M 持有内存缓存(（M.mcache） ：mcache 这些资源由 M 转移到了 P 中，M 不再持有。同时 P 最多可以创建 GOMAXPROCS 个，远小于 M 的数量，内存消耗大幅减少。
4. 频繁地线程阻塞/解阻塞 ：引入线程自旋，时刻保证有自旋的 M 可用，避免在等待可用的 P 和 G 时频繁阻塞和取消阻塞。

3 参考资料

这里仅列出文章中未实时标注的参考资料。

1. 《云原生训练营-极客时间》
2. 《Go 进阶训练营-极客时间》