Scheduling: Introduction (调度：简介)

课件：[[第4次课-07. Scheduling_Introduction.pptx]]
教材：OSTEP Chapter 7

有了受限直接执行机制以后，系统终于能在进程之间切换。接下来的问题是：切给谁？切多久？评价标准是什么？ 这就是调度（Scheduling）要回答的核心。

1. 先建立一个理想化模型（4 个假设）

课件一开始先给了 4 个假设，用于把问题简化到可分析：

1. 每个作业运行时间相同；
2. 所有作业同时到达；
3. 所有作业只用 CPU，不做 I/O；
4. 每个作业运行时长已知。

这些假设不真实，但很有用：先在最干净的条件下比较算法，再逐步放宽假设看算法怎么变化。

2. 调度怎么衡量好坏？

2.1 周转时间（Turnaround Time）

最基础的性能指标是周转时间：

$$T_{turnaround}=T_{completion}-T_{arrival}$$

它反映“从到达到完成”花了多久。

2.2 公平性（Fairness）

另一个常见指标是公平性：每个作业是否获得合理的 CPU 份额。

调度里最典型的矛盾是：

• 追求极致性能时，常常会牺牲部分公平；
• 追求强公平时，平均性能可能变差。

2.3 响应时间（Response Time）

后面课件又引入了交互场景关键指标：

[
T_{response}=T_{firstrun}-T_{arrival}
]

它只关心“作业多久第一次被调度运行”。对终端交互任务，这个指标非常敏感。

3. 算法演进：从 FIFO 到 STCF

3.1 FIFO / FCFS（先来先服务）

FIFO（也叫 FCFS）最简单：谁先来谁先跑到底。

在“作业时长相同”时，它看起来没问题；但一旦放宽假设 1（作业时长不同），就会出现护航效应（Convoy Effect）。

典型例子：

• A 运行 100s，B、C 各 10s；
• 到达顺序是 A→B→C。

在 FIFO 下，B、C 会被 A 长时间堵在后面，平均周转时间明显变差。

3.2 SJF（最短作业优先）

SJF 思路是：先跑最短作业，再跑次短作业。

优点：在“同时到达 + 已知运行时长”的理想条件下，平均周转时间通常更好。
限制：经典 SJF 是非抢占式，一旦某作业开始跑，就不会被中途换下。

3.3 SJF 遇到“晚到短作业”

放宽假设 2（作业可以晚到）后，SJF 的短板会暴露：

• A 在 t=0 到达，需 100s；
• B、C 在 t=10 到达，各需 10s。

如果 A 已经开跑，非抢占 SJF 不会中断 A，B、C 仍然要等很久。

3.4 STCF / PSJF（最短剩余时间优先）

为了解决上面的问题，引入抢占得到 STCF（也常称 PSJF）：

• 新作业到达时，比较“当前运行作业的剩余时间”和“新作业总时长”；
• 谁剩余时间更短，就让谁先跑。

相比 SJF，STCF 的核心优势是：短作业晚到也能尽快插队执行，因此周转时间通常更优。

补充：n 个进程有多少种调度顺序？

课件有一道基础题：n 个进程在单处理器上的执行顺序有多少种？
答案是全排列：n!。

4. 面向交互：Round Robin（RR）

STCF 在周转时间上很强，但对响应时间不一定友好。为提升交互体验，课件引出 RR（时间片轮转）。

RR 规则：

• 每个作业最多运行一个时间片（quantum）；
• 时间片用完且未完成，则放到队尾；
• 调度器轮流给队列中的作业分配时间片。

特点很鲜明：

• 优点：响应时间通常更好，也更公平；
• 缺点：平均周转时间未必理想，且切换过频会带来上下文切换开销。

5. 时间片长度是关键权衡

课件强调：时间片长度决定系统性格。

• 时间片短：
  • 响应时间更好；
  • 但上下文切换太频繁，开销可能主导性能。
• 时间片长：
  • 切换开销被摊销（amortization）；
  • 但响应时间会变差。

所以没有“永远正确”的固定值，只能根据系统目标折中。

课件判断题要点

1. “RR 中时间片应小于上下文切换时间” → False。
   时间片若比切换成本还小，系统几乎都在切换。
2. “时间片过长时 RR 会退化为 FCFS” → True。
   当量子远大于任务运行时间时，几乎等同先来先跑完。

课件练习例（响应时间）

给定 P1=53, P2=17, P3=68, P4=24，四者同时到达，RR 时间片 20。
若按 P1→P2→P3→P4 入队，则首次运行时刻分别为 0, 20, 40, 60，平均响应时间：

[
(0+20+40+60)/4=30
]

6. 把 I/O 纳入调度

放宽假设 3 后，真实系统会出现：有的进程会发起 I/O 并阻塞。

课件示例要点：

• A、B 都总共需要 50ms CPU；
• A 每跑 10ms 就发起一次 I/O，每次 I/O 耗时 10ms；
• B 是纯 CPU 任务。

调度器的正确做法是：

1. A 发起 I/O 后进入阻塞态；
2. 立刻切到 B 使用 CPU；
3. I/O 完成时触发中断；
4. OS 把 A 从阻塞态移回就绪态，等待再次调度。

这会形成 CPU 与磁盘的重叠工作，提高整体资源利用率，而不是让 CPU 空等 I/O。

7. 本章小结

这一章的主线可以压成三句话：

1. 先在理想假设下理解基础算法（FIFO、SJF、STCF）；
2. 再引入交互目标，得到 RR 与时间片权衡；
3. 最后把 I/O 带回真实世界，理解“阻塞—唤醒—重调度”这条链路。

随堂复习自测

1）FIFO 的典型问题是什么？

护航效应：长任务堵住后面的短任务。

2）SJF 和 STCF 的关键区别是什么？

SJF 通常是非抢占式；STCF 允许抢占，按剩余时间调度。

3）为什么 RR 更有利于交互？

因为每个任务都能较快拿到第一次运行机会，响应时间更好。

4）为什么时间片不能过短？

会导致上下文切换过于频繁，CPU 时间被切换开销大量吞噬。

5）I/O 完成后进程直接变 Running 吗？

不是。通常先回到 Ready，再由调度器决定何时运行。