基础知识

Go runtime manages scheduling, garbage collection, and the runtime environment for goroutines.

在 Go 语言中,每一个并发的执行单元叫做 goroutine,当一个程序启动的时候,其主函数即在一个单独的 goroutine 中运行,称为 main goroutine。新的 goroutine 使用 go 关键字进行创建。主函数返回时,所有的 goroutine 都会被直接打断,程序退出。

goroutine 比线程还轻量,goroutine 一般以很小的栈开始生命周期,一般只需要 2KB。一个 goroutine 和 OS 线程一样,会保存其活跃或者挂起的函数调用的本地变量,但是 goroutine 的栈大小并不是固定的,栈的大小会根据需要动态地伸缩,而且 goroutine 的栈最大值有 1GB,比传统的固定大小的线程栈大的多。

一个 Go 程序中可以创建成千上万个并发的 goroutine。决定何时哪个 goroutine 将获得资源开始执行、哪个 goroutine 应该停止执行让出资源、哪个 goroutine 应该被唤醒恢复执行等就是 runtime 的职责之一,具体说是 runtime 中 scheduler 的职责。

runtime 中的 scheduler 按照一定的算法把 goroutine 调度到 “CPU” 资源上运行。在操作系统层面,线程竞争的 “CPU” 资源是真实的物理 CPU,但是在 Go 程序是用户层程序,它本身是运行在一个或多个操作系统的线程上,所以 goroutine 要竞争的 “CPU” 资源就是操作系统的线程,所以 scheduler 的任务就是:将 goroutines 按照一定算法放到不同的操作系统线程中去执行。这种在语言层面自带调度器的,我们称之为原生支持并发

本质上,操作系统运行线程,线程运行你的代码。

这个调度器使用了一些技术手段,比如 m:n 调度,因为其会在 n 个 OS 线程上调度 m 个 goroutine。Go 的调度器和内核的调度是相似的,但是这个调度器只关注单独的 Go 程序中的 goroutine(按程序独立)。Go 调度器并不是用一个硬件定时器,而是被 Go 语言“建筑”本身进行调度的。例如当一个 goroutine 调用了 time.Sleep,或者被 channel 调用或者 mutex 操作阻塞时,调度器会使其进入休眠并开始执行另一个 goroutine,直到时机到了再去唤醒第一个 goroutine。因为这种调度方式不需要进入内核的上下文,所以重新调度一个 goroutine 比调度一个线程代价要低得多。

Go 调度器使用了 GOMAXPROCS 的变量来决定会使用多少个 OS 线程同时执行 Go 的代码,其默认值是运行机器上的 CPU 的核心数(自 Go 1.5),所以在一个有 8 个核心的机器上时,调度器一次会在 8 个 OS 线程上去调度GO代码。(GOMAXPROCS是前面说的m:n调度中的n)。在休眠中的或者在通信中被阻塞的 goroutine 是不需要一个对应的线程来做调度的。在I/O中或系统调用中或调用非Go语言函数时,是需要一个对应的操作系统线程的,但是 GOMAXPROCS 并不需要将这几种情况计算在内。

可以用 GOMAXPROCS的环境变量来显式地控制这个参数,或者也可以在运行时用runtime.GOMAXPROCS函数来修改它

$ GOMAXPROCS=2 go run main.go

历史演变

G-M 模型

2012年3月28日,Go 1.0 正式发布。在这个版本中,Go team实现了一个简单的调度器。在这个调度器中,

  • 每个 goroutine 对应于runtime中的一个抽象结构:G
  • 而os thread作为“物理CPU”的存在而被抽象为一个结构:M(machine)

这个结构虽然简单,但是却存在着许多问题。前Intel blackbelt工程师、现Google工程师 Dmitry Vyukov 在其《Scalable Go Scheduler Design》一文中指出了G-M模型的一个重要不足: 限制了Go并发程序的伸缩性,尤其是对那些有高吞吐或并行计算需求的服务程序。主要体现在如下几个方面:

  • 单一全局互斥锁(Sched.Lock)和集中状态存储的存在导致所有goroutine相关操作,比如:创建、重新调度等都要上锁;
  • goroutine传递问题:M经常在M之间传递”可运行”的goroutine,这导致调度延迟增大以及额外的性能损耗;
  • 每个M做内存缓存,导致内存占用过高,数据局部性较差;
  • 由于syscall调用而形成的剧烈的worker thread阻塞和解除阻塞,导致额外的性能损耗。

G-P-M 模型

计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决

于是 Dmitry Vyukov 亲自操刀改进 Go scheduler,在Go 1.1中实现了 G-P-M调度模型work stealing算法,这个模型一直沿用至今:

