Go调度源码浅析

前一篇文章大致介绍了Go语言调度的各个方面，这篇文章通过介绍源码来进一步了解调度的一些过程。源码是基于最新的Go 1.12。

Go的编译方式是静态编译，把runtime本身直接编译到了最终的可执行文件里。

入口是系统和平台架构对应的rt0_[OS]_[arch].s（runtime文件夹下），这是一段汇编代码，做一些初始化工作，例如初始化g，新建一个线程等，然后会调用runtime.rt0_go(runtime/asm_[arch].s中）。

runtime.rt0_go会继续检查cpu信息，设置好程序运行标志，tls（thread local storage）初始化等，设置g0与m0的相互引用，然后调用runtime.args、runtime.osinit(os_[arch].go)、runtime.schedinit(proc.go)，在runtime.schedinit会调用stackinit()， mallocinit()等初始化栈，内存分配器等等。接下来调用runtime.newproc(proc.go)创建新的goroutine用于执行runtime.main进而绑定用户写的main方法。runtime.mstart(proc.go)启动m0开始goroutine的调度（也就是执行main函数的线程就是m0？）。

// The bootstrap sequence is:
//
//  call osinit
//  call schedinit
//  make & queue new G
//  call runtime·mstart
//
// The new G calls runtime·main.
func schedinit() {
    // raceinit must be the first call to race detector.
    // In particular, it must be done before mallocinit below calls racemapshadow.
    _g_ := getg()
    if raceenabled {
        _g_.racectx, raceprocctx0 = raceinit()
    }

    sched.maxmcount = 10000

    tracebackinit()
    moduledataverify()
    stackinit()
    mallocinit()
    mcommoninit(_g_.m)
    cpuinit()       // must run before alginit
    alginit()       // maps must not be used before this call
    modulesinit()   // provides activeModules
    typelinksinit() // uses maps, activeModules
    itabsinit()     // uses activeModules

有些文章会提到m0和g0。上文提到的汇编中新建的第一个线程就是m0，它在全局变量中， 无需再heap上分配，是一个脱离go本身内存分配机制的存在。而m0中的g0也是全局变量，上面提到的runtime.rt0_go中设置了很多g0的各个成员变量。但同时每个之后创建的m也都有自己的g0，负责调度而不是执行用户程序里面的函数。

runtime.main

上文讲到创建的goroutine会执行runtime.main进而执行main.main从而开启用户写的程序部分的运行。

这个函数在proc.go中：

// The main goroutine.
func main() {
    g := getg()

    // Racectx of m0->g0 is used only as the parent of the main goroutine.
    // It must not be used for anything else.
    g.m.g0.racectx = 0

    // Max stack size is 1 GB on 64-bit, 250 MB on 32-bit.
    // Using decimal instead of binary GB and MB because
    // they look nicer in the stack overflow failure message.
    if sys.PtrSize == 8 {
        maxstacksize = 1000000000
    } else {
        maxstacksize = 250000000
    }

    // Allow newproc to start new Ms.
    mainStarted = true

这个函数会标记mainStarted从而表示newproc能创建新的M了，创建新的M来启动sysmon函数（gc相关，g抢占调度相关)，调用runtime_init，gcenable等，如果是作为c的类库编译，这时就退出了。作为go程序，就继续执行main.main函数，这就是用户自己定义的程序了。等用户写的程序执行完，如果发生了panic则等待panic处理，最后exit(0)退出。

runtime.newproc (G的创建)

runtime.newproc函数本身比较简单，传入两个参数，其中siz是funcval+额外参数的长度，fn是指向函数机器代码的指针。过程只是获取参数的起始地址和调用段返回地址的pc寄存器。然后通过systemstack调用newproc1来实现G的创建和入队。

func newproc(siz int32, fn *funcval) {
    argp := add(unsafe.Pointer(&fn), sys.PtrSize)
    gp := getg()
    pc := getcallerpc()
    systemstack(func() {
        newproc1(fn, (*uint8)(argp), siz, gp, pc)
    })
}

systemstack会切换当前的g到g0（每个m里专门用于调度的g），然后调用newproc1。

func newproc1(fn *funcval, argp *uint8, narg int32, callergp *g, callerpc uintptr) {
    _g_ := getg()

    if fn == nil {
        _g_.m.throwing = -1 // do not dump full stacks
        throw("go of nil func value")
    }
    _g_.m.locks++ // disable preemption because it can be holding p in a local var
    siz := narg
    siz = (siz + 7) &^ 7
        ...

runtime.newproc1做的事情大概包括：

• 获取当前的G（也就是G0），并使绑定的M不可抢占，获取M对应的P
• 获取（或新建）一个G：
  • 通过gfget从P的gfree链表里获取G
  • 获取不到则调用malg分配一个G，初始栈2K，设置G的状态为_Gdead，这样gc不会扫描这个G。然后把G放入全局的G队列里
• 参数和返回地址复制到G的栈上
• 设置G的调度信息（sched）
• 设置G的状态为_Grunnable
• 调用runqput把G放入队列等待运行：
  • 尝试把G放到P的runnext
  • 尝试把G放到P的runq（本地运行队列）
  • 如果P的runq满了则调用runqputslow把G放入全局队列sched中（本地队列的一半G放入，而不是一次放一个）
• 检查：如果无自旋的M但是有空闲的P，则唤醒或新建一个M。这本身跟创建G已经无关了，主要是保证有足够的M来运行G。
  • 唤醒或新建M通过wakeup函数
• 释放不可抢占状态

runtime.mstart （M对G的执行)

M调用的的函数。m0在初始化后调用，其他m在线程启动时调用。
函数在proc.go中，处理大致如下：

• 调用getg获取当前的G，会得到g0
• 如果g未分配栈空间，从系统栈空间分配
• 调用mstart1
  • 检查，g不是g0就报错
  • 调用save保存当前状态，以后每次调度从这个栈地址开始
  • 执行asminit，minit，设置当前线程可以接收的信号
  • 调用schedule函数，开始调度。
• schedule是调度的核心
  • 获取g，检查是否lock，是则报错
  • 如果m被某个g锁住（locked to a g），则等待那个g能执行
  • 如果是cgo，也报错
  • 然后才进入主要的循环：
    • 如果gc需要stw（stop the world），那么用stopm休眠当前的m
    • m的p指定了需要在安全点运行的函数，就运行它
    • 获取特定的几种g，一旦获取到，就跳过获取阶段了：
      • 有trace（参考go tool trace）相关的g，执行
      • gc标记阶段，有待运行的gc worker（也是一个g），执行
      • 每61次调度，从全局g队列中获取g。主要是为公平起见，防止全局g一直不执行
      • 从p本地获取，调用runqget
    • 没有获取到，则调用findrunnable获取
      • 检查gc的stw，安全点运行函数
      • 有finalizer相关的g，运行
      • 从q的本地队列中取， runqget
      • 从全局队列中取，globrunqget，需要锁
      • 用netpoll获取可运行的g（见下面netpoll相关说明），这一步非必须，可以跳过
      • 还是没获取到的话， 检查有没有其他p有g（查看npidle）；检查自旋的M和忙碌的P的数量（为啥代码里乘以2？），如果M多则当前M可以停了；设置当前M为自旋状态，然后随机从其他p偷一半g过来（work steal算法）
      • 上面的异常分支或者最终没有偷到g，都会导致m进入休眠（findrunnable的stop部分），休眠步骤是：
        • 如果在gc标记，看有没有gc worker，运行。有trace相关，也要处理
        • gc需要stw，或者p有安全运行点函数，重新跳到findrunnable的开始执行
        • 再次检查全局队列是否有G，有则获取并返回
        • 释放P，P的状态变为_Pidle。P被添加到空闲列表
        • 让M离开自旋状态，然后再次找所有P的本地队列，GC worker等，找到就跳到findrunnable顶部重新执行
        • 最终获取不到G，则休眠当前的M，调用的是stopm
        • 如果之后被唤醒，跳到findrunnable顶部重新执行
    • 继续执行则表示找到了带运行的G
    • 如果M在自旋，让M离开自旋状态，resetspinning
    • 如果找到的G要求回到指定的M运行（lockedm != 0，例如runtime.main）
      • 调用startlockedm把G和P交给那个M，自己进入休眠
      • 自己从休眠中醒过来的时候，跳到schedule的主循环头部，执行
    • 调用execute函数执行G（这块我写简单点，因为主要是G本身的设置）
      • 获取当前G，设置状态从Grunnable到Grunning
      • 增加对应的P中记录的调用次数（为了61倍数次的时候从全局队列取)
      • 对应g和m
      • 调用gogo（汇编）函数，这个函数根据g.sched中保存的状态恢复各个寄存器中的值并开始（对应g刚创建）或继续（对应g中断之后又执行）运行g。设置寄存器的状态，然后函数执行完返回的时候调用goexit（因为newproc1中设置了返回为goexit）。
      • goexit本身的调用链是：goexit（汇编）-> goexit1（proc.go）-> mcall（汇编）-> goexit0（proc.go）。而mcall会保存运行状态到g.sched，然后切换到g0，再调用goexit0。
      • goexit0会把G的状态从Grunning设置为Gdead，清理G的各个成员，解除M和G的关系并把G放到P的自由列表（GFree）中方便下次复用，最后调用schedule函数，让M继续运行其他待运行的G

M的小结

上面的过程，是最基本的创建G和创建M的过程。其中可以看到M的创建或唤醒主要包含在3个地方：

• runtime.newproc1的最后，入队G之后，如果无自旋转的M但有空闲的P，则唤醒或创建一个M（wakep)
• M获取到G，离开自旋状态的时候（在schedule中），如果当前无自旋的M但有空闲的P，就唤醒或创建一个M(wakep)
• M取不到待执行的G的时候，离开自旋状态准备休眠时（在findrunnable的stop部分），再次检查有没有可运行的G，有则重新进入findrunnable（从而再次进入自旋状态）
• channel唤醒G的时候，无自旋M有空闲P，则唤醒或创建M

