终于到来的抢占式调度

就在2020年2月25日,我们都还因为新性冠状病毒疫情而远程办公的时候,Go语言发布了1.14版本。新版本的runtime实现了一个令人欣喜的特性,那就是实现了真正意义上的抢占式调度。Release Notes中是这样描述的:

Goroutines are now asynchronously preemptible. As a result, loops without function calls no longer potentially deadlock the scheduler or significantly delay garbage collection.

Goroutines现在可以被异步抢占了。结果就是,没有函数调用的循环不再会造成调度器死锁,或者造成垃圾回收显著延迟。

就像我在为什么一个for循环阻塞了所有协程中所展示的那样,1.13版本的runtime还没有实现真正的抢占式调度,我们可以用一个空的for循环阻止STW,进而阻塞GC。这个问题在新版本中不存在了,确实是个好消息。

好奇的同学可以用两个版本的Go分别编译一下之前的示例,做个实验。我也在得知这个特性后立刻进行了验证,程序确实不会再阻塞了。下面就来研究一下实现的原理,看看跟之前有什么不同。

📈 栈增长与协程调度

在深入研究新的抢占式调度机制之前,先回顾一下之前的Goroutines调度机制。之前提到过“让出CPU”这个概念,还提到了该调度机制依赖于编译器在函数头部插入的栈增长相关代码,但是并没有仔细梳理相关细节。这次就把编译器插入了什么样的代码,及其运作原理仔细地梳理一下。

还是以斐波那契函数为例来进行说明。实现一个函数,接受一个整型参数作为数列下标,返回斐波那契数列中对应元素的值。这只是为了研究栈增长,不考虑整型溢出等无关问题。首先来看一下基于循环的实现方式:

1
2
3
4
5
6
7
8
func fib(i int) int {
m, n := 1, 0
for i > 0 {
m, n = m+n, m
i--
}
return m
}

这个函数足够小,局部变量也很少,实际在amd64架构上m和n直接被放到寄存器里,所以对协程栈没什么消耗,因此编译器不会插入栈增长相关代码,函数最终还是老样子。接下来看一下递归版本:

1
2
3
4
5
6
func fibR(i int) int {
if i < 2 {
return 1
}
return fibR(i-1) + fibR(i-2)
}

递归函数即使没有局部变量,参数和返回值也会消耗栈空间,即使没有参数和返回值,保存在栈上的返回地址每次也会消耗一个uintptr,所以编译器会在函数头部插入栈增长相关代码。并不是所有人都喜欢读汇编代码,所以我用Go伪代码的形式展示,经过编译器修改后的函数如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func fibR(i int) int {
entry:
gp := getg()
if SP <= gp->stackguard0 {
goto morestack
}

if i < 2 {
return 1
}
return fibR(i-1) + fibR(i-2)

morestack:
runtime.morestack_noctxt()
goto entry
}

以上代码中的getg函数是一个inline function,是用来获取当前协程g结构指针的,是由编译器生成并且是平台相关的。对g结构不太清楚的话,可以Google一下Go语言的GPM模型。SP是Stack Pointer,表示当前的栈使用到了什么位置。stackguard0是专门用来和SP进行比较的栈空间下界,当协程栈的消耗达到或超过这个位置时就需要进行栈增长。

在runtime中定义了一系列跟栈相关的常量,这里摘抄部分源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Functions that need frames bigger than this use an extra
// instruction to do the stack split check, to avoid overflow
// in case SP - framesize wraps below zero.
// This value can be no bigger than the size of the unmapped
// space at zero.
_StackBig = 4096

// The stack guard is a pointer this many bytes above the
// bottom of the stack.
_StackGuard = 896*sys.StackGuardMultiplier + _StackSystem

// After a stack split check the SP is allowed to be this
// many bytes below the stack guard. This saves an instruction
// in the checking sequence for tiny frames.
_StackSmall = 128

// Goroutine preemption request.
// Stored into g->stackguard0 to cause split stack check failure.
// Must be greater than any real sp.
// 0xfffffade in hex.
stackPreempt = uintptrMask & -1314

实际上编译器插入的栈增长代码一共有3种,是根据函数的framesize来决定使用哪一种的,前面展示的伪代码只是其中的一种。接下来分别梳理这3种情况,因为差异仅在于函数头部的检测代码,所以只展示头部伪代码。

1)对于framesize不超过_StackSmall的函数,插入的代码如下:

1
2
3
4
5
gp := getg()
// 函数的framesize足够小,所以只要栈指针不超过stackguard0这个下界就可以
if SP <= gp->stackguard0 {
goto morestack
}

2)对于framesize大于_StackSmall同时不超过_StackBig的函数,插入的代码如下:

1
2
3
4
5
6
7
gp := getg()
// 因为framesize已经不是很小了,所以在比较的时候要考虑进来,相当于判断:
// SP - (framesize - _StackSmall) <= gp->stackguard0
// 即SP要先减去framesize超出_StackSmall的部分,再和stackguard0进行比较
if SP - framesize <= gp->stackguard0 - _StackSmall {
goto morestack
}

3)对于framesize超过_StackBig的函数,插入的代码如下:

