CPU 调度：让有限核心接住不断到来的工作

你在电脑上点开一个新标签页，音乐没有停，下载任务还在跑，聊天窗口也能立刻弹出来。看上去，所有程序像是在同时前进。可如果这台机器只有四个 CPU 核心，同一时刻真正能执行的线程就只有少数几个。其余任务不是消失了，而是在等操作系统决定：下一小段处理器时间应该交给谁。

这个决定就是 CPU 调度。它看似只是“从队列里挑一个任务”，实际上夹在几组互相拉扯的目标之间：交互程序希望马上响应，批处理任务希望尽快做完，后台任务不能永远饿着，实时任务还可能带着明确的截止时间。调度器每偏向一边，就要在另一边付出代价。

CPU 调度器从就绪队列中选择进程，并在运行、等待 I/O 和完成状态间组织执行。

从“同时运行”的错觉说起

先想一个最容易体会的场景。你在浏览器里滚动网页时，页面渲染线程需要一小段 CPU 时间；接着音乐播放器要解码下一块音频；随后输入法收到按键，要尽快给出候选词。每个任务单独看都没有占满一个核心，但它们醒来的时刻并不整齐。操作系统要把这些零散请求拼进一条连续的执行时间线。

CPU 突发与 I/O 等待

大多数任务不会从开始到结束一直计算。它们通常在两种阶段之间反复切换：

• CPU 突发：线程真正执行指令，例如解析数据、压缩图像或更新界面。
• I/O 等待：线程等待磁盘、网络、键盘或其他设备返回结果，此时继续占着 CPU 没有意义。

交互程序常见的形态是许多很短的 CPU 突发，中间夹着等待输入或网络的时间；视频编码、科学计算这类工作则常出现较长的 CPU 突发。这里不能简单地说哪一种“更重要”。短突发若迟迟排不上，会让用户觉得系统卡顿；长突发若总被打断，缓存局部性和总体吞吐量又会变差。

I/O 密集型与 CPU 密集型进程呈现不同的 CPU 与 I/O 突发节奏。

从状态变化到调度时机

线程处于运行状态时，下面几类事件可能让调度器重新考虑人选：

1. 当前线程发起阻塞式 I/O，主动进入等待状态。
2. 当前线程执行完毕，退出处理器。
3. 时间片耗尽，时钟中断把当前线程送回就绪状态。
4. 一个等待中的线程被 I/O 完成事件唤醒，重新变得可运行。
5. 更高优先级或截止时间更紧的任务到达。

前两种情况中，当前线程已经不能继续运行，系统必须换人。后三种情况里，系统可以选择让当前线程继续，也可以抢走 CPU。这正是非抢占式调度与抢占式调度的分界。

非抢占式调度允许线程一直执行到阻塞、退出或主动让出 CPU。它的控制路径简单，切换少，但一个长任务可能让后面的短任务干等。抢占式调度允许内核在合适的时刻中断当前线程，交给另一个任务。桌面和服务器操作系统普遍依赖抢占来维持响应性，不过抢占越频繁，保存现场、恢复现场和重建缓存热度的成本就越高。

调度器与分派器各做什么

可以把一次切换拆成两个角色。调度器负责选择：它检查可运行任务、优先级、时间份额、截止时间和 CPU 位置，决定下一位是谁。分派器负责执行：保存旧线程的寄存器和程序计数器，恢复新线程的上下文，必要时切换地址空间，最后跳回新线程上次停下的位置。

从停止一个线程到另一个线程真正执行之间的时间叫分派延迟。它不是一个固定常数。切换是否跨地址空间、缓存和地址转换缓存是否仍然有效、处理器是否要跨核心迁移任务，都会改变实际代价。

先决定“好”是什么意思

调度算法没有脱离场景的总冠军。批处理服务器、手机前台界面和工业控制器对“好”的定义并不一样。比较算法前，我们要先把指标说清楚。

五个常用时间指标

假设任务在时刻 $a$ 到达，在时刻 $f$ 完成，实际占用 CPU 的总时间为 $b$，第一次获得 CPU 的时刻为 $s$，那么：