wakep函数也位于proc.go中：

func wakep() {
    // be conservative about spinning threads
    if !atomic.Cas(&sched.nmspinning, 0, 1) {
        return
    }
    startm(nil, true)
}

• 原子交换nmspinning为1，保证多个线程执行wakep只有一个成功
• 调用startm：
  • 从空闲列表获取P，没有则结束
  • 从空闲列表获取M（mget），没有则调用newm创建。newm调用allocm创建M，会包含g0，然后调用newm1进而调用newosproc创建线程（天书般的代码）
  • 调用notewakeup唤醒线程

G的小结

上面说了G从创建，到退出的过程。然而实际执行的时候， 并不是这样“一帆风顺”的。有很多情况会导致G在执行过程中“中断”。下面会大致介绍这些情况，但并不具体展开（因为代码实在太多，每个都可以单独形成一篇文章了）。

抢占

每个M并不是执行一个G到完成再执行下一个，而是可能发生抢占。但是又不像操作系统的线程有时间片的概念。抢占由sysmon（runtime.main里面创建的）触发，调用的是retake函数，这里不再详细按代码说明，只说个大概：

• 对于每个P，如果P在系统调用Psyscall且超过一次sysmon循环，抢占这个P，解除M和P的关系（handoffp）
• 对于每个P，如果P在运行Prunning，且超过一次sysmon循环且G的运行时间超过了一定值，抢占这个P，设置g.stackguard0为stackPreempt。这个值会在G调用函数的时候触发morestack，然后经过一系列复杂的检查，再调用gopreempt_m完成抢占。

