# 11 处理机调度

> **课程**：操作系统
> **关联章节**：[[06_进程控制]] | [[12_死锁]]

---

## 一、处理器调度的概念

### 1.1 什么是调度

处理器调度的核心任务是将 **CPU 时间** 公平、合理地分配给系统中的各个进程。其本质是一种**资源分配决策**——决定在某一时刻，哪个进程获得 CPU 的使用权。

> **类比**：学校排课——教室（CPU）有限，多个班级（进程）都要使用，需要教务处（调度器）制定合理的课表。

### 1.2 调度的基本原则

| 原则 | 说明 |
|------|------|
| **公平性** | 每个进程都能获得合理的 CPU 时间 |
| **高效性** | CPU 利用率尽可能高 |
| **响应性** | 交互式进程能快速得到响应 |
| **吞吐量** | 单位时间内完成的进程数尽可能多 |

---

## 二、作业（Job）的概念

### 2.1 作业与作业步

- **作业（Job）**：用户提交给系统的一项**完整工作**，是系统进行资源分配的基本单位。
- **作业步（Job Step）**：作业中若干个**既独立又相互关联**的加工步骤。每个作业步完成一项特定的处理任务。

```
作业示例：编写并运行一个C程序
  作业步1：编辑（edit）→ 生成源代码文件
  作业步2：编译（compile）→ 生成目标文件
  作业步3：链接（link）→ 生成可执行文件
  作业步4：运行（run）→ 输出结果
```

### 2.2 作业的状态转换

```mermaid
stateDiagram-v2
    [*] --> 后备 : 用户提交作业
    后备 --> 运行 : 高级调度(被选中)
    运行 --> 完成 : 作业执行结束
    完成 --> [*] : 撤离系统

    state 运行 {
        [*] --> 就绪 : 进程创建
        就绪 --> 执行 : 低级调度(被选中)
        执行 --> 就绪 : 时间片用完
        执行 --> 阻塞 : 等待I/O
        阻塞 --> 就绪 : I/O完成
    }
```

### 2.3 作业控制块（JCB）

作业控制块是作业在系统中存在的唯一标识，包含：

- 作业名、作业状态
- 资源需求（内存大小、外设类型等）
- 优先级、提交时间
- 作业步信息

---

## 三、三级调度体系

```mermaid
graph TB
    subgraph 外存
        A[后备队列<br/>作业池]
    end

    subgraph 内存
        B[就绪队列]
        C[阻塞队列]
        D[CPU 执行]
    end

    A -->|高级调度<br/>长程调度<br/>作业调度| B
    B -->|低级调度<br/>短程调度<br/>进程调度| D
    D -->|时间片用完/等待事件| B
    D -->|等待I/O| C
    C -->|I/O完成| B

    B -->|中级调度<br/>交换调度<br/>内存调度| A

    style A fill:#f9f,stroke:#333
    style D fill:#ff9,stroke:#333
```

| 调度级别 | 别名 | 频率 | 功能 |
|----------|------|------|------|
| **高级调度** | 作业调度 / 长程调度 | 最低 | 从后备队列选择作业调入内存 |
| **中级调度** | 交换调度 / 内存调度 | 中等 | 将暂时不用的进程换出到外存（挂起） |
| **低级调度** | 进程调度 / 短程调度 | 最高 | 从就绪队列选择进程分配 CPU |

---

## 四、调度时机

### 4.1 何时触发调度

```mermaid
flowchart TD
    A{发生什么事件?} --> B[进程结束]
    A --> C[进程等待事件<br/>如I/O请求]
    A --> D[时间片用完]
    A --> E[新进程产生]
    A --> F[等待的事件已发生<br/>如I/O完成]

    B --> G[执行调度]
    C --> G
    D --> G
    E --> G
    F --> G

    G --> H[选择下一个<br/>运行的进程]

    style G fill:#ff9,stroke:#333
```