周转时间看的是整项工作多久交付，响应时间只看多久产生第一次可见进展。一个搜索请求可以在 50 毫秒内返回首屏结果，却花 2 秒才把所有结果传完；这时响应时间很好，周转时间却不算短。

另外两个系统级指标是 CPU 利用率和吞吐量。利用率描述观察窗口内 CPU 忙碌的比例，吞吐量描述单位时间完成多少项工作。把利用率推到接近 100% 不等于体验一定好：当新任务到达速度接近系统处理上限，就绪队列会拉长，响应时间可能突然恶化。

平均值藏不住的尾部

平均等待时间很方便，却可能掩盖少数极慢请求。九十九个任务都在 5 毫秒内响应，一个任务等待 5 秒，平均值仍不算夸张，但那个倒霉用户已经明确感到故障。因此真实系统还会观察中位数、百分位延迟、截止时间错失率和长期公平性。

公平也不等于每个线程拿到完全相同的时间。两项任务权重不同，合理结果可能是按权重分配；一项任务正在等待用户输入，另一项任务在后台批量计算，调度器也可能优先缩短前者的唤醒延迟。公平是一套明确的分配规则，不是机械平分。

经典算法其实在选择不同的代价

为了看清算法本身，我们先从单核、任务 CPU 时间已知、暂不考虑 I/O 的简化模型出发。这个模型不完全真实，但它能把每种规则最在意的东西暴露出来。

经典调度算法在响应、公平和上下文切换开销之间做出不同取舍。

先来先服务：排队最简单，护航最明显

先来先服务按照进入就绪队列的顺序执行，通常是非抢占式的。它像窗口排队：先到的人先办，规则清楚，实现成本低。

假设三个任务几乎同时到达，CPU 时间分别为 20、2、2 毫秒。若 20 毫秒的任务排在最前面，后两个短任务只能跟在后面等。长任务像一辆慢车带着一串快车，这就是护航效应。算法没有偏袒谁，但平均等待时间和交互体验都会受抵达顺序影响。

最短作业优先：平均等待很漂亮，未来却看不见

最短作业优先总挑预计 CPU 突发最短的任务。在一批同时到达、长度已知且不抢占的任务里，把短任务排在前面可以最小化平均等待时间。抢占版本叫最短剩余时间优先：新任务到达后，如果它比当前任务的剩余时间更短，就立即抢占。

困难不在排序，而在“预计”二字。操作系统通常不知道下一次 CPU 突发会持续多久，只能用历史行为猜测。一个常见的平滑思路是：

其中 $t_n$ 是刚发生的真实突发长度，$\tau_n$ 是此前的预测，$\alpha$ 决定新观察占多大权重。$\alpha$ 较大，预测追随最近变化更快；较小则更信任长期历史。预测错了，算法的优势也会缩小。若短任务持续到达，长任务还可能饥饿。

时间片轮转：给每个人机会，但机会不是免费的

时间片轮转让可运行任务组成一个循环队列。任务最多运行一个时间片，没做完就回到队尾。假设有 $n$ 个任务且时间片为 $q$，在忽略切换开销的理想模型里，每个任务大约每隔 $(n-1)q$ 就能再次获得机会。

时间片太大时，轮转逐渐接近先来先服务，交互任务要等很久；时间片太小时，系统频繁切换，真正做事的比例下降，缓存也更容易变冷。这里没有一个可以抄到所有机器上的固定毫秒数。上下文切换成本、任务突发分布、核心速度和交互目标都会影响选择。

优先级调度：紧急任务先行，也可能饿死别人

优先级调度总选择优先级最高的可运行任务，可以抢占，也可以不抢占。它能表达“声音播放不能轻易断”“后台索引可以慢一点”这类差异，但持续到来的高优先级工作可能让低优先级任务无限等待。

老化会随着等待时间提升任务的有效优先级，让它迟早能排到前面。另一类麻烦是优先级反转：高优先级任务等待一把锁，而锁被低优先级任务持有；中优先级任务不断抢占低优先级任务，间接拖住最高优先级者。优先级继承会临时提升锁持有者，让它尽快完成临界区并释放锁。

