上一篇梳理了调度的基本问题：什么时候调度、从哪里选择任务，以及上下文切换如何让 CPU 从一个执行流转向另一个执行流。这一篇继续讨论调度器最核心的决策——就绪队列里有多个任务时，到底应该选择谁？

不同系统追求的目标不同：批处理系统希望提高吞吐量并缩短平均周转时间，交互式系统希望快速响应用户，实时系统则必须满足截止时间。因此，不存在一种算法能在所有场景中同时做到最好。

一、批处理系统中的调度

批处理系统中的作业通常不需要频繁与用户交互，系统可以更关注一批作业的整体完成效率。这里最经典的三种思想是先来先服务、最短作业优先和最短剩余时间优先。

1. 先来先服务（FCFS）

**FCFS（First-Come, First-Served）**按照任务进入就绪队列的先后顺序分配 CPU，队列结构与现实中的排队非常相似：

新任务到达 → 插入队尾
调度任务   → 从队头取出

在经典描述中**，FCFS 通常是非抢占式的**。队首进程获得 CPU 后，会一直运行到完成、主动让出 CPU 或因 I/O 等原因阻塞。阻塞进程重新就绪后，一般重新进入队尾。

就绪队列：[A] [B] [C]
             ↓
CPU 先运行 A

A 阻塞或结束后：
CPU 再运行 B

FCFS 的优势是规则直观、实现简单，并且按照到达顺序看起来很公平。但它存在明显的护航效应（convoy effect）：如果队首是一个很长的 CPU 密集型任务，后面大量短任务或 I/O 密集型任务都要跟着等待。

例如：

A：需要 20ms
B：需要 2ms
C：需要 2ms
D：需要 2ms

FCFS 顺序：A → B → C → D

三个短任务都被 A 挡在后面，平均等待时间会明显增大，I/O 设备也可能因短任务迟迟不能发起下一次 I/O 而空闲。

严格来说，只要队列不断向前移动，标准 FCFS 通常不会让已经排队的任务永久饥饿；它的主要问题是短任务可能被长任务拖延很久，而不是算法天然造成无限期饥饿。

作业调度与 CPU 调度也要区分：作业调度更偏向决定哪些磁盘作业进入内存，CPU 调度则从内存中的就绪任务里选择执行者。

2. 最短作业优先（SJF）

**SJF（Shortest Job First）**每次从候选任务中选择预计运行时间最短的作业。它的直觉是：让短任务尽早离开系统，可以避免许多短任务被少数长任务堵住。

假设四个作业同时到达，运行时间分别为：

作业	运行时间
A	8 分钟
B	4 分钟
C	4 分钟
D	4 分钟

若按 A → B → C → D 执行，完成时间也就是周转时间：

A：8
B：8 + 4 = 12
C：8 + 4 + 4 = 16
D：8 + 4 + 4 + 4 = 20

平均周转时间 = (8 + 12 + 16 + 20) / 4 = 14 分钟

若采用 SJF，顺序变为 B → C → D → A：

B：4
C：4 + 4 = 8
D：4 + 4 + 4 = 12
A：4 + 4 + 4 + 8 = 20

平均周转时间 = (4 + 8 + 12 + 20) / 4 = 11 分钟

在所有作业同时到达、运行时间已知且不考虑其他因素的理想模型下，SJF 可以最小化平均等待时间。

这里的**周转时间（turnaround time）**是：

周转时间 = 完成时间 - 到达时间

它包括排队时间、实际执行时间以及可能的 I/O 等待，而不只是 CPU 真正执行该作业的时间。

SJF 的难点在于：操作系统无法预知一个未来任务准确运行多久。理论分析通常假设运行时间已知；现实中只能依靠用户声明、历史运行记录或过去的 CPU burst 进行估计。

此外，如果短作业持续到来，长作业可能一次次被排到后面，从而发生饥饿。因此实际系统往往还要配合老化、优先级提升或等待时间补偿。

3. 最短剩余时间优先（SRTN / SRTF）

最短剩余时间优先是 SJF 的抢占式版本，常写作 SRTF（Shortest Remaining Time First），部分教材写作 SRTN（Shortest Remaining Time Next）。它比较的不是任务最初的总长度，而是当前还剩多少运行时间。

