深度探索Go语言(六)：抢占式调度

幼麟实验室 2021-07-10

1388

就像操作系统要负责线程的调度一样，Go的runtime要负责goroutine的调度。现代操作系统调度线程都是抢占式的，我们不能依赖用户代码主动让出CPU，或者因为IO、锁等待而让出，这样会造成调度的不公平。基于经典的时间片算法，当线程的时间片用完之后，会被时钟中断给打断，调度器会将当前线程的执行上下文进行保存，然后恢复下一个线程的上下文，分配新的时间片令其开始执行。这种抢占对于线程本身是无感知的，系统底层支持，不需要开发人员特殊处理。

基于时间片的抢占式调度有个明显的优点，能够避免CPU资源持续被少数线程占用，从而使其他线程长时间处于饥饿状态。goroutine的调度器也用到了时间片算法，但是和操作系统的线程调度还是有些区别的，因为整个Go程序都是运行在用户态的，所以不能像操作系统那样利用时钟中断来打断运行中的goroutine。也得益于完全在用户态实现，goroutine的调度切换更加轻量。

那么runtime到底是如何抢占运行中的goroutine的？

为了避免过于枯燥乏味，先不直接解读源码，而是先做个实验。准备如下所示的代码：

package main
 
import "fmt"
 
func main() {
     gofunc(n int) {
             for{
                      n++
                      fmt.Println(n)
             }
     }(0)
     for{}
}

使用1.13版本的Go来build上述代码，build完成后运行得到的可执行文件。程序会如你所料的跑起来，飞快地打印出一行行递增的数字。不要着急，让程序多运行一会儿，用不了太长时间你就会发现程序突然停了，不再继续打印。在笔者测试的64位Linux上，最大数字没有超过500000，程序似乎就停住了。是真的停住了吗？如果用top命令查看，就会发现CPU占用达到100%还要稍微多一点。也就是说程序还在运行中，并且跑满了一个CPU核心。

为了弄清楚程序到底在做什么，我们使用调试delve查看一下当前所有的goroutine状态：

(dlv) grs
* Goroutine 1 - User:./main.go:12 main.main (0x48cf9e) (thread 17835)
 Goroutine 2 - User: root/go1.13/src/runtime/proc.go:305 runtime.gopark(0x42b4e0) [force gc (idle)]
 Goroutine 3 - User: /root/go1.13/src/runtime/proc.go:305 runtime.gopark(0x42b4e0) [GC sweep wait]
 Goroutine 4 - User: /root/go1.13/src/runtime/proc.go:305 runtime.gopark(0x42b4e0) [GC scavenge wait]
 Goroutine 5 - User: /root/go1.13/src/runtime/proc.go:305 runtime.gopark(0x42b4e0) [GC worker (idle)]
 Goroutine 6 - User: /root/go1.13/src/runtime/proc.go:305 runtime.gopark(0x42b4e0) [GC worker (idle)]
 Goroutine 17 - User: /root/go1.13/src/runtime/proc.go:305 runtime.gopark(0x42b4e0) [finalizer wait]
 Goroutine 18 - User: ./main.go:9 main.main.func1 (0x48cfe7) (thread17837)
[8 goroutines]

可以看到一共有8个goroutine，除了1号和18号是在执行用户代码外，其他都是GC相关的且都处于空闲或等待状态。1号goroutine正在执行main函数，main.go的第12行就是main函数最后那个空的for循环，说明它一直在这里循环，跑满一个CPU核心的应该就是它。18号goroutine执行的位置在func1中，对照源码行号来看就是协程中的那个fmt.Println函数。我们通过调试器切换到18号goroutine，然后查看它的调用栈：

(dlv) gr 18
Switched from 1 to 18 (thread 17837)
(dlv) bt
0 0x0000000000455553 in runtime.futex
  at /root/go1.13/src/runtime/sys_linux_amd64.s:536
1 0x0000000000451700 in runtime.systemstack_switch
  at /root/go1.13/src/runtime/asm_amd64.s:330
2 0x0000000000417457 in runtime.gcStart
  at /root/go1.13/src/runtime/mgc.go:1287
3 0x000000000040b026 in runtime.mallocgc
  at /root/go1.13/src/runtime/malloc.go:1115