| 调度时机 | 说明 | 触发场景 |
|----------|------|----------|
| 进程结束 | 运行进程执行完毕 | 正常退出 |
| 等待事件 | 进程因 I/O 等阻塞 | 读磁盘、等待键盘输入 |
| 时间片用完 | 当前进程的时间配额耗尽 | 时钟中断 |
| 新进程产生 | 新进程进入就绪队列 | fork() 创建子进程 |
| 等待事件已发生 | 阻塞进程变就绪 | I/O 中断 |

---

## 五、调度方式

### 5.1 非抢占式调度

进程**自愿放弃** CPU，系统不会强制剥夺。只有当进程结束、阻塞或主动让出时才调度。

- **优点**：实现简单，系统开销小
- **缺点**：响应时间不可预测，不适合交互式系统

### 5.2 抢占式调度

系统**强制剥夺**当前运行进程的 CPU，分配给其他进程。

- **优点**：响应快，适合分时/实时系统
- **缺点**：实现复杂，需要保存/恢复现场，开销较大

```mermaid
graph LR
    subgraph 非抢占式
        A[进程A运行] -->|自愿放弃| B[调度]
        B --> C[进程B运行]
    end

    subgraph 抢占式
        D[进程A运行] -->|强制剥夺| E[调度]
        E --> F[进程B运行]
    end

    style E fill:#f96,stroke:#333
```

---

## 六、调度算法的设计目标

| 系统类型 | 主要目标 | 关键指标 |
|----------|----------|----------|
| **批处理系统** | 周转时间短、吞吐量高 | 平均周转时间、吞吐量 |
| **分时系统** | 响应时间快、均衡性 | 响应时间、公平性 |
| **实时系统** | 满足截止时间、可预测性 | 截止时间满足率 |

### 关键性能指标

$$\text{周转时间} = \text{完成时间} - \text{提交时间}$$

$$\text{等待时间} = \text{周转时间} - \text{运行时间}$$

$$\text{带权周转时间} = \frac{\text{周转时间}}{\text{运行时间}}$$

---

## 七、批处理调度算法

### 7.1 FCFS — 先来先服务

**First Come First Served**：按进程到达就绪队列的**先后顺序**依次调度。

#### 示例

假设三个进程 P1、P2、P3 几乎同时到达：

| 进程 | 运行时间 |
|------|----------|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |

**按 P1→P2→P3 顺序执行：**

```
时间轴（Gantt图）：
|--------P1(24)--------|--P2(3)--|--P3(3)--|
0                      24       27       30
```

| 进程 | 完成时间 | 周转时间 | 等待时间 |
|------|----------|----------|----------|
| P1 | 24 | 24 | 0 |
| P2 | 27 | 27 | 24 |
| P3 | 30 | 30 | 27 |
| **平均** | | **27** | **17** |

**按 P2→P3→P1 顺序执行（短作业在前）：**

```
时间轴（Gantt图）：
|--P2(3)--|--P3(3)--|--------P1(24)--------|
0         3         6                      30
```

| 进程 | 完成时间 | 周转时间 | 等待时间 |
|------|----------|----------|----------|
| P2 | 3 | 3 | 0 |
| P3 | 6 | 6 | 3 |
| P1 | 30 | 30 | 6 |
| **平均** | | **13** | **3** |

> **结论**：FCFS 对短作业非常不利，平均等待时间从 17 降到仅 3（仅调整顺序）。

### 7.2 SJF — 短作业优先

**Shortest Job First**：选择**估计运行时间最短**的进程优先执行。

#### 两种变体

```mermaid
graph TD
    A[SJF 短作业优先] --> B[非抢占式 SJF]
    A --> C[抢占式 SJF<br/>即 SRTF]

    B --> D[进程开始执行后<br/>不会被中断]
    C --> E[新进程到达时<br/>比较剩余时间<br/>更短则抢占]

    style C fill:#f96,stroke:#333
```

#### 示例（非抢占式 SJF）

| 进程 | 到达时间 | 运行时间 |
|------|----------|----------|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |

```
Gantt图（非抢占SJF）：
|--P1(7)--|-P3(1)-|---P2(4)---|---P4(4)---|
0         7       8          12          16
```

- t=0 时只有 P1，P1 先执行
- t=7 时 P2、P3、P4 都已到达，选最短的 P3（运行时间 1）
- t=8 时选 P2（运行时间 4）
- t=12 时选 P4

#### 示例（抢占式 SRTF）

| 进程 | 到达时间 | 运行时间 |
|------|----------|----------|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |

```
Gantt图（抢占式SRTF）：
|--P1--|P1|P3|---P2---|---P4---|--P1--|
0      2  4  5       9       13     16

时间线：
0-2: P1运行(剩5)
2: P2到达(需4) < P1剩余(5), P2抢占
2-4: P2运行(剩2)
4: P3到达(需1) < P2剩余(2), P3抢占
4-5: P3完成
5: P4到达(需4) = P2剩余(2), P2先到
5-7: P2完成(剩2)
7: P4(需4) vs P1(剩5), P4更短
7-11: P4完成
11-16: P1完成(剩5)
```

| 进程 | 完成时间 | 周转时间 | 等待时间 |
|------|----------|----------|----------|
| P1 | 16 | 16 | 9 |
| P2 | 9 | 7 | 3 |
| P3 | 5 | 1 | 0 |
| P4 | 13 | 8 | 4 |
| **平均** | | **8** | **4** |

#### SJF 的优缺点

| 优点 | 缺点 |
|------|------|
| 平均等待时间最小（理论上最优） | 对长作业不利，可能产生**饥饿** |
| 吞吐量高 | 需要预知运行时间（难以精确估计） |

### 7.3 HRRF — 响应比高优先

**Highest Response Ratio First**：FCFS 和 SJF 的折衷方案。

$$\text{响应比} = 1 + \frac{\text{等待时间}}{\text{估计运行时间}}$$

- 短作业：运行时间小，响应比容易变高 → 兼顾 SJF
- 长作业：随着等待时间增长，响应比逐渐增大 → 避免饥饿

```mermaid
flowchart LR
    A[选择响应比最高的进程] --> B{响应比 = 1 + 等待时间/运行时间}
    B --> C[短作业：等待时间相同时<br/>运行时间短 → 响应比高]
    B --> D[长作业：等待时间越长<br/>响应比越高 → 不会饥饿]
```

#### 示例

| 进程 | 到达时间 | 运行时间 |
|------|----------|----------|
| P1 | 0 | 20 |
| P2 | 0 | 5 |
| P3 | 0 | 10 |

t=0: 三个进程同时到达，计算响应比：
- P1: 1 + 0/20 = 1
- P2: 1 + 0/5 = 1
- P3: 1 + 0/10 = 1

全部相同，按 FCFS 选 P1（运行时间 20）。

t=20: P1 完成，计算剩余进程响应比：
- P2: 1 + 20/5 = 5
- P3: 1 + 20/10 = 3

选 P2（响应比 5），P2 执行到 t=25。

t=25: 选 P3（响应比 1+25/10=3.5），P3 执行到 t=35。

### 7.4 优先级调度

**Priority Scheduling**：为每个进程分配优先级，选择优先级最高的进程执行。

| 分类方式 | 说明 |
|----------|------|
| **静态优先级** | 创建时确定，运行期间不变 |
| **动态优先级** | 运行期间根据情况调整 |
| **抢占式** | 高优先级进程到达时可抢占当前进程 |
| **非抢占式** | 等当前进程完成后才重新调度 |

---

## 八、分时调度算法

### 8.1 RR — 时间片轮转

**Round Robin**：就绪队列中的进程按**先来先服务**依次执行，每个进程每次最多运行一个**时间片**（quantum）的时间。

#### 示例

4 个进程，时间片 q = 4：

| 进程 | 到达时间 | 运行时间 |
|------|----------|----------|
| P1 | 0 | 24 |
| P2 | 0 | 3 |
| P3 | 0 | 3 |
| P4 | 0 | 6 |