多级队列与多级反馈队列：先分类，再根据行为修正

多级队列把任务按类别放进不同队列，例如前台交互、普通服务和后台批处理。每个队列可以使用自己的算法，队列之间再按固定优先级或时间份额竞争。问题是任务一旦被分错类，很难自动纠正。

多级反馈队列允许任务移动。新任务通常从高优先级队列开始；如果连续用完整个时间片，系统把它降到更低队列，并可能给它更长的时间片；经常很快阻塞的任务留在高层，以便 I/O 完成后迅速响应。为了防止底层任务饿死，系统可以周期性提升所有任务，或按等待时间逐步上调。

反馈规则能在不知道未来突发长度的情况下逼近“短任务优先”，代价是参数很多。队列数量、各层时间片、降级条件和提升周期都会改变结果。工作负载换了，原先好用的参数可能不再合适。

比例份额：公平可以按权重定义

有些系统并不想把任务分成谁绝对压过谁，而是希望长期按比例分 CPU。假设甲的权重是 2，乙的权重是 1，那么在两者都持续可运行时，目标可以是甲大约得到三分之二的处理器时间，乙得到三分之一。这个比例不要求每个短时间窗口都精确成立，但观察时间足够长后，实际份额应逐渐靠近目标。

份额还可以分层计算。一个用户启动一百个线程，不应该因此自动获得另一个只启动一个线程的用户一百倍 CPU；调度器可以先在用户组之间分份额，再在组内线程之间分。代价是“公平对象”变复杂了：按线程、进程、用户还是容器分配，会得到完全不同的结果。

动手比较算法

下面的实验把同一组任务交给先来先服务、最短作业优先和时间片轮转。修改任务长度和时间片，再观察平均等待与平均周转如何变化。所有计算都在当前页面完成，不依赖网络。

线程才是内核真正排队的对象

日常表达常说“进程获得 CPU”，但现代操作系统真正调度的通常是可执行线程。一个浏览器进程可以有界面线程、网络线程和渲染工作线程；它们共享进程资源，却可以分别进入就绪、运行或等待状态。

用户线程与内核线程

用户级线程库可以在进程内部安排协程或用户线程。只要切换不进入内核，成本可以很低。不过内核看不到这些用户级执行单元时，只能调度它认识的内核线程。若一个内核线程背后承载许多用户线程，这些用户线程之间的公平性要由运行库负责。

线程一对一映射到内核线程时，每个线程都能独立参与系统调度，也能在多个核心上并行。代价是创建、切换和内核数据结构的成本更高。实际语言运行时常把两层结合起来：少量内核线程承载大量轻量任务，运行时做本地调度，内核做全局处理器分配。

竞争范围

进程竞争范围指线程只与同一进程中的其他用户线程竞争某个执行位置；系统竞争范围指内核线程与全系统的可运行线程竞争 CPU。理解这一区别很重要：应用运行时里“最高优先级”的任务，不一定比另一个进程的内核线程更先运行，它可能只是在本进程的工作队列中排得更靠前。

POSIX 策略表达的语义

POSIX 用策略和优先级描述实时线程的基本行为。SCHED_FIFO 中，同一静态优先级的线程按先进先出排队，运行线程不会因为普通时间片耗尽而自动轮转；它会运行到阻塞、让出、退出，或被更高优先级线程抢占。SCHED_RR 在相同优先级的 FIFO 规则上增加时间片，让同级线程轮换。SCHED_OTHER 则把普通分时调度的细节留给具体系统实现。

“实时策略”不等于任务一定按时完成。若高优先级线程不阻塞地死循环，它可以压住普通任务；若任务集合本来就要求超过处理器能力，再强的优先级也造不出额外时间。实时保证还需要可调度性分析、资源预留和受控的临界区。

多核之后，选择“在哪个核心运行”同样重要

