操作系统调度：CPU 时间是如何被分配的

一台计算机上同时运行着大量的程序：浏览器、编辑器、音乐播放器、后台的同步服务、系统守护进程，在服务器上还可能有成百上千个处理请求的线程。然而，处理器核心的数量是有限的，一个核心在任一时刻只能执行一个线程的指令。

那么，这些程序是如何"同时"运行的？操作系统如何决定在每个时刻让哪个线程使用 CPU？为什么在后台编译大型项目时，前台的界面依然能够流畅响应？为什么有时一个程序会突然变得很慢，即使 CPU 使用率并不高？

回答这些问题的，是操作系统内核中的调度器（Scheduler）。本文介绍进程与线程的基本概念、调度的目标与评价指标、经典的调度算法、现代操作系统中的调度器设计、多核处理器上的调度问题，以及优先级反转、实时调度等相关话题。

一、基本概念

进程与线程

进程（Process）是程序的一次运行实例。每个进程拥有独立的虚拟地址空间、打开的文件、信号处理设置等资源。进程之间相互隔离，一个进程无法直接访问另一个进程的内存。

线程（Thread）是进程内部的执行单元。同一个进程中的多个线程共享进程的地址空间和资源，但每个线程有自己独立的执行状态：程序计数器、寄存器的值、栈。

从调度器的角度看，被调度的基本单位是线程。在许多操作系统中，内核将进程和线程统一视为可调度的任务，只是它们共享资源的程度不同。为了简洁，下文中"任务"一词泛指被调度的对象。

任务的状态

一个任务在其生命周期中会处于几种不同的状态：

• 运行：正在某个 CPU 核心上执行；
• 就绪：已经准备好执行，正在等待被分配 CPU；
• 阻塞（也称等待或睡眠）：正在等待某个事件的发生，例如等待磁盘读取完成、等待网络数据到达、等待获取一把锁、等待定时器到期。处于阻塞状态的任务，即使有空闲的 CPU 也无法执行；
• 终止：已经执行完毕。

调度器的职责，就是从所有处于就绪状态的任务中，选择下一个要运行的任务，并决定让它运行多长时间。

上下文切换

当 CPU 从运行一个任务切换到运行另一个任务时，需要进行上下文切换（Context Switch）：

1. 保存当前任务的执行状态，包括所有寄存器的值、程序计数器、栈指针等，存入该任务在内核中的数据结构中；
2. 如果新任务属于另一个进程，切换地址空间，即让处理器使用新进程的页表；
3. 恢复新任务之前保存的执行状态；
4. 从新任务上次中断的位置继续执行。

上下文切换本身需要消耗时间，通常在微秒级别。但它的间接代价往往更大：切换到新任务后，处理器的各级缓存中保存的是前一个任务的数据，新任务的数据需要重新从内存中加载；如果切换了地址空间，转译后备缓冲区中的地址映射也可能失效。因此，过于频繁的上下文切换会显著降低系统的整体效率。

抢占

调度可以分为两种方式：

• 非抢占式调度：一个任务一旦开始运行，就会一直运行，直到它主动放弃 CPU，例如执行完毕、进入阻塞状态，或者主动让出。早期的一些操作系统采用这种方式，其问题在于，一个陷入死循环或者长时间计算的任务，会让整个系统失去响应；
• 抢占式调度：调度器可以在任务运行的过程中强制中断它，将 CPU 分配给其他任务。抢占通常通过定时器中断实现：硬件定时器以固定的频率产生中断，每次中断时，内核检查当前任务是否已经运行了足够长的时间，或者是否有更重要的任务需要运行，如果是，就进行切换。

现代通用操作系统都采用抢占式调度。

二、调度的目标

调度器需要在多个相互冲突的目标之间进行权衡。

评价指标