```
Gantt图（时间片q=4）：
|P1(4)|P2(3)|P3(3)|P4(4)|P1(4)|P4(2)|P1(4)|P1(4)|P1(4)|P1(4)|
0     4     7    10    14    18    20   24    28    32    36

执行顺序：
0-4:   P1执行(剩20)
4-7:   P2执行(完成) ← P2只需3 < 时间片4
7-10:  P3执行(完成) ← P3只需3 < 时间片4
10-14: P4执行(剩2)
14-18: P1执行(剩16)
18-20: P4执行(完成) ← P4剩2 < 时间片4
20-24: P1执行(剩12)
24-28: P1执行(剩8)
28-32: P1执行(剩4)
32-36: P1执行(完成)
```

| 进程 | 完成时间 | 周转时间 | 等待时间 |
|------|----------|----------|----------|
| P1 | 36 | 36 | 12 |
| P2 | 7 | 7 | 4 |
| P3 | 10 | 10 | 7 |
| P4 | 20 | 20 | 14 |
| **平均** | | **18.25** | **9.25** |

#### 时间片大小的影响

```mermaid
graph TD
    A[时间片 q 的选择] --> B[q 太大]
    A --> C[q 太小]
    A --> D[q 适中]

    B --> E[退化为 FCFS<br/>响应时间变长]
    C --> F[进程切换频繁<br/>系统开销过大]
    D --> G[兼顾响应性和效率<br/>通常 10~100ms]

    style B fill:#f99,stroke:#333
    style C fill:#f99,stroke:#333
    style D fill:#9f9,stroke:#333
```

#### 时间片选择示例

> 10 个进程，进程切换开销为 10ms。
>
> - 时间片 q = 200ms：每个进程切换一次，总切换时间 = 10×10ms = 100ms
>   - 开销比 = 100 / (10×200) = **5%** → 可接受
> - 时间片 q = 100ms：每个进程切换约2次，总切换时间 = 20×10ms = 200ms
>   - 开销比 = 200 / (10×200) = **10%** → 开销偏高

### 8.2 多级反馈队列（MFQ）

**Multi-level Feedback Queue**：综合多种调度算法优点的经典调度算法。

```mermaid
graph TB
    subgraph MFQ多级反馈队列
        A[新进程到达] --> B[队列1<br/>优先级最高<br/>时间片最小 如4ms]
        B -->|时间片用完<br/>未完成| C[队列2<br/>优先级中等<br/>时间片中等 如8ms]
        C -->|时间片用完<br/>未完成| D[队列3<br/>优先级最低<br/>时间片最大 如16ms]
    end

    B -->|完成| E[进程结束]
    C -->|完成| E
    D -->|完成| E

    B -->|等待I/O| F[阻塞]
    F -->|I/O完成| B

    style B fill:#9f9,stroke:#333
    style C fill:#ff9,stroke:#333
    style D fill:#f99,stroke:#333
```

#### MFQ 的核心规则

1. **新进程**进入**最高优先级**队列（队列1）
2. 进程在当前队列用完时间片 → **降级**到下一优先级队列
3. 高优先级队列**空**时，才调度低优先级队列
4. 可设置**队列间调度策略**：固定优先级 或 按时间比例分配

| 特点 | 说明 |
|------|------|
| 自适应 | I/O 密集型进程常在高优先级队列（因时间片未用完就阻塞） |
| 周转时间短 | CPU 密集型进程最终会降到低优先级队列，用大时间片执行 |
| 公平性 | 各类用户（交互型、批处理型）都能得到合理服务 |

---

## 九、实时调度算法

### 9.1 EDF — 最早截止时间优先

**Earliest Deadline First**：截止时间越早的进程，优先级越高。

```mermaid
gantt
    title EDF 调度示例
    dateFormat X
    axisFormat %s

    section 进程
    P1(截止t=4) :a1, 0, 2
    P2(截止t=6) :a2, 2, 5
    P3(截止t=8) :a3, 5, 7
```

