Go 调度器

星期三, 4月 29, 2020 | 18分钟阅读 | 更新于 星期二, 3月 14, 2023

@

POSIX线程API(实现了这个api的库常被称作pthreads)在很大程度上可以看做是对现有Unix进程模型的逻辑延伸,线程和进程有很多相似处。线程有自己的信号掩码,可以分配与CPU关联,可以被放入cgroups,可以被查询使用了哪些资源。所有这些控制的特性都增加了开销,当你的程序中有10万个线程的时候,这些开销将会非常巨大。 另一个问题是,操作系统在Go模型下不能做出好的调度决策。举例来说,Go垃圾回收器在执行一次回收时,需要所有线程都停止,使得内存处于一致性状态。这导致需要等待所有运行着的线程到达某一个我们可以确定内存一致的时刻。当你有很多线程被调度运行时,你必须等待它们达到一致性状态。而Go调度器可以决策出只调度到它可以确认内存是一致的时刻即可。这意味着当我们停下来做垃圾回收时,我们只需要等待那些正在CPU上运行的活跃的线程。 Go GC的时候需要全局内存一致性,也即全局都停下来不操作内存,Go的调度器更容易做到这一点。比如所有空闲系统线程不用管,所有运行时的系统线程都在执行完当前协程后暂停。 Go语言在并发编程方面有强大的能力,通过协程(Goroutine)实现,由调度器来管理执行。与操作系统提供的线程相比,去掉无用特性,使用一个小的可伸缩的栈,更短的上下文切换,显得十分轻量。调度器通过使用与CPU数量相等的线程减少线程频繁切换的内存开销,同时在每一个线程上执行额外开销更低的Goroutine来降低操作系统和硬件的负载。

一、Go调度器

今天的Go语言调度器有着优异的性能,最初的调度器不仅实现非常简陋,也无法支撑高并发的服务,调度器经过几个大版本的迭代才有今天的优异性能,几个不同版本的调度器引入了不同的改进,也存在不同的缺陷。

  • 单线程调度器 0.x
  • 只包含40多行代码;
  • 程序中只能存在一个活跃线程,由G-M模型组成;
  • 多线程调度器 1.0
  • 允许运行多线程的程序;
  • 全局锁导致竞争严重;
  • 任务窃取调度器 1.1
  • 引入了处理器P,构成了目前的G-M-P模型;
  • 在处理器P的基础上实现了基于工作窃取的调度器;
  • 在某些情况下,Goroutine不会让出线程,进而造成饥饿问题;
  • 时间过长的垃圾回收(Stop-the-world,STW)会导致程序长时间无法工作;
  • 抢占式调度器 1.2~至今
  • 基于协作的抢占式调度器 1.2~1.13
  • 通过编译器在函数调用时插入抢占检查指令,在函数调用时检查当前Goroutine是否发起了抢占请求,实现基于协作的抢占式调度;
  • Goroutine可能会因为垃圾回收和循环长时间占用资源导致程序暂停;
  • 基于信号的抢占式调度器 1.14~至今
  • 实现基于信号的真抢占式调度;
  • 垃圾回收在扫描栈时会触发抢占调度;
  • 抢占的时间点不够多,还不能覆盖全部的边缘情况;
  • 非均匀存储访问调度器 提案
  • 对运行时的各种资源进行分区;
  • 实现非常复杂,到今天还没有提上日程

1、单线程调度器

0.x版本调度器只包含表示Goroutine的G和表示线程的M两种结构,全局也只有一个线程。在这时Go语言的调度器还是由C语言实现的,调度函数runtime.schedule也只包含40多行代码。该函数会遵循如下的过程调度Goroutine:

  • 获取调度器的全局锁;
  • 调用runtime.gosave保存栈寄存器和程序计数器;
  • 调用runtime.nextgandunlock获取下一个需要运行的Goroutine并解锁调度器;
  • 修改全局线程m上要执行的Goroutine;
  • 调用runtime.gogo函数运行最新的Goroutine; 显然这个单线程调度器的唯一优点就是能运行。