• 吞吐量：单位时间内完成的工作量。为了最大化吞吐量，应当减少上下文切换的开销，让每个任务尽可能长时间地连续运行，充分利用缓存；
• 周转时间：一个任务从提交到完成所经历的总时间。对于批处理任务，这是最重要的指标；
• 响应时间：从用户发出请求，例如按下一个键，到系统做出第一次响应的时间。对于交互式应用，这是最重要的指标。为了缩短响应时间，交互式任务需要在就绪后尽快获得 CPU；
• 公平性：各个任务能够获得合理份额的 CPU 时间，不会有任务长时间得不到执行，即饥饿；
• CPU 利用率：让 CPU 尽可能保持忙碌，而不是在有就绪任务时处于空闲；
• 可预测性：任务的执行时间和延迟应当稳定、可预测，这对于实时系统尤为重要；
• 能耗：在移动设备和数据中心中，调度决策还需要考虑能耗，例如将任务集中到少数核心上，让其余核心进入低功耗状态。

目标之间的冲突

这些目标常常相互冲突：

• 缩短响应时间需要频繁地切换任务，让交互式任务能够及时运行；而提高吞吐量需要减少切换，让任务长时间连续运行；
• 让短任务优先运行可以缩短平均周转时间，但可能导致长任务长时间得不到执行；
• 严格的公平性可能导致重要的任务得不到足够的资源。

不同类型的系统，侧重点也不同：批处理系统更关注吞吐量和周转时间；桌面系统更关注交互的响应速度；服务器更关注吞吐量和尾部延迟；实时系统则要求任务必须在截止时间之前完成。

任务的行为特征

任务的执行通常在使用 CPU 和等待 I/O 之间交替进行。一段连续使用 CPU 的时间称为一次 CPU 突发。根据 CPU 突发的特点，任务大致可以分为两类：

• CPU 密集型任务：大部分时间都在进行计算，CPU 突发较长，例如视频编码、科学计算、编译；
• I/O 密集型任务：大部分时间都在等待 I/O，每次只使用很短的 CPU 时间就进入阻塞，例如文本编辑器、网络服务器、交互式程序。

一个好的调度器应当优先照顾 I/O 密集型任务：它们每次只需要很短的 CPU 时间，让它们尽快运行，可以使其尽快发出下一个 I/O 请求，从而让 CPU 和 I/O 设备都保持忙碌；同时，交互式程序通常属于这一类，优先运行它们能够改善响应速度。

三、经典调度算法

先来先服务

先来先服务（First-Come, First-Served，FCFS）是最简单的调度算法：按照任务进入就绪状态的顺序，依次运行。

其主要问题是护航效应：如果一个运行时间很长的任务排在前面，后面所有的短任务都必须等待它完成，即使它们只需要很短的时间。这导致平均周转时间和响应时间都很长。

最短作业优先

最短作业优先（Shortest Job First，SJF）总是选择预计运行时间最短的任务。可以证明，在所有任务同时到达的情况下，最短作业优先能够使平均周转时间最小。

它的抢占式版本是最短剩余时间优先：当一个新任务到达时，如果它的运行时间比当前任务的剩余时间还短，就抢占当前任务。

最短作业优先在理论上是最优的，但在实践中面临两个问题：

• 无法预知运行时间：操作系统通常不知道一个任务需要运行多久。一种近似的方法是根据任务过去的 CPU 突发长度，用指数加权平均来预测下一次的突发长度；
• 饥饿：如果短任务源源不断地到达，长任务可能永远得不到执行。

时间片轮转

时间片轮转（Round Robin，RR）为每个任务分配一个固定长度的时间片，例如 10 毫秒。任务按照队列的顺序依次运行，每个任务最多运行一个时间片，如果时间片用完时任务还没有完成，就被抢占并放到就绪队列的末尾，等待下一轮。

时间片轮转保证了每个就绪的任务都能在有限的时间内获得 CPU，具有良好的公平性和响应时间。

时间片的长度是一个关键的参数：

• 时间片太长：算法退化为先来先服务，响应时间变差；
• 时间片太短：上下文切换过于频繁，切换的开销占据了大量的 CPU 时间，并且缓存的效率降低。

一般的经验是：时间片应当比大多数交互式任务的 CPU 突发长度略长，使它们能够在一个时间片内完成一次突发并进入阻塞，同时又远大于上下文切换的开销。

