【操作系统】磁盘调度算法（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

按顺序服务，计算磁头移动距离：

总寻道距离：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，请求序列同上）：

总寻道距离：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的特点

6️⃣ 四种算法对比表

补充算法（了解）：

• 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。

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 #操作系统