第三章 CPU调度

导读

CPU是计算机最核心的资源，而CPU调度（CPU Scheduling）是操作系统最重要的功能之一。当系统中有多个进程竞争CPU时间时，调度器（Scheduler）负责决定哪个进程在何时使用CPU。调度器的决策直接影响系统的性能指标——吞吐量、响应时间、等待时间、CPU利用率等。

本章将系统介绍CPU调度的基本原理和经典算法。我们将从调度器的基本工作开始，逐步深入先进先出（FIFO）、最短作业优先（SJF）、轮转调度（RR）、多级反馈队列（MLFQ）等经典算法，最后讨论实时调度和多处理器调度等高级话题。理解这些调度算法的设计思想和权衡取舍，不仅有助于理解操作系统的工作原理，也能为设计高效的并发系统提供重要参考。

3.1 调度器的基本工作

3.1.1 调度器的职责

调度器是操作系统内核的一部分，其核心职责是从就绪队列中选择一个进程，分配CPU给它执行。调度器需要在以下时机被调用：

进程从运行态转为阻塞态：如发起I/O请求。

进程从运行态转为就绪态：如时间片用完或被抢占。

进程从阻塞态转为就绪态：如I/O完成。

进程终止：需要选择新的进程运行。

在第1和第4种情况下，进程必须离开CPU，调度器必须选择新的进程（强制性调度）。在第2和第3种情况下，调度器可以选择继续运行当前进程或切换到另一个进程（非强制性调度）。

3.1.2 调度器的层次

现代操作系统通常包含多个层次的调度器：

• 长期调度器（Long-term Scheduler）：控制系统的多道程序度（Degree of Multiprogramming），决定哪些进程从磁盘加载到内存。在批处理系统中，长期调度器从作业池中选取作业。在交互式系统中，长期调度器的作用较小。
• 短期调度器（Short-term Scheduler）：即通常所说的调度器，从就绪队列中选择进程分配CPU。短期调度器执行频率很高（每毫秒到每几十毫秒一次），因此其代码必须高效。
• 中期调度器（Medium-term Scheduler）：负责进程的换入换出（Swapping），用于平衡系统负载和缓解内存紧张。

3.1.3 抢占式与非抢占式调度

非抢占式调度（Non-preemptive）：一旦进程获得CPU，就一直运行直到终止或主动让出CPU（如发起I/O请求）。实现简单，但可能导致短作业等待长作业。

抢占式调度（Preemptive）：操作系统可以在进程运行过程中强制暂停它（通常通过定时器中断），将CPU分配给其他进程。抢占式调度更灵活，能提供更好的响应时间，但实现更复杂（需要处理并发和同步问题）。

现代操作系统几乎都采用抢占式调度，因为它能保证系统的响应性和公平性。

3.2 调度指标

评价调度算法优劣的指标主要有以下几个：

3.2.1 CPU利用率

CPU利用率 = CPU忙碌时间 / 总时间 × 100%

CPU是昂贵资源，理想情况下CPU利用率应保持在40%（轻负载）到90%（重负载）之间。过低说明CPU资源浪费，过高可能导致队列过长、响应变慢。

3.2.2 吞吐量

吞吐量 = 完成的进程数 / 总时间

吞吐量衡量系统单位时间内完成的工作量。高吞吐量意味着系统能高效处理大量任务。

3.2.3 周转时间

周转时间 = 进程完成时间 - 进程提交时间

周转时间衡量一个进程从提交到完成所需的总时间，包括等待CPU的时间、实际执行时间、等待I/O的时间等。

3.2.4 等待时间

等待时间 = 周转时间 - 实际执行时间 - I/O时间

等待时间衡量进程在就绪队列中等待CPU的时间。好的调度算法应最小化总等待时间。

3.2.5 响应时间

响应时间 = 首次开始运行时间 - 进程提交时间

在交互式系统中，响应时间是用户最关心的指标。它衡量从用户发出请求到系统首次产生响应的时间。

3.2.6 指标之间的权衡

不同的调度指标往往是相互矛盾的。例如：

• 最大化CPU利用率和吞吐量，可能导致响应时间变长。
• 最小化平均周转时间（如SJF），可能导致长作业饥饿。
• 保证公平性（每个进程获得相同的CPU时间），可能增加平均等待时间。