| 进程 | 到达时间 | 运行时间 | 截止时间 |
|------|----------|----------|----------|
| P1 | 0 | 2 | 4 |
| P2 | 0 | 3 | 6 |
| P3 | 0 | 2 | 8 |

调度过程：
1. t=0：P1(截止4) < P2(截止6) < P3(截止8) → 执行 P1
2. t=2：P1 完成，P2(截止6) < P3(截止8) → 执行 P2
3. t=5：P2 完成，执行 P3
4. t=7：全部完成，均满足截止时间

### 9.2 LLF — 最低松弛度优先

**Least Laxity First**：选择**松弛度最小**的进程优先执行。

$$\text{松弛度} = \text{必须完成时间} - \text{本身运行时间} - \text{当前时间}$$

> 松弛度越小，说明该进程越"紧迫"。

#### 示例

| 进程 | 运行时间 | 截止时间 |
|------|----------|----------|
| P1 | 2 | 8 |
| P2 | 4 | 12 |

t=0 时刻：
- P1 松弛度 = 8 - 2 - 0 = **6**
- P2 松弛度 = 12 - 4 - 0 = **8**

P1 松弛度更小，先执行 P1。

---

## 十、优先级倒置问题

### 10.1 问题描述

**优先级倒置（Priority Inversion）**：高优先级进程被低优先级进程间接阻塞的现象。

```mermaid
sequenceDiagram
    participant H as 高优先级进程H
    participant M as 中优先级进程M
    participant L as 低优先级进程L
    participant R as 共享资源R

    L->>R: 获得资源R(加锁)
    H->>R: 请求资源R → 阻塞！
    Note over H: H必须等待L释放R
    M->>M: M到达，优先级高于L
    Note over M: M抢占L执行
    Note over H: H被M间接阻塞！<br/>优先级倒置发生！
    M->>M: M执行完毕
    L->>R: 释放资源R
    H->>R: 获得资源R，继续执行
```

### 10.2 解决方案——优先级继承

**Priority Inheritance Protocol**：当高优先级进程因共享资源阻塞时，**临时提升**持有该资源的低优先级进程的优先级，使其尽快完成并释放资源。

```mermaid
sequenceDiagram
    participant H as 高优先级进程H
    participant L as 低优先级进程L(提升优先级)
    participant M as 中优先级进程M
    participant R as 共享资源R

    L->>R: 获得资源R
    H->>R: 请求资源R → 阻塞
    Note over L: L的优先级临时提升为H的优先级
    Note over M: M到达，但L优先级已提升
    Note over M: M无法抢占L！
    L->>R: 释放资源R
    Note over L: L优先级恢复原值
    H->>R: 获得资源R，继续执行
```

---

## 十一、Linux 调度器

### 11.1 CFS — 完全公平调度器

**Completely Fair Scheduler**：Linux 默认调度器，基于**虚拟运行时间（vruntime）**实现公平调度。

核心思想：**vruntime 最小的进程优先执行**。

$$\text{vruntime} += \text{实际运行时间} \times \frac{\text{nice 值基准权重}}{\text{该进程权重}}$$

```mermaid
graph TD
    A[CFS调度器] --> B{选择 vruntime<br/>最小的进程}
    B --> C[红黑树组织<br/>就绪进程]
    C --> D[最左叶子节点<br/>= vruntime 最小]
    D --> E[执行该进程]
    E --> F[更新 vruntime]
    F --> C

    style D fill:#9f9,stroke:#333
```

#### CFS 特点

| 特性 | 说明 |
|------|------|
| 无固定时间片 | 根据进程权重和系统负载动态计算 |
| 红黑树结构 | O(log n) 插入/查找，高效调度 |
| 公平性保证 | nice 值越低（优先级越高），vruntime 增长越慢 |
| 自动适配 | I/O 密集型进程 vruntime 自然较小，获得更多 CPU |

### 11.2 调度器类层次

