为什么会发生调度？因为 CPU 是有限的，而操作系统上的进程很多，所以操作系统需要平衡各个进程的运行时间。比如说有的进程运行时间已经很长了，已经占用了 CPU 很长时间了，这个时候操作系统要公平，就会换下一个需要运行的进程。

抢占 vs 协作

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

非抢占，协作

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

抢占

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

基于时间片

给每个进程分配时间片，当时间片用完后，则停止该进程重新调度下一个进程，这种均分 CPU 的算法，又叫轮转调度算法。

基于优先级

给每个进程分配一个优先级，一旦出现一个优先级更高的进程，则停止当前进程并切换到该高优先级进程，这种调度算法又叫优先级抢占。轮转调度和优先级抢占结合，即相同优先级的进程使用轮转调度，如果遇到更高优先级的进程，则可抢占 CPU，现代 OS 如 Linux 通常都使用这种混合调度策略（Linux 具体的调度器体系见 Linux 进程调度）。

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

解决优先级反转的方案：

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

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

实时 vs 非实时

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

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

为什么现代 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 和 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 引入，需要在启动时通过参数开启）中执行；

Erlang OTP R17 之后提供了脏调度器功能，这也是继 R13B 之后对调度结构的又一次改进，虚拟机调度器就变成了 M+N 个。以上方案可以说都是治标不治本，写纯 Erlang 代码可以享受到它很多的便利，但是一旦因为性能问题，或要对接外部库等各种原因需要用到 C 的时候，一切都开始不美好了。

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

  • 提升 logger 进程的优先级；
  • 开多个 logger 进程争取更多的执行权；
  • 从设计上尽量避免这种扇入扇出模型，同一节点尽可能跑相同类型的任务，比如将 logger 放到其它节点；
  • 通过 NIF 来绕过时间片限制；

因此，Erlang 在进程数少的时候表现不怎么样，而在进程多的时候却有很好的低延时表现。Erlang 调度器还有一些其它细节，比如：通过三个优先级队列（low/normal、high、max）来实现进程的优先级调度；当调度器 idle 时，会自旋一段时间，如果没有新任务到达，则关闭该调度器（节能减排）；除了 Process 外，Erlang 还处理 Port 任务，Port 是 Erlang 与外部通信（文件、网络、C 等）的一种机制；Erlang 对网络 IO 进行了特别的优化（System Level Activities），即将所有的 socket 设置为非阻塞，然后通过 epoll 机制去轮询并唤醒调用进程，通过应用层的阻塞/唤醒模拟系统调用。

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

另外，由于 Erlang 和 Go 都是为服务器设计的语言，因此它们都对网络 IO 进行了优化，将所有 socket 设置为 nonblock，通过轮询/唤醒来向应用层屏蔽系统调用，通过 IO 复用 + 应用层阻塞来避免调度器阻塞在系统调用上。

小结

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

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

参考

延伸阅读（原文未附链接）：Go 调度模型、Linux 用户抢占和内核抢占详解、Inside the Erlang VM、Erlang 的调度原理（译文）。

本节 Erlang/Go 调度器对比部分作者：wudaijun，原文链接：http://wudaijun.com/2018/11/scheduler-blabla/，版权声明：原作者博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议，转载请注明出处。

维护记录

时间 修改内容 原因
2026-07-14 文件由 调度策略.md 重命名为 scheduler-design-patterns.md，url 由缺失改为 scheduler-design-patterns；标题改为「Scheduler Design Patterns, 调度器设计：抢占与协作」；categories 由 inbox 改为 development；删除文中与 Linux 进程调度、CFS 完全公平调度器 重复的 CFS/FIFO/RR/vruntime 小节；删除「Linux 进程的睡眠和唤醒」一节（内容已整理补充进 Linux Process State, 进程状态）；保留并整理抢占/协作、优先级反转、实时/非实时理论，以及 Erlang/Go 应用层调度器对比这部分独有内容 原文件是多篇不同来源文章拼接，与另外两篇调度器文章存在大量 CFS 相关重复内容，读者要求整理去重后再给红黑树文章补充 CFS 内链；Erlang/Go 调度器设计对比是应用层/语言运行时话题，和 Linux 内核 CFS 关系不大，值得保留为独立主题；睡眠/唤醒内容与已有文章重复度高，转移合并避免维护两份