SCAN 磁盘调度
SCAN 算法（电梯算法）沿一个方向移动到磁盘边界后反向扫描，避免饥饿且效率较高。
#type / concept
#status / evergreen
#resource / operating-system
[!info] related notes
SCAN 磁盘调度
一句话定义
SCAN 算法（电梯算法）让磁头从当前位置沿一个方向移动，依次服务该方向上的所有请求，到达磁盘边界后反向扫描，类似电梯运行方式。
核心机制
- 单向扫描：沿一个方向移动，服务途经的所有请求
- 到达边界后反向：必须移动到磁盘最外道（或最内道）才改变方向
- 无饥饿：所有请求最终都会被服务
- 对两端磁道请求有利，中间位置请求可能等待较久
与 LOOK 的区别
SCAN 必须到达磁盘边界（最外道或最内道），而 LOOK 只需到达该方向上最远的请求位置。
例题
题目：
- 磁头初始位置：53
- 请求序列：98, 183, 37, 122, 14, 124, 65, 67
- 磁道范围：0-199
- 初始方向：向磁道号增大方向（向右）
- 假设边界为 199
服务顺序推导：
- 从 53 向右移动，服务途经请求：65, 67, 98, 122, 124, 183
- 到达边界 199
- 反向向左移动，服务剩余请求：37, 14
- 到达边界 0（或最内道）
服务顺序：53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 37 → 14
计算过程：
| 步骤 | 当前位置 | 目标位置 | 移动距离 |
|---|---|---|---|
| 1 | 53 | 65 | |
| 2 | 65 | 67 | |
| 3 | 67 | 98 | |
| 4 | 98 | 122 | |
| 5 | 122 | 124 | |
| 6 | 124 | 183 | |
| 7 | 183 | 199 | |
| 8 | 199 | 37 | |
| 9 | 37 | 14 |
总寻道距离 = 12 + 2 + 31 + 24 + 2 + 59 + 16 + 162 + 23 = 331
平均寻道距离 = 331 / 8 = 41.375
边界与易混淆点
- SCAN 必须到达磁盘边界，LOOK 只到最远请求
- SCAN 对边缘磁道请求较公平，中间位置可能等待
- 与 CSCAN 对比：CSCAN 更公平，但回程不服务
- SCAN 是非抢占式算法