Amal Cao

作为当前业界比较关注的两种面向并发领域的编程语言，Erlang和Go的调度是如何实现的？

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 机制让出处理器或进入了一个长时间执行的系统调用时，该任务才会被添加到公共队列中。

以上关于Go调度器的部分内容及图片转自：http://morsmachine.dk/go-scheduler

Erlang的调度模型简介

由于 Erlang 程序是运行在 BEAM 虚拟机之上，因此其调度器在实现上和 Go 等 Native 语言存在较大的差异，但其内部涉及的基本原理都是类似的，可以互相参考。

早期的 BEAM 虚拟机是单线程运行的，直到2006年才引入了 SMP 版本的 BEAM 虚拟机，经过了若干早期版本的演化，逐渐形成了今天的版本。最新版本的Erlang可以通过命令行参数指定是否启用 SMP 版本虚拟机。

BEAM 上的调度单位是“轻量进程”，这是一种虚拟机上的轻量级执行线索（由于 Erlang 的 process 是不共享内存的，行为更像进程而非线程，因此我们在这里叫它“轻量进程”）。每个 Erlang 进程包括一个控制块（PCB）、一个栈和私有的堆空间，一些特殊的结构，如二进制数据，ETS 表是进程间共享的，使用全局堆空间。

BEAM 虚拟机里存在一些并行的调度器，一般情况下，一个调度器会映射为一个 OS 线程，这种方式类似于早期的Go语言实现（只有M和G，没有P），每个调度器拥有各自的任务队列，调度器之间的负载平衡通过引入专门的任务迁移机制得以实现。其原理如下图所示：

通常，调度器的数量与运行平台的处理器核数或硬件线程数相等，也可以通过 BEAM 命令行参数指定，或在运行时动态修改。

在BEAM系统中，除了process之外，还存在三种其他的调度单位：端口（ports）、链入式驱动（linkd-in drivers）和系统级活动（system level activities）; 这三种特殊的任务形式主要用来进行IO操作和执行其他语言的代码等功能，其部分功能很像 Go 中对执行阻塞 Syscall 任务的“剥离”机制，具体实现方法这里暂时不讨论。我们主要将精力集中在 Erlang 的 process 的调度机制上。

与 Go 不同，Erlang 的调度器是一个轮转而非协作式的调度器，每个进程创建时会被分配一个称为“reduction”的值，是一个计算量的度量（基本上等同于函数调用的次数），类似 OS 的时间片。进程每执行一定量的计算后，reduction值就会累计，一旦达到阈值，该进程就会给切换出去。这种调度方式在 Erlang 中被称为 “reduction-counting”。

采用轮转的调度方式能更好的防止程序设计不当而导致的个别进程饿死的情况，同时能够实现更好的实时性功能。

同时，Erlang还为进程提供了四个不同的优先级：max，high，normal和low。不同优先级进程按优先级调度；同级进程按轮转方式调度。每个调度器包含3个任务队列，Max和High具有单独的队列，normal和low则位于同一个队列 —— 调度器忽略一定次数的low级进程来实现二者间的差别。

Erlang 调度器之所以能够实现优先级轮转调度，主要是得益于其基于虚拟机的执行方式：由于每条Erlang指令都需要经过 BEAM 解释执行，因此 process 的运行完全处于BEAM的监控之下，BEAM可以方便的完成对进程的切换。与之相对，由于 Go 的 Goroutine 与 RUNTIME 都是 Native 执行的，其在执行上的地位是平等的，RUNTIME 没有能力切换一个执行中的 Goroutine，除非其自己调出或调用RUNTIME 功在 ，因而只能实现协作调度。

注： Go 1.2 中，添加了简单的“用户态”任务抢占机制，主要是在系统线程sysmon中监控Goroutine的执行时间，然后借助“动态栈扩展”机制，在函数调用时刻切入RUNTIME并实现抢占。这种方式虽然很巧妙，但对某些特殊的情况，如没有调用非inline函数的耗时计算等，就没有多大效果力了。

Erlang 调度器通过定期进行“任务迁移”来达到负载平衡。“任务迁移”过程在同一时刻只能由一个调度器发起。首先，根据各调度器的任务队列的长度计算一个叫“Migtation limit”的值，这个值就是各调度器就绪队列长度的均值；然后，开始计算“Migataion Path”，算法是：

1. 计算各队列长度与“Migtation limit”差值
2. 找到差值中正最大和负最小的队列，记录一个从前者到后者进行任务迁移路径，以达到二者都接近“Migtation limit”
3. 重复步骤1，直到达到负载均衡

下图显示了上述算法的实例：

“Migatation Path” 计算完成后，在每个调度时刻，调度器都会检查该路径，根据其指导去抓取（pull）或推送（push）相应任务队列的任务。这一步骤完成了真正的负载均衡。

作为“任务迁移”机制的补充，Erlang调度器还支持“任务窃取”机制：当一个活跃的调度器自己的任务队列为空且不能通过“任务迁移路径”抓取任务时，它会主动窃取其他调度器任务队列上的就绪任务，如果仍然没有可供执行的任务，则该调度器进入Waiting状态。

关于Erlang调度模型，主要部分参考了这篇文章的第三章及Erlang/OTP源码。

结论

通过上述简单对比，我们大体上了解了Erlang和Go两种语言在并发任务调度上的异同，可以说二者各有优缺点：Go 的调度模型更加高效（Native）而 Erlang 则提供了更强大的功能（实时性、优先级）。

关于调度器，其实还有很多内容，如 Go 和 Erlang 都支持“垃圾回收”，而GC在两种语言中对调度的影响如何等；同时，讲Go的 M：N 调度时说到 M 一旦陷入Syscall 阻塞后，系统会创建一个新的M（OS 线程）来接管 P 及其任务队列，那么当设计一个高度并发的IO系统时（如 Web 服务器），频繁的Syscall会导致大量 OS 线程创建，从而影响性能。Go如何解决这个问题呢？

在后续分析中，会针对 IO 和 GC 部分进行更加深入的讨论，以解答余下的有关调度器的问题。

特别说明： 由于Go语言正处于高速发展的阶段，因此一些现在分析的内容可能会随时更新，在本文完成时， 其稳定版本是 1.2 ， 而包含大量更新的 1.3 版也呼之欲出，因此若本文内容不免出现滞后或错误，请大家及时指正！