4 0x0000000000408f8b in runtime.convT64
  at /root/go1.13/src/runtime/iface.go:352
5 0x000000000048cfe7 in main.main.func1
  at ./main.go:9
6 0x0000000000453651 in runtime.goexit
  at /root/go1.13/src/runtime/asm_amd64.s:1357

按照这个调用栈，结合我们看到的现象来进行分析：协程中要调用fmt.Println函数，该函数的参数类型是interface{}，所以要先调用runtime.convT64来把一个int64（amd64平台上的int本质上是int64）转化为interface{}类型。而convT64内部需要分配内存，经过多次循环之后达到了GC阈值，所以要先进行GC才能分配，所以mallocgc调用gcStart开始执行GC。后续的能够看出gcStart内部切换至了系统栈，然后发生了等待阻塞。

我们通过源码看一下mgc.go的1287行到底是在干什么：

systemstack(stopTheWorldWithSema)

原来是通过systemstack切换至系统栈，然后调用stopTheWorldWithSema，看来是要STW。但为什么会阻塞呢？这就要说说STW的实现原理了，第一小节中在解释schedt的gcwaiting字段时有过简单介绍，这里摘选了该函数的核心代码来看一下：

lock(&sched.lock)
sched.stopwait = gomaxprocs
atomic.Store(&sched.gcwaiting, 1)
preemptall()
 
_g_.m.p.ptr().status = _Pgcstop
sched.stopwait--
 
for _, p := range allp {
     s:= p.status
     ifs == _Psyscall && atomic.Cas(&p.status, s, _Pgcstop) {
             iftrace.enabled {
                      traceGoSysBlock(p)
                      traceProcStop(p)
             }
             p.syscalltick++
             sched.stopwait--
     }
}
 
for {
     p:= pidleget()
     ifp == nil {
             break
     }
     p.status= _Pgcstop
     sched.stopwait--
}
wait := sched.stopwait > 0
unlock(&sched.lock)
 
if wait {
     for{
             ifnotetsleep(&sched.stopnote, 100*1000) {
                      noteclear(&sched.stopnote)
                      break
             }
             preemptall()
     }
}

1. 根据gomaxprocs的值来设置stopwait，实际上就是P的个数。

2. 把gcwaiting置为1，并通过preemptall去抢占所有运行中的P。

preemptall会遍历allp这个切片，调用preemptone逐个抢占处于_Prunning状态的P。接下来把当前M持有的P置为_Pgcstop状态，并把stopwait减去1，表示当前P已经被抢占了。

3. 遍历allp，把所有处于_Psyscall状态的P置为_Pgcstop状态，并把stopwait减去对应的数量。

4. 再循环通过pidleget取得所有空闲的P，都置为_Pgcstop状态，从stopwait减去相应的数量。

5. 最后通过判断stopwait是否大于0，也就是是否还有没被抢占的P，来确定是否需要等待。如果需要等待，就以100微秒为超时时间，在sched.stopnote上等待，超时后再次通过preemptall抢占所有P。

因为preemptall不能保证一次就成功，所以需要循环。最后一个响应gcwaiting的工作线程在自我挂起之前，会通过stopnote唤醒当前线程，STW也就完成了。

实际用来执行抢占的preemptone的代码如下所示：

func preemptone(_p_ *p) bool {
     mp:= _p_.m.ptr()
     ifmp == nil || mp == getg().m {
             returnfalse
     }
     gp:= mp.curg
     ifgp == nil || gp == mp.g0 {
             returnfalse
     }
 
     gp.preempt= true
 
     gp.stackguard0= stackPreempt
     returntrue
}

第一个if判断是为了避开当前M，不能抢占自己。

第二个if是避开处于系统栈的M，不能打断调度器自身。

而所谓的抢占，就是把g的preempt字段设置成true，并把stackguard0这个栈增长检测的下界设置成stackPreempt。这样就能实现抢占了吗？

还记不记得之前反编译很多函数的时候，都会看到编译器安插在函数头部的栈增长代码？比如对于一个递归式的斐波那契函数：

func fibonacci(n int) int {
     ifn < 2 {
             return1
     }
     returnfibonacci(n-1) + fibonacci(n-2)
}

经过反编译之后，可以看到最终生成的汇编指令是这样的：

