golang scheduler

Go调度器

我们知道Go里面有成千上万coroutine需要调度执行,而这里面起关键作用的就是Go的调度器,那么Go的调度器在哪里呢?因为我们写Go代码的时候从未显式创建过调度器实例。为了了解调度器,我们先来了解下Go的运行时(Runtime)。

为什么要有Runtime

开销上

我们知道操作系统是可以调度线程的,那么我们可不可以直接让操作系统调用go的线程呢。
POSIX线程(POSIX是线程标准,定义了创建和操纵线程的一套API)通常是在已有的进程模型中增加的逻辑扩展,所以线程控制和进程控制很相似。线程也有自己的信号掩码(signal mask), 线程也可以设置CPU亲和性(CPU affinity),也可以放进cgroups中进行资源管理。假如goroutines(go的执行单元)对应线程的话,使用这些特性对线程进行控制管理就增加了开销,因为go程序运行goroutines(go的执行单元)不需要这些特性。这类消耗在goroutine达到比如10,0000个的时候就会很大。所以go需要有个运行时在调度goroutines而不是只是让操作系统调度线程。

垃圾回收上

go包含垃圾回收(GC)的特性,在垃圾回收的时候所有goroutines必须处于暂停的状态,这样go的内存才会处于一种一致的状态. 所以我们必须等待所有线程处于内存一致的状态才能进行垃圾回收。

在没有调度器的时候,线程调度是随操作系统的意的,你不得不试图去等待所有的已经暂停和还没暂停的线程,而且不知道等多久(如果线程进入了阻塞状态比如sleep中是无法立即响应signal的)。

在有调度器的时候,调度器可以决定只在内存一致的时候才发起调度(即只要有活跃的线程就不执行新的任务),因此当需要执行gc的时候,调度器便决定只在内存一致的时候才发起调度,所以所有线程都无法再次活跃,调度器只需要等待当前活跃的线程暂停即可。后面还会讲到调度器还想办法避免一个活跃的线程长时间不停下来。

需要调度器自然就需要运行调度器的运行时。

基于这两个原因, golang需要一个运行时(Runtime).

或者简单的讲,要想做协程线程调度就要有运行时。要想做垃圾回收就要有运行时。

什么是Runtime

上面可以分析出Runtime所担任的职责:goroutines调度,垃圾回收,当然还提供goroutines执行的环境。

所以这也相当于简要解释了什么是Runtime。

go的可执行程序可以分成两个层:用户代码和运行时,运行时提供接口函数供用户代码调用,用来管理goroutines,channels和其他一些内置抽象结构。用户代码对操作系统API的任何调用都会被运行时层截取,以方便调度和垃圾回收。分层如如些:

runtime layer

图片来自 Analysis of the Go runtime scheduler

初代调度器

Go的调度程序是Go运行时的一个更重要的方面。运行时会跟踪每个Goroutine,并将安排它们在线程池中运行。goroutines与线程分离(解耦不强绑定),但运行于线程之上。如何有效地将goroutine调度到线程上对于go程序的高性能至关重要。

Goroutines的背后逻辑是:它们能够同时运行,与线程类似,但相比之下非常轻量。因此,程序运行时,Goroutines的个数应该是远大于线程的个数的。

同时多线程在程序中是很有必要的,因为当goroutine调用了一个阻塞的系统调用,比如sleep,那么运行这个goroutine的线程就会被阻塞,那么这时运行时至少应该再创建一个线程来运行别的没有阻塞的goroutine。线程这里可以创建不止一个,可以按需不断地创建,而活跃的线程(处于非阻塞状态的线程)的最大个数存储在变量GOMAXPROCS中。

go运行时使用3个结构来跟踪所有成员来支持调度器的工作。

G:

一个G代表一个goroutine,包含当前栈,当前状态和函数体。

1
2
3
4
5
6
7
8
9
10
11
12
struct G
{
byte∗ stackguard; // stack guard information
byte∗ stackbase; // base of stack
byte∗ stack0; // current stack pointer
byte∗ entry; // initial function
void∗ param; // passed parameter on wakeup
int16 status; // status
int32 goid; // unique id
M∗ lockedm; // used for locking M’s and G’s
...
}