时间片轮转的问题在于，它对所有任务一视同仁，没有区分任务的重要程度和行为特征，平均周转时间也往往不理想。

优先级调度

优先级调度为每个任务分配一个优先级，总是选择优先级最高的就绪任务运行。优先级相同的任务之间，可以使用时间片轮转。

优先级可以由用户或系统管理员指定，也可以由系统根据任务的行为动态调整。

优先级调度的主要问题是饥饿：低优先级的任务可能永远得不到执行。一种常见的解决方法是老化（Aging）：任务在就绪队列中等待的时间越长，其优先级就逐渐提高，直到最终能够获得执行。

多级反馈队列

多级反馈队列（Multi-Level Feedback Queue，MLFQ）试图在不预先知道任务特征的情况下，自动地区分交互式任务和 CPU 密集型任务，并对它们区别对待。它是许多操作系统调度器的设计基础。

多级反馈队列包含多个优先级不同的就绪队列，其基本规则如下：

1. 总是运行最高优先级队列中的任务；同一队列中的任务使用时间片轮转；
2. 新任务进入时，放入最高优先级的队列；
3. 如果一个任务用完了它在当前队列的时间片，说明它可能是 CPU 密集型的，将它降低一级优先级；
4. 如果一个任务在时间片用完之前主动放弃了 CPU，例如进入 I/O 等待，说明它可能是交互式的，保持其优先级不变；
5. 通常，优先级越低的队列，时间片越长。

在这些规则下，交互式任务由于经常主动放弃 CPU，会一直保持在高优先级的队列中，能够迅速得到响应；而 CPU 密集型任务会逐渐下沉到低优先级的队列中，在没有交互式任务需要运行时，以较长的时间片运行，减少上下文切换的开销。

但这一基本设计存在几个问题，需要额外的规则来解决：

• 饥饿：如果高优先级的交互式任务很多，低优先级的 CPU 密集型任务可能长时间无法执行。解决方法是周期性地提升：每隔一段时间，将所有任务都移回最高优先级的队列；
• 行为的变化：一个任务可能在某个阶段是 CPU 密集型的，之后变成交互式的。周期性提升也使得这样的任务有机会重新获得高优先级；
• 博弈：一个狡猾的程序可以在每个时间片即将用完之前，主动发起一次无意义的 I/O 操作，从而一直保持高优先级，独占大量的 CPU 时间。解决方法是累计计算任务在某个优先级上使用的 CPU 时间，一旦累计用完了该级别的时间配额，无论它中途是否放弃过 CPU，都将其降级。

比例份额调度

比例份额调度的目标不是优化周转时间或响应时间，而是保证每个任务获得预定比例的 CPU 时间。

彩票调度是一种简单而巧妙的比例份额算法：为每个任务分配一定数量的彩票，每次调度时随机抽取一张彩票，持有这张彩票的任务获得运行的机会。持有的彩票越多，被选中的概率越大，长期来看获得的 CPU 时间比例就越接近其彩票所占的比例。彩票调度实现简单，并且可以方便地在任务之间转让彩票。但由于其随机性，在较短的时间尺度上，实际的分配比例可能与目标有较大的偏差。

步幅调度是彩票调度的确定性版本：为每个任务计算一个步幅，与其彩票数成反比。每个任务维护一个行程值，初始为零。每次调度时，选择行程值最小的任务运行，运行后将其行程值增加一个步幅。彩票越多的任务，步幅越小，行程值增长得越慢，因此被选中的次数越多。步幅调度能够在任何时间尺度上都精确地实现比例分配。

比例份额调度的思想，直接影响了现代通用操作系统中的公平调度器设计。

四、现代操作系统的调度器

完全公平调度器

Linux 内核长期以来使用的完全公平调度器（Completely Fair Scheduler，CFS），是比例份额调度思想在通用操作系统中的一个重要实践。

理想的公平。 完全公平调度器的设计目标，是模拟一个"理想的多任务处理器"：如果有 n 个任务同时就绪，每个任务都能够同时以 1/n 的速度运行。现实中的处理器无法做到这一点，调度器只能通过快速地在任务之间切换来近似它。

