基本概念

进程:是操作系统的根本,所有代码都是在进程中执行的,进程是操作系统进行资源分配的最基本单位。

线程:是操作系统调度时的最基本单元。线程可以理解为进程中的控制流,一个进程至少包含一个线程,可以通过调用系统调用创建多个线程,拥有多个线程的进程可以并发执行多个任务,这样可以大大改善程序的响应时间和吞吐量。线程不可能独立于进程存在,它的声明周期不可能逾越所属进程的生命周期。

多个线程属于同一个进程并共享内存空间,所以他们之间不需要内存管理单元处理上下文调度,因此比较轻量级,线程间通信是基于共享的内存进行的。

虽然线程比较轻量级,但是在调度时也有比较大的额外开销,线程间切换时不止会消耗较多的内存,恢复寄存器中的内容还需要向操作系统申请或销毁对应的资源。

Go语言的调度器通过使用CPU数量相等的线程减少线程频繁切换的内存开销,同时在每个线程上执行额外开销更低的Goroutine来降低操作系统和硬件的负载。

不要通过共享内存来通信,而应该通过通信来共享内存。

设计原理

先看一下旧版本的Go语言调度器实现

  • 0.x 单线程调度器,只有一个活跃线程,由G-M模型组成
  • 1.0 多线程调度,全局锁导致竞争严重
  • 1.1 任务窃取调度。引入了P。构成了目前的G-M-P模型。在处理器P的基础上实现了基于工作窃取的调度器,在某些情况下goroutine不会让出线程,造成饥饿问题,时间过长的垃圾回收(STW)导致程序长时间无法工作
  • 1.2-至今,抢占式调度。
    • 1.2-1.13,基于协作的抢占式调度器。
    • 1.14-至今,基于信号的抢占式调度器。
  • 提案:非均匀存储访问调度器,对运行时的各种资源进行分区。

基于协作的抢占式调度原理

  • 编译器会在调度函数前插入runtime.morestack
  • Go语言运行时会在垃圾回收暂停程序、系统监控发现Goroutine运行超过10ms时发出抢占请求StackPreempt
  • 当发生函数调用时,可能会执行编译器插入的runtime.morestack函数,它调用的runtime.newstack会检查Goroutine的stackguard0字段是否为StackPreempt
  • 如果stackguard0StackPreempt,就会触发抢占让出当前线程。

因为这里的抢占是通过编译器插入函数实现的,还是需要函数调用作为入口才能触发抢占,所以这是一种协作式的抢占式调度。

基于信号的抢占式调度原理

目前的抢占式调度只会在垃圾回收扫描任务时触发。流程如下:

  • 程序启动时,在runtime.sighandler函数中注册SIGURG信号的处理函数runtime.doSigPreempt
  • 在触发垃圾回收的栈扫描时会调用runtime.suspendG挂起Goroutine,该函数会执行下面的逻辑:1.将_Grunning状态的Goroutine标记成可以被抢占,即将premmptStop设置为true;2.调用runtime.preemptM触发抢占
  • runtime.preemptM会调用runtime.signalM向线程发送信号SIGURG
  • 操作系统会终端正在运行的线程并执行预先注册的信号处理函数runtime.doSigPreempt
  • runtime.doSigPreempt函数会处理抢占信号,获取当前的SP和PC寄存器并调用runtime.sigctxt.pushCall
  • runtime.sigctxt.pushCall会修改寄存器并在程序回到用户态时执行runtime.asyncPreempt
  • 汇编指令runtime.asyncPreempt会调用函数runtime.asyncPreempt2
  • runtime.asyncPreempt2会调用runtime.preemptPark
  • runtime.preemptPar会修改当前Goroutine的状态到_Gpreempted并调用runtime.schedule让当前函数陷入休眠并让出线程。调度器会选择其它的Goroutine继续执行。

上面9个步骤展示了基于信号的抢占式调度的执行过程。STW和栈扫描是一个可以抢占的安全点(Safe-points)

非均匀内存访问调度器

非均匀内存访问调度现在还是go语言的提案,原理就是通过拆分全局资源,让各个处理器能够就近获取,减少锁竞争并增加数据的局部性。

总结

Go语言的调度器在最初几个版本迅速迭代,1.2之后没多大的变化,直到1.14引入了真正的基于信号的抢占式调度。解决了go语言的调度器在一些无法被抢占的边缘情况。例如for循环或者垃圾回收长时间占用线程。在未来,go语言的调度器还会进一步演进,增加触发抢占式调度的时间点来减少存在的边缘情况。