每当新任务到达或调度时机出现，调度器都会比较所有就绪任务的剩余时间。如果新任务比当前任务剩余时间更短，就立即抢占当前任务。

例如：

A 总共需要 10 分钟，已经运行 5 分钟，还剩 5 分钟
B 此时到达，需要 2 分钟

B 的 2 分钟 < A 剩余的 5 分钟
→ B 抢占 A

B 完成后，如果还有一个剩余 8 分钟的 C，那么调度器会在 A 的 5 分钟与 C 的 8 分钟之间选择 A。

SRTF 能进一步改善短任务的等待与响应，但同样依赖剩余时间估计，并会带来更多抢占和上下文切换；长任务也仍可能因短任务持续到来而饥饿。

二、交互式系统中的调度

交互式系统最在意用户操作能否快速得到反馈。因此，调度器不能让一个长任务长时间独占 CPU，而要让多个任务频繁获得短暂的运行机会。

1. 时间片轮转（RR）

**RR（Round Robin）**为每个就绪任务分配一个固定的时间片（quantum），并按队列顺序轮流运行：

就绪队列：[A] [B] [C]

A 运行一个时间片
├─ 提前结束或阻塞 → 立即运行 B
└─ 时间片耗尽仍可运行 → A 回到队尾

队列变为：[B] [C] [A]

RR 不需要预测任务长度，规则简单，而且每个可运行任务都能周期性得到 CPU，因而非常适合分时和交互场景。

操作系统怎样知道时间片到了？

正在运行的进程不会主动检查自己的时间片，内核也不会在每条指令后读取时钟。抢占依赖独立于当前进程的硬件定时器。

系统启动时，内核会配置硬件定时器，并建立中断号与定时器中断处理程序之间的对应关系。当定时器到期：

用户进程 A 正在运行
        ↓
硬件定时器产生中断
        ↓
CPU 根据中断入口进入内核处理程序
        ↓
内核更新计时信息并检查 A 的运行额度
        ↓
时间片耗尽则标记需要重新调度
        ↓
保存 A 上下文，选择并恢复下一个任务

传统系统可以周期性产生 tick，例如每 1ms 更新一次计数；现代内核也可能使用一次性定时器或无周期时钟设计，但本质相同：由硬件在指定时刻打断当前执行流，让内核重新获得控制权。

定时器不只服务调度，还维护 sleep、网络超时和各种内核定时事件。例如进程等待网络数据并设置 5ms 超时：

A 调用带超时的接收操作
        ↓
暂时没有数据，A 阻塞
        ↓
内核登记超时时刻
        ↓
定时器到期，内核唤醒 A
        ↓
A：阻塞态 → 就绪态

A 是否立即运行仍取决于调度策略。唤醒只让它获得参加调度的资格，并不等于马上占有 CPU。

时间片应该多长？

时间片过短，任务切换频繁，保存和恢复上下文的开销占比过高。假设有效运行 4ms、切换耗时 1ms，则管理开销占一个周期的 1 / (4 + 1) = 20%。

时间片过长，切换开销占比下降，但排在队尾的交互任务需要等待更久。若 50 个任务各运行 100ms，最后一个任务首次获得 CPU 前理论上可能等待接近 5 秒，交互体验会非常差。

因此：

时间片短 → 响应快，但切换开销大
时间片长 → 开销小，但响应变慢
时间片极长 → RR 逐渐接近 FCFS

最佳时间片没有脱离硬件和工作负载的固定答案。它应明显大于一次上下文切换的成本，同时又要让交互任务在可接受时间内得到响应。

2. 优先级调度

RR 假设所有任务同等重要，但现实中任务可能有紧急程度、权限或服务等级差异。优先级调度为每个任务分配优先级，优先运行优先级最高的就绪任务；同一优先级内部可以继续使用 RR。

优先级调度可以是非抢占式，也可以是抢占式。抢占式优先级调度中，高优先级任务一旦就绪，就可能立即抢占当前的低优先级任务。

静态优先级

静态优先级在任务创建或配置时确定，运行期间通常不变。它适合重要程度能够事先确定的任务，但不容易适应任务行为变化，也要防止低优先级任务长期饥饿。

动态优先级

