---
title: "03-CPU调度：三级调度与经典算法"
aliases:
  - CPU调度
created: 2026-08-29
tags:
  - 基础与理论
  - 操作系统
  - "408"
---

# CPU调度：三级调度与经典算法

> 本篇对应王道第二章下半（原 09 篇）。两个问题贯穿：**为什么要进行处理机调度**（进程比 CPU 多，不抢不行）、**调度算法有哪些、适用什么情况**。

## 一、调度的概念与层次

调度就是资源怎么公平高效地分配，处理机调度就是 **CPU 怎么公平高效地分配**。多道程序系统中进程数量往往多于处理机个数，争用在所难免——从就绪队列中按一定算法选一个进程，把处理机分配给它，就是处理机调度。

一个作业从提交到完成，要经历**三级调度**：

| 层次 | 又名 | 干什么 | 备注 |
| --- | --- | --- | --- |
| **高级调度** | 作业调度 | 从外存后备队列挑作业，分配内存等资源、建立进程 | **内存与辅存之间的调度**；每个作业只调入一次调出一次 |
| **中级调度** | 内存调度 | 暂时不运行的进程调到外存（**挂起态**），条件好了再调回 | 提高**内存利用率**和吞吐量；本质是存储器管理的对换功能 |
| **低级调度** | 进程调度 | 从就绪队列选一个进程，分配 CPU | **最基本、所有 OS 必须配置**；频率最高，几十毫秒一次 |

![[image-023325d9.png]]

我自己梳理的三层画面感：外存里有 n 个程序同时要运行——要执行就得读入内存，所以第一层调度决定**让哪些程序先进内存**建立进程；但不需要整个程序都读进来，用一部分换一部分（虚拟内存那套），有些进程暂时执行不了还占着内存就是浪费空间，**挂到外存去，能用了再调回来排队**，这是第二层；第三层就发生在 CPU 和就绪队列之间——进程 PCB 里记着优先级，说明就绪队列不一定是先进先出，**谁先上 CPU** 是第三层要考虑的事。

几条关系：

1. 作业调度为进程活动做准备，进程调度使进程正常活动起来
2. 中级调度夹在两者之间，负责挂起/激活
3. 频率：作业调度最少 < 中级调度 < 进程调度最高
4. 进程调度是最基本的，不可或缺

## 二、调度算法好不好，看什么指标

| 指标 | 定义 | 备注 |
| --- | --- | --- |
| **CPU 利用率** | 忙碌时间 / 总时间 | CPU 是最贵资源之一，要让它保持忙 |
| **系统吞吐量** | 单位时间内完成的作业数量 | 长作业拉低、短作业拉高 |
| **周转时间** | 提交到完成的全过程时间（等待+排队+运行+IO） | 带权周转时间 = 周转时间 / 实际运行时间 |
| **等待时间** | 处于等待处理机状态的时间之和 | **调度算法只影响它**（执行和 IO 的时间它管不着），所以衡量优劣主要看等待时间 |
| **响应时间** | 提交请求到首次产生响应的时间 | **交互式系统**用这个衡量，周转时间不是好准则 |

周转时间公式：

![[image-6ea66eff.png]]

![[image-a53b818e.png]]

想让一个算法满足所有用户和系统要求几乎不可能：既要照顾特定进程的快速响应（实时/交互），又要整体效率（平均周转时间短），还要考虑调度本身的开销。

## 三、调度的实现

### 调度程序三部件

![[image-5146c667.png]]

- **排队器**：把就绪进程按策略排成队列；进程变就绪时由它插入相应队列
- **分派器**：按调度程序的选择，把进程从就绪队列取出、分配 CPU
- **上下文切换器**：切换时要**两对**上下文切换——第一对：旧进程上下文存回 PCB → 装入分派程序上下文（让分派程序跑起来）；第二对：移出分派程序上下文 → 装入新进程的 CPU 现场

上下文切换要执行大量 load/store 指令保存寄存器，很费时间。硬件优化思路：**两组寄存器**（内核一组用户一组），切换时只需改变指针指向当前寄存器组。

### 调度时机：什么时候能换人

想象 OS 是个忙碌的办公室经理，决定哪位员工（进程）用电脑（CPU）。请求调度的事件：时间片到期、进程阻塞、进程终止、更高优先级进程就绪……