2、多线程调度器

Go语言在1.0版本正式发布时就支持了多线程的调度器,与上一个版本几乎不可用的调度器相比,Go语言团队在这一阶段实现了从不可用到可用的跨越。多线程版本的调度函数runtime.schedule包含70多行代码。整体的逻辑与单线程调度器没有太多区别,因为我们的程序中可能同时存在多个活跃线程,所以多线程调度器引入了GOMAXPROCS变量帮助我们灵活控制程序中的最大处理器数,即活跃线程数。多线程调度器的主要问题是调度时的锁竞争会严重浪费资源。该调度器有以下问题需要解决:

  • 调度器和锁是全局资源,所有的调度状态都是中心化存储的,锁竞争问严重;
  • 线程需要经常互相传递可运行的Goroutine,引入了大量的延迟;
  • 每个线程都需要处理内存缓存,导致大量的内存占用并影响数据局部性(Data locality);
  • 系统调用频繁阻塞和解除阻塞正在运行的线程,增加了额外开销;

3、任务窃取调度器

在现有多线程调度器基础上提出了两个改进的手段:

  • 在当前的G-M模型中引入了处理器P,增加中间层;
  • 在处理器P的基础上实现基于工作窃取的调度器;

使用了新的G-M-P模型,调度器的runtime.schedule函数在这个版本的调度器中反而更简单了:

static void schedule(void) {
    G *gp;
 top:
    if(runtime·gcwaiting) {
        gcstopm();
        goto top;
    }

    gp = runqget(m->p);
    if(gp == nil)
        gp = findrunnable();

    ...

    execute(gp);
}
  • 如果当前运行时在等待垃圾回收,调用runtime.gcstopm函数;
  • 调用runtime.runqget和runtime.findrunnable从本地或者全局的运行队列中获取待执行的Goroutine;
  • 调用runtime.execute函数在当前线程M上运行Goroutine; 当前处理器本地的运行队列中不包含Goroutine时,调用findrunnable函数会触发工作窃取,从其它的处理器的队列中随机获取一些Goroutine。运行时G-M-P模型中引入的处理器P是线程M和线程G的中间层。基于工作窃取的多线程调度器将每一个线程绑定到了独立的CPU上,这些线程会被不同处理器管理,不同的处理器通过工作窃取对任务进行再分配实现任务的平衡,也能提升调度器和Go语言程序的整体性能。

4、抢占式调度器

对Go语言并发模型的修改提升了调度器的性能,但是1.1版本中的调度器仍然不支持抢占式调度,程序只能依靠Goroutine主动让出CPU资源才能触发调度。Go语言的调度器在1.2版本中引入基于协作的抢占式调度解决下面的问题:

  • 某些Goroutine可以长时间占用线程,造成其它Goroutine的饥饿;
  • 垃圾回收需要暂停整个程序(Stop-the-world,STW),最长可能需要几分钟的时间6,导致整个程序无法工作; 1.2版本的抢占式调度虽然能够缓解这个问题,但是它实现的抢占式调度是基于协作的,在之后很长的一段时间里Go语言的调度器都有一些无法被抢占的边缘情况,例如:for循环或者垃圾回收长时间占用线程,这些问题中的一部分直到1.14才被基于信号的抢占式调度解决。

