# 3.3 调度算法

## 一、先来先服务调度算法（FCFS）

### 1.1 算法思想

按照进程到达的先后顺序进行调度，先到达的进程先执行。

### 1.2 算法特点

**非抢占式**：一旦进程获得CPU，直到完成才释放。

**优点**：
- 实现简单
- 公平（按到达顺序）

**缺点**：
- 平均等待时间长
- 对短作业不利（护航效应）
- 对I/O繁忙型进程不利

### 1.3 护航效应

**定义**：长进程占用CPU，导致短进程长时间等待。

**例子**：
- 进程P1：执行时间24，到达时间0
- 进程P2：执行时间3，到达时间0
- 进程P3：执行时间3，到达时间0

如果按P1、P2、P3顺序：
- P1等待0，完成24
- P2等待24，完成27
- P3等待27，完成30
- 平均等待时间 = (0+24+27)/3 = 17

如果按P2、P3、P1顺序：
- P2等待0，完成3
- P3等待3，完成6
- P1等待6，完成30
- 平均等待时间 = (0+3+6)/3 = 3

---

## 二、短作业优先调度算法（SJF）

### 2.1 算法思想

选择估计运行时间最短的进程优先执行。

### 2.2 算法特点

**可以是抢占式或非抢占式**

**优点**：
- 平均等待时间最短
- 系统吞吐量高

**缺点**：
- 需要估计运行时间
- 对长作业不利（饥饿）
- 没有考虑作业的紧迫程度

### 2.3 抢占式短作业优先（SRTN）

**最短剩余时间优先**：
- 新进程到达时，如果其运行时间比当前进程的剩余时间短，则抢占CPU
- 总是选择剩余运行时间最短的进程

### 2.4 运行时间的估计

**指数平均法**：
$$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$$

其中：
- $\tau_{n+1}$：下次估计运行时间
- $t_n$：本次实际运行时间
- $\tau_n$：本次估计运行时间
- $\alpha$：平滑因子（0 ≤ α ≤ 1）

---

## 三、优先级调度算法

### 3.1 算法思想

每个进程都有一个优先级，调度时选择优先级最高的进程。

### 3.2 优先级类型

**静态优先级**：
- 进程创建时确定，运行期间不变
- 确定因素：进程类型、资源需求、用户要求

**动态优先级**：
- 进程运行期间可以改变
- 调整因素：等待时间、运行时间、I/O操作

### 3.3 调度方式

**非抢占式优先级调度**：
- 一旦进程获得CPU，直到完成或阻塞才释放

**抢占式优先级调度**：
- 高优先级进程到达时，可以抢占低优先级进程的CPU

### 3.4 优先级反转问题

**定义**：高优先级进程被低优先级进程阻塞的现象。

**例子**：
- 低优先级进程L持有资源R
- 中优先级进程M运行，抢占L
- 高优先级进程H需要资源R，被阻塞
- 结果：M运行，H等待（优先级反转）

**解决方法**：
- **优先级继承**：L临时继承H的优先级
- **优先级天花板**：资源有优先级上限

---

## 四、时间片轮转调度算法（RR）

### 4.1 算法思想

将CPU时间划分为固定长度的时间片，每个进程轮流执行一个时间片。

### 4.2 算法特点

**抢占式**：时间片用完强制切换

**优点**：
- 响应时间快
- 公平
- 适合分时系统

**缺点**：
- 时间片大小难以确定
- 上下文切换开销

### 4.3 时间片大小的确定

**时间片太大**：
- 退化为FCFS
- 响应时间长

**时间片太小**：
- 上下文切换频繁
- 系统开销大

**经验公式**：
- 时间片 = 最大响应时间 / 进程数
- 通常：10-100ms

### 4.4 算法实现

```
就绪队列：P1, P2, P3, P4, ...

P1执行一个时间片
    ↓
P1插入就绪队列尾部
    ↓
P2执行一个时间片
    ↓
P2插入就绪队列尾部
    ↓
...
```

---

## 五、高响应比优先调度算法（HRRN）

### 5.1 算法思想

综合考虑作业的等待时间和要求服务时间，计算响应比，选择响应比最高的作业。

### 5.2 响应比计算

$$响应比 = \frac{等待时间 + 要求服务时间}{要求服务时间} = 1 + \frac{等待时间}{要求服务时间}$$

### 5.3 算法特点

**非抢占式**

**优点**：
- 既考虑等待时间（公平）
- 又考虑运行时间（效率）
- 避免长作业饥饿

**缺点**：
- 需要估计运行时间
- 每次调度都要计算响应比

---

## 六、多级队列调度算法

### 6.1 算法思想

将就绪队列分成多个独立队列，每个队列有自己的调度算法。

### 6.2 队列划分

**按进程类型**：
- 系统进程队列
- 交互进程队列
- 批处理进程队列

**按优先级**：
- 高优先级队列
- 中优先级队列
- 低优先级队列

### 6.3 调度方式

**固定优先级**：
- 先调度高优先级队列
- 只有高优先级队列为空，才调度低优先级队列

**时间片分配**：
- 每个队列分配不同的时间片比例
- 高优先级队列获得更多CPU时间

---

## 七、多级反馈队列调度算法

### 7.1 算法思想

设置多个就绪队列，每个队列有不同优先级和时间片，进程可以在队列之间移动。

### 7.2 算法特点

- 队列优先级从高到低
- 时间片从小到大
- 新进程进入最高优先级队列
- 进程用完时间片后降级到下一队列
- 等待时间过长的进程升级

### 7.3 算法优点

- 短作业优先（在高级队列快速完成）
- 长作业也能得到服务（不会饥饿）
- I/O繁忙型进程优先（快速响应）
- CPU繁忙型进程在后级队列（减少切换）

---

## 八、调度算法比较

| 算法 | 抢占性 | 优点 | 缺点 | 适用场景 |
|-----|--------|------|------|---------|
| FCFS | 非抢占 | 简单公平 | 平均等待时间长 | 批处理 |
| SJF | 都可 | 平均等待时间最短 | 可能饥饿 | 批处理 |
| 优先级 | 都可 | 考虑紧迫程度 | 可能饥饿 | 实时系统 |
| RR | 抢占 | 响应快 | 切换开销 | 分时系统 |
| HRRN | 非抢占 | 综合考虑 | 计算开销 | 批处理 |
| 多级反馈 | 抢占 | 兼顾长短作业 | 复杂 | 通用 |

---

## 九、考研重点

1. **各种调度算法的思想**：FCFS、SJF、优先级、RR、HRRN
2. **算法特点**：抢占/非抢占、优缺点
3. **平均等待时间计算**：会计算各种算法的平均等待时间
4. **护航效应**：FCFS的问题
5. **饥饿问题**：SJF和优先级调度的问题
6. **时间片大小的影响**：RR算法
7. **多级反馈队列**：进程如何在队列间移动

---

*下一节：3.4 优先级调度*