单核调度只需要回答下一位是谁。多核系统还要回答：任务放在哪个核心？要不要迁移？一个核心很忙、另一个核心很闲时，看上去应该立刻搬任务，但迁移并不免费。

多核调度既要组织共享或私有队列，也要权衡负载均衡与处理器亲和性。

全局队列还是每核队列

全局就绪队列让所有核心从同一处取任务，负载天然容易摊开，但多个核心会竞争队列锁，共享数据也会在缓存之间来回移动。每核队列降低了争用，常用路径更局部，不过某个核心可能堆满任务，另一个核心却已经空闲。

现代调度器通常组合两种思路：任务先进入某个 CPU 的运行队列，调度域再定期或在核心空闲时做负载均衡。忙碌核心可以把任务推出去，空闲核心也可以从别处拉取工作。均衡频率太低会浪费核心，太高又会产生迁移成本。

处理器亲和性为何有价值

线程在一个核心运行后，它用过的指令和数据可能还留在该核心附近的缓存中。让它继续留在原核心，这种软亲和性往往能减少缓存未命中。硬亲和性则明确限制线程只能在哪些 CPU 上运行，常用于隔离、设备中断配合或性能实验。

亲和性与均衡直接冲突。坚持不迁移能保护缓存，却可能让负载倾斜；积极迁移能填满空闲核心，却可能让任务每次换核都重新预热。在 NUMA 机器上，任务迁移到另一个节点还可能继续访问原节点内存，远程访存延迟会把均衡收益吃掉。

同时多线程不等于两个完整核心

同时多线程让一个物理核心暴露多个逻辑 CPU。两个硬件线程共享部分执行资源和缓存，所以把两项重计算任务塞进同一物理核心，效果往往不如放到两个独立物理核心。调度器需要理解拓扑：逻辑线程、核心、缓存簇、NUMA 节点不是同一级别的资源。

异构核心让“空闲”不再等于“合适”

手机和越来越多的个人电脑包含性能不同的核心。高性能核心适合延迟敏感或计算强的工作，能效核心适合后台与轻负载。调度器除了估算任务利用率，还要估算 CPU 容量、能耗与热约束。把任务放上最快核心可能缩短延迟，却会更耗电、更快触发温度限制；一味追求省电又可能让界面掉帧。

亲手观察迁移的得失

下面的模型用四个核心和八个任务演示“保持亲和性”与“积极均衡”的差别。它不是某个真实内核的实现，但能直观看到迁移次数、最大核心负载和缓存热度如何互相拉扯。

实时调度关心的是“能否赶上”，不只是“平均多快”

普通桌面程序偶尔慢几十毫秒，用户可能只觉得一次卡顿。飞行控制、工业采样或音频缓冲若错过时刻，后果可能是数据失效、声音爆裂，甚至控制错误。实时系统因此关注时间上界和截止时间，而不是只看平均吞吐量。

实时任务是否成功，关键在于能否在截止时刻前完成。

硬实时与软实时

硬实时任务把错过截止时间视为不可接受的系统失败，设计时必须给出可验证的时间保证。软实时任务允许偶发超时，但超时会降低结果价值，例如视频帧来晚了就应丢弃，而不是继续堆积。两者的区别不在“快多少”，而在截止时间错失是否可以容忍。

一次事件从发生到任务真正处理，中间至少包含中断延迟和分派延迟。中断延迟是硬件事件到处理程序开始之间的时间，分派延迟是调度决策、抢占内核路径和切换上下文所花的时间。实时内核会缩短不可抢占区、约束中断处理时间，并避免运行时出现不可预测的缺页和动态分配。

周期任务模型

常用模型把任务 $i$ 表示成执行时间 $C_i$、周期 $T_i$ 和相对截止时间 $D_i$。每经过一个周期，任务释放一个新作业；每个作业最多需要 $C_i$ 的 CPU 时间，并希望在释放后的 $D_i$ 内完成。单个任务的处理器利用率是：

所有任务利用率之和超过 1 时，单核无论怎样排列都不可能完成全部工作。但利用率不超过 1 只是最基本的容量检查，能否调度还取决于截止时间、阻塞、抢占成本和任务模型。