**三种情况不能调度和切换**：

1. **处理中断的过程中**——紧急事件要快速响应，不属于任何进程的运行范畴
2. **进程在操作系统内核临界区中**——加锁独占访问，切走会访问冲突
3. **执行原子操作时**（加锁、解锁、中断现场保护）——必须完全屏蔽中断，不能停

**可以调度的情况**：当前进程无法继续执行时（阻塞/终止）立即调度；中断/自陷处理完成后、返回用户态之前，若设了请求调度标志则调度。

**盲点辨析**：进程处于**临界区**≠不能调度。进程在临界区说明它正占着处理机，只要不破坏临界资源的使用规则就不影响调度——比如进程访问打印机这种慢速外设时，若不能调度，系统性能会非常差。不能调度的是**内核临界区**，不是普通临界区。

### 抢占与非抢占

进程在 CPU 上跑着，来了个更重要的进程，给不给？

- **非抢占（非剥夺）**：让当前进程跑完或阻塞，才轮到别人。像在优先队列里操作——新事件优先级再高也只能排队，等当前的做完取队头。实现简单、开销小，适合批处理系统；**不能用于分时和实时系统**
- **抢占（剥夺）**：允许暂停当前进程，把 CPU 给更重要的。对吞吐量和响应效率好处明显，但抢占要有原则：**优先权、短进程优先、时间片**

### 闲逛进程

就绪队列空了怎么办？调度**闲逛进程**（idle）运行：优先级最低，没有就绪进程时才跑；不需要 CPU 之外的资源，所以**不会被阻塞**；一直在跑、顺便测试中断，只要有进程就绪立刻让位。

### 线程的调度

- **用户级线程**：内核不知道线程存在，照旧选进程、给时间，**进程自己的调度程序**决定跑哪个线程；同进程内线程切换只需少量机器指令
- **内核级线程**：内核直接选线程（通常不考虑它属于哪个进程），给时间片，超时强制挂起；切换需要完整上下文切换、修改内存映像、高速缓存失效——**若干数量级的延迟**

## 四、经典调度算法

### FCFS：先来先服务

最简单直观，作业调度和进程调度都可用：按到达顺序排队，谁先来谁先跑，跑到完成或阻塞才释放 CPU。

![[image-33eb0dc6.png]]

表面公平，实际有坑——**购物结账**：前面的人买了两车东西，你只买一盒口香糖，明明一眨眼的事，却要等两车加一件的时间。这不是欺负人吗。

特点：算法简单但效率低；**对长作业有利、对短作业不利**（长作业先来就拖死后面一堆短作业）；有利于 CPU 繁忙型作业（跑起来不被打断），不利于 IO 繁忙型作业（等 IO 期间 CPU 干等着别人也用不上）。不能作为分时/实时系统的主策略，但常被结合使用——优先级调度里，同优先级的进程往往按 FCFS 处理。

### SJF：短作业优先

从后备/就绪队列里选**估计运行时间最短**的，立即执行直到完成或阻塞。

![[image-eede216b.png]]

还是超市的例子：买了两车的人看你只有一件让你先扫，后面又来一群一两件的，让一个两个可以，数量一多，买两车的人也会不情愿——**根本让不完**，这就是**饥饿现象**。

三个缺点：

1. 对长作业不利 → 饥饿
2. 完全未考虑紧迫程度，紧急作业可能被晾着
3. 运行时间靠**用户估计**，用户会有意无意报短——不一定真短

但它是**平均等待时间、平均周转时间最短**的算法（证明见盲点）。

自己写过一个 SPF 的 C 实现，链表 + 每次找当前时间已到达的最短作业：