基于协作的抢占式调度: Go语言在分段栈的机制上实现抢占调度,利用编译器在分段栈上插入的函数,所有Goroutine在函数调用时都有机会进入运行时执行检查函数判断是否需要执行抢占。基于协作的抢占式调度的工作原理:

  • 编译器会在调用函数前插入runtime.morestack;
  • Go语言运行时会在垃圾回收暂停程序、系统监控发现Goroutine运行超过10ms时发出抢占请求StackPreempt;
  • 当发生函数调用时,可能会执行编译器插入的runtime.morestack函数,它调用的runtime.newstack会检查Goroutine的stackguard0字段是否为StackPreempt;
  • 如果stackguard0是StackPreempt,就会触发抢占让出当前线程; 这种实现方式虽然增加了运行时的复杂度,但是实现相对简单,也没有带来过多的额外开销,总体来看还是比较成功的实现。因为这里的抢占是通过编译器插入函数实现的,还是需要函数调用作为入口才能触发抢占,所以这是一种协作式的抢占式调度。

基于信号的抢占式调度: Go语言在1.14版本中实现了非协作的抢占式调度,在实现的过程中重构已有的逻辑并为Goroutine增加新的状态和字段来支持抢占。目前的抢占式调度也只会在垃圾回收扫描任务时触发,调度过程:

  • 程序启动时,在runtime.sighandler函数中注册SIGURG信号的处理函数runtime.doSigPreempt;
  • 在触发垃圾回收的栈扫描时会调用runtime.suspendG挂起Goroutine,该函数会执行下面的逻辑:
  • 将_Grunning状态的Goroutine标记成可以被抢占,即将preemptStop设置成true;
  • 调用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.preemptPark会修改当前Goroutine的状态到_Gpreempted并调用runtime.schedule让当前函数陷入休眠并让出线程,调度器会选择其它的Goroutine继续执行;

根据以下的四个原因选择SIGURG作为触发异步抢占的信号;

  • 该信号需要被调试器透传;
  • 该信号不会被内部的libc库使用并拦截;
  • 该信号可以随意出现并且不触发任何后果;
  • 需要处理多个平台上的不同信号;

STW和栈扫描是一个可以抢占的安全点(Safe-points),所以Go语言会在这里先加入抢占功能。

5、非均匀内存访问调度器

非均匀内存访问(Non-uniform memory access,NUMA)调度器现在只是Go语言的提案,因为该提案过于复杂,而目前的调度器的性能已经足够优异,所以我们暂时没有实现该提案。该提案的原理就是通过拆分全局资源,让各个处理器能够就近获取,减少锁竞争并增加数据的局部性。 在目前的运行时中,线程、处理器、网络轮询器、运行队列、全局内存分配器状态、内存分配缓存和垃圾收集器都是全局资源。运行时没有保证本地化,也不清楚系统的拓扑结构,部分结构可以提供一定的局部性,但是从全局来看没有这种保证。

二、GMP模型

运行时调度器有三个重要组成部分:

  • G:代表一个Goroutine对象,每次go调用的时候,都会创建一个G对象,它包括栈、指令指针以及对于调用goroutines很重要的其它信息,比如阻塞它的任何channel
  • M:表示一个操作系统的线程,由操作系统的调度器调度和管理;每次创建一个M的时候,都会有一个底层线程创建,所有的G任务,最终还是在M上执行
  • P:表示一个处理器,每一个运行的M都必须绑定一个P,就像线程必须在一个CPU核上执行一样,由P来调度G在M上的运行,P的个数是GOMAXPROCS。

1、G

G(Gorotuine)就是Go语言调度器中待执行的任务,它在运行时调度器中的地位与线程在操作系统中差不多,但是它占用了更小的内存空间,也降低了上下文切换的开销。Goroutine只存在于Go语言的运行时,它是Go语言在用户态提供的线程,作为一种粒度更细的资源调度单元,如果使用得当能够在高并发的场景下更高效地利用机器的CPU。Goroutine在运行时里使用私有结构体runtime.g表示。这个私有结构体非常复杂,总共包含40多个用于表示各种状态的成员变量,首先是与栈相关的两个字段:

type g struct {
	stack       stack
	stackguard0 uintptr
}

其中stack字段描述了当前Goroutine的栈内存范围[stack.lo, stack.hi),另一个字段stackguard0可以用于调度器抢占式调度。除了stackguard0之外,Goroutine中还包含另外三个与抢占密切相关的字段:

type g struct {
	preempt       bool // 抢占信号
	preemptStop   bool // 抢占时将状态修改成 `_Gpreempted`
	preemptShrink bool // 在同步安全点收缩栈
}

Goroutine与我们在前面章节提到的defer和panic也有千丝万缕的联系,每一个Goroutine上都持有两个分别存储defer和panic对应结构体的链表:

type g struct {
	_panic       *_panic // 最内侧的 panic 结构体
	_defer       *_defer // 最内侧的延迟函数结构体
}

结构体runtime.g的atomicstatus字段就存储了当前Goroutine的状态。除了几个已经不被使用的以及与GC相关的状态之外,Goroutine可能处于以下9个状态:

状态描述
_Gidle刚刚被分配并且还没有被初始化
_Grunnable没有执行代码,没有栈的所有权,存储在运行队列中
_Grunning可以执行代码,拥有栈的所有权,被赋予了内核线程 M 和处理器 P
_Gsyscall正在执行系统调用,拥有栈的所有权,没有执行用户代码,被赋予了内核线程 M 但是不在运行队列上
_Gwaiting由于运行时而被阻塞,没有执行用户代码并且不在运行队列上,但是可能存在于 Channel 的等待队列上
_Gdead没有被使用,没有执行代码,可能有分配的栈
_Gcopystack栈正在被拷贝,没有执行代码,不在运行队列上
_Gpreempted由于抢占而被阻塞,没有执行用户代码并且不在运行队列上,等待唤醒
_Gscan GC正在扫描栈空间,没有执行代码,可以与其他状态同时存在

虽然Goroutine在运行时中定义的状态及触发迁移的方法非常多而且复杂,但是我们可以将这些不同的状态聚合成最终的三种:等待中、可运行、运行中,在运行期间我们会在这三种不同的状态来回切换:

  • 等待中:Goroutine正在等待某些条件满足,例如:系统调用结束等,包括_Gwaiting、_Gsyscall和_Gpreempted几个状态;
  • 可运行:Goroutine已经准备就绪,可以在线程运行,如果当前程序中有非常多的Goroutine,每个Goroutine就可能会等待更多的时间,即_Grunnable;
  • 运行中:Goroutine正在某个线程上运行,即_Grunning;

2、M

Go语言并发模型中的M(Machine)是操作系统线程。调度器最多可以创建10000个线程,但是其中大多数的线程都不会执行用户代码(可能陷入系统调用),最多只会有GOMAXPROCS个活跃线程能够正常运行。在默认情况下,运行时会将GOMAXPROCS设置成当前机器的核数,我们也可以使用runtime.GOMAXPROCS来改变程序中最大的线程数。在大多数情况下,我们都会使用Go的默认设置,也就是线程数等于CPU个数,在这种情况下不会触发操作系统的线程调度和上下文切换,所有的调度都会发生在用户态,由Go语言调度器触发,能够减少非常多的额外开销。 操作系统线程在Go语言中会使用私有结构体runtime.m来表示,这个结构体中也包含了几十个私有的字段,与Goroutine直接相关的字段:

type m struct {
	g0   *g 
	curg *g
	...
}

其中g0是持有调度栈的Goroutine,curg是在当前线程上运行的用户Goroutine,这也是操作系统线程唯一关心的两个Goroutine。g0是一个运行时中比较特殊的Goroutine,它会深度参与运行时的调度过程,包括Goroutine的创建、大内存分配和 CGO函数的执行。runtime.m结构体中还存在着三个处理器字段,它们分别表示正在运行代码的处理器p、暂存的处理器nextp和执行系统调用之前的使用线程的处理器oldp:

type m struct {
	p             puintptr
	nextp         puintptr
	oldp          puintptr
}

3、P

调度器中的处理器P(Processor)是线程和Goroutine的中间层,它能提供线程需要的上下文环境,也会负责调度线程上的等待队列,通过处理器P的调度,每一个内核线程都能够执行多个Goroutine,它能在Goroutine进行一些I/O操作时及时切换,提高线程的利用率。因为调度器在启动时就会创建GOMAXPROCS个处理器,所以Go语言程序的处理器数量一定会等于GOMAXPROCS,这些处理器会绑定到不同的内核线程上并利用线程的计算资源运行Goroutine。runtime.p是处理器的运行时表示,作为调度器的内部实现,它包含的字段也非常多,其中包括与性能追踪、垃圾回收和计时器相关的字段,主要关注其中的线程和运行队列:

type p struct {
	m           muintptr

	runqhead uint32
	runqtail uint32
	runq     [256]guintptr
	runnext guintptr
	...
}

反向存储的线程维护着线程与处理器之间的关系,而runhead、runqtail和runq三个字段表示处理器持有的运行队列,其中存储着待执行的Goroutine列表,runnext中是线程下一个需要执行的Goroutine。 runtime.p结构体中的状态status字段会是以下五种中的一种:

状态描述
_Pidle处理器没有运行用户代码或者调度器,被空闲队列或者改变其状态的结构持有,运行队列为空
_Prunning被线程 M 持有,并且正在执行用户代码或者调度器
_Psyscall没有执行用户代码,当前线程陷入系统调用
_Pgcstop被线程 M 持有,当前处理器由于垃圾回收被停止
_Pdead当前处理器已经不被使用

通过分析处理器P的状态,我们能够对处理器的工作过程有一些简单理解,例如处理器在执行用户代码时会处于_Prunning状态,在当前线程执行I/O操作时会陷入_Psyscall状态。

三、调度

运行时有一个重要的全局变量sched,可以看做一个全局的调度者,数据类型是schedt。

type schedt struct {
    ...
    lock mutex

    midle        muintptr // idle状态的m
    nmidle       int32    // idle状态的m个数
    nmidlelocked int32    // lockde状态的m个数
    mcount       int32    // 创建的m的总数
    maxmcount    int32    // m允许的最大个数

    ngsys uint32 // 系统中goroutine的数目,会自动更新

    // 全局的可运行的g队列
    runqhead guintptr
    runqtail guintptr
    runqsize int32

    // dead的G的全局缓存
    gflock       mutex
    gfreeStack   *g
    gfreeNoStack *g
    ngfree       int32
    ...
}

大多数需要的信息都已放在了结构体M、G和P中,schedt结构体只是一个壳。可以看到,其中有M的idle队列,P的idle队列,以及一个全局的就绪的G队列。schedt结构体中的Lock是非常必须的,如果M或P等做一些非局部的操作,它们一般需要先锁住调度器。

1、调度器启动

运行时通过runtime.schedinit函数初始化调度器:

func schedinit() {
	_g_ := getg()
	...

	sched.maxmcount = 10000

	...
	sched.lastpoll = uint64(nanotime())
	procs := ncpu
	if n, ok := atoi32(gogetenv("GOMAXPROCS")); ok && n > 0 {
		procs = n
	}
	if procresize(procs) != nil {
		throw("unknown runnable goroutine during bootstrap")
	}
}

在调度器初始函数执行的过程中会将maxmcount设置成10000,这也就是一个Go语言程序能够创建的最大线程数,虽然最多可以创建10000个线程,但是可以同时运行的线程还是由GOMAXPROCS变量控制。启动完成之后,等待用户创建运行新的Goroutine并为Goroutine调度处理器资源。

2、创建Goroutine

想要启动一个新的Goroutine来执行任务时,需要使用Go语言中的go关键字。编译器会将其转换成runtime.newproc函数,该函数会接收大小和表示函数的指针funcval。在这个函数中会获取Goroutine以及调用方的程序计数器,然后调用runtime.newproc1函数:

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

