Go 协程调度

Go 协程与并发

设计 Go 语言时所处的背景：

摩尔定律失效；
时钟频率提高使得 CPU 功耗和发热剧增，反过来制约了 CPU 的性能；
研究重点转向把多个执行内核放进一个处理器，让每个内核在较低的频率下工作来降低功耗、提高性能，处理器进入全新的多核时代（2007 年）。多核 CPU 带来了更强的并行处理能力、更高的计算密度和更低的时钟频率，并大大减少了散热和功耗。

Go 设计者顺应 CPU 向多核方向发展的这一趋势，将面向多核、原生内置并发支持作为语言的设计原则。

进程与线程

进程是应用程序的启动实例，每个进程都有独立的内存空间，不同进程通过进程间的通信方式来通信。

线程从属于进程，每个进程至少包含一个线程，线程是 CPU 调度的基本单位，多个线程之间可以共享进程的资源并通过共享内存等线程间的通信方式来通信。

线程可分为用户线程和内核线程，用户线程由用户创建、同步和销毁；内核线程由内核来管理。

传统编程语言（C、C++ 等）的并发实现实际上是基于操作系统调度，即程序负责创建线程（一般通过 pthread 等函数库调用实现），操作系统负责调度。

这种方式复杂且难于扩展。
每个线程占用的资源不小，操作系统调度切换线程的代价也不小。
对于很多网络服务程序，由于不能大量创建线程，就要在少量线程里做网络的多路复用。

频繁创建、销毁线程会造成不必要的开销，于是有了线程池技术：线程池中预先保存一定数量的 worker 线程（M），新任务不以创建新线程的方式去执行，而是将任务（G）发布到任务队列中，线程池中的线程不断地从任务队列中取出任务并执行。

若 worker 线程执行的 G 任务中发生系统调用，则操作系统会将该线程置为阻塞状态，意味着该线程在怠工，消费任务队列中的 worker 线程变少，所以线程池消费任务队列的能力变弱了。
- 如果任务队列中的大部分任务都进行系统调用，则会让这种状态恶化，大部分 worker 线程进入阻塞状态，会导致任务队列中的任务产生堆积。
- 增加线程池中的线程数量可以在一定程度上提高消费能力，但随着线程数量增多，过多线程争抢 CPU 资源，消费能力会有上限，甚至出现消费能力下降的现象。

int $0x80 解析：

int 指令称为软中断指令，可以用这条指令故意产生一个异常，异常的处理和中断类似，CPU 从用户模式切换到特权模式，然后跳转到内核代码中执行异常处理程序。
立即数 0x80 是一个参数，在异常处理程序中要根据这个参数决定如何处理。
在 Linux 内核中 int $0x80 这种异常称为系统调用（System Call），Linux 的各种系统调用都是由 int $0x80 指令引发的。
- 内核提供了很多系统服务供用户程序使用，这些系统服务不能像库函数（如 printf）那样调用，因为在执行用户程序时 CPU 处于用户模式，不能直接调用内核函数，所以需要通过系统调用切换 CPU 模式，经由异常处理程序进入内核；用户程序只能通过寄存器传几个参数，之后就要按内核设计好的代码路线走，而不能由用户程序随心所欲想调哪个内核函数就调哪个内核函数，这样可以保证系统服务被安全地调用。
- 调用结束之后，CPU 再切换回用户模式，继续执行 int $0x80 的下一条指令，在用户程序看来就像函数调用和返回一样。
eax 和 ebx 的值是传递给系统调用的两个参数。
- eax 的值是系统调用号，内核需要通过 eax 判断用户要调哪个系统调用；_exit 的系统调用号是 1。
  - 大多数系统调用完成之后会返回用户空间继续执行后面的指令，_exit 系统调用比较特殊，它会终止掉当前进程，而不是返回用户空间继续执行。
- ebx 的值是传给 _exit 的参数，表示退出状态。

goroutine