M:

一个M代表一个线程,包含全局G队列,当前G,内存等。

1
2
3
4
5
6
7
8
9
10
11
struct M
{
G∗ curg; // current running goroutine
int32 id; // unique id
int32 locks ; // locks held by this M
MCache ∗mcache; // cache for this thread
G∗ lockedg; // used for locking M’s and G’s
uintptr createstack [32]; // Stack that created this thread
M∗ nextwaitm; // next M waiting for lock
...
};

SCHED:

SCHED是全局单例,用来跟踪G队列和M队列,和维护其他一些信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Sched {
Lock; // global sched lock .
// must be held to edit G or M queues
G ∗gfree; // available g’ s ( status == Gdead)
G ∗ghead; // g’ s waiting to run queue
G ∗gtail; // tail of g’ s waiting to run queue
int32 gwait; // number of g’s waiting to run
int32 gcount; // number of g’s that are alive
int32 grunning; // number of g’s running on cpu
// or in syscall
M ∗mhead; // m’s waiting for work
int32 mwait; // number of m’s waiting for work
int32 mcount; // number of m’s that have been created
...
};

运行时刚启动时会启动一些G,其中一个负责垃圾回收,其中一个负责调度,其中一个负责用户的入口函数。一开始运行时只有一个M被创建,随后,用户层面的更多G被创建,然后更多的M被创建出来执行更多的G。同时最多同时支持GOMAXPROCS个活跃的线程。

M代表一个线程,M需要从全局G队列中取出一个G并且执行G对应的代码,如果G代码执行阻塞的系统调用,那么会首先从空闲的M队列中取出一个M唤醒,随后执行阻塞调用,陷入阻塞。这么做是因为线程阻塞后,活跃的线程数肯定就小于GOMAXPROCS了,这时我们就可以增加一个活跃的线程以防止当前有G在等在M。

造成阻塞的都是系统调用,在调用返回之前,线程会一直阻塞。但是注意,M不会在channel的操作中阻塞,这是因为操作系统并不知道channel,channel的所有的操作都是有运行时来处理的。所以如果goroutine执行了channel操作,这时goroutine可能会需要阻塞,但是这个阻塞不是操作系统带来的阻塞,因此M并不需要一起阻塞。这种场景下,这个G会被标记为waiting,然后原来执行这个G的M会继续去执行别的G。waiting的G在channel操作完成后会设为runable状态,并把自己放回到原来那个q的队列下,等待空闲的M来执行,不一定是先前那个M了。为了完成g的唤醒,waitting的这个g必然会在wating前先找个地方某个字段某个数组保存。

初代的问题

初代的调度器相对简单,所以也存在一定的问题,当然初代调度器的目的不是要马上做到成熟,只是在有限的时间内做出一个还可以的版本。

Dmitry Vyukov(新调度器的作者)写的一个论文列举了老调度器存在的问题:

以下来自Scalable Go Scheduler Design Doc

第一个问题是全局锁,无论是修改M还是G的队列还是其他SCHED结构的相关字段,都需要获取这个全局锁,当遇到高吞吐高并发的程序的时候,这个设计会导致调度器的性能问题。

第二个是当前有很多M之间传递G的情况,比如新建的G会被被放到全局队列,而不是在M本地执行,这导致了不必要的开销和延迟,应该优先在创建G的M上执行就可以了。

第三个问题是每一个M现在都持有一个内存,包括了阻塞状态的M也是持有的。Active状态的M跟总的M个数之比可以达到1:100。这就导致了过多的内存消耗,以及较差的数据局部性。数据局部性怎么理解呢?数据局部性这里是指G当前在M运行后对M的内存进行了预热,后面如果再次调度到同一个M那么可以加速访问,可想而知,因为现在G调度到同一个M的概率不高,所以数据局部性不好。

第四个是M持续的阻塞和唤醒带来的开销。比如M找不到G(目的是一有runable的G就执行),此时M就会进入频繁阻塞/唤醒来进行检查的逻辑,以便及时发现新的G来执行。

新调度器

调度器细节