虚拟运行时间。 完全公平调度器为每个任务维护一个虚拟运行时间，记录它已经获得的、经过加权调整的 CPU 时间。调度器总是选择虚拟运行时间最小的任务运行，即"到目前为止获得 CPU 最少"的那个任务。这与步幅调度中选择行程值最小的任务是相同的思想。

权重与友好值。 任务的优先级通过友好值（nice 值）来表达，取值范围通常是负 20 到正 19，值越低表示优先级越高，即越"不友好"，越愿意占用 CPU。每个友好值对应一个权重，相邻的友好值之间，权重大约相差 1.25 倍，这意味着友好值每降低一级，任务获得的 CPU 时间大约增加 10%。

任务实际运行时，其虚拟运行时间的增长速度与权重成反比：权重越高的任务，虚拟运行时间增长得越慢，因此能够更频繁地被选中，获得更多的实际 CPU 时间。

红黑树。 为了高效地找到虚拟运行时间最小的任务，完全公平调度器将所有就绪任务按照虚拟运行时间组织在一棵红黑树中。最左边的节点就是虚拟运行时间最小的任务。插入和删除任务的时间复杂度都是对数级的，并且调度器会缓存最左边的节点，使得选择下一个任务的操作非常快。

调度周期与最小粒度。 完全公平调度器没有固定的时间片。它定义了一个目标调度延迟：在这段时间内，每个就绪任务都应当至少运行一次。每个任务在一个调度周期中能够运行的时间，按照其权重占所有就绪任务总权重的比例来分配。当就绪任务非常多时，每个任务分到的时间会变得很短，为了避免过于频繁的上下文切换，调度器设置了一个最小粒度，每个任务每次至少运行这么长的时间。

睡眠任务的处理。 一个长时间处于睡眠状态的任务，其虚拟运行时间会远小于其他一直在运行的任务。如果它醒来后直接以原来的虚拟运行时间参与调度，就会在很长一段时间内独占 CPU。为了避免这种情况，调度器会将刚醒来的任务的虚拟运行时间，调整为接近当前就绪任务中的最小值，并给予少量的补偿。这样，刚醒来的交互式任务能够较快地得到运行，但不会无限制地独占 CPU。

基于截止时间的公平调度

近年来，Linux 内核将完全公平调度器替换为一种新的调度算法，称为最早合格虚拟截止时间优先（Earliest Eligible Virtual Deadline First，EEVDF）。

完全公平调度器在长期的公平性上表现良好，但在延迟的控制上存在一些不足：对于需要快速响应的任务，它缺乏一个清晰的机制来保证它们能够及时运行，因此积累了大量启发式的调整规则，行为难以预测。

新算法在保持公平性的基础上，引入了两个概念：

• 合格性：一个任务只有在它获得的服务不超过其应得的公平份额时，才是"合格"的，可以被调度。这保证了没有任务能够长期占用超过其份额的 CPU 时间；
• 虚拟截止时间：每个任务根据其每次请求的运行时长，计算出一个虚拟的截止时间。在所有合格的任务中，调度器选择虚拟截止时间最早的任务运行。

这样，那些每次只需要运行很短时间的任务，例如交互式任务，其虚拟截止时间会更早，从而能够更快地获得 CPU，即获得更低的延迟；而它们获得的总 CPU 时间仍然受到公平份额的约束，不会因此占用更多资源。新算法用一个更有原则的框架，取代了许多零散的启发式规则，使调度行为更加清晰和可预测。

其他操作系统的调度器

其他主流操作系统的调度器，大多采用了基于优先级的多级队列设计：

• 一些系统使用数十个优先级级别，分为普通优先级和实时优先级两个范围；
• 对于前台窗口所属的进程、刚刚完成 I/O 的线程、等待用户输入后被唤醒的线程，会临时提升其优先级，以改善交互的响应速度；
• 随着线程连续运行，临时提升的优先级会逐渐衰减回其基础优先级。