```c
#include<stdio.h>
#include<stdlib.h>

typedef struct pro {
    int num;
    int arriveTime;
    int burst;
    struct pro *next;
} process;

process* create_process(int num, int arriveTime, int burst) {
    process *new_process = (process*)malloc(sizeof(process));
    if(new_process) {
        new_process->num = num;
        new_process->arriveTime = arriveTime;
        new_process->burst = burst;
        new_process->next = NULL;
    }
    return new_process;
}

process* find_shortest_job(process *head, int currentTime) {
    process *prev = head;
    process *selected_prev = NULL;
    int shortest_burst = __INT_MAX__;
    while(prev->next != NULL) {
        if(prev->next->arriveTime <= currentTime && prev->next->burst < shortest_burst) {
            shortest_burst = prev->next->burst;
            selected_prev = prev;
        }
        prev = prev->next;
    }
    return selected_prev;
}

void delete_process(process *prev) {
    if(prev != NULL && prev->next != NULL) {
        process *to_delete = prev->next;
        prev->next = to_delete->next;
        free(to_delete);
    }
}

int getCount(process *head, int currentTime) {
    int count = 0;
    process *current = head->next;
    while (current != NULL) {
        if (current->arriveTime <= currentTime) count++;
        current = current->next;
    }
    return count;
}

void spf(process *head) {
    int currentTime = 0;
    while(head->next != NULL) {
        if(getCount(head, currentTime) == 0) {
            currentTime++;
        } else {
            process *selected_prev = find_shortest_job(head, currentTime);
            if(selected_prev != NULL) {
                process *selected = selected_prev->next;
                printf("进程名：%d 到达：%d 响应时间：%d\n",
                       selected->num, selected->arriveTime,
                       currentTime - selected->arriveTime);
                printf("开始：%d", currentTime);
                currentTime += selected->burst;
                printf(" 结束：%d 周转时间：%d\n",
                       currentTime, currentTime - selected->arriveTime);
                delete_process(selected_prev);
            }
        }
    }
}

int main() {
    process *head = create_process(-1, -1, -1);
    process *tail = head;
    int num, arrive, burst;
    printf("请输入进程名、到达时间、运行时间，用逗号隔开，输入-1结束：\n");
    while(scanf("%d,%d,%d", &num, &arrive, &burst) == 3 && num != -1) {
        tail->next = create_process(num, arrive, burst);
        tail = tail->next;
    }
    spf(head);
    process *curr = head;
    while(curr != NULL) {
        process *temp = curr;
        curr = curr->next;
        free(temp);
    }
    return 0;
}
```

### 优先级调度

既可用于作业调度又可用于进程调度：选**优先级最高**的。按能否抢占分：

- **非抢占式**：正在跑的进程不受后来高优先级影响，直到自己让出
- **抢占式**：更高优先级一来，立即暂停当前进程

按创建后能否改变分：**静态优先级**（创建时定死，依据进程类型、资源要求、用户要求）和**动态优先级**（运行中调整，依据占 CPU 长短、等待 CPU 时长）。

设置优先级的经验原则：

1. **系统进程 > 用户进程**——管理者理应优先
2. **交互型 > 非交互型**（前台 > 后台）——正在跟你交互的当然要快响应
3. **IO 型 > 计算型**——IO 设备比 CPU 慢得多，让 IO 型进程先跑，IO 设备能尽早开工，整体效率反而更高

### 高响应比优先

主要用于**作业调度**，是 FCFS 和 SJF 的折中。每次调度先算响应比，选最高的：

$$R = \frac{等待时间 + 要求服务时间}{要求服务时间}$$

三条推论：

1. 等待时间相同 → 服务时间越短响应比越高 → **照顾短作业**（像 SJF）
2. 服务时间相同 → 等得越久响应比越高 → **先来先服务**（像 FCFS）
3. 长作业等得足够久，响应比也能涨上去 → **克服饥饿**

（小声 bb：之前都是估算确定，现在还得额外计算每个任务的响应比，不凭空多了 n 条进程吗……）

### 时间片轮转

主要用于**分时系统**：所有就绪进程按 FCFS 排队，队头进程跑**一个时间片**（如 5ms），用完必须让出 CPU 回队尾重新排队，下一个上。

（我一开始觉得这队列用 FCFS 还是优先级都无所谓，反正执行时间固定——哦不对，如果是优先队列，再次排队就不是去末尾了，那就不平均了。所以就用**普通 FIFO 队列**，有先进先出的性质就行。）

**时间片大小是命门**：

- 足够大（人人一个时间片内跑完）→ **退化成 FCFS**
- 太小 → 进程间切换过于频繁，开销吃掉有效运行时间

选时间片要考虑：系统响应时间、就绪进程数目、系统处理能力。

### 多级队列

