Chap 9. 单处理器调度（Uniprocessor Scheduling）

---

一、 Concept

在学习具体的调度算法之前，先理清调度的“三大层次”和“核心考核指标”。

1. 调度的三个层次

操作系统中不仅有CPU调度，实际上包含了四个维度的调度（其中 I/O 调度在第11章讨论），本章重点关注与进程状态转换密切相关的三种处理器调度：

• 长程调度 (Long-term Scheduling)： 决定是否将一个新进程加入到待执行的进程池中（控制系统的多道程序调度）。
• 中程调度 (Medium-term Scheduling)： 属于对换（Swapping）功能的一部分，决定是否将进程部分或全部调入主存（处理挂起状态 Suspend）。
• 短程调度 (Short-term Scheduling / Dispatcher)： 发生频率最高，决定当前主存中哪个就绪进程将获得 CPU 的执行权。

2. 短程调度的核心性能指标

• 周转时间 (Turnaround Time, TAT)： 进程从提交到完成的总时间。$TAT = \text{等待时间} + \text{服务时间}$。这是批处理系统最看重的指标。
• 响应时间 (Response Time)： 进程从提交请求到系统首次产生响应的时间。这是交互式系统最看重的指标。
• 归一化周转时间 (Normalized Turnaround Time)： $TAT / \text{服务时间}$。该值越接近1越好，表明进程没有被无谓地等待。

---

二、 调度算法的演进

1. 先来先服务 (FCFS - First-Come-First-Served)

• 机制： 非抢占式。谁先进入就绪队列，谁先执行，直到完成或阻塞。
• 缺点： 虽然简单公平，但如果一个长进程排在前面，后面的短进程会被严重拖累（即所谓的“护航效应”）。此外，它极度偏袒 CPU密集型进程，导致 I/O密集型进程经常吃亏。

2. 时间片轮转 (Round Robin, RR)

• 机制： 抢占式。每个进程分配一个时间片（Time Quantum / Slice），时间片用完后触发时钟中断，强行剥夺 CPU，进程回到队列尾部排队。
• 缺点： FCFS 响应时间太差了！RR 的引入是为了在分时系统中提供良好的交互响应时间。
• 设计权衡： 时间片太长，就退化成了 FCFS；时间片太短，CPU的大部分时间都浪费在进程上下文切换上了。

3. 最短进程优先 (SPN - Shortest Process Next)

• 机制： 非抢占式。每次挑选预计处理时间最短的进程优先执行。
• 特点： 能够提供所有非抢占式算法中最优的平均等待时间和平均周转时间。
• 预测技术（指数平滑法 Exponential Averaging）： 我们怎么提前知道进程要跑多久？操作系统通过历史数据来预测未来。公式为：$S_{n+1} = \alpha T_n + (1-\alpha)S_n$。其中 $\alpha$ 控制着权重的分配：$\alpha$ 越大（如0.8），系统对近期的突发变化反应越快。

4. 最短剩余时间优先 (SRT - Shortest Remaining Time)

• 机制： 抢占式。SPN的升级版。如果新到达的进程比当前运行进程的剩余时间还要短，立即抢占 CPU。
• 缺点： SPN 一旦开始执行长进程就不会停，新来的短进程依然要等。SRT 通过引入抢占进一步优化了短进程的响应速度，但带来了更高的系统开销。

5. 最高响应比优先 (HRRN - Highest Response Ratio Next)

• 机制： 非抢占式。每次调度时，计算所有就绪进程的响应比 $R$，选最大的执行。公式：$R = \frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}} = 1 + \frac{w}{s}$。
• The 'Why' (解决饥饿)： SPN 和 SRT 有一个致命缺陷——长进程会无限期饥饿 (Starvation)。HRRN 巧妙地引入了“年龄（等待时间 w）”因素。随着等待时间的增加，即使是长进程，其响应比也会越来越大，最终一定会获得 CPU。

6. 多级反馈队列 (Multilevel Feedback Queue)

• 机制： 抢占式。设立多个优先级队列。新进程进入最高优先级队列（时间片最短）；如果在时间片内没跑完，就被“降级”惩罚到下一级队列。
• The 'Why'： 之前那些优秀的算法（SPN, SRT, HRRN）都有一个共同前提——必须预先知道或估算进程的运行时间。但在实际中很难精准估算。Feedback 算法不需要知道进程多长。它通过“惩罚耗时进程，奖励快速I/O进程”的动态调整机制，完美兼顾了短进程响应、I/O 密集型效率和不用预知长度的难题，是现代操作系统的基石。

7. 传统 UNIX 调度 (Traditional UNIX Scheduling)

• 机制： 采用带有多级反馈和循环轮转（Round Robin）的抢占式调度。
• 优先数计算： $P_j(i) = Base_j + \frac{CPU_j(i)}{2} + nice_j$。系统根据进程的历史 CPU 使用情况动态调整优先级，确保 I/O 密集型和交互式进程的高优先级。

---

三、 Common Pitfalls

1. 混淆“优先数大小”与“优先级高低”： 在 UNIX/Linux 系统和大量的学术计算题中，数值越小，优先级越高（即 Priority 0 比 Priority 10 优先）；但在 Windows 系统中，数值越大代表优先级越高。做题时务必先看清题目设定！
2. 搞混 周转时间 (Turnaround) 与 响应时间 (Response)：
   • 陷阱： 计算响应时间时，算成了进程执行结束的时间。
   • 正解： 周转时间 = 整个任务全部做完的时间 - 到达时间。响应时间 = 任务第一次获得 CPU 开始执行的时间 - 到达时间。
3. 忽略了“非抢占式 (Nonpreemptive)”的锁死效应：
   • 陷阱： 在做 SPN 或 HRRN 推演时，一旦有新的短进程到达，就立刻让当前长进程下台。
   • 正解： SPN, HRRN, FCFS 是非抢占式的！这意味着只要一个进程上了 CPU，除非它自己执行完毕或主动阻塞，否则天王老子来了也不能把它赶下来。抢占只发生在时间片到期（RR, Feedback）或特定事件（SRT）发生时。
4. 死板地计算指数平滑法 ($\alpha$)：
   • 陷阱： 记不住公式中 $\alpha$ 到底乘的是过去真实的观测值还是预测值。
   • 正解： $S_{n+1} = \alpha T_n + (1-\alpha)S_n$。记住口诀：“$\alpha$ 永远跟最新的真实观测值 $T_n$ 在一起”。$\alpha$ 越大，表示操作系统越“健忘”，越相信最近刚刚发生的事。