关键问题：如何开发调度策略？我们该如何开发一个考虑调度策略的基本框架？什么是关键假设？哪些指标非常重要？哪些基本方法已经在早期的系统中使用？
工作负载 (Workload) 与假设
工作负载 (Workload) 是指系统中运行的所有进程及其特征（如运行时间、到达时间、I/O 行为等）。确定工作负载是构建调度策略的关键：了解得越多，策略就越优化。
为了简化分析，最初做出以下不切实际的假设（后续会逐步放宽）：
- 每一个工作运行相同的时间。
- 所有的工作同时到达。
- 一旦开始，每个工作保持运行直到完成。
- 所有的工作只是用 CPU（不执行 I/O）。
- 每个工作的运行时间是已知的。
调度指标 (Scheduling Metrics)
周转时间 (Turnaround Time)
性能指标，侧重于任务完成的快慢。
响应时间 (Response Time)
交互性指标，侧重于用户感知的延迟。
性能与公平的权衡优化性能（如周转时间）往往会降低公平性（如阻止某些任务运行）。
调度策略对比
先进先出 FIFO
先进先出 (First In First Out, FIFO) 是一种最基础的调度算法，其核心逻辑是按任务到达系统的先后顺序进行服务。先到达的任务先占用 CPU 运行，直到运行结束或被阻塞，才会轮到下一个任务。虽然它简单易实现，但在不同长度任务混合时表现极差。
- 正常情况：若 A, B, C 均运行 10s，平均周转时间为 。
- 特殊情况：若 A 运行 100s，B、C 运行 10s，平均周转时间飙升至 。
护航效应(Convoy Effect)耗时较少的资源消费者被排在重量级资源消费者之后，导致排队时间过长。类比：在超市排队时，你只买一瓶水却排在推着三辆购物车的人后面。
最短任务优先 SJF
最短任务优先 (Shortest Job First, SJF) 的核心原则是：先运行运行时间最短的任务。
- 优势：在所有任务同时到达的假设下，SJF 可证明是最优调度算法（平均周转时间最小）。
- 效果：沿用 FIFO 的例子（A=100s, B=10s, C=10s），若先运行 B、C 再运行 A，平均周转时间从 110s 降至 50s。
- 局限性：若任务非同时到达，SJF 仍会面临护航效应。例如 A(100s) 在 到达，B、C(10s) 在 到达，由于 SJF 是非抢占的，B、C 必须等待 A 运行完，平均周转时间依然很高。
最短完成时间优先 STCF
抢占与非抢占
- 非抢占式 (Non-preemptive)：任务必须运行直到完成，调度程序才考虑下一个任务（如早期批处理系统）。
- 抢占式 (Preemptive)：调度程序可以随时停止当前进程并切换到另一个进程。
最短完成时间优先 (Shortest Time-to-Completion First, STCF) 是 SJF 的抢占式版本，也称为抢占式最短作业优先（Preemptive Shortest Job First ，PSJF）。
- 原理：每当新任务进入系统，调度程序会比较所有任务（包括新任务和当前运行任务）的剩余运行时间，并优先调度剩余时间最短的任务。
- 效果：在 A(100s) 运行期间，若 B、C(10s) 在 到达，STCF 会立即抢占 A，转而运行 B 和 C，待其完成后再恢复 A。
- 优势：在任务随机到达的情况下，STCF 可证明是最优调度算法（平均周转时间最小）。
轮转调度 RR
轮转调度 (Round-Robin, RR) 是为了优化响应时间而设计的。
- 原理：在一个时间片 (Time Slice/Quantum) 内运行一个工作，然后切换到队列中的下一个任务，循环执行直到完成。
- 优势：极佳的响应时间。对于交互式应用，用户能更早看到系统的反馈。
- 劣势：周转时间表现极差。由于 RR 会延伸每个工作的完成时间，其周转时间通常甚至不如 FIFO。
- 权衡 (Trade-off)：
性能与公平的权衡RR 是一种公平的策略，它在小规模时间内均匀分配 CPU。然而，公平性与周转时间往往是矛盾的：如果你重视公平，响应时间会变短，但周转时间会变长。你不能既拥有蛋糕又吃掉它。
对比总结
| 策略 | 原理 | 抢占式 | 优化目标 | 缺点 |
|---|---|---|---|---|
| FIFO | 按到达顺序执行 | 否 | 简单性 | 护航效应（长任务阻塞短任务） |
| SJF | 优先运行最短任务 | 否 | 周转时间 | 长任务先到时仍有护航效应 |
| STCF | 优先运行剩余时间最短任务 | 是 | 周转时间 | 响应时间较差 |
| RR | 时间片轮转 | 是 | 响应时间 | 周转时间差；受时间片长度影响 |
结合 I/O
重叠 (Overlap) 提高利用率在进程执行 I/O 被阻塞时，调度程序应切换到其他就绪进程运行 CPU。当 I/O 完成产生中断时，操作系统将该进程移回就绪状态。通过这种重叠，可以最大化 CPU 利用率。
为了在调度中处理 I/O，常用的方法是将一个进程的每个 CPU 突发 (CPU burst) 视为一项独立的工作。
- 场景：工作 A 运行 10ms 后执行 10ms I/O；工作 B 纯 CPU 运行 50ms。
- 策略：STCF 会将 A 的每个 10ms 子工作视为短任务优先调度。
- 效果：当 A 在等待 I/O 时，B 占用 CPU；当 A 的 I/O 完成，它作为短任务抢占 B。系统资源得到充分利用。
无法预知
目前的策略（SJF, STCF）都依赖于假设 5：已知每个工作的运行时间。但在通用操作系统中，这是不可知的。
关键问题：如何在不知道任务长度的情况下进行调度？