【导读】本文详细介绍了 Go 语言的 MGP 模型中调度器的设计和演进。
我们知道Go里面有成千上万coroutine需要调度执行,而这里面起关键作用的就是Go的调度器,那么Go的调度器在哪里呢?因为我们写Go代码的时候从未显式创建过调度器实例。为了了解调度器,我们先来了解下Go的运行时(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 所担任的职责:goroutines 调度,垃圾回收,当然还提供goroutines 执行的环境。
所以这也相当于简要解释了什么是 Runtime。
go 的可执行程序可以分成两个层:用户代码和运行时,运行时提供接口函数供用户代码调用,用来管理 goroutines, channels 和其他一些内置抽象结构。用户代码对操作系统 API 的任何调用都会被运行时层截取,以方便调度和垃圾回收。分层如如些:
Go的调度程序是Go运行时的一个更重要的方面。运行时会跟踪每个Goroutine,并将安排它们在线程池中运行。goroutines 与线程分离(解耦不强绑定),但运行于线程之上。如何有效地将 goroutine 调度到线程上对于go程序的高性能至关重要。
Goroutines 的背后逻辑是:它们能够同时运行,与线程类似,但相比之下非常轻量。因此,程序运行时,Goroutines 的个数应该是远大于线程的个数的。
同时多线程在程序中是很有必要的,因为当 goroutine 调用了一个阻塞的系统调用,比如 sleep,那么运行这个 goroutine 的线程就会被阻塞,那么这时运行时至少应该再创建一个线程来运行别的没有阻塞的 goroutine。线程这里可以创建不止一个,可以按需不断地创建,而活跃的线程(处于非阻塞状态的线程)的最大个数存储在变量GOMAXPROCS
中。
go 运行时使用3个结构来跟踪所有成员来支持调度器的工作。
G:
一个 G 代表一个 goroutine,包含当前栈,当前状态和函数体。
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 ,内存等。
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 队列,和维护其他一些信息。
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状态,并等待空闲的 M 来执行,不一定是先前那个 M 了。
初代的调度器相对简单,所以也存在一定的问题,当然初代调度器的目的不是要马上做到成熟,只是在有限的时间内做出一个还可以的版本。
Dmitry Vyukov(新调度器的作者)写的一个论文列举了老调度器存在的问题:
以下来自Scalable Go Scheduler Design Doc (https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/edit#heading=h.mmq8lm48qfcw)
第一个问题是全局锁,无论是修改 M 还是 G 的队列还是其他 SCHED 结构的相关字段,都需要获取这个全局锁,当遇到高吞吐高并发的程序的时候,这个设计会导致调度器的性能问题。
第二个是当前有很多 M 之间传递 G 的情况,比如新建的 G 会被被放到全局队列,而不是在 M 本地执行,这导致了不必要的开销和延迟,应该优先在创建 G 的 M 上执行就可以了。
第三个问题是每一个 M 现在都持有一个内存,包括了阻塞状态的 M 也是持有的。Active 状态的 M 跟总的 M 个数之比可以达到 1:100 。这就导致了过多的内存消耗,以及较差的数据局部性。数据局部性怎么理解呢?数据局部性这里是指 G 当前在 M 运行后对 M 的内存进行了预热,后面如果再次调度到同一个 M 那么可以加速访问,可想而知,因为现在 G 调度到同一个 M 的概率不高,所以数据局部性不好。
第四个是 M 持续的阻塞和唤醒带来的开销。比如 M 找不到 P (目的是一有 P 释放就结合),M 找到了 P 但找不到 G(目的是一有 runable 的 G 就执行),此时 M 就会进入频繁阻塞/唤醒来进行检查的逻辑,以便及时发现新的 P 新的 G 来执行。
Dmitry Vyukov 的方案是引入一个结构 P ,用来模拟处理器, M 依旧表示操作系统线程,G 依旧表示一个 goroutine。
GOMAXPROCS
用来控制 P 的个数,同时 P 作为 M 执行 G 代码时的必需资源。
新的 P 结构会带走原来的 M 和 SCHED 结构中的一些属性,比如 MCache 从 M 移到了 P,而 G 队列也被分成两类,SCHED 结构保留全局 G 队列,同时每个 P 中都会有一个本地的 G 队列。
P 的本地队列可以解决旧调度器中单一全局锁的问题。注意 P 的本地 G 队列还是可能面临一个并发访问的场景,比如下面讲到的窃取算法。为了避免加锁,这里 P 的本地队列是一个 LockFree 的队列,窃取 G 时使用 CAS 原子操作来完成。
而 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 中,有一些 G 是标记了它绑定的 M 的,遇到这类 G 的话,当前 M 就会检查这个绑定的 M 是否是空闲状态,如果是空闲的话(不空闲就有问题了,这个 M 是专门执行这个 G 的不会执行别的 G )就会把这个 M 唤醒,然后把 P 和 G 交给它去执行,自己则进入阻塞状态。这部分逻辑是实现协程和线程一一绑定的关系,参见 LockOSThread (https://github.com/golang/go/wiki/LockOSThread)。
同时新调度器中引入了线程自旋,自旋有好处有坏处,好处是避免线程被阻塞陷入内核,坏处是自旋属于空转,浪费 CPU 。只能说适度使用自旋是可以带来好处的。新方案在两个地方引入自旋:
M 找不到 P(目的是一有 P 释放就结合)
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 空着的。
现在来看下面这个图应该在理解上就没有大问题了:
到这里,老调度器中的问题已经一一被解决了。我们来一一回顾下:
G 被分成全局 G 队列和 P 的本地 G 队列,全局 G 队列依旧是全局锁,但是使用场景明显很少,P 本地队列使用无锁队列,使用原子操作来面对可能的并发场景。
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 时频繁的阻塞和唤醒。
整个程序始于一段汇编:
// _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 就是程序的主线程,程序启动必然会拥有一个主线程,这个就是 m0.
每一个 m 结构中会包含两个主要的 g :
type m struct {
g0 *g // goroutine with scheduling stack
...
curg *g // current running goroutine
...
}
可以看到 m 中的g0负责调度,curg 是具体的任务 g。因此这里的 g0 也就是 m0 的 g0。而 m0 的 curg 现在还是空的。
这里并不是去初始化 g0,而是创建出了所需的 p,p 的数目优先取环境变量GOMAXPROCS
,否则默认是 cpu 核数。随后把第一个 p(便于理解可以叫它 p0)与 m0 进行绑定,这样 m0 就有他自己的 p 了,就有条件执行后续的任务 g 了。
这里 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 的创建,如此循环往复。
我们前面遗留了一些没有解释的工作流程,一个是调度器如何抢占长时间不返回的 g,一个是 sysmon 是做什么的.这里可以一起解释了。因为调度器就是通过 sysmon 来进行抢占的。
sysmon 也叫监控线程,它无需 P 也可以运行,他是一个死循环,每20us~10ms
循环一次,循环完一次就 sleep 一会,为什么会是一个变动的周期呢,主要是避免空转,如果每次循环都没什么需要做的事,那么 sleep 的时间就会加大。
sysmon 主要做下面几个事:
释放闲置超过5 分钟的 span 物理内存;
如果超过2分钟没有垃圾回收,强制执行;
将长时间未处理的 netpoll 结果添加到全局 G 队列;
向长时间运行的 G 任务发出抢占调度;
收回因 syscall 长时间阻塞的 P;
那么抢占就是发生在第 4 点。
当 sysmon 发现一个 p 一直处于 running 状态超过了 10ms,那么就给这个 g 设置一个标志位,随后等到这个 g 调用新函数的时候,会检查到这个标志位,并且重新进行调度,不让这个 g 继续执行。
不过并不是设置了标志位就一定会被调度,这里有两个条件,一个是 g 必须调用函数,否则如果是一个简单的死循环是无法抢占成功的;另一个条件是即使调用了新函数,如果新函数所需的栈空间很少,那么也不会触发检查这个标志位,只有调用了会触发栈空间检查(所需栈大于128字节,详见知乎回答 https://www.zhihu.com/question/308020301/answer/587239642)的函数,才会抢占成功。
第5点是什么意思呢,我们知道 g 中调用系统调用后会解绑 p,然后 m 和 g 进入阻塞,而 p 此时的状态就是 syscall ,表明这个 p 的 g 正在 syscall 中,这时的 p 是不能被调度给别的 m 的。如果在短时间内阻塞的m就唤醒了,那么 m 会优先来重新获取这个 p,能获取到就继续绑回去,这样有利于数据的局部性。
但是当 m 较长时间没有唤醒的话,p 继续等的成本就有点大了,这个时候 sysmon 就会吧他设为 idle,重新调度给需要的 M 。这个时间界限是 10ms,超过 10ms 就会被 sysmon 回收用于调度。
这部分跟调度器关系不大,主要是补充一个知识点。
golang 的 goroutines 是基于 CSP(Communicating Sequential Processes)理论模型来设计的。
CSP 主要是指两个独立的 Process,通过共享 Channel 来交互。并发模型除了 CSP 另外还有 Actors 模型。
CSP 模型就是 coroutine+channel 的模式。
coroutine 之间通信是通过 channel 实现的,coroutine 之间可以共享 channel 。
比如 golang 就是基于 CSP 实现的。
Actors 模型就是 coroutine+message 的模式。
coroutine 之间通信是通过 message 实现的,message 是明确的发送给某个 coroutine的。
比如 erlang 就是基于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 支持容错,你可以定义错误的类型,错误处理方式,错误的级别等。
转自:yizhi.ren/2019/06/03/goscheduler/
- EOF -
Go 开发大全
参与维护一个非常全面的Go开源技术资源库。日常分享 Go, 云原生、k8s、Docker和微服务方面的技术文章和行业动态。
关注后获取
回复 Go 获取6万star的Go资源库
分享、点赞和在看
支持我们分享更多好文章,谢谢!