一些移动和桌面操作系统还引入了服务质量等级的概念：应用程序为不同的任务声明其用途，例如直接响应用户交互的任务、用户发起但可以稍等的任务、后台维护任务。调度器根据这些声明，决定任务的优先级、运行在哪种类型的处理器核心上，以及使用的频率和功耗策略。

五、多核调度

现代处理器普遍具有多个核心，调度器不仅要决定"何时"运行哪个任务，还要决定"在哪个核心上"运行。

全局队列与每核队列

一种简单的做法是使用一个全局的就绪队列，所有核心都从这个队列中选择任务。这种方式天然地实现了负载均衡，但存在明显的问题：

• 所有核心访问同一个队列需要加锁，在核心数量较多时，锁的争用会成为严重的瓶颈；
• 任务可能在不同的核心之间频繁迁移，丢失缓存中的数据。

因此，现代操作系统普遍为每个核心维护一个独立的就绪队列。每个核心只从自己的队列中选择任务，大部分调度操作无需与其他核心同步，扩展性好；任务倾向于一直在同一个核心上运行，缓存的局部性好。

处理器亲和性

任务在一个核心上运行一段时间后，该核心的缓存中积累了大量这个任务的数据。如果将它迁移到另一个核心上运行，这些缓存数据就无法再利用，需要重新从内存中加载。

处理器亲和性（Processor Affinity）是指调度器倾向于让任务继续在它上次运行的核心上运行，以利用缓存中已有的数据。这称为软亲和性。

用户或程序还可以显式地指定一个任务只能在某些特定的核心上运行，这称为硬亲和性或CPU 绑定。这在高性能计算、低延迟的网络应用、数据库等场景中常被使用，以获得更稳定、可预测的性能。

负载均衡

使用每核队列后，可能出现负载不均衡的情况：某些核心的队列中有大量任务在等待，而另一些核心却处于空闲状态。调度器需要通过负载均衡在核心之间迁移任务：

• 推送迁移：一个后台的负载均衡过程定期检查各个核心的负载，将任务从繁忙的核心推送到空闲的核心；
• 拉取迁移：当一个核心变为空闲时，主动从其他繁忙的核心上"窃取"任务来运行。

负载均衡需要在均衡负载和保持亲和性之间进行权衡。过于积极的迁移会破坏缓存的局部性，过于保守的迁移则会导致部分核心空闲而其他核心过载。

调度域

现代计算机的处理器拓扑结构往往是层次化的：

• 一个物理核心可能支持多个硬件线程，即同时多线程技术，它们共享核心的执行单元和一级、二级缓存；
• 多个核心组成一个处理器芯片，共享三级缓存；
• 多个处理器芯片组成一个非一致内存访问节点，或者一台机器有多个这样的节点，每个节点有自己的本地内存，访问其他节点的内存延迟更高。

在这样的拓扑中，将任务迁移到不同的位置，代价差别很大：在共享缓存的硬件线程之间迁移，几乎没有缓存损失；在不同的处理器芯片之间迁移，会丢失三级缓存中的数据；在不同的内存节点之间迁移，任务之后访问原来的内存时都需要跨节点，延迟显著增加。

调度器将这种拓扑结构组织为多层的调度域：在底层的调度域中，例如共享缓存的核心之间，负载均衡更加积极和频繁；在高层的调度域中，例如不同的内存节点之间，负载均衡更加保守，只有在负载严重失衡时才进行迁移。

对于非一致内存访问的架构，调度器还会尽量让任务运行在其内存所在的节点上，或者在任务长期运行在某个节点上时，将其内存迁移到该节点。

同时多线程的影响

同时多线程技术让一个物理核心看起来像是两个或更多的逻辑处理器。但这些逻辑处理器共享执行资源，两个任务同时运行在同一个物理核心的两个硬件线程上时，各自的性能都会低于独占一个物理核心的情况。

因此，当系统负载不高时，调度器应当优先将任务分散到不同的物理核心上，而不是将它们集中在同一个物理核心的多个硬件线程上。