动态优先级根据任务的运行行为、等待时间和 CPU 使用量进行调整。例如，一个任务每次只运行很短时间就因 I/O 阻塞，可以推测它偏向 I/O 密集型；让它较快获得 CPU，有助于尽早发起下一次 I/O，提高响应和设备利用率。

反之，总是用完整个时间片的任务更像 CPU 密集型，可以让它在较低优先级上获得更长的连续运行时间。

但简单规则可能被“博弈”：进程可以频繁 sleep 或 yield，伪装成 I/O 密集型以维持高优先级。因此成熟算法不能只看“这一次是否用完时间片”，还要统计累计 CPU 使用量，并配合配额、老化和周期性提升。

3. 多级队列与多级反馈队列（MLFQ）

先区分三个容易混淆的概念：

• 动态优先级是一种思想：任务的优先级会随行为和等待时间改变；
• 多级队列是一种组织方式：系统维护多个优先级或类型不同的就绪队列；
• 多级反馈队列 MLFQ 允许任务在多个队列之间移动，把多级队列与动态优先级结合起来。

传统多级队列可能把前台、后台和批处理任务固定放在不同队列：

Q0：前台交互任务
Q1：后台服务
Q2：批处理任务

任务被分到某个队列后通常不再移动，属于静态分类。MLFQ 则根据任务实际使用 CPU 的方式进行反馈：

新任务 → Q0（最高优先级）
大量使用 CPU → Q1 → Q2
等待过久或周期性提升 → 回到高优先级

一套典型的 MLFQ 规则是：

1. 高优先级队列中的任务优先于低优先级队列；
2. 同一队列内使用 RR；
3. 新任务进入最高优先级队列，以获得良好首次响应；
4. 每层为任务设置累计 CPU 时间配额，用完配额后降到下一层；
5. 经过一段时间，把所有任务提升到最高优先级，避免低层任务饥饿。

按累计配额降级比“只要主动阻塞就不降级”更稳健，因为任务不能通过反复短暂休眠逃避降级。

各层时间片通常可以逐渐变长：

Q0：高优先级，时间片 10ms
Q1：中优先级，时间片 20ms
Q2：低优先级，时间片 40ms

高层多为新任务和交互型任务，它们通常只需很短 CPU burst，因此短时间片可以提升响应；逐渐降到低层的任务更像 CPU 密集型，较长时间片能减少切换开销。

MLFQ 不需要预先给任务贴上“CPU 密集型”或“I/O 密集型”的永久标签，而是通过行为反馈近似识别任务类型。这也是它名称中“反馈”的含义。

4. 最短进程优先

交互进程通常呈现“等待命令—执行一小段—再次等待”的模式。如果把每次命令处理视作一个独立 CPU burst，就可以优先运行预计 burst 最短的任务，以改善响应时间。

问题仍然是预测。常见做法是使用指数加权平均：

$${\tau }_{n+1}=\alpha t_n+(1-\alpha ){\tau }_n$$

其中：

• $t_n$ 是刚刚测得的实际 CPU burst；
• ${\tau }_n$ 是此前的预测；
• ${\tau }_{n+1}$ 是下一次预测；
• $\alpha$ 决定更相信近期测量还是长期历史。

当 $\alpha =\frac{1}{2}$ 时，越新的观测权重越大，旧数据的影响会按 1/2、1/4、1/8…… 逐渐衰减。这种预测既保留历史趋势，又能适应进程行为变化。

这里的“最短进程优先”更准确地说是在比较下一次 CPU burst，而批处理语境下的“最短作业优先”更偏向整个作业的预计长度。不过很多教材会统一称为 SJF，因此应根据上下文判断它比较的是总作业长度还是下一次 CPU burst，不必把名称机械地当成两个完全不同的算法。

5. 保证调度

**保证调度（Guaranteed Scheduling）**不只规定选择顺序，还向任务承诺 CPU 份额。若系统中有 n 个地位相同的可运行进程，理想情况下每个进程应获得大约 1/n 的 CPU 时间。

调度器可以比较“任务实际获得的 CPU 时间”与“按照承诺应获得的 CPU 时间”，优先补偿落后的任务。它强调的是每个进程能否得到约定份额。

6. 彩票调度