goroutine 是由 Go 运行时负责调度的用户层轻量级线程。

goroutine 相较于操作系统线程的优势：

轻量；

// $GOROOT/src/runtime/stack.go
// The minimum size of stack used by Go code
const (
	_StackMin = 2048 // 2kb
)

由 Go 运行时调度，而不是操作系统调度，上下文切换代价较小；
goroutine 由 go 关键字接函数或方法创建，函数或方法返回即表示 goroutine 退出，易用；
原生并发，内置 channel 作为 goroutine 间的通信原语。

多个协程分享操作系统分给线程的时间片，从而达到充分利用 CPU 算力的目的，协程调度器则决定了协程运行的顺序。

goroutine 调度器

协程调度器把可运行的协程逐个调度到线程中执行，同时及时把阻塞的协程调度出协程，从而有效地避免了线程的频繁切换，达到了使用少量线程实现高并发的效果。

根据用户线程管理方式的不同，分为 3 种线程模型：

N : 1：N 个用户线程运行在一个内核线程中，优点是用户线程上下文切换快，缺点是无法充分利用 CPU 多核的算力。
1 : 1：每个用户线程对应一个内核线程，优点是充分利用 CPU 算力，缺点是线程上下文切换慢。
M : N：M 个用户线程（协程）运行在 N 个内核线程，结合了以上两种模型的优点，缺点是调度算法较为复杂；Go 实现的就是这种模型。

GMP 模型：

G 对应 goroutine；
M 对应 machine，表示操作系统线程，由操作系统调度；
- M 的个数通常略大于 P。
  - 多出来的 M 会在 G 产生系统调用时发挥作用。
  - 除了运行 Go 代码，runtime 包还有其它内置任务要处理。
- M 必须持有 P 才可以执行代码，跟系统中其它线程一样，M 也会被系统调用阻塞。
P 对应 processor，表示逻辑处理器，包含运行 Go 代码的必要资源，也有调度 goroutine 的能力。
- P 个数在程序启动时确定，默认等于 CPU 核数，可以用环境变量 GOMAXPROCS 或在程序中使用 runtime.GOMAXPROCS() 方法指定 P 的个数。
- G 必须分配得到 P 才能运行；
- P 只有和 M 绑定才能让本地队列中的 G 真正运行起来；
  - Ps may have no Ms if they are blocked or in a system call.
- P 和 M 的关系是多对多；
- 每个 P 有一个 runqueues 队列，用于存放等待调度的 G；
- 此外还有一个全局的 runqueues 队列，由多个 P 共享。

// https://github.com/golang/go/blob/go1.12.7/src/runtime/runtime2.go#L339
type g struct {
	stack 	stack
	sched 	gobuf
	goid	int64
	gopc	uintptr
	startpc	uintptr
	// ...
}

Go 1.1 之前的的调度器实现中只包含全局 runqueues，多个 P 通过互斥锁来调度队列中的协程，在多 CPU 或多核环境中，多个 P 需要经常争抢锁来调度全局队列中的协程，严重影响并发效率。后来引入了局部的 runqueues，每个 P 访问自己的 runqueues 时无需加锁。

P 中的 G 额外再创建的协程通常会加入本地的 runqueues，如果本地的队列已满，则协程会被放入全局 runqueues。

基于队列轮转的调度策略：

P 依次将自己维护的协程队列中的 G 调度到 M 中执行。
P 会周期性查看全局队列中是否有 G 待运行并将其调度到 M 中执行，避免全局队列中的 G 因长时间得不到调度机会而饿死。
- 全局队列中的 G 主要来自于从系统调用中恢复的 G。
若某个 G 中出现死循环的代码逻辑，那么 G 将永久占用分配给它的 P 和 M，而位于同一个 P 中的其它 G 将得不到调度，出现饥饿问题。

Go 1.1 实现了 G-M-P 模型和 work stealing 算法：