runtime.newproc1会根据传入参数初始化一个g,该函数分成以下几个步骤:

  • 获取或者创建新的Goroutine结构体;
  • 将传入的参数移到Goroutine的栈上;
  • 更新Goroutine调度相关的属性;
  • 将Goroutine加入处理器的运行队列; Go语言中有两个运行队列,其中一个是处理器本地的运行队列,另一个是调度器持有的全局运行队列,只有在本地运行队列没有剩余空间时才会使用全局队列。

3、调度循环

调度器启动之后,会调用runtime.schedule进入调度循环:

func schedule() {
	_g_ := getg()

top:
	var gp *g
	var inheritTime bool

	if gp == nil {
		if _g_.m.p.ptr().schedtick%61 == 0 && sched.runqsize > 0 {
			lock(&sched.lock)
			gp = globrunqget(_g_.m.p.ptr(), 1)
			unlock(&sched.lock)
		}
	}
	if gp == nil {
		gp, inheritTime = runqget(_g_.m.p.ptr())
	}
	if gp == nil {
		gp, inheritTime = findrunnable()
	}

	execute(gp, inheritTime)
}

runtime.schedule函数的会从不同地方查找待执行的Goroutine:

  • 为了保证公平,当全局运行队列中有待执行的Goroutine时,通过schedtick保证有一定几率会从全局的运行队列中查找对应的Goroutine;
  • 从处理器本地的运行队列中查找待执行的Goroutine;
  • 如果前两种方法都没有找到Goroutine,就会通过runtime.findrunnable进行阻塞地查找Goroutine; runtime.findrunnable通过以下的过程获取可运行的Goroutine,且一定会返回一个可执行的 Goroutine,如果当前不存在就会阻塞等待。
  • 从本地运行队列、全局运行队列中查找;
  • 从网络轮询器中查找是否有Goroutine等待运行;
  • 通过runtime.runqsteal函数尝试从其他随机的处理器中窃取待运行的 Goroutine,在该过程中还可能窃取处理器中的计时器; 接下来由runtime.execute函数执行获取的Goroutine,做好准备工作后,它会通过runtime.gogo将Goroutine调度到当前线程上执行。
func execute(gp *g, inheritTime bool) {
	_g_ := getg()

	_g_.m.curg = gp
	gp.m = _g_.m
	casgstatus(gp, _Grunnable, _Grunning)
	gp.waitsince = 0
	gp.preempt = false
	gp.stackguard0 = gp.stack.lo + _StackGuard
	if !inheritTime {
		_g_.m.p.ptr().schedtick++
	}

	gogo(&gp.sched)
}

最后会调用runtime.goexit0函数,该函数会将Goroutine转换会_Gdead状态、清理其中的字段、移除Goroutine和线程的关联并调用runtime.gfput重新加入处理器的Goroutine空闲列表gFree。

func goexit0(gp *g) {
	_g_ := getg()

	casgstatus(gp, _Grunning, _Gdead)
	gp.m = nil
	...
	gp.param = nil
	gp.labels = nil
	gp.timer = nil

	dropg()
	gfput(_g_.m.p.ptr(), gp)
	schedule()
}

在最后runtime.goexit0函数会重新调用runtime.schedule触发新的Goroutine调度,我们可以认为调度循环永远都不会返回。 golang-scheduler-loop.png Go语言中的运行时调度循环会从runtime.schedule函数开始,最终又回到runtime.schedule;上述介绍的是Goroutine正常执行并退出的逻辑,实际情况会复杂得多,多数情况下Goroutine的执行的过程中都会经历协作式或者抢占式调度,这时会让出线程的使用权等待调度器的唤醒。

© 2026 我的博客

🌱 Powered by Hugo with theme Dream.

关于这个博客

关于博客

记录软件开发过程的一些知识和技巧,提升自我

关于博主

除了才华一无所有~~ 薪尽自然凉~~ 强迫症患者~~ 热爱古风~~