系统里只设一个就绪队列、用单一算法，满足不了不同用户的口味。**多级队列**：设多个就绪队列，不同类型进程**固定**分到不同队列，每队列可用不同算法，队列之间也有优先级。多处理机系统还能给每个处理机配独立队列、各自策略。

### 多级反馈队列：统筹兼顾

时间片轮转和优先级调度的综合与发展，**动态调整**优先级和时间片，兼顾多方面目标——照顾短进程（吞吐量、周转时间）、照顾 IO 型进程（设备利用率、响应时间），还**不用事先估计执行时间**。

![[image-95f40d96.png]]

规则：

1. 设多个就绪队列，优先级第 1 级最高、依次递减；**优先级越高的队列时间片越小**（第 i+1 级时间片一般是第 i 级的 2 倍）
2. 新进程先进第 1 级队列末尾，按 FCFS 等待；轮到时能在时间片内完成就撤离，完不成 → 降到第 2 级队列末尾，以此类推
3. 降到第 n 级（最低级）后，在第 n 级里用**时间片轮转**跑
4. **按队列优先级调度**：第 1 级空了才跑第 2 级……第 i 级空了才跑第 i+1 级
5. 处理机在跑第 i 级进程时，只要有**任何更高优先级队列来了新进程** → 立即把当前进程放回第 i 级队尾，CPU 给新的

很巧妙。效果：

- 终端型作业用户（短作业）：高优先级队列里几个时间片就跑完 → **短作业优先**
- 短批处理作业用户：周转时间较短
- 长批处理作业用户：在前面队列里已得到部分执行，**不会长期得不到处理**

统筹兼顾，而不是像前面那些算法一样"if 什么就执行什么"。

各算法总览：

![[image-ce925d62.png]]

## 五、进程切换：上下文切换

任何进程都是在操作系统内核支持下运行的，进程切换也一样。

**上下文** = 某一时刻 CPU 寄存器和程序计数器的内容。上下文切换 = 内核把旧进程状态存进它的 PCB，再加载新进程的上下文。流程：

1. 挂起当前进程，保存 CPU 上下文（PC + 各寄存器）
2. 更新 PCB 信息，把 PCB 移入相应队列（就绪/某事件阻塞队列）
3. 选择另一个进程执行，更新其 PCB
4. 跳到新进程 PCB 中 PC 指向的位置，恢复处理机上下文

上下文切换是计算密集型的，每秒几十上百次切换、每次纳秒级——所以才有"线程内切换省开销"和"硬件多寄存器组切换"这些优化。

**上下文切换 vs 模式切换**（容易混）：

- **模式切换**：用户态 ↔ 核心态，CPU 逻辑上**还在执行同一个进程**（进内核处理完中断又回到该进程），不算上下文切换
- **上下文切换**：换了进程，只能发生在**内核态**

## 六、盲点总复习

1. **CPU 繁忙型作业**类似长作业，占 CPU 久、很少请求 IO，用 FCFS 可从容完成；**IO 繁忙型**作业频繁放弃 CPU、占用时间不长，一放弃就得重新排队，用 SJF 合适
2. **为什么 SJF 平均周转时间最短**：j1、j2、j3 同时到达，执行时间 t1、t2、t3，按 j1j2j3 顺序跑，周转时间分别是 t1、t1+t2、t1+t2+t3，平均 = (3t1+2t2+t3)/3——**先执行的权重更大**，要平均最小就把小的数乘大权重，所以短作业先跑
3. **中断向量**本身是中断服务程序的入口地址，所以**中断向量地址是该入口地址的地址**
4. 高响应比不会饥饿：长作业等待时间增加，响应比变大，执行机会增大
5. 调度时机三禁（处理中断、内核临界区、原子操作）≠ 进程在（普通）临界区时不能调度——普通临界区访问慢速外设时若禁止调度，系统性能会非常差
6. 计算题画**甘特图**：横轴时间、纵轴进程，按算法规则一格格画出来，周转时间和等待时间直接从图上数

---

CPU 分完了，但多个进程要同时碰一份资源怎么办？下一章讲同步与互斥 → [[04-同步与互斥]]

⬅️ 🏠 [[00-操作系统总览]] ➡️ [[04-同步与互斥]]