磁盘结构
- 盘片（Platter）：磁盘的物理盘片，双面均可记录数据
- 磁道（Track）：盘片上的同心圆数据轨道
- 扇区（Sector）：磁道上的最小存储单元，通常 512B
- 柱面（Cylinder）：所有盘片上相同半径的磁道集合
- 磁盘容量 = 每扇区字节数 × 每磁道扇区数 × 每面磁道数 × 面数
磁盘访问时间组成
- 寻道时间（Seek Time）：磁头移动到目标柱面所花费的时间，访问时间的主要部分
- 旋转延迟（Rotational Latency）：目标扇区旋转到磁头下方的时间，平均为转半圈的时间
- 传输时间（Transfer Time）：数据读写的时间
- 总访问时间 = 寻道时间 + 旋转延迟 + 传输时间
重点 磁盘调度算法
| 算法 | 策略 | 平均寻道 | 特点 |
|---|
| FCFS | 按请求顺序服务 | ~55.3 | 简单公平，平均寻道长 |
| SSTF（最短寻道时间优先） | 选离当前磁头最近的请求 | ~27.5 | 效率高，可能发生饥饿（磁壁粘着） |
| SCAN（电梯算法） | 单向移动，沿途服务，到端头反向 | 中等 | 请求等待时间较均匀 |
| C-SCAN（循环扫描） | 单向服务，另一端直接返回不服务 | 中等 | 响应时间更均匀 |
| N-step SCAN | 请求分 N 个子队列，逐队列 SCAN | 较好 | 防止磁壁粘着 |
| FSCAN | 两个队列交替 SCAN，简化的 N-step | 较好 | 减少粘着、实现简单 |
| LOOK / C-LOOK | SCAN 变种，磁头只走到最后一个请求位置 | 更好 | 不到达磁盘端头，减少无效移动 |
FCFS（先来先服务）
- 按请求到达的顺序依次服务
- 优点：实现简单，公平无饥饿
- 缺点：平均寻道时间长，磁头在磁盘上来回移动，效率低
- 平均寻道距离约 55.3（典型请求序列）
SSTF（最短寻道时间优先，Shortest Seek Time First）
- 每次选择离当前磁头位置最近的请求服务
- 优点：平均寻道时间减少，约 27.5
- 缺点：靠近中间磁道的请求可能被不断推迟，产生饥饿；极端情况下出现磁壁粘着（magnetic wall adhesion），即磁头长时间停留在某区域服务最近的请求，远处请求无限期等待
SCAN（电梯算法，Elevator Algorithm）
- 磁头从一端向另一端移动，沿途服务经过的请求
- 到达磁盘端头后反向继续服务
- 优点：不会饥饿，等待时间较为均匀
- 缺点：两端磁道的请求等待时间比中间长
C-SCAN（循环扫描，Circular SCAN）
- 磁头只在一个方向上服务请求
- 到达端头后直接快速返回另一端（返回路径不服务）
- 优点：各磁道请求的等待时间更加均匀
- 缺点：每次扫描服务请求数比 SCAN 少
N-step SCAN
- 将请求队列分成 N 个子队列
- 每次 SCAN 只处理一个子队列，新请求放入后续子队列
- 优点：有效防止磁壁粘着现象
- 参数 N 控制吞吐量和公平性的平衡
FSCAN
- N-step SCAN 的简化版本（N=2）
- 使用两个请求队列交替服务
- 当前队列用 SCAN 处理时，新请求放入另一个队列
- 优点：实现简单，同样能防止磁壁粘着
LOOK / C-LOOK（提前折返算法）
- 改进的 SCAN/C-SCAN
- 磁头不需要移动到磁盘端头，只移动到该方向最远的请求位置就折返
- LOOK 对应 SCAN，C-LOOK 对应 C-SCAN
- 优点：减少无效移动，缩短平均寻道时间
- 现代磁盘调度中实际采用 LOOK/C-LOOK
扇区交错（Sector Interleaving）
- 逻辑扇区号与物理扇区号错开排列
- 原因：磁盘旋转速度快，CPU 处理完一个扇区数据后若来不及读取下一个连续的物理扇区，需等一整圈
- 交错因子（Interleave Factor）：逻辑连续扇区之间的物理扇区间隔
- 目的：减少旋转延迟，匹配 CPU 处理速度与磁盘传输速度
RAID 与磁盘调度
- 磁盘阵列中调度算法需要考虑条带分布，利用并行性
- 独立磁盘间可并行执行多个请求