通过 go 关键字创建的协程会优先放到当前协程对应的处理器的队列中，就会出现有些协程可能会不断地派生新的协程而有些协程则不派生协程的情况，所以多个 P 中维护的 G 队列有能不均衡。
- 当 P 的本地运行队列已经没有剩余空间时就会把本地队列中的一部分 goroutine 和待加入的 goroutine 通过 runtime.runqputslow 添加到调度器持有的全局运行队列上。
work stealing 的实现中当某个 P 没有协程需要调度时会查询全局队列，如果全局队列中也没有协程需要调度，则会随机选取一个正在运行的处理器 P 窃取协程，每次窃取一半。

Go 1.2 实现了基于协作的抢占式调度，原理是在每个函数的入口加上一段额外的代码，所有 goroutine 在函数调用时都有机会进入运行时检查是否需要执行抢占。

与操作系统按时间片调度线程不同，Go 中并没有时间片的概念，M 通过抢占式调度让 G 停下来并调度下一个可运行的 G。
Go 程序启动时，运行时会启动一个名为 sysmon 的 M，该 M 的特殊之处在于它无须绑定 P 即可运行。
- sysmon 每 20us~10ms 启动一次，主要完成如下工作：
  - 释放闲置超过 5 分钟的 span 物理内存；
  - 如果超过 2 分钟没有垃圾回收，强制执行；
  - 将长时间未处理的 netpoll 结果添加到任务队列；
  - 向长时间运行（超过 10ms）的 G 任务发出抢占调度；
    - 一旦 G 的抢占标志位被设为 true，此 G 下一次调用函数或方法时，运行时便可以进行抢占并将其移除运行状态，放入 P 的本地运行队列中（如果 P 的本地运行队列已满，则放在全局运行队列中），等待下一次被调度。
  - 收回因 syscall 长时间阻塞的 P。

// https://github.com/golang/go/blob/go1.12.7/src/runtime/proc.go#L110
func main() {
	// ...
	if GOARCH != "wasm" { // no threads on wasm yet, so no sysmon
		systemstack(func() {
			newm(sysmon, nil)
		})
	}
	// ...
}
// https://github.com/golang/go/blob/go1.12.7/src/runtime/proc.go#L4251
func sysmon() {
	// ...
	// If a heap span goes unused for 5 minutes after a garbage collection,
	// we hand it back to the operating system.
	scavengelimit := int64(5 * 60 * 1e9)
	// ...
	for {
		// ...
		// retake P's blocked in syscalls
		// and preempt long running G's
		if retake(now) != 0 {
			idle = 0
		} else {
			idle++
		}
	}
}
// https://github.com/golang/go/blob/go1.12.7/src/runtime/proc.go#L4376
// forcePreemptNS is the time slice given to a G before it is
// preempted.
const forcePreemptNS = 10 * 1000 * 1000 // 10ms
func retake(now int64) uint32 {
	// ...
	for i := 0; i < len(allp); i++ {
		// ...
		if s == _Psyscall {
			// ...
		} else if s == _Prunning {
			// Preempt G if it's running for too long.
			t := int64(_p_.schedtick)
			if int64(pd.schedtick) != t {
				pd.schedtick = uint32(t)
				pd.schedwhen = now
				continue
			}
			if pd.schedwhen+forcePreemptNS > now {
				continue
			}
			preemptone(_p_)
		}
	}
	// ...
}

这种基于协作的抢占调度的方案局部解决了饥饿问题，对于没有函数调用而是纯算法循环计算的 G，goroutine 调度器依然无法抢占。

// Go 1.14 之前以下程序会陷入无限循环
func main() {
	runtime.GOMAXPROCS(1)
	go func() {
		for {
			// 死循环
		}
	}()
	time.Sleep(time.Second) // 系统调用，让出执行权给上面的协程
	println("Done")
}