1
2
3
4
5
6
7
8
9
10
gp := getg()
// 因为这里的指针都是无符号整型,后面的运算方式无法检测到preempt标识,所以要前置检测
if gp->stackguard0 == stackPreempt {
goto morestack
}
// 为了避免SP非常小的时候,无符号减法造成地址wraparound,在两侧都加上_StackGuard
// 本质上还是判断SP - (framesize - _StackSmall) <= gp->stackguard0
if SP - gp->stackguard0 + _StackGuard <= framesize + (_StackGuard - _StackSmall) {
goto morestack
}

出现在第3段代码中的stackPreempt就是和协程调度相关的标识,当runtime希望某个协程让出CPU时,就会把它的stackguard0赋值为stackPreempt。stackPreempt是一个非常大的值,真正的栈指针不可能指向这个位置,所以可以安全的用作特殊标识。

因为stackPreempt这个值足够大,所以第1、2这两段代码中的判断结果都会为true,进而跳转到morestack,morestack处的代码调用runtime.morestack_noctxt函数,该函数会直接跳转到runtime.morestack函数,后者会调用runtime.newstack。runtime.newstack函数实际负责栈增长工作,不过它在进行栈增长前会先判断stackguard0 == stackPreempt,结果为true的话,就不进行栈增长了,而是执行一次协程调度。

将这一系列简化成一个流程图:

这种依赖于编译器在函数头部插入检测代码的调度实现有很大的局限性,典型的问题就是没有任何函数调用的循环无法被打断。所以在1.14版runtime中,实现了真正的抢占式调度。

🚀 抢占式调度

要实现真正的抢占式调度,就要拥有系统中断那样打断执行中的线程的能力。1.14版runtime就实现了这种能力,在Unix系统上使用了signal机制,在Windows使用了系统提供的Thread相关Win32 API。

在具体的代码实现中,是由runtime.preemptM这个函数来执行抢占式调度的。函数原型如下所示:

1
2
// 参数mp指向要被抢占的线程对应的m结构
func preemptM(mp *m)

因为Unix和Windows系统的差异较大,preemptM在两个平台上的实现也有较多不同,下面分别进行讨论。

Unix系统上

在Unix系统上,preemptM会首先判断当前操作系统是否被支持,因为Go并没有实现所有Unix系统上的抢占式调度。如果系统不被支持,函数会直接返回,若被支持,则会进一步通过runtime.signalM函数向目标线程发送sigPreempt信号。signalM函数内部调用了依赖具体实现的系统调用,所以对应不同系统有不同的实现。函数原型如下:

1
func signalM(mp *m, sig int)

在Linux系统上,signalM被实现为通过tgkill向目标线程发送sig信号。如下所示:

1
2
3
4
// signalM sends a signal to mp.
func signalM(mp *m, sig int) {
tgkill(getpid(), int(mp.procid), sig)
}

截止到信号发送,整个过程走完了前一半,画一个很简单的流程图:

接下来,目标线程会被信号中断,转去执行runtime.sighandler,在sighandler函数中检测到sig == sigPreempt后,就会调用runtime.doSigPreempt函数,doSigPreempt会向当前被打断的协程的上下文中注入一个runtime.asyncPreempt函数调用。继续这部分的流程图:

处理完信号后sighandler返回,被中断的协程得到恢复,立刻执行被注入的asyncPreempt函数调用,该函数是用汇编语言实现的,它会将当前CPU寄存器保存到栈上,然后调用runtime.asyncPreempt2函数,asyncPreempt2会调用runtime中的调度逻辑,从而完成整个抢占式调度过程。

整个过程利用signal来中断目标线程,并通过sighandler注入函数调用,sighandler返回后,目标协程通过执行注入的函数从而被抢占,整体是一个异步过程。

Windows系统上

在Windows系统上,整个抢占逻辑都实现在preemptM函数内,而且并不是异步的,需要通过SuspendThread函数暂停目标线程来进行操作。所以preemptM除了要检查CPU架构是否被支持外,还要保证线程不能抢占自己。

主要流程如下:

  1. 通过DuplicateHandle复制一个目标线程的句柄以便后续操作;
  2. 通过SuspendThread函数暂停目标线程;
  3. 通过GetThreadContext函数拿到线程上下文;
  4. 对上下文进行修改,注入runtime.asyncPreempt函数调用;
  5. 通过SetThreadContext函数把修改过的线程上下文设置回去;
  6. 通过ResumeThread函数恢复线程运行;
  7. 通过CloseHandle函数关闭之前复制的句柄。

整个过程就结束了,简要流程图如下:

线程恢复运行后立刻执行被注入的asyncPreempt函数调用,这之后就与在Unix系统上就没什么差别了。

最后需要强调一下,虽然1.14版runtime实现了这种真正的抢占式调度,但是这并不是第一选择。执行一次这样的抢占所造成的开销,比基于stackPreempt来“让出CPU”要大很多。这种抢占式调度的出现,主要是解决了之前一直无法解决的一些问题,使整个调度机制更加完善。

关于Go1.14的抢占式调度就先分析到这里,如果有理解错误之处,望不吝指正。