调度杂谈

调度的概念这里就不赘述了,调度本质上就是一个资源分配算法,本文谈谈调度的基础策略,常见模型,以及 Go 和 Erlang 的一些调度特性。

调度策略

抢占 vs 协作

从调度机制上来讲,调度可以分为抢占式和协作式。

非抢占方式是指一旦将调度资源(如 CPU)分配给某任务 后,便让该任务一直执行,直到该任务完成或阻塞或主动让出CPU控制权,非抢占调度又称为协作式调度,它实现简单,并且对共享资源的访问也更安全(如允许使用不可重入函数)。非抢占算法常见的如 FIFO,STCF(Short time to complete first)等。

抢占方式则允许调度程序根据某种规则,剥夺当前进程的调度资源,将其分配给其它进程。常见的抢占策略有:

  1. 基于时间片: 给每个进程分配时间片,当时间片用完后,则停止该进程重新调度下一个进程,这种均分CPU 的算法,又叫轮转调度算法
  2. 基于优先级: 给每个进程分配一个优先级,一旦出现一个优先级更高的进程,则停止当前进程并切换到该高优先级进程,这种调度算法又叫优先级抢占
  3. 轮转调度和优先级抢占结合: 即相同优先级的进程使用轮转调度,如果遇到更高优先级的进程,则可抢占CPU。现代 OS 如 Linux 通常都使用这种混合调度策略。

PS: 基于优先级抢占容易出现优先级反转的问题: 优先级低的任务持有一个被优先级高的任务所需要的共享资源,这种情况下,优先级低的任务有资源而得不到CPU,优先级高的资源有CPU而得不到资源,从而阻塞(导致其它中优先级的任务获得执行)或者忙等(可能永远无法获得资源)。

解决优先级反转的方案:

  1. 给临界区一个高优先级,所有进入该临界区的任务将获得该高优先级,避免其被随意抢占
  2. 当高优先级任务在等待低优先级进程持有资源时,低优先级进程将暂时获得高优先级进程的优先级,VxWorks采用的方式。
  3. 禁止中断,也就是在临界区不可被抢占,Linux 采用的就是这种方式,在 thread_info.preeempt_count 记录每个进程当前持锁计数。

另外,调度器是不能在进程指令流的任意一点执行打断的,因为进程可能此时正在做任何事情,如系统调用,死循环,锁操作等,要实现任意状态的可抢占性代价是很大的,需要 OS 和 App 的通力配合,特别是在涉及在内核态的时候,目前所有OS都不能在进程执行的任意点进行抢占。只是说不断让抢占区更大,抢占点尽可能地密集。

实时 vs 非实时

从系统需求或用户角度而言,调度系统可以分为实习系统和非实时系统。

在实时操作系统中,系统必须在特定的时间内完成指定的应用。实时通常分为软实时(soft real-time)和硬实时(hard real-time),硬实时是指系统要有确定的最坏情况下的服务时间,即对于事件的响应时间截止期限无论如何都必须得到满足,通常应用在军工航天领域。而软实时只提供统计意义上的实时,比如应用要求在95%的情况下都会确保在规定的时间内执行某个任务,而不一定要求100%。实时系统通常采用抢占调度,实现一个硬实时系统的代价是很高的,要做到进程可以在任意时刻被抢占,在现代OS上来讲,基本是不可能的,因为OS的很多系统调用都是不可被打断的,并且很多操作具备时间的随机性,比如 CPU Cache Miss,Page Fault,CPU Branch Predictor 等等。

BTW, 为什么现代OS不尽可能地去掉这些不稳定性(如虚拟内存,CPU多级Cache,分支预测等),从而为成为实时系统打好基础呢?对桌面操作系统而言,对实时性的要求没有那么高,应用切换偶尔卡一卡并无大碍,桌面系统更关注的一方面是对内核的统一抽象,屏蔽硬件差异化,接口丰富易用,让上层应用易于开发,比如虚拟内存,文件描述符等。另一方面,桌面系统在选择牺牲部分的实时性来提高吞吐量,比如多级Cache,分支预测。因此尽管如 Linux 这类桌面系统支持实时优先级和多种调度机制,但仍然最多只能实现软实时,这是设计目标决定的。