在安全方面，运行在同一个物理核心的不同硬件线程上的任务，可能通过共享的硬件资源相互泄露信息。为此，一些系统提供了核心调度功能，确保只有相互信任的任务，例如属于同一个用户或同一个虚拟机的任务，才会同时运行在同一个物理核心上。

异构处理器

越来越多的处理器采用异构设计：在同一个芯片上集成了高性能的大核和高能效的小核。大核的单线程性能更强，但功耗更高；小核的性能较弱，但能效更好。

在这样的处理器上，调度器需要考虑：

• 哪些任务对性能敏感，应当运行在大核上，例如前台的交互任务；
• 哪些任务可以运行在小核上以节省能量，例如后台的同步和维护任务；
• 任务的负载会随时间变化，需要在大核和小核之间动态地迁移。

处理器硬件通常会向操作系统提供关于每个任务在不同类型核心上运行特征的反馈信息，帮助调度器做出更好的决策。能耗感知调度会综合考虑性能需求和能量消耗，选择在满足性能要求的前提下，总能耗最低的放置方式。

六、优先级反转

问题的产生

在使用优先级调度和锁的系统中，可能出现一种称为优先级反转（Priority Inversion）的问题。

假设有三个任务，优先级从高到低分别为甲、乙、丙：

1. 低优先级的任务丙获得了一把锁，正在执行临界区的代码；
2. 高优先级的任务甲就绪了，抢占了丙。甲运行一段时间后，需要获取同一把锁，但锁被丙持有，于是甲进入阻塞，等待丙释放锁；
3. 此时，调度器应当让丙继续运行，以便它尽快释放锁。但中等优先级的任务乙就绪了，由于乙的优先级高于丙，乙抢占了丙；
4. 只要乙一直在运行，丙就无法运行，也就无法释放锁，甲就只能一直等待。

结果是，高优先级的任务甲，实际上被一个与它毫无关系的中等优先级任务乙所阻塞。系统的行为与优先级的设定完全相反。如果存在多个中等优先级的任务，甲的等待时间甚至可能是无限的。

历史上，一次著名的火星探测任务中，着陆器的计算机系统就曾因为优先级反转问题而反复重启。工程师最终通过远程修改系统配置，启用了优先级继承功能，解决了这一问题。

解决方法

优先级继承（Priority Inheritance）：当一个高优先级任务因为等待某把锁而阻塞时，持有这把锁的低优先级任务临时继承高优先级任务的优先级。这样，中等优先级的任务无法再抢占它，它能够尽快执行完临界区并释放锁。释放锁后，其优先级恢复原值。

优先级天花板（Priority Ceiling）：为每把锁预先设定一个天花板优先级，等于所有可能使用这把锁的任务中最高的优先级。任何任务一旦获取了这把锁，其优先级立即提升到天花板优先级。这种方法不仅能够避免优先级反转，还能够防止某些类型的死锁，但需要预先知道每把锁会被哪些任务使用，主要用于实时系统。

通用系统中的类似问题

即使在不使用严格优先级的通用系统中，类似的问题也会以其他形式出现：一个重要的任务等待一把锁，而持有锁的任务由于优先级较低或者所在的控制组的资源配额已经耗尽，得不到运行的机会，导致重要任务被长时间阻塞。

在用户态程序中，自旋锁还可能带来另一个问题：如果持有锁的线程被调度器抢占，其他等待这把锁的线程会持续地自旋，白白消耗 CPU 时间，而持有锁的线程却无法运行以释放锁。因此，在用户态程序中，通常更适合使用在等待时能够让出 CPU 的锁，或者在自旋一段时间后转为阻塞等待的锁。

七、实时调度

实时系统的要求

实时系统的正确性，不仅取决于计算结果是否正确，还取决于结果是否在规定的截止时间之前产生。

• 硬实时系统：错过截止时间会导致严重的后果，例如飞机的飞行控制、汽车的安全气囊、工业控制系统、心脏起搏器。任务必须在任何情况下都满足截止时间；
• 软实时系统：偶尔错过截止时间是可以接受的，只会导致服务质量下降，例如音视频播放、游戏、网络通话。