调度算法的设计本质上是在这些指标之间进行权衡。没有一种算法能在所有指标上都表现最优。

3.3 先进先出调度（FIFO/FCFS）

3.3.1 算法描述

先进先出（First-In-First-Out, FIFO）或先来先服务（First-Come-First-Served, FCFS）是最简单的调度算法：按照进程到达就绪队列的顺序，依次分配CPU。先到达的进程先执行，后到达的进程后执行。

3.3.2 实现

FIFO可以使用一个简单的FIFO队列实现：

• 进程到达时，加入队尾。
• 调度时，从队头取出进程。

3.3.3 示例

假设有三个进程，到达时间和执行时间如下：

FIFO调度的执行顺序：P1(0-10) → P2(10-12) → P3(12-15)

• P1 周转时间：10 - 0 = 10
• P2 周转时间：12 - 1 = 11
• P3 周转时间：15 - 2 = 13
• 平均周转时间：(10 + 11 + 13) / 3 = 11.33

3.3.4 护航效应（Convoy Effect）

FIFO最大的问题是护航效应：如果一个CPU密集型进程先到达，它会阻塞后面所有I/O密集型进程。即使I/O密集型进程只需要很短的执行时间，也必须等待长进程完成。这导致CPU和I/O设备的利用率都降低。

在上例中，P2和P3都是短进程，但因为P1先到，它们不得不等待10个时间单位。如果按P2→P3→P1的顺序执行，平均周转时间仅为 (2 + 5 + 15) / 3 = 7.33，远优于FIFO的11.33。

3.4 最短作业优先调度（SJF/SRTF）

3.4.1 非抢占式SJF

最短作业优先（Shortest Job First, SJF）选择预计执行时间最短的进程优先执行。SJF在数学上被证明能最小化平均等待时间。

示例（使用上例数据）：

• P2(1-3) → P3(3-6) → P1(6-16)
• P1 周转时间：16 - 0 = 16
• P2 周转时间：3 - 1 = 2
• P3 周转时间：6 - 2 = 4
• 平均周转时间：(16 + 2 + 4) / 3 = 7.33

3.4.2 抢占式SRTF

最短剩余时间优先（Shortest Remaining Time First, SRTF）是SJF的抢占式版本：当新进程到达时，如果其执行时间小于当前运行进程的剩余时间，则抢占CPU。

示例（使用上例数据）：

• P1(0-1) → P2(1-3) → P3(3-6) → P1(6-16)
• P1 周转时间：16 - 0 = 16
• P2 周转时间：3 - 1 = 2
• P3 周转时间：6 - 2 = 4
• 平均周转时间：(16 + 2 + 4) / 3 = 7.33

3.4.3 SJF的问题

SJF虽然理论上最优，但在实际中面临两个主要问题：

无法预知执行时间：操作系统通常无法准确知道进程的执行时间。虽然可以通过历史数据估算（如指数平均法），但估算本身就有误差。

长作业饥饿：如果系统不断有短作业到达，长作业可能永远得不到执行。这就是饥饿（Starvation） 问题。

3.5 轮转调度（Round Robin, RR）

3.5.1 算法描述

轮转调度（Round Robin, RR）是专门为分时系统设计的调度算法。它的核心思想是：为每个进程分配一个固定的时间片（Time Quantum），进程在时间片内运行，时间片用完后被抢占并放到就绪队列的末尾。

RR算法的关键参数是时间片的长度：

• 时间片太大：退化为FIFO，响应时间变长。
• 时间片太小：上下文切换开销占比增大，CPU利用率下降。
• 经验法则：时间片应远大于上下文切换的时间，通常为10-100毫秒。

3.5.2 示例

假设有三个进程，执行时间分别为：P1=10, P2=3, P3=3，时间片=3。

执行顺序：

• P1(0-3) → P2(3-6) → P3(6-9) → P1(9-12) → P2(9-12完成) → P3(12-15完成) → P1(15-18) → P1(18-21) → P1(21-24完成)

等等，让我重新计算：

• P1(0-3) → P2(3-6,完成) → P3(6-9,完成) → P1(9-12) → P1(12-15) → P1(15-18,完成)

• P1 周转时间：18 - 0 = 18
• P2 周转时间：6 - 0 = 6
• P3 周转时间：9 - 0 = 9
• 平均周转时间：(18 + 6 + 9) / 3 = 11

