【操作系统】磁盘调度算法（FCFS/SSTF/SCAN/C-SCAN）
考点频率：★★★★☆（选择题常考，有时结合计算题考查寻道距离）
难度：⭐⭐⭐
建议：重点掌握每种算法的磁头移动顺序和总寻道距离的计算方法，理解SCAN与C-SCAN的核心区别
1️⃣ 为什么需要磁盘调度？
磁盘（机械硬盘）的访问时间由三部分组成：
| 组成部分 | 说明 | 占比 |
|---|---|---|
| 寻道时间 | 磁头移动到目标磁道的时间 | 最大（占主导） |
| 旋转延迟 | 目标扇区旋转到磁头下方的时间 | 中等 |
| 传输时间 | 实际读写数据的时间 | 最小 |
其中寻道时间占比最大，因此减少平均寻道距离是磁盘调度算法的主要目标。
注：SSD固态硬盘没有机械结构，不存在寻道时间，因此磁盘调度算法主要针对传统机械硬盘（HDD）。
2️⃣ 先来先服务（FCFS，First Come First Served）
2.1 核心思想
按请求到达的先后顺序依次服务，公平、无饥饿，但效率通常最低。
2.2 计算示例
磁头初始位置：100
请求序列：55, 58, 39, 18, 90, 160, 150, 38, 184
按顺序服务，计算磁头移动距离：
| 步骤 | 当前磁道 → 目标磁道 | 移动距离 |
|---|---|---|
| 1 | 100 → 55 | 45 |
| 2 | 55 → 58 | 3 |
| 3 | 58 → 39 | 19 |
| 4 | 39 → 18 | 21 |
| 5 | 18 → 90 | 72 |
| 6 | 90 → 160 | 70 |
| 7 | 160 → 150 | 10 |
| 8 | 150 → 38 | 112 |
| 9 | 38 → 184 | 146 |
总寻道距离：45+3+19+21+72+70+10+112+146 =498
平均寻道距离：498/9 ≈ 55.3
3️⃣ 最短寻道时间优先（SSTF，Shortest Seek Time First）
3.1 核心思想
每次选择距离当前磁头最近的请求服务。平均寻道距离优于FCFS，但可能导致饥饿（远处的请求长期得不到服务），也可能导致磁头在局部区域来回震荡。
3.2 计算示例
同上条件（初始100，请求序列同上）：
| 步骤 | 当前磁道 | 最近请求 | 移动距离 |
|---|---|---|---|
| 1 | 100 | 90 | 10 |
| 2 | 90 | 58 | 32 |
| 3 | 58 | 55 | 3 |
| 4 | 55 | 39 | 16 |
| 5 | 39 | 38 | 1 |
| 6 | 38 | 18 | 20 |
| 7 | 18 | 150 | 132 |
| 8 | 150 | 160 | 10 |
| 9 | 160 | 184 | 24 |
总寻道距离：10+32+3+16+1+20+132+10+24 =248
平均寻道距离：248/9 ≈ 27.6（明显优于FCFS）
4️⃣ 扫描算法（SCAN，电梯算法）
4.1 核心思想
磁头沿一个方向移动，服务沿途所有请求，直到该方向最末端（最大磁道号），然后反向移动，继续服务另一方向的请求。
类比电梯：电梯向上运行，中途有人按楼层就停，一直跑到顶楼，然后向下运行，再服务下行的请求。
4.2 计算示例
同上条件，假设磁头初始向磁道号增大的方向移动，最大磁道号为199。
服务顺序：
- 向大号方向：先遇到的请求有哪些？从100向大号，依次遇到
160, 150, 184（按磁道号排序：150, 160, 184）。
但注意：从100向大号移动，最先遇到的是150？是的，因为90、58等都在小号方向，当前方向不会服务它们。 - 到达184（或到达199）后反向，服务小号方向的请求：
90, 58, 55, 39, 38, 18（按递减顺序：90, 58, 55, 39, 38, 18）
总寻道距离（假设从100移动到最大磁道199，再反向到最小请求18）：
- 100 → 199：99
- 199 → 18：181
- 总距离 = 99 + 181 =280
（如果只移动到最大请求184，距离为 84 + 166 = 250）
4.3 SCAN的特点
| 优点 | 缺点 |
|---|---|
| 吞吐量较高，平均寻道时间较短 | 两端请求响应慢（边缘地区等待时间长） |
| 无饥饿（所有请求最终都会服务） | 磁头移动方向变化频繁 |
5️⃣ 循环扫描算法（C-SCAN，Circular SCAN）
5.1 核心思想
磁头单向移动（如只向磁道号增大的方向），服务沿途所有请求，到达最远端后快速返回到起点（返回过程中不服务任何请求），然后重新开始向大号方向移动。
类比：把磁道想象成一个环形，磁头永远沿着一个方向转圈。
5.2 计算示例
同上条件，初始100，向大号方向。
服务顺序：
- 向大号方向服务：150, 160, 184（按顺序）
- 到达184（或199）后，快速返回0（返回过程不服务）
- 从0重新向大号方向移动，服务剩余的小号请求：18, 38, 39, 55, 58, 90（按递增顺序）
总寻道距离（假设从184快速返回0，再从0到90）：
- 100 → 184：84
- 184 → 0：184（返回，不服务）
- 0 → 90：90
- 总距离 = 84 + 184 + 90 =358
（如果最大磁道号为199，则距离为 99 + 199 + 90 = 388）
5.3 C-SCAN的特点
| 优点 | 缺点 |
|---|---|
| 对各磁道位置的请求响应时间更均匀 | 返回过程浪费寻道时间 |
| 无饥饿 | 总寻道距离通常略大于SCAN |
6️⃣ 四种算法对比表
| 算法 | 选择依据 | 是否有饥饿 | 平均寻道 | 实现复杂度 |
|---|---|---|---|---|
| FCFS | 请求到达顺序 | 无 | 高 | 最低 |
| SSTF | 离当前磁头最近 | 有（远处可能被饿死） | 较低 | 中等 |
| SCAN（电梯） | 当前方向上的下一个 | 无 | 低 | 中等 |
| C-SCAN | 单向循环 | 无 | 较低 | 较高 |
补充算法（了解）：
- LOOK算法：SCAN的改进版，磁头只需移动到当前方向上的最远请求，不需要到达物理最末端（如199）。上面的SCAN示例中，如果采用LOOK，磁头只到184就反向，距离会从280降到250。
- C-LOOK：C-SCAN的改进版，磁头只移动到当前方向上的最远请求，然后直接返回到当前方向上的最近请求。在示例中，C-LOOK的距离为 (184-100) + (184-18) + (90-18) = 84 + 166 + 72 = 322，比C-SCAN的358更优。
7️⃣ 经典例题
例题1：某磁盘请求序列（磁道号）：98, 183, 37, 122, 14, 124, 65, 67，磁头初始在53，向磁道号增大的方向。分别用SCAN和C-SCAN调度，求服务顺序。
解析：
SCAN（向大号，到199后反向）：
向大号：98, 122, 124, 183（按递增）
反向向小号：67, 65, 37, 14（按递减）
服务顺序：98 → 122 → 124 → 183 → 67 → 65 → 37 → 14C-SCAN（向大号，到199后返回0，再向大号）：
向大号：98, 122, 124, 183
返回0（不服务）
从0向大号：14, 37, 65, 67
服务顺序：98 → 122 → 124 → 183 → 14 → 37 → 65 → 67
答案：SCAN: 98→122→124→183→67→65→37→14；C-SCAN: 98→122→124→183→14→37→65→67
例题2：以下关于磁盘调度算法的叙述中，正确的是（ ）。
A. SSTF算法不会导致饥饿
B. SCAN算法在服务过程中不会改变方向
C. C-SCAN算法在返回过程中也服务请求
D. FCFS算法公平性最好
解析：A错误（SSTF可能导致饥饿）；B错误（SCAN到达最远端后会改变方向）；C错误（C-SCAN返回时不服务）；D正确。选D。
8️⃣ 记忆口诀
FCFS按序来，SSTF找最近。
SCAN像电梯，到顶再回移。
C-SCAN单向走，返回不服务。
9️⃣ 小测验（评论区对答案）
磁头初始在50，向磁道号增大的方向，请求序列为
10, 80, 30, 90, 60。采用SCAN算法，服务顺序为（ ）。
A. 60→80→90→30→10
B. 60→80→90→10→30
C. 60→90→80→30→10
D. 80→90→60→30→10
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #磁盘调度 #FCFS #SSTF #SCAN #C-SCAN #操作系统