Dmitry Vyukov的方案是引入一个结构P,用来模拟处理器,M依旧表示操作系统线程,G依旧表示一个goroutine。

GOMAXPROCS用来控制P的个数,同时P作为M执行G代码时的必需资源。

新的P结构会带走原来的M和SCHED结构中的一些属性,比如MCache从M移到了P,而G队列也被分成两类,SCHED结构保留全局G队列,同时每个P中都会有一个本地的G队列。

m-p-g

图片来自go-scheduler

P的本地队列可以解决旧调度器中单一全局锁的问题。注意P的本地G队列还是可能面临一个并发访问的场景,比如下面讲到的窃取算法。为了避免加锁,这里P的本地队列是一个LockFree的队列,窃取G时使用CAS原子操作来完成。关于LockFree和CAS的知识参见Lock-Free

而P的MCache也就意味着不必为每一个M都配备一块内存,避免了过多的内存消耗。

当一个新的G被创建的时候,G被放到当前M所关联的P的本地队列结尾,这样G虽然不是立即执行,但最终会得到执行。

当P执行系统调用即将阻塞时,M会释放P,并进入阻塞,直到系统调用返回时,M会尝试获取空闲的P,有的话继续执行,没有就把G会放到全局G,而M会进入空闲的M队列。

由于每个P都有G队列,那么当一个P的G队列执行完了的时候,另一个P却可能堆积了很多G,所以新的调度器有个G的调度算法,一般都叫做窃取算法(stealing algorithm)。

当一个P执行完本地所有的G之后,会尝试随机挑选一个受害者P,从它的G队列中窃取一半的G。当尝试若干次窃取都失败之后,会从全局G队列中获取G。那么一次从全局队列取多少个呢,取 [当前个数/GOMAXPROCS]个(忽略其他一些限值检查)。所以可以看到这个全局队列使用的频率很低,虽然也是全局锁但是不至于影响性能。当然光窃取失败时获取是不够的可能会导致全局队列饥饿。P的算法中还会每个N轮调度之后就去全局队列拿一个G。那么全局队列的G又是谁放进去的呢?是在新建G时P的本地G队列放不下的时候会放半数G到全局队列去,阻塞的系统调用返回时找不到空闲P也会放到全局队列。
完整的过程其实比较繁琐,取g的完整顺序为: local->global->netpoll->steal->global->netpoll

在窃取到的G中,有一些G是标记了它绑定的M的,遇到这类G的话,当前M就会检查这个绑定的M是否是空闲状态,如果是空闲的话(不空闲就有问题了,这个M是专门执行这个G的不会执行别的G)就会把这个M唤醒,然后把P和G交给它去执行,自己则进入阻塞状态。这部分逻辑是实现协程和线程一一绑定的关系,参见LockOSThread

同时新调度器中引入了线程自旋,自旋有好处有坏处,好处是避免线程被阻塞陷入内核,坏处是自旋属于空转,浪费CPU。只能说适度使用自旋是可以带来好处的。新方案在两个地方引入自旋:

1,M找不到P(目的是一有P释放就结合)

2,M找到了P但找不到G(目的是一有runable的G就执行)

由于P最多只有GOMAXPROCS,所以自旋的M最多只允许GOMAXPROCS个,多了就没有意义了。同时当有类型1的自旋M存在时,类型2的自旋M就不阻塞,阻塞会释放P,一释放P就马上被类型1的自旋M抢走了,没必要。

在新G被创建,M进入系统调用,M从空闲被激活这三种状态变化前,调度器会确保至少有一个自旋M存在,除非没有空闲的P。

我们来分析下,当新G创建,如果有可用P,就意味着新G可以被立即执行,即便不在同一个P也无妨,所以我们保留一个自旋的M(这时应该不存在类型1的自旋只有类型2的自旋)就可以保证新G很快被运行。当M进入系统调用,意味着M不知道何时可以醒来,那么M对应的P中剩下的G就得有新的M来执行,所以我们保留一个自旋的M来执行剩下的G(这时应该不存在类型2的自旋只有类型1的自旋)。如果M从空闲变成活跃,意味着可能一个处于自旋状态的M进入工作状态了,这时要检查并确保还有一个自旋M存在,以防还有G或者还有P空着的。