3.5.3 RR的特点

• 公平：每个进程获得相同的CPU时间份额。
• 响应时间好：对于n个进程，时间片为q，最坏情况下的响应时间为 (n-1)×q。
• 吞吐量一般：如果时间片设置不当，上下文切换开销可能较大。

3.6 多级反馈队列（MLFQ）

3.6.1 设计动机

前面介绍的算法各有优缺点：

• FIFO/SJF：无法适应交互式应用的需求。
• RR：公平但无法区分进程的优先级。

多级反馈队列（Multi-Level Feedback Queue, MLFQ）试图综合多种算法的优点，在不要求用户提前提供执行时间的前提下，自动适应不同类型的进程。

3.6.2 算法描述

MLFQ 维护多个就绪队列，每个队列有不同的优先级和时间片：

• 高优先级队列：时间片短，适合交互式短进程。
• 低优先级队列：时间长，适合CPU密集型长进程。

基本规则：

如果进程A的优先级高于进程B，则A先运行。

如果进程A和B优先级相同，则使用轮转调度。

新进程放在最高优先级队列。

当进程用完当前队列的时间片后，降低优先级（移入下一个队列）。

当进程主动让出CPU（如I/O请求）后，恢复原来的优先级。

反馈机制：

• 如果一个进程频繁使用完整时间片（CPU密集型），它会被逐步降低优先级。
• 如果一个进程频繁在时间片用完前让出CPU（I/O密集型），它会保持高优先级。
• 为了防止低优先级进程饥饿，可以定期将所有进程提升到最高优先级（称为"提升"操作）。

3.6.3 MLFQ的优势

• 自适应：不需要预知进程的执行时间，通过反馈机制自动调整。
• 交互式进程友好：I/O密集型和短进程能保持高优先级，获得快速响应。
• CPU利用率好：CPU密集型进程在低优先级队列中使用长时间片，减少上下文切换。

3.6.4 MLFQ在Linux中的应用

Linux的CFS（Completely Fair Scheduler）调度器可以看作MLFQ思想的一种实现。CFS使用红黑树来管理进程，根据进程的虚拟运行时间（vruntime）进行排序，始终选择vruntime最小的进程运行。这种机制保证了所有进程获得公平的CPU时间分配。

3.7 实时调度

3.7.1 实时系统的特点

实时系统（Real-Time System）对响应时间有严格的要求——不仅要求结果正确，还要求在规定的时间内返回结果。实时系统分为：

• 硬实时（Hard Real-Time）：错过截止时间会导致灾难性后果（如飞行控制系统、心脏起搏器）。
• 软实时（Soft Real-Time）：偶尔错过截止时间可以接受，但会降低系统质量（如视频播放、网络通信）。

3.7.2 实时调度算法

速率单调调度（Rate-Monotonic Scheduling, RMS）

• 适用于周期性实时任务。
• 周期越短的任务，优先级越高。
• 是一种静态优先级调度算法。
• 在CPU利用率不超过 ln(2) ≈ 69.3% 时，可以保证所有任务满足截止时间。

最早截止时间优先（Earliest Deadline First, EDF）

• 截止时间最早的任务优先级最高。
• 是一种动态优先级调度算法。
• 在CPU利用率不超过100%时，可以保证所有任务满足截止时间。
• 比RMS更优，但实现更复杂。

3.7.3 Linux中的实时调度

Linux支持两种实时调度策略：

• SCHED_FIFO：实时先进先出，进程一直运行直到终止或被更高优先级的实时进程抢占。
• SCHED_RR：实时轮转，类似SCHED_FIFO但使用时间片。

实时进程的优先级高于普通进程。Linux的实时优先级范围为1-99（数字越大优先级越高）。

3.8 多处理器调度

3.8.1 多处理器调度的挑战

多处理器系统（包括多核处理器）的调度比单处理器更复杂，因为需要同时管理多个CPU核心。主要挑战包括：

• 负载均衡：确保所有CPU核心的工作负载大致均衡。
• 缓存亲和性：尽量让进程在同一个核心上运行，以提高缓存命中率。
• 同步开销：多个核心上的调度器需要协调，避免竞争。

3.8.2 调度策略

非对称多处理（Asymmetric Multiprocessing, ASP）