G 被阻塞在某个 channel 操作或网络 I/O 操作上：
- G 会被放置到某个等待队列中，M 会尝试运行 P 的下一个可运行的 G；
- 此时如果 P 没有可运行的 G 供 M 运行，M 将解绑 P 并进入挂起状态；
- 当 I/O 操作完成或 channel 操作完成，等待队列中的 G 会被唤醒，标记为 runnable 并被放入某个 P 的队列中，绑定一个 M 后继续执行。
如果 G 被阻塞在某个系统调用上：
- 线程执行系统调用时，可能会被阻塞；对应到协程调度器模型，若一个协程发起系统调用，对应的工作线程会被阻塞，工作线程所属的 P 的 runqueues 队列中的 G 得不到调度，相当于队列中的所有协程都被阻塞。
- 不仅 G 会阻塞，执行该 G 的 M 也会解绑 P（被 sysmon 抢走），M 与 G 一起进入阻塞状态。
- 判断是否有空闲的 M：
  1. 如果此时有空闲的 M，则 P 会与其绑定并继续执行其它 G；
  2. 如果没有空闲的 M，但仍然有其它 G 要执行，那么就会创建一个新 M（线程）。
  - 与线程池类似，Go 提供了一个 M 的池子，需要时从池子中取，用完放回池子。
  - 只要 P 不空闲，就可以充分利用 CPU。
- 当系统调用返回后，阻塞在该系统调用上的 G 会尝试获取一个可用的 P:
  1. 如果有可用 P，之前运行该 G 的 M 将绑定 P 继续运行 G；
  2. 如果没有可用的 P，那么 G 与 M 之间的关联将解除，同时 G 会被标记为 runnable，放入全局的运行队列中，等待调度器的再次调度，M 则进入缓存池睡眠。
M 阻塞到 Go 调度器检测到 M 被阻塞有一定延迟，即旧 M 被阻塞到新 M 得到运行之间有一定时间间隔。

Go 1.14 加入了基于系统信号的 goroutine 抢占式调度机制，解决了垃圾回收和栈扫描时存在的饥饿问题。

查看调度器状态：

# 每 1000ms 打印一次 goroutine 调度器状态
GODEBUG=schedtrace=1000 godoc -http=:6060
# SCHED 0ms: gomaxprocs=8 idleprocs=6 threads=4 spinningthreads=1 idlethreads=0 runqueue=0 [0 0 0 0 0 0 0 0]
# SCHED 1000ms: gomaxprocs=8 idleprocs=0 threads=28 spinningthreads=0 idlethreads=12 runqueue=8 [0 0 0 0 0 0 0 0]
# SCHED 2000ms: gomaxprocs=8 idleprocs=0 threads=31 spinningthreads=1 idlethreads=5 runqueue=0 [0 0 0 0 0 0 0 0]
# SCHED 3000ms: gomaxprocs=8 idleprocs=0 threads=31 spinningthreads=0 idlethreads=15 runqueue=8 [0 0 0 0 1 1 0 0]

SCHED：调试信息输出标志字符串，代表本行是调度器相关信息的输出；
1000ms：从程序启动到输出这行日志经过的时间；
gomaxprocs：P 的数量；
idleprocs：处于空闲状态的 P 的数量（gomaxprocs 和 idleprocs 的差值就是当前正在执行 Go 代码的 P 的数量）；
threads：操作系统线程的数量，包含调度器使用的 M 数量和运行时自用的类似 sysmon 这样的线程的数量；
spinningthreads：处于自旋状态的操作系统线程数量；
idlethread：处于空闲状态的操作系统线程的数量；
runqueue=8：Go 调度器全局运行队列中 G 的数量；
[0 0 0 0 1 1 0 0]：分别为 8 个 P 的本地运行队列中的 G 的数量。

References

https://book.douban.com/subject/35720728/

https://book.douban.com/subject/35144587/

G-M 模型的不足

Go Preemptive Scheduler Design

Go’s work-stealing scheduler

https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-goroutine/

Debugging Performance Issues in Go Programs

Contents

Go 协程与并发

进程与线程

goroutine

goroutine 调度器