现在来看下面这个图应该在理解上就没有大问题了:

dance between gmp

图片来自go-scheduler

问题总结

到这里,老调度器中的问题已经一一被解决了。我们来一一回顾下:

全局锁的问题

G被分成全局G队列和P的本地G队列,全局G队列依旧是全局锁,但是使用场景明显很少,P本地队列使用无锁队列,使用原子操作来面对可能的并发场景。

G传递带来开销的问题

G创建时就在P的本地队列,可以避免在G之间传递(窃取除外); 当G开始执行了,系统调用返回后M会尝试获取可用P,获取到了的话可以避免在M之间传递。

内存消耗问题

内存MCache只存在P结构中,P最多只有GOMAXPROCS个,远小于M的个数,所以内存没有过多的消耗。

数据局部性问题

新建的G放在本地队列,所以G对P的数据局部性好;系统调用后尝试获取可用P并执行,而且优先获取调用阻塞前的P,所以G对M数据局部性好,G对P的数据局部性也好;由于总的内存数目最多只有GOMAXPROCS而不是M的个数了,因此G调度到拥有同一块内存的执行单元的概率也就变大了,数据局部性也就变好了。

数据局部性还可以更好的,比如M选择空闲P时可以优先选择上一次绑定过的P。

频繁阻塞和唤醒

通过引入自旋,保证任何时候都有处于等待状态的自旋M,避免在等待可用的P和G时频繁的阻塞和唤醒。

Go程序的启动过程

整个程序始于一段汇编:

1
2
3
4
5
6
7
8
// _rt0_amd64 is common startup code for most amd64 systems when using
// internal linking. This is the entry point for the program from the
// kernel for an ordinary -buildmode=exe program. The stack holds the
// number of arguments and the C-style argv.
TEXT _rt0_amd64(SB),NOSPLIT,$-8
MOVQ 0(SP), DI // argc
LEAQ 8(SP), SI // argv
JMP runtime·rt0_go(SB)

而在随后的runtime·rt0_go(也是汇编程序)中,go一共做了这么几件事:

绑定m0和g0

m0和g0是什么呢,m0就是程序的主线程,程序启动必然会拥有一个主线程,这个就是m0.

每一个m结构中会包含两个主要的g:

1
2
3
4
5
6
type m struct {
g0 *g // goroutine with scheduling stack
...
curg *g // current running goroutine
...
}

可以看到m中的g0负责调度,curg是具体的任务g。因此这里的g0也就是m0的g0。而m0的curg现在还是空的。

创建p,绑定m0和p0

这里并不是去初始化g0,而是创建出了所需的p,p的数目优先取环境变量GOMAXPROCS,否则默认是cpu核数。随后把第一个p(便于理解可以叫它p0)与m0进行绑定,这样m0就有他自己的p了,就有条件执行后续的任务g了。

新建任务g到p0本地队列

这里m0的g0会执行调度任务(runtime.newproc),创建一个g,g指向runtime.main()(还不是我们main包中的main),并放到p的本地队列。这样m0就已经同时具有了任务g和p,什么条件都具备了。

执行统一的调度任务

调度器实现中有个同一个调度器入口,叫mstart(),这个实现中会去获取一个空闲的p(如果没有),然后执行schedule(), schedule中就会去不停的寻找可用的g来执行。这里其实初始工作已经全部完成并且把调度器启动起来了。后面可以不用管了,可以自动跑起来了。

持续调度

由于前一个步骤已经在p0中插入了一个指向runtime.main的g,所以显然之后第一个跑起来的任务g就是runtime.main。

runtime.main的工作包括:启动sysmon线程(这个线程游离在调度器之外,不受调度器管理,下面再讲);启动gc协程;执行init,这个就是统一执行我们代码中书写的各种init函数;执行main函数,这个就是我们main包中的main,可以看到,到这里我们的函数入口才终于被执行到了。

再后面就是前面讲过的GMP模型的工作过程了,main会创建g,g被放入p,并且触发m的创建,如此循环往复。

Sysmon线程