• 只有一个主处理器负责调度决策，其他处理器执行主处理器分配的进程。
• 简单但存在瓶颈（主处理器可能成为瓶颈）。

对称多处理（Symmetric Multiprocessing, SMP）

• 每个处理器都可以自主进行调度决策。
• 需要处理多个调度器之间的协调问题。
• 通常使用"每个CPU一个就绪队列"或"共享就绪队列"的方式。

3.8.3 处理器亲和性

软亲和性（Soft Affinity）：调度器尽量让进程在同一个CPU上运行，但不强制。如果负载均衡需要，进程可以迁移。

硬亲和性（Hard Affinity）：通过系统调用（如Linux的 sched_setaffinity()）将进程绑定到特定的CPU集合，不允许迁移。

3.9 常见误区

误区一：最短作业优先在实际中可以使用

SJF需要预知进程的执行时间，而这在通用操作系统中几乎不可能。虽然可以通过历史数据估算，但估算误差可能导致性能下降。实际系统中更多使用基于优先级的调度或MLFQ等自适应算法。

误区二：时间片越小越好

时间片过小会导致频繁的上下文切换，切换开销可能超过并行执行带来的收益。时间片的选择需要在响应时间和吞吐量之间权衡。

误区三：高CPU利用率意味着好的调度

高CPU利用率可能意味着进程在等待队列中排队时间过长，响应时间变差。调度算法应综合考虑多个指标，而非单纯追求CPU利用率。

误区四：公平调度就是给每个进程相同的时间

公平调度不等于平均分配。不同进程有不同的需求和优先级。好的公平调度应保证每个进程获得"合理"的CPU时间，而非"相同"的CPU时间。

误区五：实时调度只用于嵌入式系统

实时调度不仅用于嵌入式系统。桌面操作系统中的音频/视频播放、数据库系统的事务处理、网络数据包处理等都需要实时调度的支持。

3.10 实践应用

3.10.1 观察调度行为

# 查看进程的调度策略和优先级
ps -eo pid,comm,cls,pri,ni

# 修改进程的优先级（nice值）
nice -n 10 command    # 以较低优先级运行
renice -n -5 -p PID   # 提高运行中进程的优先级

3.10.2 Linux CFS调度器

Linux的CFS调度器使用红黑树管理进程，以vruntime为排序键。可以通过 /proc/sched_debug 查看调度器的内部状态：

cat /proc/sched_debug

3.10.3 调度算法模拟器

学习调度算法的最好方式之一是编写模拟器。以下是一个简单的FIFO调度模拟：

class Process:
    def __init__(self, pid, arrival_time, burst_time):
        self.pid = pid
        self.arrival_time = arrival_time
        self.burst_time = burst_time
        self.waiting_time = 0
        self.turnaround_time = 0

def fifo_scheduling(processes):
    processes.sort(key=lambda p: p.arrival_time)
    current_time = 0
    
    for p in processes:
        if current_time < p.arrival_time:
            current_time = p.arrival_time
        p.waiting_time = current_time - p.arrival_time
        current_time += p.burst_time
        p.turnaround_time = current_time - p.arrival_time
    
    total_wait = sum(p.waiting_time for p in processes)
    total_turn = sum(p.turnaround_time for p in processes)
    n = len(processes)
    print(f"平均等待时间: {total_wait/n:.2f}")
    print(f"平均周转时间: {total_turn/n:.2f}")

3.11 本章小结

本章系统介绍了CPU调度的原理和经典算法，主要内容包括：

调度器的职责：从就绪队列中选择进程分配CPU。调度器分为长期、中期和短期三个层次。

调度指标：CPU利用率、吞吐量、周转时间、等待时间、响应时间。不同指标之间往往存在矛盾。

经典调度算法：

- FIFO：简单但存在护航效应。

- SJF/SRTF：理论上最优但无法预知执行时间。

- RR：公平且响应性好，但时间片选择需要权衡。

- MLFQ：自适应，综合多种算法优点。

实时调度：RMS和EDF是两种经典的实时调度算法，保证任务在截止时间前完成。

多处理器调度：需要考虑负载均衡和缓存亲和性，SMP是主流架构。

调度是操作系统的核心功能，直接影响系统的性能和用户体验。在实际系统中，调度算法的选择需要根据具体的应用场景和性能需求进行权衡。