gopreempt_m调用goschedImpl：

• 设置G从Grunning到Grunnable
• 解绑G和M
• 把G放到全局队列
• 调用schedule函数，让M继续执行

抢占可以保证一个G不会长时间运行导致其他G饿死。前提是这个G要调用函数，因为抢占在调用函数的时候才能检测出来。

channel

channel收发时可能会“阻塞”，导致G从Grunning变成Gwaiting，并与M解绑，M继续调用schedule函数。

网络调用

为了效率，go的网络调用采用了异步方式epoll或kqueue等，当网络调用读写数据的时候，G也可能被“阻塞”，从而被调度。

补充说明

上面介绍代码的时候，提到了G，M，P使用中用到的很多属性，这些定义在runtime2.go中。

type g struct {
    // Stack parameters.
    // stack describes the actual stack memory: [stack.lo, stack.hi).
    // stackguard0 is the stack pointer compared in the Go stack growth prologue.
    // It is stack.lo+StackGuard normally, but can be StackPreempt to trigger a preemption.
    // stackguard1 is the stack pointer compared in the C stack growth prologue.
    // It is stack.lo+StackGuard on g0 and gsignal stacks.
    // It is ~0 on other goroutine stacks, to trigger a call to morestackc (and crash).
    stack       stack   // offset known to runtime/cgo
    stackguard0 uintptr // offset known to liblink
    stackguard1 uintptr // offset known to liblin
...
}

type m struct {
    g0      *g     // goroutine with scheduling stack
    morebuf gobuf  // gobuf arg to morestack
    divmod  uint32 // div/mod denominator for arm - known to liblin
...
}

type p struct {
    lock mutex

    id          int32
    status      uint32 // one of pidle/prunning/...
    link        puintpt
...
}

参考：

1. https://github.com/JerryZhou/golang-doc/blob/master/Golang-Internals/Part-6.Bootstrapping.and.Memory.Allocator.Initialization.md
2. https://studygolang.com/articles/11627
3. http://cbsheng.github.io/posts/%E6%8E%A2%E7%B4%A2goroutine%E7%9A%84%E5%88%9B%E5%BB%BA/
4. https://making.pusher.com/go-tool-trace/
5. https://tonybai.com/2017/06/23/an-intro-about-goroutine-scheduler/