**彩票调度（Lottery Scheduling）**是一种概率性份额调度。系统给每个任务分配一定数量的彩票，每次调度随机抽取一张：

A：50 张彩票
B：30 张彩票
C：20 张彩票

长期数学期望上，A、B、C 大约获得 50%、30%、20% 的 CPU 时间。彩票数量可以表达权重，也容易通过转让彩票实现临时资源倾斜。

随机性意味着短时间窗口内不能保证严格比例，但只要任务的彩票数大于 0，它就一直保留被选中的机会，从而避免严格优先级下的确定性饥饿。

7. 公平分享调度

普通进程级公平可能被“多开进程”利用：用户 A 启动 9 个进程，用户 B 只启动 1 个；若 10 个进程等额轮转，A 总共获得 90% CPU，B 只有 10%。

**公平分享调度（Fair-Share Scheduling）**先按用户、用户组或组织分配 CPU，再在各自内部的进程之间分配：

用户 A：10 个进程 → 用户整体获得 50%
用户 B： 1 个进程 → 用户整体获得 50%

A 的 10 个进程再分享 A 的 50%
B 的 1 个进程使用 B 的 50%

保证调度与公平分享调度的区别在于公平对象：

调度方式	公平对象	多开进程能否提高用户总份额
保证调度	进程	可能可以
公平分享调度	用户、用户组或组织	通常不可以

三、实时系统中的调度

1. 实时调度关注的是按时完成

实时系统中，时间是正确性的一部分。医疗监护、自动驾驶、工业控制和多媒体播放不仅要计算正确，还要在规定时间内给出结果。一个正确但严重迟到的控制信号，可能与错误结果一样不可接受。

实时调度需要知道任务的执行时间、周期或截止时间，并判断现有 CPU 能否满足全部约束。接受一个无法按时完成的新任务，只会让原有实时保证一起失效，因此某些系统会先做接纳控制（admission control）：能保证完成才接纳，否则拒绝。

2. 硬实时与软实时

• 硬实时（hard real-time）：截止时间不能错过，超时可能导致系统失效或安全事故；
• 软实时（soft real-time）：偶尔超时可以容忍，但服务质量会下降，例如画面卡顿或音频破音。

实时并不等于“平均运行得非常快”，而是执行时间和响应必须可预测，尤其要关注最坏情况能否满足截止时间。

3. 周期性事件与非周期性事件

周期性任务按固定间隔到来，例如传感器每 10ms 采样一次；非周期性任务的到达时间不可预测，例如突发告警。

若有 m 个独立周期性任务，第 i 个任务每个周期需要 $C_i$ 时间、周期为 $T_i$，忽略切换等开销时，一个必要的处理器负载条件是：

$$\sum _{i=1}^m\frac{C_i}{T_i}\le 1$$

例如三个任务的周期分别为 100ms、200ms、500ms，每次分别需要 50ms、30ms、100ms：

$$\frac{50}{100}+\frac{30}{200}+\frac{100}{500}=0.5+0.15+0.2=0.85<1$$

从总利用率看，CPU 仍有 15% 余量。若加入周期 1000ms 的第四个任务，在这个简化模型中，它每周期最多只能再使用 150ms，才能让总利用率不超过 1。

要注意，利用率不超过 1 只是通用的必要条件，并不自动保证任意调度算法都满足全部截止时间；具体可调度性还与截止时间、优先级和所选算法有关。

实时调度还可分为：

• 静态调度：运行前已经知道任务、执行时间和截止时间，提前制定计划；
• 动态调度：任务运行过程中到达，调度器根据当前状态实时决策。

四、调度策略与调度机制

调度器不一定掌握应用内部的全部语义。例如一个数据库主进程管理多个工作线程或子进程，它比内核更清楚哪个请求紧急、哪个任务可以推迟；但内核才有权限真正分配 CPU。

因此操作系统设计强调策略（policy）与机制（mechanism）分离：

• 机制回答“怎样做到”，例如维护运行队列、设置优先级、抢占任务和切换上下文；
• 策略回答“应该怎样选择”，例如哪个数据库请求更重要、某个用户应获得多少份额。

