运行时调度程序（go runtime scheduler）

1 为什么Golang需要调度器？

Goroutine的引入是为了方便高并发程序的编写。 一个Goroutine在进行阻塞操作（比如系统调用）时，会把当前线程中的其他Goroutine移交到其他线程中继续执行， 从而避免了整个程序的阻塞。

由于Golang引入了垃圾回收（gc），在执行gc时就要求Goroutine是停止的。通过自己实现调度器，就可以方便的实现该功能。 通过多个Goroutine来实现并发程序，既有异步IO的优势，又具有多线程、多进程编写程序的便利性。

引入Goroutine，也意味着引入了极大的复杂性。一个Goroutine既要包含要执行的代码， 又要包含用于执行该代码的栈和PC、SP指针。

2 调度器解决了什么问题？

2.1 栈管理

既然每个Goroutine都有自己的栈，那么在创建Goroutine时，就要同时创建对应的栈。 Goroutine在执行时，栈空间会不停增长。 栈通常是连续增长的，由于每个进程中的各个线程共享虚拟内存空间，当有多个线程时，就需要为每个线程分配不同起始地址的栈。 这就需要在分配栈之前先预估每个线程栈的大小。如果线程数量非常多，就很容易栈溢出。

为了解决这个问题，就有了Split Stacks技术： 创建栈时，只分配一块比较小的内存，如果进行某次函数调用导致栈空间不足时，就会在其他地方分配一块新的栈空间。 新的空间不需要和老的栈空间连续。函数调用的参数会拷贝到新的栈空间中，接下来的函数执行都在新栈空间中进行。

Golang的栈管理方式与此类似，但是为了更高的效率，使用了连续栈 （Golang连续栈） 实现方式也是先分配一块固定大小的栈，在栈空间不足时，分配一块更大的栈，并把旧的栈全部拷贝到新栈中。 这样避免了Split Stacks方法可能导致的频繁内存分配和释放。

2.2 抢占式调度

Goroutine的执行是可以被抢占的。如果一个Goroutine一直占用CPU，长时间没有被调度过， 就会被runtime抢占掉，把CPU时间交给其他Goroutine。

3 调度器的设计

Golang调度器引入了三个结构来对调度的过程建模：

• G 代表一个Goroutine；
• M 代表一个操作系统的线程；
• P 代表一个CPU处理器，通常P的数量等于CPU核数（GOMAXPROCS）。

三者都在runtime2.go中定义，他们之间的关系如下：

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

早期版本的Golang是没有P的，调度是由G与M完成。 这样的问题在于每当创建、终止Goroutine或者需要调度时，需要一个全局的锁来保护调度的相关对象(sched)。 全局锁严重影响Goroutine的并发性能。 (Scalable Go Scheduler)

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

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

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

4 调度器的实现

4.1 schedule()与findrunnable()函数

Goroutine调度是在P中进行，每当runtime需要进行调度时，会调用schedule()函数， 该函数在proc1.go文件中定义。

schedule()函数首先调用runqget()从当前P的队列中取一个可以执行的G。 如果队列为空，继续调用findrunnable()函数。findrunnable()函数会按照以下顺序来取得G：

1. 调用runqget()从当前P的队列中取G（和schedule()中的调用相同）；
2. 调用globrunqget()从全局队列中取可执行的G；
3. 调用netpoll()取异步调用结束的G，该次调用为非阻塞调用，直接返回；
4. 调用runqsteal()从其他P的队列中“偷”。

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

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

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

4.2 如何进行抢占?

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。

关于Golang抢占式调度的进一步学习，可以参考 Go Preemptive Scheduler Design Doc。

Go 语言和 Erlang 都是面向并发应用的语言，都采用轻量级线程和消息传递模型。尽管Go在语法上也支持共享，但必须以通信的方式同步方能保证其正确性。Erlang则是完全不支持进程间的共享，状态信息完全需要依靠消息彼此传递。

从底层来看，在 Google 官方编译器中，Go 语言的 Goroutine 是一种类似协程的结构，由于采用了定制的C编译器来构建，因此其上下文切换的效率要高于C库的 coroutine（只需要切换PC和栈帧，其他寄存器由函数调用者负责保存）； 而在 Go 的 GCC 前端中，Goroutine 则直接由C库的 coroutine 机制实现。由于 Erlang 是基于 BEAM 虚拟机执行的，因此它的所谓 “轻量进程” 也就仅仅是 BEAM 上的概念，不对应C语言或OS级的概念。