TEXT main.fibonacci(SB)/root/work/sched/main.go
func fibonacci(nint) int {
 0x4526e0     64488b0c25f8ffffff      MOVQFS:0xfffffff8, CX
 0x4526e9      483b6110                CMPQ 0x10(CX), SP
 0x4526ed      766e                    JBE 0x45275d
 0x4526ef      4883ec20                SUBQ $0x20, SP
 0x4526f3      48896c2418              MOVQ BP, 0x18(SP)
 0x4526f8      488d6c2418              LEAQ 0x18(SP), BP
       if n < 2 {
 0x4526fd      488b442428              MOVQ 0x28(SP), AX
 0x452702      4883f802                CMPQ $0x2, AX
 0x452706      7d13                    JGE 0x45271b
            return 1
 0x452708     48c744243001000000      MOVQ $0x1,0x30(SP)
 0x452711      488b6c2418              MOVQ 0x18(SP), BP
 0x452716      4883c420                ADDQ $0x20, SP
 0x45271a      c3                      RET
       return fibonacci(n-1) + fibonacci(n-2)
 0x45271b      488d48ff                LEAQ -0x1(AX), CX
 0x45271f      48890c24                MOVQ CX, 0(SP)
 0x452723      e8b8ffffff              CALL main.fibonacci(SB)
 0x452728      488b442408              MOVQ 0x8(SP), AX
 0x45272d      4889442410              MOVQ AX, 0x10(SP)
 0x452732      488b4c2428              MOVQ 0x28(SP), CX
 0x452737      4883c1fe                ADDQ $-0x2, CX
 0x45273b      48890c24                MOVQ CX, 0(SP)
 0x45273f      e89cffffff              CALL main.fibonacci(SB)
 0x452744      488b442410              MOVQ 0x10(SP), AX
 0x452749      4803442408              ADDQ 0x8(SP), AX
 0x45274e      4889442430              MOVQ AX, 0x30(SP)
 0x452753      488b6c2418              MOVQ 0x18(SP), BP
 0x452758      4883c420                ADDQ $0x20, SP
 0x45275c      c3                      RET
func fibonacci(n int) int {
 0x45275d      e85e7affff              CALL runtime.morestack_noctxt(SB)
 0x452762      e979ffffff              JMP main.fibonacci(SB)

还是转换成等价的Go风格的伪代码更容易理解，也更直观：

func fibonacci(n int) int {
entry:
     gp:= getg()
     ifSP <= gp.stackguard0 {
             gotomorestack
     }
     returnfibonacci(n-1) + fibonacci(n-2)
morestack:
     runtime.morestack_noctxt()
     gotoentry
}

实际上，编译器安插在函数开头的检测代码会有几种不同的形式，具体用哪种是根据函数栈帧的大小来定的。不管怎样检测，最终目的都是一样的，就是避免当前函数的栈帧超过已分配栈空间的下界，也就是通过提前分配空间来避免栈溢出。

执行抢占的时候，preemptone设置的那个stackPreempt是个常量，将其赋值给stackguard0之后，就会得到一个很大的无符号整数，在64位系统上是0xfffffffffffffade，在32位系统上是0xfffffade。实际的栈不可能位于这个地方，也就是说SP寄存器始终会小于这个值。因此，只要代码执行到这里，肯定就会去执行runtime.morestack_noctxt。而morestack_noctxt只是直接跳转到runtime.morestack，而后者又会调用runtime.newstack。newstack内部检测到如果stackguard0等于stackPreempt这个常量的话，就不会真正进行栈增长操作，而是去调用gopreempt_m，后者又会调用goschedImpl。最终goschedImpl会调用schedule，还记得schedule开头检测gcwaiting的if语句吗？工作线程就是在那些地方响应STW的，这就是通过栈增长检测代码实现goroutine抢占的原理。

现在就比较容易理解我们实验程序停住的原因了，执行fmt.Println的goroutine需要执行GC，进而发起了STW。而main函数中的空for循环因为没有调用任何函数，所以没有机会执行栈增长检测代码，也就不能被抢占。

综上所述，1.13之前的抢占依赖于goroutine检测到stackPreempt标识而自动让出，并不算是真正意义上的抢占。

数据库

文章转载自幼麟实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

深度探索Go语言(六)：抢占式调度

评论