内核可以提供设置优先级、调度类别或资源份额的接口，由应用或管理员提供策略参数；内核再负责安全地执行这些参数。这样既保留内核对硬件资源的统一控制，也允许了解业务语义的上层参与决策。

策略与机制分离不等于允许应用无限提高自己的权限。内核仍需执行权限检查、配额和系统级约束，防止单个应用破坏整体公平与稳定性。

五、线程调度

当一个进程内存在多个线程时，调度可能分成两层：内核选择进程或内核执行实体，用户态运行时再选择具体用户线程。实际行为取决于线程是用户级线程还是内核级线程，以及二者采用何种映射模型。

1. 用户级线程的两层调度

在经典的多对一用户级线程模型中，内核只看到进程 A，看不到其中的 A1、A2、A3：

内核调度：选择进程 A
          ↓
A 的用户态线程库：选择 A1、A2 或 A3

假设内核让 A 运行 50ms，A 的线程库可以在内部多次切换：

A1 运行 5ms → A2 运行 5ms → A3 运行 5ms → ……

用户级线程切换通常只需保存和恢复 PC、寄存器、栈指针以及线程状态，不一定进入内核，也无需切换地址空间，因此开销较小。

但“每个用户线程精确运行 5ms”仍需要用户态运行时的计时或安全点机制；纯协作式线程则要靠线程主动让出执行权。

2. 用户级线程阻塞的问题

在经典多对一模型中，若 A1 发起会阻塞整个内核执行实体的系统调用，内核看到的是进程 A 阻塞，而不是只有 A1 阻塞：

A1 调用阻塞 read()
        ↓
内核认为 A 阻塞
        ↓
A2、A3 即使可运行也得不到 CPU

用户态运行时可以借助非阻塞 I/O、异步 I/O 或多对多映射缓解这个问题，但“一个线程阻塞可能拖住整个进程”是传统纯用户级线程模型的重要缺点。

3. 内核级线程的调度

内核级线程对操作系统完全可见。若进程 A 有 A1、A2、A3，进程 B 有 B1、B2、B3，内核可以直接在所有可运行线程之间选择：

A1 → B1 → A2 → B2 → A3 → B3

时间片通常直接分配给内核线程，而不是先固定分给整个进程。因此 A1 时间片耗尽后，下一位可能是 B1，不一定是同进程的 A2。

若 A1 等待 I/O，只需阻塞 A1；A2、A3 仍可运行，并且在多核上可以真正并行：

CPU0 → A2
CPU1 → A3

4. 线程切换开销

用户态线程在同一进程内切换，通常不进入内核、不更换地址空间，开销较小。内核级线程切换需要内核参与调度和上下文管理；若两个线程属于同一进程，通常仍可共享地址空间。

跨进程线程切换则可能还要更换地址空间和页表相关状态，并影响 TLB、CPU Cache 与分支预测的局部性，因此通常比同进程线程切换更昂贵。

对比项	经典用户级线程	内核级线程
谁负责调度	用户态线程库	操作系统内核
内核是否看见每个线程	否	是
切换开销	通常较小	通常较大
一个线程阻塞	多对一模型下可能拖住整个进程	通常只阻塞该线程
多核并行	多对一模型不能直接并行	可以并行

总结

调度算法没有统一的“最好”，只有是否适合目标和工作负载：

• FCFS 简单，但容易产生护航效应；
• SJF 和 SRTF 能改善平均等待时间，却依赖运行时间预测，并可能让长任务饥饿；
• RR 用时间片换取公平与响应，关键取舍是时间片长度；
• 优先级与 MLFQ 根据任务重要性和行为分配 CPU，必须同时处理饥饿和规则博弈；
• 保证调度、彩票调度和公平分享调度从不同角度表达 CPU 份额；
• 实时调度关注截止时间与可调度性，而非平均意义上的“快”；
• 策略与机制分离，让应用提供业务判断、内核负责安全执行；
• 用户级线程和内核级线程的可见性不同，因此调度层次、阻塞影响、多核能力和切换成本也不同。

真正理解调度，不是背下一串算法名称，而是对每种方法追问三件事：它在优化什么、为此牺牲了什么、任务行为变化后会不会出现饥饿或不公平。

如果这篇文章对你有帮助，欢迎点赞、评论、关注、收藏。你们的支持是我前进的动力！