第一章：操作系统调度导论 🧐
1.1 调度的核心问题
【重点】 操作系统的一个核心功能是虚拟化 CPU。在一个仅有单颗 CPU 的系统中，操作系统通过快速地在不同进程之间切换，使得多个进程看起来像是在“同时”运行。实现这一功能的关键技术就是调度（Scheduling）。
调度主要解决两个核心问题：
- 如何切换：即从一个进程切换到另一个进程的具体机制是什么？
- 切换到谁：即在众多“准备就绪”的进程中，应该选择哪一个来运行？
1.2 机制与策略的分离
【重点】 为了使操作系统设计更加清晰和灵活，调度被清晰地划分为两个层面：
- 机制（Mechanism）：负责“如何切换”的底层操作。它提供了切换进程所需的能力，但不关心下一个应该运行谁。
- 主要机制包括：上下文切换（Context Switching） 和 抢占（Preemption）。
- 策略（Policy）：负责“切换到谁”的上层决策。它根据特定的算法和目标，决定下一个获得 CPU 使用权的进程。
- 例如：哪个进程优先级最高？如何保证公平性？
设计思想：将机制与策略分离是一种经典的设计模式。底层机制保持稳定，而上层策略可以根据需求灵活调整和优化，而无需修改底层代码。
1.3 内核如何保持控制权
【了解】 要实现调度，操作系统内核必须能够周期性地收回对 CPU 的控制权。如果一个进程开始运行后，内核就失去了控制，那么它将永远运行下去，调度也无从谈起。
内核通过以下两种主要方式来确保自己能够“夺回”控制权：
- 协作式调度（Cooperative Scheduling）：进程通过执行特定的系统调用，如
yield()（主动放弃 CPU）或执行 I/O 操作，自愿地将控制权交还给内核。 - 抢占式调度（Preemptive Scheduling）：这是现代操作系统的主流方式。内核配置一个定时器中断（Timer Interrupt）。当中断发生时，当前运行的进程会被强制暂停，CPU 的控制权自动转移到内核的中断处理程序。这样，内核就可以决定是让该进程继续运行，还是调度另一个进程。
核心思想：无论是进程自愿放弃，还是通过定时器中断强制抢占，其目的都是为了让 CPU 的执行流重新回到操作系统内核，从而让调度程序有机会做出新的决策。
第二章：核心调度机制 ⚙️
2.1 上下文切换（Context Switching）
【重点】 上下文切换是操作系统实现多任务处理的核心机制。
上下文切换发生的原因：
- 进程完成或退出：当前进程执行完毕。
- I/O 操作：进程需要等待缓慢的 I/O 设备（如磁盘），内核会切换到其他就绪进程以提高 CPU 利用率。
- 中断：硬件中断发生，需要内核介入处理。
- 抢占：当前进程的时间片（Time Slice） 用完，被调度器强制切换。
上下文切换的逻辑步骤（CS 函数逻辑）： 假设要从进程 A 切换到进程 B：
- 保存进程 A 的上下文：内核将进程 A 的所有寄存器（如程序计数器 PC、栈指针 SP、通用寄存器等）的值保存在内存中的特定区域，通常是该进程的内核栈或**进程控制块（Process Control Block, PCB）**中。
- 切换地址空间：更新内存管理单元（MMU）中的指针，将虚拟地址空间从进程 A 的映射切换到进程 B 的映射。
- 恢复进程 B 的上下文：从内存中加载进程 B 的 PCB 中保存的寄存器值到 CPU 的相应寄存器中。
- 返回并执行：执行特殊的返回指令，将控制权交给进程 B。此时，程序计数器 PC 指向了进程 B 上次被中断时的位置，进程 B 从该位置无缝地继续执行。
【了解】 上下文切换的具体实现是高度体系结构相关的。例如，在 x86 架构下，这会涉及一系列的汇编指令来保存和恢复 %eax, %ebx, %esp, %ebp 等寄存器。（具体汇编实现过程已省略，详见讲义图 9）。
关键点：对于进程本身而言，上下文切换是透明的。进程并不知道自己被暂停和恢复，它感觉自己一直在连续运行。
2.2 抢占（Preemption）
【重点】 抢占机制是防止单个任务永久霸占 CPU、保证系统响应能力和公平性的关键。
核心思想：如果一个任务长时间不主动放弃 CPU（例如，陷入死循环），操作系统必须有能力强行收回控制权。
这个能力由定时器中断提供。操作系统在将 CPU 交给一个进程之前，会启动一个硬件定时器，并设定一个固定的时间间隔（即时间片）。当时间到达后，定时器会触发一个硬件中断，强制 CPU 停止当前工作，并跳转到内核预设的中断服务程序。在这个服务程序中，调度器得以运行，从而决定下一个要执行的进程。
第三章：调度策略与评价指标 📊
3.1 调度器评价指标
【核心考点】 要评价一个调度策略的优劣，我们需要一套量化的指标。不同的策略在这些指标上各有取舍。
- CPU 利用率（Utilization）：CPU 处于“忙碌”状态（即执行用户程序或内核任务）的时间比例。目标是最大化。
- 周转时间（Turnaround Time）：一个任务从到达系统到执行完成所花费的总时间。 目标是最小化。这个指标衡量了系统的处理能力。
- 响应时间（Response Time）：一个任务从到达系统到首次被调度运行所花费的时间。 目标是最小化。这个指标对于交互式系统（如桌面操作系统）至关重要，直接影响用户体验。
- 公平性（Fairness）：确保每个进程都能获得合理的 CPU 时间，避免某些进程被“饿死”（Starvation）。
3.2 知识回顾：进程状态
【了解】 在讨论调度策略前，我们先回顾一下进程的三种基本状态，调度器正是在这些状态之间移动进程。
- 运行（Running）：进程当前正在 CPU 上执行。
- 就绪（Ready）：进程已经准备好运行，但正在等待被调度器选中。
- 阻塞（Blocked）：进程正在等待某个事件发生（如 I/O 完成），在此之前它无法运行，即使 CPU 空闲。 ![[Pic/Pasted image 20251014224250.png]] [图 3.1：进程三状态转换图（详见讲义图 14）]
3.3 简化的调度假设
【了解】 为了循序渐进地理解各种调度策略，我们首先引入一系列理想化的假设。在后续章节中，我们将逐步放宽这些假设，以应对更复杂的现实场景。
初始假设集：
- 每个任务的运行时间都相同。
- 所有任务在同一时间到达系统。
- 任务一旦开始，就会一直运行直到完成（非抢占）。
- 所有任务都只使用 CPU，不执行 I/O 操作。
- 每个任务的运行时间是已知的。
第四章：基本调度算法 💡
4.1 先来先服务（First Come, First Served - FCFS）
【重点】 FCFS，也称为 FIFO（First In, First Out），是最简单的调度算法。它按照任务到达的顺序来执行任务。
示例： 假设任务 A, B, C 都在 T=0 时刻到达，每个任务运行时间为 2。
- 执行顺序：A -> B -> C
- 平均周转时间：
- 平均响应时间： ![[Pic/Pasted image 20251014224517.png]] [图 4.1：FCFS 调度示例（详见讲义图 18）]
缺点：护航效应（Convoy Effect）
【核心考点】 当一个运行时间很长的任务先于许多运行时间很短的任务到达时，这些短任务必须排队等待，导致平均周转时间急剧恶化。这就像一辆缓慢的卡车（长任务）挡住了一队长龙般的快车（短任务）。
示例： 假设任务 A (len=6), B (len=2), C (len=2) 都在 T=0 到达。
- FCFS 顺序：A -> B -> C
- 平均周转时间：
- 这个结果远劣于先执行短任务的情况。 ![[Pic/Pasted image 20251014224648.png]] [图 4.2：FCFS 的护航效应（详见讲义图 22）]
4.2 最短工作优先（Shortest Job First - SJF）
【重点】 为了解决 FCFS 的护航效应，SJF 算法被提出。它总是选择当前就绪队列中运行时间最短的任务来执行。
放宽假设：我们放宽了“每个任务运行时间相同”的假设。
示例：（接上例） 任务 A (len=6), B (len=2), C (len=2) 都在 T=0 到达。
- SJF 顺序：B -> C -> A (或 C -> B -> A)
- 平均周转时间：
- 相比 FCFS 的 8，周转时间得到了显著优化。 ![[Pic/Pasted image 20251014224702.png]] [图 4.3：SJF 调度示例（详见讲义图 25）]
SJF 的问题： SJF 在“所有任务同时到达”的假设下，对于优化平均周转时间是最优的。但是，如果任务在不同时间到达呢？
【核心考点】 SJF 是一种非抢占式算法。一旦一个任务开始运行，即使在它运行期间，一个更短的任务到达了，SJF 也必须等待当前任务完成后才能调度那个更短的任务。这同样会导致护航效应。
4.3 最短完成时间优先（Shortest Time-to-Completion First - STCF）
【核心考点】 STCF（也称为 Preemptive Shortest Job First, PSJF）是 SJF 的抢占式版本。
放宽假设：我们放宽了“任务一旦开始就必须运行到完成”的假设，引入了抢占。
STCF 规则：
示例： 任务 A 在 T=0 到达 (len=6)，任务 B, C 在 T=1 到达 (len=2)。
- T=0：只有 A 在，运行 A。
- T=1：B, C 到达。此时 A 还剩 5 个单位时间，B 和 C 都只需要 2 个单位。调度器抢占 A，选择运行 B。
- T=3：B 完成，运行 C。
- T=5：C 完成，运行 A 剩下的部分。
- T=10：A 完成。
[图 4.4：STCF 抢占式调度示例（详见讲义图 31）]
- 平均周转时间：
- STCF 在任何情况下（无论任务何时到达），对于优化平均周转时间都是最优的。
第五章：优化响应时间：轮转调度 🔄
5.1 响应时间的重要性
【重点】 到目前为止，我们优化的核心指标一直是周转时间。STCF 算法虽然在这方面做到了极致，但对于响应时间却可能表现很差。在交互式系统中，用户希望程序能被快速响应，而不是等待一个长任务完成后才有反应。
5.2 轮转调度（Round Robin - RR）
【核心考点】 RR 调度算法的核心目标是优化响应时间。
RR 规则：RR 维护一个就绪进程队列。调度器选择队列头部的进程，让它运行一个固定的时间单位，这个单位被称为时间片（Time Slice / Quantum）。时间片用完后，如果进程还未完成，它将被抢占并被移动到就绪队列的末尾。然后调度器再选择新的队首进程运行。
示例： 任务 A, B, C 都在 T=0 到达，每个任务运行时间为 3，时间片为 1。
- RR 顺序：A, B, C, A, B, C, A, B, C
- 平均响应时间：
- 作为对比，FCFS/SJF 的平均响应时间为：
[图 5.1：RR 调度示例（详见讲义图 37）]
RR 的权衡（Trade-off）
【核心考点】 RR 通过频繁切换，极大地改善了响应时间，但这是以牺牲周转时间为代价的。因为频繁的上下文切换本身是有开销的，并且任务的完成时间被拉长了。在上面的例子中，RR 的平均周转时间是 ，而 FCFS/SJF 则是 。
5.3 时间片长度的权衡
【重点】 时间片长度的设定是一个关键的权衡：
- 时间片过长：RR 退化成 FCFS，响应时间变差。
- 时间片过短：响应时间看似很好，但上下文切换的开销会变得非常显著，导致系统整体吞吐量下降。
经验值：通常设置为 10 到 100 毫秒，以在响应时间和开销之间取得平衡。
第六章：高级调度算法 🚀
6.1 综合挑战
【重点】 现实世界远比我们的简化假设复杂。一个现代调度器必须面对以下挑战：
- 它无法预知任务的运行总时长（SJF/STCF 的致命缺陷）。
- 它需要同时优化周转时间（对于批处理任务）和响应时间（对于交互式任务）。
- 它必须考虑 I/O 操作。当一个进程阻塞等待 I/O 时，CPU 应该被调度给其他进程。
核心问题：我们如何设计一个调度器，既能为交互类任务最小化响应时间，又能为计算密集型任务最小化周转时间，且无需预知任务运行时间？
6.2 多级反馈队列（Multi-level Feedback Queue - MLFQ）
【核心考点】 MLFQ 是一种非常经典且实用的调度算法，它试图通过观察进程过去的行为来预测其未来的行为，从而近似实现 STCF 的效果。
6.2.1 MLFQ 的目标与基本思想
- 目标：实现通用调度，同时满足交互式任务（需要低响应时间）和批处理任务（需要高吞吐量）的需求。
- 基本思想：
- 设置多个独立的调度队列，每个队列有不同的优先级。
- 高优先级队列的进程优先被调度。
- 同一队列内的进程使用**轮转（RR）**方式调度。
- 通过一套规则，在不同队列之间动态地移动进程，从而调整其优先级。
[图 6.1：MLFQ 优先级与时间片示意图（详见讲义图 47）]
6.2.2 MLFQ 的核心规则 MLFQ 的行为由一组规则定义，以下是基本规则集：
- 规则 1：如果
prio(A) > prio(B)，则运行 A。- 规则 2：如果
prio(A) == prio(B)，则 A 和 B 以 RR 方式轮流运行。- 规则 3：新进程进入系统时，被放入最高优先级的队列。
- 规则 4：如果一个进程用完了其所在队列的全部时间片，则将其降低一级优先级。（这表明它是一个长时运行的计算密集型任务）。如果它在时间片用完前主动放弃 CPU（如进行 I/O），则其优先级保持不变（这表明它可能是一个交互式任务）。
6.2.3 MLFQ 的挑战与完善 上述基本规则还存在一些问题，需要进一步完善：
- 饥饿问题（Starvation）：如果系统中持续有大量高优先级的交互式任务，那么低优先级的批处理任务可能永远得不到运行。
- 解决方案（规则 5）：周期性地提升（Priority Boost）。每隔一段时间，将系统中的所有任务都重新移动到最高优先级队列。这确保了长任务也能被周期性地调度。
- 欺骗调度器（Gaming the Scheduler）：一个进程可能通过在时间片结束前发起一次无意义的 I/O 操作来“欺骗”调度器，使其认为自己是交互式任务，从而永久保持高优先级。
- 解决方案（规则 4'）：修改优先级降低规则。不再是根据进程是否用完“一个”时间片，而是根据进程在某个优先级上累计消耗的总 CPU 时间。一旦超过该层的配额，就降低其优先级。
6.2.4 MLFQ 规则总结
6.3 完全公平调度程序（Completely Fair Scheduler - CFS）
【了解】 CFS 是当前 Linux 操作系统中使用的标准调度器，它采用了一种与 MLFQ 不同的哲学来实现公平性。
核心理念：CFS 追求的目标不是复杂的优先级规则，而是提供一种理想的、完全公平的多任务 CPU 模型。在一个拥有 N 个进程的理想系统中，每个进程应该精确地获得 1/N 的 CPU 时间。
实现方法：虚拟运行时（Virtual Runtime -
vruntime）- CFS 为每个进程维护一个
vruntime变量，记录该进程已经获得的虚拟运行时间。 - 每次时钟节拍中断时，CFS 会将当前运行进程消耗的物理时间累加到其
vruntime上。 - 调度规则：CFS 总是选择当前所有就绪进程中
vruntime最小的那个来运行。 - 数据结构：为了能高效地找到
vruntime最小的进程，CFS 使用**红黑树（Red-Black Tree）**来组织所有就绪进程，树的最左侧节点即为下一个要调度的进程。
- CFS 为每个进程维护一个
效果：一个进程的
vruntime越小，说明它过去获得的 CPU 时间越少，因此它就越应该被优先调度。通过这种方式，CFS 动态地、平滑地保证了所有进程在宏观上能公平地分享 CPU。
第七章：总结 🏆
本讲义系统地介绍了操作系统 CPU 调度的核心概念、机制和策略。
- 基本机制：上下文切换和抢占是实现调度的基石，它们确保了操作系统始终掌握控制权。
- 调度指标：我们围绕周转时间和响应时间这两个核心指标，评估和设计调度算法。
- 算法演进：
- FIFO/FCFS：简单，但有护航效应。
- SJF：非抢占式，优化了同时到达任务的平均周转时间。
- STCF：抢占式，对平均周转时间最优，但需预知未来。
- RR：以牺牲周转时间为代价，极大地优化了响应时间。
- MLFQ：不需预知未来，通过多级队列和动态优先级调整，试图同时兼顾周转时间和响应时间，是一种非常实用的策略。
- CFS：Linux 的调度器，通过
vruntime和红黑树，追求一种极致的运行时间公平性。
最后的思考：调度算法的核心在于“用过去预测未来”。无论是 MLFQ 观察进程行为，还是 CFS 追踪历史运行时间，都是在信息不完整的情况下，做出当前最优的决策。这不仅是操作系统的智慧，也是许多计算机科学领域问题的缩影。
Xyea