对于实时系统，重要的不是平均性能，而是最坏情况下的行为和可预测性。

周期性任务

许多实时任务是周期性的：每隔固定的时间间隔被激活一次，每次需要一定的执行时间，并且必须在下一次激活之前，或者在规定的截止时间之前完成。

速率单调调度

速率单调调度（Rate Monotonic Scheduling）是一种静态优先级的实时调度算法：周期越短的任务，优先级越高。

可以证明，在所有静态优先级的调度算法中，速率单调调度是最优的：如果一组周期性任务能够被任何静态优先级算法调度，那么速率单调调度也一定能够调度它们。

速率单调调度还有一个简单的可调度性判定条件：对于 n 个任务，如果它们的总 CPU 利用率，即每个任务的执行时间与周期之比的总和，不超过 n × (2^(1/n) − 1)，那么这组任务一定可以被调度。当 n 趋于无穷时，这个界限约为 69.3%。这是一个充分条件，许多利用率更高的任务组实际上也是可调度的，需要进行更精确的分析。

最早截止时间优先

最早截止时间优先（Earliest Deadline First，EDF）是一种动态优先级的实时调度算法：在每个时刻，总是选择截止时间最早的任务运行。

在单处理器上，最早截止时间优先是最优的：只要总的 CPU 利用率不超过 100%，就能保证所有任务都满足截止时间。这比速率单调调度的利用率界限高得多。

但最早截止时间优先也有其缺点：实现比静态优先级更复杂；更重要的是，当系统过载时，其行为难以预测，可能导致大量任务连锁地错过截止时间，而速率单调调度在过载时，至少能保证高优先级的任务不受影响。

通用操作系统中的实时支持

通用操作系统通常也提供一定程度的实时调度支持：

• 实时优先级类：使用固定优先级的调度策略，包括先来先服务和时间片轮转两种。实时任务的优先级总是高于所有普通任务，只要有实时任务就绪，普通任务就无法运行；
• 截止时间调度类：一些系统还提供基于最早截止时间优先的调度类，任务需要声明其执行时间、截止时间和周期，系统会在接纳新任务之前进行可调度性检查，拒绝那些会导致系统过载的任务。

使用实时优先级需要格外谨慎：一个陷入死循环的实时任务，会使所有普通任务都无法运行，导致系统失去响应。为此，操作系统通常会为实时任务设置一个运行时间上限，在每个周期中，保留一小部分 CPU 时间给普通任务。

内核的可抢占性

即使调度器设计得再好，如果内核本身的代码不能被抢占，实时性也无法保证：当一个低优先级的任务正在执行一个耗时的系统调用时，高优先级的任务即使已经就绪，也必须等待系统调用完成。

为此，现代操作系统的内核大多支持不同程度的内核抢占：内核代码在不持有某些关键锁的时候，可以被更高优先级的任务抢占。对于有严格实时要求的场景，还有一些针对内核的修改，进一步缩短不可抢占的区间，将中断处理转化为可调度的线程，并将大部分自旋锁替换为支持优先级继承的睡眠锁。这些修改已经逐步合并进了主线内核，使得通用操作系统也能够用于许多软实时甚至部分硬实时的场景。

八、资源控制与容器

控制组

在服务器和云计算环境中，往往需要对一组任务整体进行资源控制，而不是对单个任务。例如，限制一个容器、一个用户或一个服务能够使用的 CPU 资源，防止它影响其他工作负载。

控制组（Control Groups）机制将任务组织成层次化的组，调度器可以对每个组进行资源控制：

• 按权重分配：每个组有一个权重。当 CPU 资源紧张时，各个组按照权重的比例分配 CPU 时间。在组的内部，再按照组内各任务的权重进一步分配。这称为组调度，它使得公平性在组的层面上实现：一个运行了 100 个线程的组，并不会因为线程数量多而比只运行 1 个线程的组获得更多的 CPU 时间，只要它们的权重相同；
• 按配额限制：为一个组设定每个周期内最多可以使用的 CPU 时间。例如，每 100 毫秒最多使用 50 毫秒，相当于将其限制在半个核心的计算能力。即使系统中有空闲的 CPU，组内的任务用完配额后也必须等待下一个周期。