goroutine-scheduler-model
goroutine-scheduler-model

P是一个“逻辑Proccessor”,每个G要想真正运行起来,首先需要被分配一个P(进入到P的local runq中,这里暂忽略global runq那个环节)。对于G来说,P就是运行它的“CPU”,可以说:G的眼里只有P。但从Go scheduler视角来看,真正的“CPU”是M,只有将P和M绑定才能让P的runq中G得以真实运行起来。这样的P与M的关系,就好比Linux操作系统调度层面用户线程(user thread)与核心线程(kernel thread)的对应关系那样(N x M)。

抢占式调度

G-P-M 模型仍然有一个头疼的问题,那就是不支持抢占式调度,导致一旦某个 G 中出现死循环或永久循环的代码逻辑,那么G将永久占用分配给它的 P 和 M,位于同一个 P 中的其他 G 将得不到调度,出现“饿死”的情况。更为严重的是,当只有一个 P 时(GOMAXPROCS=1)时,整个Go程序中的其他 G 都将“饿死”。于是Dmitry Vyukov又提出了《Go Preemptive Scheduler Design》并在Go 1.2中实现了“抢占式”调度。

这个抢占式调度的原理则是在每个函数或方法的入口,加上一段额外的代码,让 runtime 有机会检查是否需要执行抢占调度。这种解决方案只能说局部解决了“饿死”问题,对于没有函数调用,纯算法循环计算的G,scheduler依然无法抢占。

其他优化

从Go 1.2以后,Go似乎将重点放在了对GC的低延迟的优化上了,对scheduler的优化和改进似乎不那么热心了,只是伴随着GC的改进而作了些小的改动。Dmitry Vyukov 在2014年9月提出了一个新的 proposal design doc:《NUMA‐aware scheduler for Go》,作为未来Go scheduler演进方向的一个提议,不过至今似乎这个proposal也没有列入开发计划。

Go runtime已经实现了 netpoller,这使得即便G发起网络I/O操作也不会导致M被阻塞(仅阻塞G),从而不会导致大量M被创建出来。但是对于regular file的I/O操作一旦阻塞,那么M将进入sleep状态,等待I/O返回后被唤醒;这种情况下P将与sleep的M分离,再选择一个idle的M。如果此时没有idle的M,则会新创建一个M,这就是为何大量I/O操作导致大量Thread被创建的原因。

Ian Lance Taylor在 Go 1.9 dev 周期中增加了一个Poller for os package的功能,这个功能可以像netpoller那样,在G操作支持pollable的fd时,仅阻塞G,而不阻塞M。不过该功能依然不能对regular file有效,regular file不是pollable的。不过,对于scheduler而言,这也算是一个进步了。

具体分析

简单说就是,runtime准备好G,P,M,然后 M 绑定 P ,M 从各种队列中获取 G,切换到 G 的执行栈上并执行 G 上的任务函数,调用 goexit 做清理工作并回到M,如此反复。

go-sched
go-sched

  • G(Goroutine): 表示 goroutine。
    • 存储了 goroutine 的执行stack信息、goroutine状态以及goroutine的任务函数等;另外G对象是可以重用的。
    • 在G的眼中只有 P,P 就是运行 G 的“CPU”。
    • 相当于两级线程
  • P(Processor): 表示逻辑 processor(约等于CPU)
    • 是线程 M 的执行的上下文,用来调度G和M之间的关联关系
    • 其数量可通过 GOMAXPROCS() 来设置,P的数量决定了系统内最大可并行的G的数量(前提:系统的物理cpu核数>=P的数量)
    • P的最大作用还是其拥有的各种 G 对象队列、链表、cache和状态。
  • M(Machine): M代表着真正的执行计算资源(对应系统的线程)
    • 数量对应是真的 CPU 数量,真正干活的对象,可以认为是系统线程
    • 在绑定有效的p后,进入schedule循环,而schedule循环的机制大致是从各种队列、p的本地队列中获取G,切换到G的执行栈上并执行G的函数,调用goexit做清理工作并回到m,如此反复。M并不保留G状态,这是G可以跨M调度的基础。

他们之间的关系是

  • G 需要绑定在 M 上才能运行;
  • M 需要绑定 P 才能运行;
  • 程序中的多个 M 并不会同时都处于执行状态,最多只有 GOMAXPROCS 个 M 在执行。

GOMAXPROCS 就是 go 中 runtime 包的一个函数。它设置了 P 的最多的个数。这也就直接导致了 M 最多的个数是多少,而 M 的个数就决定了各个 G 队列能同时被多少个 M 线程来进行调取执行。