我们前面遗留了一些没有解释的工作流程,一个是调度器如何抢占长时间不返回的g,一个是sysmon是做什么的.这里可以一起解释了。因为调度器就是通过sysmon来进行抢占的。

sysmon也叫监控线程,它无需P也可以运行,他是一个死循环,每20us~10ms循环一次,循环完一次就sleep一会,为什么会是一个变动的周期呢,主要是避免空转,如果每次循环都没什么需要做的事,那么sleep的时间就会加大。

sysmon主要做下面几个事:

  1. 释放闲置超过5分钟的span物理内存;

  2. 如果超过2分钟没有垃圾回收,强制执行;

  3. 将长时间未处理的netpoll结果添加到全局G队列;

  4. 向长时间运行的G任务发出抢占调度;

  5. 收回因syscall长时间阻塞的P;

那么抢占就是发生在第4点。

当sysmon发现一个p一直处于running状态超过了10ms,那么就给这个g设置一个标志位,随后等到这个g调用新函数的时候,会检查到这个标志位,并且重新进行调度,不让这个g继续执行。

不过并不是设置了标志位就一定会被调度,这里有两个条件,一个是g必须调用函数,否则如果是一个简单的死循环是无法抢占成功的;另一个条件是即使调用了新函数,如果新函数所需的栈空间很少,那么也不会触发检查这个标志位,只有调用了会触发栈空间检查(所需栈大于128字节,详见知乎回答)的函数,才会抢占成功。

第5点是什么意思呢,我们知道g中调用系统调用后会解绑p,然后m和g进入阻塞,而p此时的状态就是syscall,表明这个p的g正在syscall中,这时的p是不能被调度给别的m的。如果在短时间内阻塞的m就唤醒了,那么m会优先来重新获取这个p,能获取到就继续绑回去,这样有利于数据的局部性。

但是当m较长时间没有唤醒的话,p继续等的成本就有点大了,这个时候sysmon就会吧他设为idle,重新调度给需要的M。这个时间界限是10ms,超过10ms就会被sysmon回收用于调度。

go的协程模型

这部分跟调度器关系不大,主要是补充一个知识点。

golang的goroutines是基于CSP(Communicating Sequential Processes)理论模型来设计的。

CSP主要是指两个独立的Process,通过共享Channel来交互。并发模型除了CSP另外还有Actors模型。

CSP和Actors简介

CSP模型就是coroutine+channel的模式。

coroutine之间通信是通过channel实现的,coroutine之间可以共享channel。

比如golang就是基于CSP实现的。

Actors模型就是coroutine+message的模式。

coroutine之间通信是通过message实现的,message是明确的发送给某个coroutine的。

比如erlang就是基于Actors实现的。

CSP和Actors的区别

同步异步

CSP的通信机制通常是同步的,任务被推进channel后立即被对端收到并执行,如果对端正忙,则发送者就阻塞无法推送该任务,golang对channel进行了修改,支持缓存任务,可以缓存多个任务等待执行,避免发送者阻塞。

Actors的通信机制通常是异步的,消息发送时发送者不会阻塞,接收者也不一定马上收到,收到也不一定马上执行。erlang中的actor角色非常广泛,可以是同个runtime下的,也可以是runtime间的,甚至可以是机器间的。

匿名性

CSP中的channel通常是匿名的,任务放进channel后你并不知道对端是谁在接收。

Actors中的message通常有确定目标,你需要确切的知道对方的地址(ID/NAME/PORT等)才能将信息发送出去。

耦合性

CSP中channel是共享的,可以多个生产者可多个消费者公用,生产者消费者之间不强关联。

Actors中你必须知道对方的地址(ID/NAME/PORT等),这导致生产者和消费者之间发生耦合,对方actor是不可替换的。

容错

CSP没有定义容错方面的内容,所以开发者需要自己处理channel接收和发送的错误,这些错误处理逻辑可能会到处都是。

Actors支持容错,你可以定义错误的类型,错误处理方式,错误的级别等。

参考资料

go-scheduler

Analysis of the Go runtime scheduler

Scalable Go Scheduler Design Doc

goroutine的生老病死

Actors模型和CSP模型

AKKA容错

is Scala’s actors similar to go’s coroutine?