数据结构

Go的运行时管理着调度、垃圾回收、Goroutine的运行环境。

Go调度本质上是,操作系统运行线程M,线程运行你的代码G,Go的技巧是编译器会在Go运行时的一些地方插入系统调用(类似P的功能),通过channel发送值,调用runtime包等,这样go就可以通知调度器执行特定的操作。

go runtime scheduler Go运行时存在两种类型的queue,一个全局queue(schedt结构体中,很少用),一种是每个P都要维护自己的G的queue

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

当创建goroutine时(go func()方法),它会被放入当前P的queue中。

当M执行了一些G后,发现当前P的queue为空,则会随机选择一个P中取走一半G到自己队列中执行(偷)

当有goroutine执行阻塞的系统调用时(syscall),会被中断执行另外一个G,如下情况:

  • blocking syscall (for example open file)
  • network input
  • channel operrations
  • primitives in the sync package(同步操作原语)

G

G - 表示Goroutine,它是一个待执行的任务,需要绑定在M上才能运行;

type g struct {
	stack       stack
	stackguard0 uintptr
}

这个结构体字段主要用来跟踪Goroutine的栈(Stack)和状态。

M

M - 表示操作系统的线程,它由操作系统的调度器调度和管理。程序中的多个M并不会同时都处于执行状态,最多只有GOMAXPROCS个M在执行。

P

P - 表示处理器,通常P的数量等于CPU核数(GOMAXPROCS)。它可以被看做运行在线程上的本地调度器。早起版本是没有P的,调度需要G与M完成,这样每次创建、终止Goroutine或者调度时,需要一个全局锁来保护调度的相关对象(sched)。全局锁严重影响Goroutine的并发性能。 (Scalable Go Scheduler)

通过引入P,实现了一种叫做work-stealing的调度算法:

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

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

调度器的实现

schedule()与findrunnable()函数

Goroutine调度是在P中进行,每当runtime需要进行调度时,会调用schedule()函数,流程如下:

  • 调用runqget()从当前P的队列中取G(和schedule()中的调用相同);
  • 调用globrunqget()从全局队列中取可执行的G;
  • 调用netpoll()取异步调用结束的G,该次调用为非阻塞调用,直接返回;
  • 调用runqsteal()从其他P的队列中“偷”。

如果以上四步都没能获取成功,就继续执行一些低优先级的工作:

  • 如果处于垃圾回收标记阶段,就进行垃圾回收的标记工作;
  • 再次调用globrunqget()从全局队列中取可执行的G;
  • 再次调用netpoll()取异步调用结束的G,该次调用为阻塞调用。

如果还没有获得G,就停止当前M的执行,返回findrunnable()函数开头重新执行。 如果findrunnable()正常返回一个G,shedule()函数会调用execute()函数执行该G。 execute()函数会调用gogo()函数(在汇编源文件asm_XXX.s中定义,XXX代表系统架构),gogo() 函数会从G.sched结构中恢复出G上次被调度器暂停时的寄存器现场(SP、PC等),然后继续执行。

如何进行抢占式调用

runtime在程序启动时,会自动创建一个系统线程,运行sysmon()函数(在proc1.go中定义)。 sysmon()函数在整个程序生命周期中一直执行,负责监视各个Goroutine的状态、判断是否要进行垃圾回收等。

sysmon()会调用retake()函数,retake()函数会遍历所有的P,如果一个P处于执行状态, 且已经连续执行了较长时间,就会被抢占。retake()调用preemptone()将P的stackguard0设为stackPreempt(关于stackguard的详细内容,可以参考 Split Stacks),这将导致该P中正在执行的G进行下一次函数调用时, 导致栈空间检查失败。进而触发morestack()(汇编代码,位于asm_XXX.s中)然后进行一连串的函数调用,主要的调用过程如下:

morestack()(汇编代码)-> newstack() -> gopreempt_m() -> goschedImpl() -> schedule()

在goschedImpl()函数中,会通过调用dropg()将G与M解除绑定;再调用globrunqput()将G加入全局runnable队列中。最后调用schedule() 来为当前P设置新的可执行的G。

参考

GO调度器

Go Preemptive Scheduler Design Doc

Golang调度器源码分析

Go runtime scheduler

GO SCHEDULER: MS, PS & GS