```mermaid
graph TB
    A[调度器类优先级] --> B[Stop Task<br/>最高优先级<br/>停止特定CPU]
    A --> C[Real-Time<br/>实时调度类]
    A --> D[Fair<br/>CFS 调度类<br/>普通进程]
    A --> E[Idle Task<br/>最低优先级<br/>空闲任务]

    B --> C --> D --> E

    style B fill:#f66,stroke:#333
    style C fill:#f96,stroke:#333
    style D fill:#9f9,stroke:#333
    style E fill:#99f,stroke:#333
```

**调度顺序**：Stop Task > Real-Time > Fair > Idle Task

每次调度时，优先从高优先级调度类中选择进程。

### 11.3 实时进程调度策略

| 策略 | 说明 |
|------|------|
| **SCHED_FIFO** | 先来先服务。实时进程一旦获得 CPU，将一直执行直到主动放弃或被更高优先级进程抢占 |
| **SCHED_RR** | 时间片轮转。同优先级的实时进程轮流使用 CPU，时间片用完后回到队尾 |

---

## 十二、调度算法对比总结

```mermaid
graph LR
    subgraph 批处理算法
        FCFS[FCFS<br/>简单公平]
        SJF[SJF/SRTF<br/>最优平均等待]
        HRRF[HRRF<br/>FCFS+SJF折衷]
        PRIO[优先级调度<br/>灵活控制]
    end

    subgraph 分时算法
        RR[RR 轮转<br/>公平响应]
        MFQ[多级反馈队列<br/>综合最优]
    end

    subgraph 实时算法
        EDF[EDF<br/>截止时间优先]
        LLF[LLF<br/>松弛度优先]
    end

    FCFS -.->|缺点: 短作业等待久| SJF
    SJF -.->|缺点: 长作业饥饿| HRRF
    RR -.->|时间片选择关键| MFQ
```

| 算法 | 类型 | 抢占 | 优点 | 缺点 |
|------|------|------|------|------|
| FCFS | 批处理 | 否 | 简单公平 | 短作业等待时间长 |
| SJF | 批处理 | 否 | 最小平均等待 | 长作业饥饿 |
| SRTF | 批处理 | 是 | 更优的平均等待 | 长作业饥饿 |
| HRRF | 批处理 | 否 | 兼顾公平 | 需预估运行时间 |
| RR | 分时 | 是 | 响应快 | 时间片选择影响大 |
| MFQ | 分时 | 是 | 自适应各类进程 | 参数调整复杂 |
| EDF | 实时 | 是 | 利用率可达100% | 过载时不确定 |
| LLF | 实时 | 是 | 松弛度精确 | 频繁切换开销 |

---

## 十三、本讲关键公式

$$\text{周转时间} = \text{完成时间} - \text{提交时间}$$

$$\text{等待时间} = \text{周转时间} - \text{运行时间}$$

$$\text{带权周转时间} = \frac{\text{周转时间}}{\text{运行时间}} \geq 1$$

$$\text{平均周转时间} = \frac{1}{n}\sum_{i=1}^{n}T_i$$

$$\text{响应比} = 1 + \frac{\text{等待时间}}{\text{估计运行时间}}$$

$$\text{松弛度} = \text{必须完成时间} - \text{本身运行时间} - \text{当前时间}$$

$$\text{时间片开销比} = \frac{\text{进程数} \times \text{切换时间}}{\text{进程数} \times \text{时间片}} = \frac{\text{切换时间}}{\text{时间片}}$$

---

## 十四、常见考点

1. **FCFS/SJF/RR 手工计算**：给定进程到达时间和运行时间，画 Gantt 图，计算平均等待时间和周转时间
2. **时间片大小对 RR 的影响**：太大退化为 FCFS，太小切换开销大
3. **响应比计算**：HRRF 的每一步调度决策
4. **优先级倒置场景分析**及优先级继承原理
5. **CFS 核心思想**：vruntime 最小优先

---

**上一章**：[[06_进程控制]]
**下一章**：[[12_死锁]]