Go runtime 存在两种类型的queue: 一种是一个全局的queue(在schedt结构体中,很少用到), 一种是每个P都维护自己的G的queue。

为了运行goroutine, M需要持有上下文P。M会从P的queue弹出一个goroutine并执行。

当你创建一个新的 goroutine 的时候(go func()方法),它会被放入P的queue。当然还有一个 work-stealing 调度算法,当M执行了一些G后,如果它的 queue 为空,它会随机的选择另外一个P,从它的queue中取走一半的G到自己的queue中执行。(偷!)

当你的 goroutine 执行阻塞的系统调用的时候(syscall),阻塞的系统调用会中断(intercepted),如果当前有一些G在执行, runtime 会把这个线程从P中摘除(detach),然后再创建一个新的操作系统的线程(如果没有空闲的线程可用的话)来服务于这个P。

当系统调用继续的时候,这个 goroutine 被放入到本地运行queue,线程会park它自己(休眠), 加入到空闲线程中。

如果一个 goroutine 执行网络调用,runtime 会做类似的动作。调用会被中断,但是由于Go使用集成的 network poller,它有自己的线程,所以还给它。

发生调度的时机

Go runtime 会在下面的 goroutine 被阻塞的情况下运行另外一个goroutine:

  • blocking syscall (for example opening a file),
  • network input,
  • channel operations,
  • primitives in the sync package.
  • runtime.Gosched()

work-stealing 调度算法

  • 每个P维护一个G队列;
  • 当一个 G 被创建出来,或者变为可执行状态时,就把他放到 P 的可执行队列中;
  • 当一个 G 执行结束时,P 会从队列中把该G取出;如果此时 P 的队列为空,即没有其他 G 可以执行, 就随机选择另外一个 P,从其可执行的 G 队列中偷取一半。

该算法避免了在 goroutine 调度时使用全局锁。

调试

Go可以跟踪运行时的调度器,这是通过 GODEBUG 环境变量实现的:

$ GODEBUG=schedtrace=1000 go run a.go
SCHED 0ms: gomaxprocs=4 idleprocs=3 threads=3 spinningthreads=0 idlethreads=0 runqueue=0 [0 0 0 0]

GODEBUG 这个 Go 运行时环境变量很是强大,通过给其传入不同的key1=value1,key2=value2… 组合,Go的runtime会输出不同的调试信息,比如在这里我们给GODEBUG传入了”schedtrace=1000″,其含义就是每1000ms,打印输出一次goroutine scheduler的状态,每次一行。

以下面为示例

SCHED 6016ms: gomaxprocs=4 idleprocs=0 threads=26 spinningthreads=0 idlethreads=20 runqueue=1 [3 4 0 10]
  • SCHED:调试信息输出标志字符串,代表本行是goroutine scheduler的输出;
  • 6016ms:即从程序启动到输出这行日志的时间;
  • gomaxprocs: P的数量;
  • idleprocs: 处于idle状态的P的数量;通过gomaxprocs和idleprocs的差值,我们就可知道执行go代码的P的数量;
  • threads: os threads的数量,包含scheduler使用的m数量,加上runtime自用的类似sysmon这样的thread的数量;
  • spinningthreads: 处于自旋状态的os thread数量;
  • idlethread: 处于idle状态的os thread的数量;
  • runqueue=1: go scheduler全局队列中G的数量;
  • [3 4 0 10]: 分别为4个P的local queue中的G的数量。

还可以输出更多关于 GPM 的信息

$ GODEBUG=scheddetail=1,schedtrace=1000 ./a
SCHED 0ms: gomaxprocs=4 idleprocs=2 threads=3 spinningthreads=1 idlethreads=0 runqueue=0 gcwaiting=0 nmidlelocked=0 stopwait=0 sysmonwait=0
  P0: status=1 schedtick=0 syscalltick=0 m=0 runqsize=0 gfreecnt=0
  P1: status=1 schedtick=0 syscalltick=0 m=2 runqsize=0 gfreecnt=0
  P2: status=0 schedtick=0 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  P3: status=0 schedtick=0 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  M2: p=1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=-1
  M1: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=-1
  M0: p=0 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=1
  G1: status=1() m=-1 lockedm=0
  G2: status=1() m=-1 lockedm=-1

关于go scheduler调试信息输出的详细信息,可以参考Dmitry Vyukov的大作:《Debugging performance issues in Go programs》。这也应该是必读的经典文章。当然更详尽的代码可参考 $GOROOT/src/runtime/proc.go 中的 schedtrace 函数。或者是查看 William Kennedy 的Scheduler Tracing In Go

参考链接