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

磁盘寻道时间计算与调度算法（FCFS、SSTF、SCAN、C-SCAN）

news 2026/6/4 3:53:14

适合读者：软考中级备考同学
阅读时间：4分钟
内容：四种磁盘调度算法、寻道时间计算、优缺点对比、例题

1. 为什么需要磁盘调度？

磁盘访问时间主要由三部分组成：寻道时间 + 旋转延迟 + 传输时间。其中寻道时间（磁头移动到目标磁道的时间）占比最大。磁盘调度算法通过优化多个I/O请求的执行顺序，减少平均寻道时间，从而提高磁盘吞吐量。

软考中常考查四种经典算法：FCFS、SSTF、SCAN、C-SCAN。要求能模拟请求序列，计算总寻道距离或平均寻道时间。

2. 基本概念

磁道号：磁头位置用磁道编号表示（如0~199）。
寻道距离：从一个磁道移动到另一个磁道需要经过的磁道数（绝对值差）。
总寻道距离：所有请求执行过程中，磁头移动的磁道数之和。
平均寻道距离：总寻道距离 ÷ 请求个数。

假设磁头初始位置为P0P_0P0，请求序列为R1,R2,...,RnR_1, R_2, ..., R_nR1,R2,...,Rn。调度算法决定服务顺序。

3. 四种调度算法详解

3.1 FCFS（First Come First Served，先来先服务）

原理：按请求到达的先后顺序依次服务。

优点：公平，实现简单。
缺点：平均寻道距离通常很大，性能较差。

计算示例：
初始磁道 = 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.2 SSTF（Shortest Seek Time First，最短寻道时间优先）

原理：每次选择离当前磁道最近（寻道距离最小）的请求先服务。

优点：平均寻道距离明显小于FCFS。
缺点：可能导致“饥饿”（远处请求长期得不到服务）。

示例：初始100，请求 [55,58,39,18,90,160,150,38,184]

当前100，最近的是90（距离10）→ 服务90
当前90，最近的是58（距离32）还是55（35）？58更近，服务58
当前58，最近的是55（3），服务55
当前55，最近的是39（16），服务39
当前39，最近的是38（1），服务38
当前38，最近的是18（20），服务18
当前18，最近的是150（132）还是160（142）还是184（166）？150最近，服务150
当前150，最近的是160（10），服务160
当前160，最近的是184（24），服务184
计算移动距离：|100-90|=10，|90-58|=32，|58-55|=3，|55-39|=16，|39-38|=1，|38-18|=20，|18-150|=132，|150-160|=10，|160-184|=24，总和=10+32+3+16+1+20+132+10+24=248。明显小于498。

3.3 SCAN（电梯算法）

原理：磁头从当前位置开始，沿一个方向移动（如向磁道号增加方向），服务沿途所有请求，直到该方向最末端，然后反向移动服务另一方向的请求。如同电梯上下楼。

优点：吞吐量高，无饥饿。
缺点：两端请求响应慢。

示例：初始100，方向向大号（增加），请求同上。

先向大号方向移动，沿途请求：90(?) 注意90小于100，反向？SCAN先按指定方向，通常先服务同方向上的请求。假设方向向大号，则先服务大于等于100的：160,150,184。顺序按磁道号：150,160,184（或按遇到顺序，通常按递增）。但标准SCAN会一直移动到最大磁道（假设最大199），然后再反向。这里我们按移动到最大请求184后反向。
实际步骤：从100向大号移动，首先遇到150？但150>100，还有160、184。应服务顺序150,160,184。然后反向（向小号），服务剩余小号请求：90,58,55,39,38,18（按递减顺序）。
计算：
100→150 (50)，150→160 (10)，160→184 (24)，然后184反向到18：184→90? 不对，反向时应从184一直走到最小请求18，沿途服务所有。移动距离：184→90=94，但90不是最小，还有58,55,39,38,18。所以实际移动：184→18=166。但中间经过90,58,…会依次服务，但移动距离只算起点到终点？不，需要分段计算：
正确方法：先向大号到184，然后反向到18，总移动距离 = (184-100) + (184-18) = 84 + 166 = 250。
如果只到最大请求（184）而不必到磁道尽头，则反向时从184到18距离166。总250。

3.4 C-SCAN（循环扫描算法）

原理：磁头单向移动（比如向大号），服务所有沿途请求，到达末端后直接快速返回到另一端（起始端），不服务返回途中的请求，然后继续同向移动。类似循环。

优点：所有请求响应时间更均匀，避免两端不公平。
缺点：返回过程浪费寻道时间。

示例：初始100，向大号移动，服务大于100的请求150,160,184，到达184后（或磁道最大199），直接返回到最小请求（0或18），然后继续向大号移动服务剩余小号请求？注意C-SCAN是单向，返回时不服务，然后重新从最小向大号移动。但剩余小号请求（90,58,55,39,38,18）都小于100，在第一次向大号时已经错过，所以返回后从最小开始向大号移动，会依次服务18,38,39,55,58,90。
移动距离：100→184 = 84，184→0 = 184（假设返回起点0），然后0→90 = 90，总 = 84+184+90 = 358。如果只返回到最小请求18：184→18=166，然后18→90=72，总84+166+72=322。