速率单调：周期越短，静态优先级越高

速率单调调度给周期更短的任务更高固定优先级。它适合周期等于截止时间、任务相互独立、可抢占且执行时间有可靠上界的经典模型。在这些假设下，$n$ 个任务满足下面的充分条件时一定可调度：

当任务数增多，右侧趋近 $\ln 2$。这是一条保守的充分条件，不是说利用率超过它就必然失败；精确的响应时间分析可能证明更高利用率的任务集仍能按时完成。

最早截止时间优先：动态优先级随时间变化

最早截止时间优先每次选择绝对截止时间最近的就绪作业。对理想的单核、可抢占、独立且截止时间等于周期的周期任务模型，总利用率不超过 1 时，EDF 可以调度任务集。离开这些假设后，不能只凭一个利用率数字下结论。

EDF 能把处理器用得更紧，但过载时可能在一段时间内连续错过多个截止期。固定优先级调度在过载时更容易保护最关键的高优先级任务。选择哪种策略，取决于系统希望“尽量完成更多任务”，还是希望“无论如何先守住关键任务”。

预算、准入与带宽隔离

真实系统不会只写一个截止时间就相信任务会自律。预算机制约束任务在每个周期最多消耗多少 CPU；用完预算的任务会被限制到下一周期。准入控制在接纳新实时任务前检查现有承诺，若容量不足就拒绝，而不是让所有任务一起超时。

Linux 的截止时间调度把最早截止时间选择与恒定带宽服务器结合起来。任务声明运行预算、截止时间和周期，内核用预算限制越界任务，并对新参数做可行性检查。这说明“截止时间优先”只是选择规则，隔离和承诺还需要另一层机制。

比较固定优先级与动态截止时间

下面的实验提供三项周期任务。选择速率单调或最早截止时间优先，模型会逐毫秒安排作业，并标出有没有错过截止时间。你可以提高某项任务的执行时间，观察系统从可调度变为过载的过程。

现代操作系统不会只运行一种算法

真实内核面对普通任务、实时任务、截止时间任务、空闲任务和受资源组约束的任务，通常会建立调度类层次。先决定哪一类有资格运行，再在类内部应用对应规则。这样可以扩展策略，也能让高约束任务明确压过普通分时任务。

公平调度优先运行已用时间较少的任务，并在任务状态变化后动态再平衡。

Linux：从 CFS 的公平思想走向 EEVDF

讲 Linux 普通任务调度时，经常会看到“CFS 按最小虚拟运行时间选择红黑树最左节点”的概括。它准确描述了很长一段时期的核心思路，但不能当成当前演进的终点。Linux 从 6.6 起逐步让普通调度路径转向 EEVDF，也就是最早合格虚拟截止时间优先。

公平思想仍然保留。调度器根据任务实际得到的 CPU 份额计算虚拟运行量和滞后值：正滞后表示任务相对“欠”了处理器时间，负滞后表示它已经多拿了一些。调度器先从合格任务中筛选，再选虚拟截止时间最早者。较短的请求时间片可以对应较早的虚拟截止时间，因此延迟敏感任务有机会更快响应，同时长期份额仍受公平模型约束。

普通任务的 nice 值影响相对权重，不是一个保证“立刻执行”的绝对优先级。Linux 还把普通、批处理、空闲、实时 FIFO、实时轮转和截止时间策略放进不同调度类。实时 FIFO 或轮转任务若配置不当，仍可能压制普通任务；截止时间任务则需要预算参数和准入检查。

Windows：先看线程优先级，再在同级轮转

Windows 为线程计算调度优先级，范围从 0 到 31，其中普通应用主要处在可变优先级范围，实时范围位于更高区间。系统从最高的非空优先级选线程；同一优先级的就绪线程按时间片轮转。更高优先级线程一旦就绪，可以抢占当前较低优先级线程。

