调度的概念这里就不赘述了，调度本质上就是一个资源分配算法，本文谈谈调度的基础策略，常见模型，以及 Go 和 Erlang 的一些调度特性。
调度策略
抢占 vs 协作
从调度机制上来讲，调度可以分为抢占式和协作式。
非抢占方式是指一旦将调度资源(如 CPU)分配给某任务 后，便让该任务一直执行，直到该任务完成或阻塞或主动让出CPU控制权，非抢占调度又称为协作式调度，它实现简单，并且对共享资源的访问也更安全(如允许使用不可重入函数)。非抢占算法常见的如 FIFO，STCF(Short time to complete first)等。
抢占方式则允许调度程序根据某种规则，剥夺当前进程的调度资源，将其分配给其它进程。常见的抢占策略有:
- 基于时间片: 给每个进程分配时间片，当时间片用完后，则停止该进程重新调度下一个进程，这种均分CPU 的算法，又叫轮转调度算法
- 基于优先级: 给每个进程分配一个优先级，一旦出现一个优先级更高的进程，则停止当前进程并切换到该高优先级进程，这种调度算法又叫优先级抢占
- 轮转调度和优先级抢占结合: 即相同优先级的进程使用轮转调度，如果遇到更高优先级的进程，则可抢占CPU。现代 OS 如 Linux 通常都使用这种混合调度策略。
PS: 基于优先级抢占容易出现优先级反转的问题: 优先级低的任务持有一个被优先级高的任务所需要的共享资源，这种情况下，优先级低的任务有资源而得不到CPU，优先级高的资源有CPU而得不到资源，从而阻塞(导致其它中优先级的任务获得执行)或者忙等(可能永远无法获得资源)。
解决优先级反转的方案:
- 给临界区一个高优先级，所有进入该临界区的任务将获得该高优先级，避免其被随意抢占
- 当高优先级任务在等待低优先级进程持有资源时，低优先级进程将暂时获得高优先级进程的优先级，VxWorks采用的方式。
- 禁止中断，也就是在临界区不可被抢占，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打出了如下补丁:
- 官方建议NIF不要超过1ms(相信开发者对自己写的代码心里有数…)
- 在NIF中给Erlang虚拟机手动汇报当前执行时间，并手动记录上下文和恢复(抢占式变成了协作式，强制变成了自愿…)
- 将NIF放到自己创建的OS线程中执行，通过消息的方式将结果返回到Erlang进程(走开，别脏了我的公平调度器)
- 将NIF放到OTP为你准备的脏调度器(OTP R17引入，需要在启动时通过参数开启)中执行(好吧，我给你提供脏调度器)
PS: Erlang OTP R17之后提供了脏调度器功能，这也是继R13B之后对调度结构的又一次改进，虚拟机调度器就变成了M+N个。
以上方案可以说都是治标不治本，所以写纯Erlang代码，你可以享受到它很多的便利，但是一旦你因为性能问题，或要对接外部库等各种原因需要用到C的时候，一切都开始不美好了。
Erlang 的另一个问题也来自于其”公平调度”，我们假设有10000个逻辑进程，它们会将日志数据发到一个logger进程，那么系统上一共有10001个进程(忽略其它)，理想情况下，我们当然希望这个logger有任务就处理，避免消息堆积，最大化吞吐量，但Erlang的公平调度会想尽办法让这个logger进程和其它逻辑进程平起平坐，哪怕它有很多事情要做，然后导致导致logger进程消息队列膨胀，内存随之增长，甚至VM随之挂掉。针对这个问题通常的处理方案是:
- 提升logger进程的优先级(没有具体测试过)
- 开多个logger进程争取更多的执行权(笨办法)
- 从设计上尽量避免这种扇入扇出模型，同一节点尽可能跑相同类型的任务，比如将logger放到其它节点(Erlang的”并发思维”)
- 通过NIF来绕过时间片限制(骚操作)
因此，我们通常说Erlang在进程数少的时候表现不怎么样，而在进程多的却有很好的低延时表现。Erlang 调度器还有一些其它细节没有提到，比如:
- 通过三个优先级队列(low/normal,high,max)来实现进程的优先级调度
- 当调度器idle时，会自旋一段时间，如果没有新任务到达，则关闭该调度器(节能减排)
- 除了Process外，Erlang还处理Port任务，Port是Erlang与外部通信(文件，网络，C等)的一种机制
- Erlang对网络IO进行了特别的优化(System Level Activities)，即将所有的套接字设置为非阻塞，然后通过epoll机制去轮询并唤醒调用进程，通过应用层的阻塞/唤醒模拟系统调用。
反过来谈 Go，如果说 Erlang 为实时性殚精竭虑的话，那么Go则要实务得多，更加偏向于吞吐量和实用性，我之前谈过Go GPM模型，Go没有时间片或规约的概念，它的抢占也不是完全抢占的，它通过一个后台线程sysmon来监控并决定何时发起抢占，何时 GC 等，比如一个goroutine执行超过了10ms，sysmon则会向其发出抢占请求。抢占的方式也很简单，给goroutine打一个标记，goroutine在调用函数分配函数栈时会检查该标记，来决定当前G是否应该让出调度权，因此它没办法抢占死循环。可以看到，Go的调度模型实现相对比较简单，一方面可能调度器仍然还很年轻(STW的痛还历历在目)，另一方面Go的设计哲学就是简单。如果要解释得再官方一些: Go 更看重吞吐量，而非实时性。
另外，由于Erlang和Go都是为服务器设计的语言，因此它们都是网络IO进行了优化，将所有套接字设置为 nonblock，通过轮询/唤醒来向应用层屏蔽系统调用，通过IO复用+应用层阻塞来避免调度器阻塞在系统调用上。
最后
要理解一个调度器，需要结合其产生背景，设计目标，变更历史等，万丈高楼平地起，调度器这类复杂的系统，通常都是”First make it work, then measure, then optimize”，比如 Erlang 的 NIF，Go 的 STW 等，都在逐渐优化。
实时性和吞吐量是不可兼得的，这已经在其它系统上得到了验证。实时系统通常实现都比较复杂，并且由于现代 OS 最多满足软实时特性，因此应用层的调度也最多实现软实时。严格意义上的硬实时系统通常由特定领域的嵌入式系统实现。同时，也因为应用层的调度受更底层的OS调度的影响，要达到一个系统的整体最优，需要协调不同的调度层级，比如 Erlang 提供一个+sbt参数可以将调度器与 CPU 核心绑定，这样可以更好地利用 CPU 缓存和局部性，以提升整体性能。
相关资料: