操作系统深度学习笔记：CPU 调度 (Chapter 5)

1. 核心概念与分派机制

CPU-I/O 爆发周期 (Burst Cycle)

进程的执行并非一直占用 CPU，而是由 CPU 爆发 (CPU burst) 和 I/O 爆发 (I/O burst) 交替组成。
通过对大量进程的统计发现：系统中存在海量的短 CPU 爆发进程，和极少量的长 CPU 爆发进程。这一分布规律是设计调度算法的重要依据。

分派器与分派延迟 (Dispatcher & Dispatch Latency)

分派器是实际执行“切换”动作的模块。分派延迟是指停止一个进程并启动另一个进程所需的时间。
在要求严格的系统中，分派延迟中的冲突阶段 (Conflict phase) 是主要瓶颈，它包括两步：

  1. 抢占在内核模式下运行的任何进程。
  2. 低优先级进程释放高优先级进程所需的系统资源。

2. 核心调度算法深度解析

FCFS (先来先服务)

  • 痛点：护送效应 (Convoy effect)。如果一个 CPU 密集型的长进程排在前面，后面一群 I/O 密集型的短进程只能被迫长时间等待，导致整体 CPU 和 I/O 设备利用率双双下降。

SJF (短作业优先) 与爆发时间预测

SJF 在理论上能给出最小的平均等待时间。难点在于如何知道进程的下一个 CPU 爆发会有多长。
操作系统通常利用历史数据，通过指数平均法 (Exponential Averaging) 来预测下一个爆发长度：
$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

  • $t_n$：第 $n$ 次实际的 CPU 爆发长度。
  • $\tau_n$：对第 $n$ 次的预测值。
  • $\alpha$：权重系数（通常设为 1/2），决定了近期历史数据对预测值的影响程度。

RR (时间片轮转)

专门为分时系统设计，给予每个进程一个时间片 $q$（通常 10-100 毫秒）。

  • 核心约束：时间片 $q$ 必须远大于上下文切换的时间（通常 < 10 微秒）。如果 $q$ 太小，CPU 的大部分时间都会浪费在上下文切换的开销上。

多级反馈队列 (Multilevel Feedback Queue)

这是最复杂但也最通用的算法。它允许进程根据其运行行为在多个队列之间移动。定义一个多级反馈队列调度器需要设定以下详细参数：

  • 队列的数量。
  • 每个队列内部的调度算法（例如顶层用 RR，底层用 FCFS）。
  • 决定何时将进程升级到高优先级队列的方法（例如老化机制）。
  • 决定何时将进程降级到低优先级队列的方法（例如用光了时间片）。
  • 决定进程初始进入时被放入哪个队列的方法。

3. 线程调度 (Thread Scheduling)

在支持线程的系统中，实际调度的单位是线程。存在两种竞争范围：

  • PCS (进程竞争范围)：由线程库在用户态进行调度，同一进程内的线程相互竞争。
  • SCS (系统竞争范围)：由操作系统内核直接将内核级线程调度到逻辑 CPU 上，全系统的线程相互竞争。

在 POSIX API (pthread) 中，程序员可以通过 PTHREAD_SCOPE_PROCESS 或 PTHREAD_SCOPE_SYSTEM 来指定竞争范围，但最终取决于操作系统的支持（如 Linux 和 macOS 仅支持 SCS）。

4. 多处理器与多核调度进阶

现代硬件架构

  • 物理核心 (Physical Core)：芯片上真实的独立处理单元。
  • 逻辑 CPU (Logical CPU)：支持硬件多线程（如超线程）时，OS 看到的执行单元。
  • 两级调度模型：
    • 第一级 (OS层)：决定哪个软件线程在哪个逻辑 CPU 上运行。
    • 第二级 (硬件层)：物理核心根据内存停顿 (Memory Stall) 自动切换执行哪个硬件线程，以填补等待数据的空隙。

多核架构与内存停顿 (Memory Stall)

现代 CPU 往往由于等待访问内存数据而发生停顿。为了利用这些停顿周期，处理器采用硬件多线程（如超线程）。当一个硬件线程发生内存停顿时，物理核心可以迅速切换去执行另一个硬件线程的指令。

NUMA 系统感知

在非一致性内存访问 (NUMA) 架构中，CPU 访问本地内存的速度远快于访问远程内存。
NUMA 感知调度：操作系统在调度时，不仅要分配 CPU，还要将进程分配给拥有离该 CPU 最近的内存节点的处理器域 (Domain)，尽量避免线程在不同物理节点间迁移。

5. 实时 CPU 调度的数学约束

实时系统处理的是周期性任务。这些任务具有三个核心参数：

  • $t$：处理时间 (Processing time)
  • $d$：截止时间 (Deadline)
  • $p$：周期 (Period)
    约束条件：$0 \le t \le d \le p$。任务的执行速率即为 $1/p$。

两种实时算法的核心逻辑

  • RMS (速率单调调度)：静态优先级。优先级由周期的倒数决定。周期越短优先级越高。缺点是当 CPU 利用率较高时，无法保证所有进程不漏掉 Deadline。
  • EDF (最早交期优先)：动态优先级。系统时刻检查哪个任务的截止时间最迫近，最迫近的任务立即获得最高优先级。
  • POSIX 实时标准：定义了 SCHED_FIFO（先进先出无时间片）和 SCHED_RR（带时间片轮转）两种硬性调度策略。

6. 三大操作系统调度器底层实现

Linux CFS (完全公平调度器)

  • 核心思想：不分配固定的时间片，而是分配 CPU 的使用比例。
  • vruntime (虚拟运行时间)：记录任务实际运行时间。基于任务的 Nice 值（-20 到 +19）设有衰减因子。低 Nice 值（高优先级）的任务，其 vruntime 增长得慢，从而能获得更多的 CPU 实际时间。
  • 数据结构：采用红黑树 (Red-Black Tree) 存储可运行任务，键值为 vruntime。调度器总是取树最左侧的节点（即 vruntime 最小的节点）执行，时间复杂度为 $O(\log N)$。

Windows (抢占式优先级调度)

  • 优先级体系：共 32 级。1-15 级为可变优先级（普通程序），16-31 级为实时优先级，0 级保留给内存管理。
  • 动态提升机制：当线程等待的事件完成时（尤其是键盘 I/O 等前台交互），Windows 会给予巨大的优先级提升奖励；同时，前台活动窗口会获得 3 倍的时间片调度量。
  • UMS (用户模式调度)：允许应用程序独立于内核管理大量并发线程，大幅提高 C++ 并发框架的效率。

Solaris (多级反馈队列的巅峰应用)

Solaris 的默认分时 (TS) 调度采用了一个复杂的分派表 (Dispatch Table)，通过状态转换来实现完美平衡：

  • 时间片耗尽惩罚 (Time quantum expired)：如果进程一口气用完了时间片（说明是计算密集型），会被丢到低优先级，但下次分配长时间片。
  • 睡眠唤醒奖励 (Return from sleep)：如果进程提前放弃 CPU 去等待 I/O（说明是交互型），唤醒时会被提升到高优先级，并分配短时间片。

7. 算法评估模型

评估哪种调度算法最适合当前操作系统，通常采用以下方法：

  • 排队模型 (Queueing Models)：将计算机描述为服务器网络，利用概率论计算稳态性能。最著名的是 利特尔法则 (Little’s Law)：
    $n = \lambda \times W$
    (平均队列长度 $n$ = 平均到达率 $\lambda$ $\times$ 队列中的平均等待时间 $W$)
  • 模拟 (Simulations)：通过编程建立计算机系统的模型，并使用真实的系统事件日志——跟踪磁带 (Trace tapes) 作为输入数据来驱动模拟，从而获得高度精确的性能统计。