磁盘调度算法

项目	值
核心概念	$$T_a = T_s + T_r + T_{\text{传输}}$$
关键公式/性质	磁道（Track）：盘片上的同心圆
考试频率	⭐⭐⭐⭐

1. 磁盘结构

• 磁道（Track）：盘片上的同心圆
• 扇区（Sector）：磁道被分割成的弧段，是最小存取单位
• 柱面（Cylinder）：所有盘片上相同编号的磁道
• 磁头（Head）：读写数据的部件

2. 磁盘访问时间组成

$$T_a = T_s + T_r + T_{\text{传输}}$$

组成部分	含义	典型值
寻道时间 $T_s$	磁头移动到目标磁道的时间	最长，几毫秒到十几毫秒
旋转延迟 $T_r$	等待目标扇区转到磁头下方的时间	平均 = 旋转半圈的时间
传输时间	读写数据的时间	通常很短

旋转延迟计算：$T_r = \dfrac{1}{2} \times \dfrac{60}{rpm} \text{ (秒)}$。

3. 六种磁盘调度算法

1. FCFS（先来先服务）：按请求到达顺序服务。优点：公平、无饥饿；缺点：寻道时间长、效率低。
2. SSTF（最短寻道时间优先）：选离当前磁头最近的请求。优点：平均寻道时间短；缺点：可能饥饿。
3. SCAN（电梯算法）：磁头单方向移动到尽头再反向。优点：寻道时间较好、无饥饿；缺点：两端磁道等待不均。
4. C-SCAN（循环扫描）：单方向移动，到头直接回起点再同方向。优点：各磁道等待更均匀；缺点：回程不服务。
5. LOOK（改进 SCAN）：该方向无请求就反向，不到尽头。
6. C-LOOK（改进 C-SCAN）：回程直接跳到最远有请求的磁道。

4. 算法对比

算法	寻道时间	公平性	饥饿	特点
FCFS	长	公平	无	简单但效率低
SSTF	短	不公平	有	可能饿死远端请求
SCAN	较短	较公平	无	电梯算法，两端不均
C-SCAN	较短	公平	无	回程不服务，等待更均匀
LOOK	较短	较公平	无	SCAN 的优化版
C-LOOK	较短	公平	无	C-SCAN 的优化版

5. 寻道时间计算示例

假设当前磁头在 53 号磁道，请求序列：98, 183, 37, 122, 14, 124, 65, 67。

• FCFS：53→98→183→37→122→14→124→65→67，总移动 $= 45+85+146+85+108+110+59+2 = $ 640 道
• SSTF：53→65→67→37→14→98→122→124→183，总移动 $= 12+2+30+23+84+24+2+59 = $ 236 道
• SCAN（向 0 方向）：53→37→14→0→65→67→98→122→124→183，总移动 $= 16+23+14+65+2+31+24+2+59 = $ 236 道