配额限制带来的问题

基于配额的 CPU 限制，在实践中可能导致一些意想不到的问题。

假设一个容器被限制为每 100 毫秒使用 100 毫秒的 CPU 时间，即一个核心的计算能力。如果容器中的应用有多个线程，在一个周期的开始，多个线程同时在多个核心上运行，可能在 25 毫秒内就用完了全部 100 毫秒的配额，随后在剩余的 75 毫秒里，所有线程都被限流，无法运行。

从平均 CPU 使用率来看，这个容器可能远未达到其限制，但它的请求延迟却会因为周期性的限流而出现大幅的波动，尾部延迟显著增加。

应对的方法包括：根据应用实际的并发度合理设置配额；缩短配额的周期，或者允许配额在周期之间有一定的累积和突发；对于延迟敏感的应用，考虑只使用基于权重的分配而不设置硬性的配额上限；在应用层面，根据容器的配额而不是机器的核心数来设置线程池的大小。

九、调度对应用的影响

理解调度的原理，有助于解释许多应用层面的性能现象，并指导应用的设计。

线程数量不是越多越好。 对于 CPU 密集型的工作，线程数量超过可用的 CPU 核心数后，并不会带来更多的计算能力，反而会增加上下文切换的开销和缓存的竞争。对于 I/O 密集型的工作，可以使用更多的线程，或者使用异步 I/O 模型，以较少的线程处理大量的并发请求。

注意运行队列的长度。 系统负载、运行队列长度等指标，反映了有多少任务在等待 CPU。CPU 使用率不高，但运行队列很长，往往意味着存在锁竞争或者配额限流等问题。

关注调度延迟。 一个任务从就绪到实际开始运行之间的等待时间，称为调度延迟。对于延迟敏感的应用，过高的调度延迟会直接体现为请求处理时间的增加。可以借助操作系统提供的跟踪工具，测量和分析调度延迟的分布。

避免忙等待。 在等待某个条件时，持续地循环检查，会占用 CPU 时间，影响其他任务的运行。应当使用能够阻塞等待的同步原语，让调度器将 CPU 分配给其他任务。

利用亲和性。 对于需要稳定低延迟的应用，可以考虑将关键线程绑定到专门的 CPU 核心上，并将其他任务和中断处理从这些核心上移走，减少干扰。

合理设置优先级。 对于后台的批处理任务，可以降低其优先级，让交互式任务和在线服务优先获得 CPU。但应当谨慎地使用实时优先级，避免一个异常的任务让整个系统失去响应。

理解垃圾回收与调度的交互。 在带有垃圾回收的语言运行时中，垃圾回收线程需要获得 CPU 才能完成工作。如果 CPU 资源被严格限制，垃圾回收可能被延迟，导致内存占用上升，或者应用的停顿时间增加。

结语

调度器是操作系统中对系统行为影响最深远的组件之一。它在每一个时刻，从众多等待运行的任务中做出选择，决定了 CPU 时间如何在任务之间分配，进而决定了系统的吞吐量、响应速度和公平性。

从先来先服务、最短作业优先、时间片轮转，到多级反馈队列和比例份额调度，经典的调度算法揭示了调度中的基本权衡。现代操作系统的调度器，以虚拟运行时间和虚拟截止时间为核心，在保证公平的同时兼顾延迟；在多核和异构处理器上，调度器还需要考虑缓存的局部性、处理器的拓扑结构和能量的消耗；在实时系统中，调度的目标变为保证每个任务都能满足其截止时间；在云计算环境中，调度器又承担起在不同的工作负载之间隔离和分配资源的职责。

对于应用开发者而言，调度器通常是透明的。但当应用的性能出现难以解释的波动，延迟出现意外的毛刺，或者在容器中的表现与在物理机上相差甚远时，理解调度器的工作原理，往往能够帮助找到问题的根源，并做出更合理的设计决策。