Appearance
408
操作系统
OS-05-06 磁盘调度算法（FCFS/SSTF/SCAN/C-SCAN/LOOK）
一、定位信息
- 所属圈层：核心层
- 前置知识回顾：理解磁盘的物理结构（磁道、扇区、磁头、寻道时间、旋转延迟），知道磁盘访问时间 = 寻道时间 + 旋转延迟 + 数据传输时间。
- 知识网络位置：本单元是I/O管理中的核心算法，直接影响磁盘I/O性能。磁盘调度算法通过优化磁头移动顺序来减少平均寻道时间。
- 考点热度等级：H级（高频重点）——磁盘调度算法的计算是几乎每年必考的核心考点。
二、知识点讲解
2.1 磁盘访问时间的组成
磁盘访问时间由三部分组成：
- 寻道时间（Seek Time）：磁头移动到目标磁道的时间。是最大的开销，通常占总时间的70%以上。
- 旋转延迟（Rotational Latency）：等待目标扇区旋转到磁头下的时间。平均为磁盘旋转半圈的时间。
- 数据传输时间（Transfer Time）：读写数据的时间。
磁盘调度算法的目标是减少总寻道时间，通过优化磁头移动顺序来实现。
2.2 FCFS（先来先服务）
FCFS：按照请求到达的顺序依次服务。
- 优点：公平，不会产生饥饿
- 缺点：磁头移动幅度大，寻道时间长
- 适用于请求较少的场景
2.3 SSTF（最短寻道时间优先）
SSTF（Shortest Seek Time First）：选择距离当前磁头位置最近的请求。
- 优点：平均寻道时间短
- 缺点：可能产生饥饿——远离磁头的请求可能长期得不到服务
- 不一定最优，但是好的近似
2.4 SCAN（电梯算法）
SCAN：磁头在一个方向上移动，依次服务途经的请求，到达磁盘末端后反向移动。
- 类似电梯的工作方式
- 优点：不会饥饿，寻道时间较短
- 缺点：对两端磁道的请求不公平（中间磁道的请求等待时间短）
2.5 C-SCAN（循环扫描）
C-SCAN（Circular SCAN）：磁头只在一个方向上服务请求，到达末端后快速回到起点（不服务），再从起点开始同方向扫描。
- 优点：提供了更均匀的等待时间
- 缺点：返回时不服务，效率略低
2.6 LOOK和C-LOOK
LOOK：SCAN的改进。磁头不需要移动到磁盘末端，只需移动到该方向最远的请求处就反向。
C-LOOK：C-SCAN的改进。磁头只移动到该方向最远的请求处，然后快速回到最近的请求处继续扫描。
三、记忆与理解辅助
1. 类比记忆：
- FCFS = 排队买票（先来先服务，不管你站哪）
- SSTF = 就近服务（谁离得近先服务谁，可能忽略远处的人）
- SCAN = 电梯（从一楼到顶楼，再从顶楼到一楼）
- C-SCAN = 单向电梯（从一楼到顶楼，然后回一楼重新开始）
- LOOK = 电梯不到头（有人按了最高层就到那层，不到顶楼）
- C-LOOK = 单向电梯不到头（同上）
2. 口诀："FCFS公平但慢，SSTF快但会饿；SCAN像电梯来回跑，C-SCAN单向更均匀；LOOK不到头更高效。"
3. 五种磁盘调度算法对比表（★高频考点）：
| 对比项 | FCFS | SSTF | SCAN | C-SCAN | LOOK/C-LOOK |
|---|---|---|---|---|---|
| 策略 | 按到达顺序 | 最近的请求 | 来回扫描 | 单向扫描 | SCAN/C-SCAN不到头 |
| 公平性 | 最公平 | 不公平 | 较公平 | 公平 | 较公平 |
| 饥饿 | 无 | 有 | 无 | 无 | 无 |
| 寻道时间 | 长 | 短 | 较短 | 较短 | 较短 |
| 实现复杂度 | 最简单 | 简单 | 中等 | 中等 | 中等 |
| 适用场景 | 请求少 | 通用 | 通用 | 高负载 | 通用 |
4. SCAN vs C-SCAN 对比：
| 对比项 | SCAN | C-SCAN |
|---|---|---|
| 移动方式 | 来回扫描 | 单向扫描 |
| 返回时服务 | 服务 | 不服务 |
| 等待时间均匀性 | 不均匀（两端好中间差） | 均匀 |
| 总寻道时间 | 较短 | 略长（返回时浪费） |
四、例题与精解
例题1（基础巩固）
题目：某磁盘有 个磁道（），磁头当前位置在磁道 ，请求队列为：。分别用FCFS、SSTF和SCAN算法计算磁头移动的总磁道数。
命题意图：考查三种磁盘调度算法的手工模拟。
精解：
1. 审题分析：起始位置53，8个请求，需要逐一模拟每种算法。
2. 解题思路：按算法规则确定服务顺序，计算磁道移动距离。
3. 完整步骤：
FCFS（按到达顺序：98, 183, 37, 122, 14, 124, 65, 67）：
- 53→98→183→37→122→14→124→65→67
- 移动距离：
- 磁道
SSTF（每次选最近的）：
- 53→37(16)→14(23)→65(51)→67(2)→98(31)→122(24)→124(2)→183(59)
- 括号内为本次移动距离
- 移动距离： 磁道
SCAN（向磁道号增大方向扫描，到请求最远处后反向）：
- 53→65→67→98→122→124→183→37→14
- 移动距离：
- 磁道
4. 方法反思：
- SSTF寻道距离最短（208），但可能导致远处的请求饥饿
- FCFS最公平但寻道距离最长（640）
- SCAN折中（299），且不会饥饿
- 考试中需要仔细计算每一步的移动距离，不能跳步
例题2（中等提升）
题目：同例题1的条件（起始位置53，请求队列：98, 183, 37, 122, 14, 124, 65, 67），分别用C-SCAN和LOOK算法计算磁头移动的总磁道数。C-SCAN向磁道号增大方向扫描。
命题意图：考查C-SCAN和LOOK算法的手工模拟。
精解：
1. 审题分析：需要区分C-SCAN和LOOK的差异。
2. 解题思路：C-SCAN返回时不服务，LOOK不到磁盘末端。
3. 完整步骤：
C-SCAN（向增大方向扫描，到该方向最远请求后跳回最近请求）：
- 53→65→67→98→122→124→183（到最远请求）
- 然后跳回：183→14（不服务返回过程中的请求，直接到反方向最近的请求）
- 然后继续：14→37
- 移动距离：
- 磁道
LOOK（SCAN的改进，不到磁盘末端）：
- 53→65→67→98→122→124→183（到该方向最远请求）
- 反向：183→37→14
- 移动距离：
- 磁道
注意：本题中LOOK和SCAN结果相同，因为请求中最远的就是183，不需要到磁盘末端199。如果请求中有190或更远的磁道，LOOK会更高效。
4. 方法反思：C-SCAN的返回距离较大（183→14=169），这是为了保证均匀性付出的代价。LOOK是SCAN的实用改进版，实际系统中通常使用LOOK而非SCAN。
五、考情分析
- 考查频次：磁盘调度算法在近5年真题中出现频率极高，约4-5次。
- 常见题型：选择题（算法判断、总磁道数计算）、计算题（多种算法对比计算）。
- 分值占比：选择题2分，计算题5-8分。
- 命题趋势：给出请求序列，要求用多种算法计算总磁道数并比较是经典题型。近年来可能结合磁盘访问时间的其他组成部分（旋转延迟、传输时间）考查。基于大纲与命题规律推测。
六、易错点提醒
错误表现：SCAN算法中，磁头到达磁盘末端后才反向，即使该方向没有更多请求。 错误原因：混淆了SCAN和LOOK。 正确理解/做法：SCAN（电梯算法）确实到达磁盘末端才反向。LOOK是改进版，只到该方向最远的请求处就反向。考试中需要看清题目要求用哪种算法。
错误表现：C-SCAN返回时仍然服务途经的请求。 错误原因：混淆了C-SCAN和SCAN。 正确理解/做法：C-SCAN返回时不服务任何请求，直接跳回起点。只有在正向扫描时才服务。
错误表现：SSTF算法中，认为一定不会出现饥饿。 错误原因：对SSTF的缺陷认识不足。 正确理解/做法：SSTF可能导致饥饿——如果不断有靠近磁头的新请求到来，远离磁头的旧请求可能永远得不到服务。
错误表现：计算总磁道数时，将起始位置到第一个请求的距离遗漏。 错误原因：忘记磁头需要从当前位置移动到第一个请求处。 正确理解/做法：总磁道数 = 起始位置到第一个请求的距离 + 各请求之间的距离之和。
七、来源标注
- 依据2026考研统考408大纲
- 依据《操作系统概念》（Operating System Concepts, Silberschatz）第12章
- 依据汤小丹《计算机操作系统》第4版第5章