而非实时系统,则没有对最低任务处理时延的要求,比如简单的非抢占调度模型。

调度结构

这里我们讨论基于OS之上的几种常见的应用层调度。对应用层而言,所谓调度器(scheduler)便是OS线程,在此之上应用实现自己的任务,任务队列,以及调度算法。

single scheduler

这是最简单的模型,实际上,几乎所有调度器最开始就是这样的,如Go,Erlang,甚至OS(单核年代)的早期版本,复杂项目的通用最佳实践是先跑起来再优化(“First make it work, then measure, then optimize”.)。这种调度模型只有一个调度器和一个任务队列,由于不需要锁,所以单核吞吐量很高,主要的缺点在于无法充分利用调度资源(如多核),并且容易出现任务饥饿(多调度器本质也会有这种情况,只不过被掩盖了一些)。

multi scheduler with global queue

为了最大化多核收益,我们需要多个调度器,理想情况下是调度器的数量和CPU核心数一致。因此有了如下调度模型:

如图,多个调度器共享一个全局任务队列,Erlang OTP R11B 便使用这种模型,该模型主要的瓶颈在于全局任务队列的操作需要加锁,并且CPU核心数越多,调度瓶颈越明显,从而限制了调度算法在多核下的扩展性。

multi scheduler with local queue

为了优化全局任务队列带来的瓶颈问题,借鉴”Cache思维”,可以给每个调度器分配一个本地的任务队列:

这样调度器可以无锁操作本地任务队列,显著减少锁竞争,提升多核下的调度效率。但这样又引入了新的问题: 如何尽可能地让各个调度器都随时有事情做(任务分配尽可能均衡)。比如如果给每个调度器本地任务队列分配了10个任务,执行最快的调度器A执行完这10个任务时,执行最慢的调度器B可能才执行完第一个,在这种情况下,调度器A是否应该去调度B的任务队列steal(窃取)一部分任务过来,以让整体调度效率最高。这个过程叫任务迁移(Task Migration)或任务窃取(Task Stealing)。Erlang R13B+ 和 Go 调度都是基于此结构,但有一些区别。

以上三种模型是大多数调度器历经的三个阶段,最终演化得到的是一个多层次,局部性的结构(类似 CPU Cache层级)。

现实中的调度器

就调度器结构而言,各个调度算法大同小异,各个调度算法的根本差异还是在调度策略上,基于设计目标,在复杂性,吞吐量,实时性之间去做取舍,这里我仍然想以 Erlang 和 Go来举例说明。

基于Erlang的产生背景(通信领域),Erlang 在设计之初就对实时性(低延迟)非常看重,为了达成软实时性,Erlang的调度必然是抢占式的,它通过给每个Erlang进程设定规约(Reduction)来作为一个进程的虚拟时间片,进程调用函数,BIF,GC,ETS操作,发送消息等,都会消耗规约,甚至用Erlang自带的用C写的正则表达式处理,也添加了扣除规约的代码,每个Erlang进程默认有2000规约,在Erlang的设计理念中,天下没有”免费”的操作,它重度依靠规约来衡量进程何时被换出。但理想和现实往往有差别,NIF的出现打破了这个定律,NIF是用户用C实现的可供Erlang调用的函数,它是不可被调度的,对此,Erlang打出了如下补丁:

  1. 官方建议NIF不要超过1ms(为什么是1ms?1.05ms怎么办…)
  2. 在NIF中给Erlang虚拟机手动汇报当前执行时间,并手动记录上下文和恢复(抢占式变成了协作式,强制变成了自愿…)
  3. 将NIF放到自己创建的OS线程中执行,通过消息的方式将结果返回到Erlang进程(走开,别脏了我的公平调度器)
  4. 将NIF放到OTP为你准备的脏调度器(OTP R17引入,需要在启动时通过参数开启)中执行(好吧,我给你提供脏调度器)

