当前位置：首页 > news >正文

【操作系统】磁盘调度算法（FCFS/SSTF/SCAN/C-SCAN）

news 2026/7/6 9:06:14

考点频率：★★★★☆（选择题常考，有时结合计算题考查寻道距离）
难度：⭐⭐⭐
建议：重点掌握每种算法的磁头移动顺序和总寻道距离的计算方法，理解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 → 14
C-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。