从调度策略来看，Go 完全是协作式调度，一个执行中的 Goroutine 仅在操作被阻塞或显示让出处理器时被切换出去，Goroutine之间也没有优先级之分； Erlang 则采用一种名为“Reduction-Counting”的轮转调度策略，并且存在4个进程优先级。

值得注意的是在 Go 1.2 版之后，增加了一些简单的抢占机制，但仅有用户程序函数调用时刻才可能触发抢占的判断，并不是真正意义上的抢占，具体思想参见这里。

Go 的调度器的最新版实现了M：N的调度方式，通过 GOMAXPROCS 指定最大的并行能力； Erlang 的 BEAM 虚拟机也支持SMP方式，一般情况下以系统的核心数或硬件线程数作为其调度器个数，每个调度器会绑定到一个OS线程，IO 等阻塞型操作由单独的系统线程负责调度。

Go 的负载平衡一般是采用 “Work-Stealing” 方式；Erlang则是维护一个“任务迁移队列”，调度器会定期计算任务迁移的路径。此外，Erlang也提供了“Work-Stealing” 方式作为补充。充。

Go的调度模型简介

对于线程调度器，一般有3中模型：

• N：1，即多个用户线程运行在一个OS线程上
• 1：1，即用户线程和OS线程一一对应
• N：M，即一定数量的用户线程映射到一定数量的OS线程上

第一种方式的优点是用户线程切换较快，但可扩展性不好，难以很好发挥多核处理器的并行性（libtask 属于该类型）； 而第二种与之相反，其能很好的利用多核并行性，但是用户线程资源开销和调度成本都比较大。 第三种方式理论上能在调度开销和并行性之间取得较好的折衷。

在Go 1.1 中，Dmirty Vyukov 对调度器进行了重新设计，由原来的 1：1 模型进化到 M：N 模型，从而使 Go 在并行编程性能上有了显著的提升。

Go 的新调度器模型主要涉及3个核心概念：M、P及G，如下图所示：

M 代表OS的线程，P代表当前系统的处理器数（一般由GOMAXPROCS 环境变量指定），G代表Go语言的用户级线程，也就是通常所说的 Goroutine。

新的调度器由1:1 进化到 M:N 的关键在于新加了 P 这个抽象结构。在多核平台上，P的数量一般对应处理器核心或硬件线程的数量，调度器需要保证所有的P都有G执行，以保证并行度。

M 必须与P绑定方能执行任务G，如下图所示：

在旧版 Go 调度器实现中，由于缺少P, 一旦运行 G （goroutine）的 M （OS线程）陷入阻塞状态（如调用某个阻塞的系统调用）时，M 对应的 OS 线程就会被操作系统调度出去，从而导致系统中其他就绪的G也不能执行；而添加了P这个逻辑结构后，一旦发生上述情况，阻塞的 M 将被与其对应的 P 剥离，RUNTIME会再分配一个 M 并将其与已经剥离出来的 P 绑定，运行其他就绪的G。这个过程如下图所示：

在实际实现中，考虑到代码执行的局部性因素，一般会倾向于推迟 M 与 P 剥离的时机。具体来说，RUNTIME中存在一个驻留的线程sysmon，用来监控所有进入Syscall 的 M，只有当 Syscall 执行时间超出某个阈值时，才会将 M 与 P 分离。

另外一个保证系统运行稳定性的方式是负载均衡机制，在Go中，用了 “任务窃取” 的方法。

首先介绍一下 Go 的任务队列，每个 P 都有一个私有的任务队列 （实现上是一个用数组表示的循环链表）以及一个公共队列（单链表表示），私有队列的功能是为了减轻公共队列的竞争开销。

当一个 P 的私有任务队列为空时，它会从全局队列中寻找就绪态的 G 执行；如果全局队列也为空，则会随机选择窃取其他 P 私有执行队列中的任务G，从而保证所有线程尽可能以最大负载工作。其示意图如下：

由于 P 的私有队列采用了数组结构，很容易计算出队列中间的位置，因此“窃取者” 采用了与 “被窃取者” 均分任务的方法，以尽可能达到负载均衡。

无论从公共队列取任务还是进行“窃取”，都会引起一定的竞争开销，因此 RUNTIME 会倾向于将新建任务或新转变为就绪态的任务添加到当前执行 P 的私有队列中。 仅当执行的任务调用 yield 机制让出处理器或进入了一个长时间执行的系统调用时，该任务才会被添加到公共队列中。