PS: Erlang OTP R17之后提供了脏调度器功能,这也是继R13B之后对调度结构的又一次改进,虚拟机调度器就变成了M+N个。

以上方案可以说都是治标不治本,所以写纯Erlang代码,你可以享受到它很多的便利,但是一旦你因为性能问题,或要对接外部库等各种原因需要用到C的时候,一切都开始不美好了。

Erlang 的另一个问题也来自于其”公平调度”,我们假设有10000个逻辑进程,它们会将日志数据发到一个logger进程,那么系统上一共有10001个进程(忽略其它),理想情况下,我们当然希望这个logger有任务就处理,避免消息堆积,最大化吞吐量,但Erlang的公平调度会想尽办法让这个logger进程和其它逻辑进程平起平坐,哪怕它有很多事情要做,然后导致导致logger进程消息队列膨胀,内存随之增长,甚至VM随之挂掉。针对这个问题通常的处理方案是:

  1. 提升logger进程的优先级(没有具体测试过)
  2. 开多个logger进程争取更多的执行权(笨办法)
  3. 从设计上尽量避免这种扇入扇出模型,同一节点尽可能跑相同类型的任务,比如将logger放到其它节点(Erlang的”并发思维”)
  4. 通过NIF来绕过时间片限制(骚操作)

因此,我们通常说Erlang在进程数少的时候表现不怎么样,而在进程多的却有很好的低延时表现。Erlang 调度器还有一些其它细节没有提到,比如:

  1. 通过三个优先级队列(low/normal,high,max)来实现进程的优先级调度
  2. 当调度器idle时,会自旋一段时间,如果没有新任务到达,则关闭该调度器(节能减排)
  3. 除了Process外,Erlang还处理Port任务,Port是Erlang与外部通信(文件,网络,C等)的一种机制

反过来谈 Go,如果说 Erlang 为实时性殚精竭虑的话,那么Go则要实务得多,更加偏向于吞吐量和实用性,我之前谈过Go GPM模型,Go没有时间片或规约的概念,它的抢占也不是完全抢占的,它通过一个后台线程sysmon来监控并决定何时发起抢占,何时 GC 等,比如一个goroutine执行超过了10ms,sysmon则会向其发出抢占请求。抢占的方式也很简单,给goroutine打一个标记,goroutine在调用函数分配函数栈时会检查该标记,来决定当前G是否应该让出调度权,因此它没办法抢占死循环。可以看到,Go的调度模型实现相对比较简单,一方面可能调度器仍然还很年轻(STW的痛还历历在目),另一方面Go的设计哲学就是简单(这里不是褒义)。如果要解释得再官方一些: Go 更看重吞吐量,而非实时性。

最后

要理解一个调度器,需要结合其产生背景,设计目标,变更历史等,万丈高楼平地起,调度器这类复杂的系统,通常都是”First make it work, then measure, then optimize”,比如 Erlang 的 NIF,Go 的 STW 等,都在逐渐优化。

实时性和吞吐量是不可兼得的,这已经在其它系统上得到了验证。实时系统通常实现都比较复杂,并且由于现代 OS 最多满足软实时特性,因此应用层的调度也最多实现软实时。严格意义上的硬实时系统通常由特定领域的嵌入式系统实现。同时,也因为应用层的调度受更底层的OS调度的影响,要达到一个系统的整体最优,需要协调不同的调度层级,比如 Erlang 提供一个+sbt参数可以将调度器与 CPU 核心绑定,这样可以更好地利用 CPU 缓存和局部性,以提升整体性能。

相关资料:

  1. Go 调度模型
  2. Linux内核态抢占机制分析
  3. Inside the Erlang VM
  4. Erlang的调度原理(译文)