线程的基础优先级由进程优先级类别和线程相对级别共同决定。系统还会针对输入、等待完成等事件做动态提升，帮助刚被唤醒的交互线程更快运行。提升会逐渐衰减，避免普通任务长期占据高位。

“实时”类别这个名字很容易让人误会。它拥有很强的调度优势，却不会自动提供完整的硬实时保证。把持续计算的线程放到过高优先级，可能妨碍输入、磁盘刷新和其他系统工作。高优先级适合短而明确的紧急工作，不适合拿来粗暴解决性能问题。

Solaris：用调度类表达不同资源政策

Solaris 把可调度的轻量级进程放入不同调度类，包括分时、交互、实时、系统、固定优先级和公平共享。分时类会根据行为动态调整优先级，在交互响应与 CPU 密集任务吞吐之间平衡；公平共享类按项目或资源组的份额分配 CPU，更适合多用户和资源治理；实时与固定优先级类提供更直接的优先级控制。

调度类的价值在于把“谁更紧急”和“谁应得到多少份额”分开表达。一个多租户服务器关心的可能不是单个线程是否公平，而是不同用户组是否拿到约定份额；一个控制系统关心的则是高优先级任务能否在延迟上界内启动。

怎么判断一个调度器真的更好

只拿四五个手算任务比较平均等待时间，适合学习算法，却不足以评价真实系统。工作负载会随时间变化，CPU 突发经常呈长尾分布，多核迁移还会改变缓存与内存访问成本。可靠评估通常要把分析、模拟和实机测量接起来。

解析模型先给出边界

排队模型把 CPU 看成服务台，把可运行任务看成队列中的顾客。若长期平均到达率是 $\lambda$，系统内平均任务数是 $L$，任务在系统内平均停留时间是 $W$，稳定状态下有：

这条关系能帮助我们检查测量是否自洽，却不能单独告诉我们尾部延迟或复杂反馈策略的行为。若到达率接近服务能力，微小波动就可能造成长队列，稳定状态假设也可能失效。

离散事件模拟比较规则

模拟器维护虚拟时钟，生成任务到达、CPU 突发、I/O 完成和时间片耗尽等事件。用同一批输入分别运行多个算法，可以比较等待、响应、切换次数和截止时间错失率。

随机分布便于覆盖大量情形，但必须说明分布假设；真实跟踪能保留某台机器上的突发关系，却可能对别的工作负载没有代表性。最稳妥的做法是同时使用合成压力场景和真实跟踪。

实机测量要看完整成本

实机实验除了记录任务完成时间，还要观察上下文切换、运行队列长度、核心迁移、CPU 利用率、缓存未命中和尾部延迟。对多核系统，只看总利用率会遗漏某个核心过载、其他核心空闲的情况；对交互系统，只看吞吐量会遗漏输入唤醒到首帧呈现的等待。

比较实验必须控制变量。相同硬件、相同输入、相同后台负载和足够长的预热期，才能把差异主要归因于调度设置。否则一次缓存未预热、温度降频或后台更新，就可能比算法差异更大。

用工作负载问题反推策略

选择策略时，可以按下面的顺序思考：

把调度看成一连串可解释的选择

CPU 调度没有神秘到无法理解。任务阻塞时，系统不让核心空等；可运行任务过多时，调度器按一套规则选人；多核环境里，它还要在负载、缓存和能耗之间决定任务位置；实时环境里，选择规则外面还要套上预算、准入和最坏情况分析。

经典算法之所以值得学，不是因为现代内核会原样照搬，而是它们把取舍讲得很干净：先来先服务重顺序，最短作业优先重平均等待，时间片轮转重及时获得机会，优先级调度重紧急程度，多级反馈队列根据行为修正分类，EDF 则把截止时间直接放进决策。

下次电脑在高负载下依然能及时响应鼠标时，你看到的不只是“CPU 很快”。更准确地说，是调度器让短小、刚被唤醒的交互工作及时插进了长任务之间，同时还在偿还其他任务应得的处理器份额。它解决的是有限处理能力与多样时间需求之间的矛盾，代价则是切换、预测、迁移和更复杂的规则。

小练习