是什么

  • 定义:操作系统对物理外存(机械硬盘/SSD)进行底层抽象与资源管理,包含三大核心职能:

    • 空闲空间管理:用特定数据结构(位示图/空闲表/空闲链表/成组链接)记录物理块的分配与空闲状态;

    • 磁盘调度算法:在机械磁头移动极慢的前提下,以柱面号(磁道号)为核心依据,合理安排访问队列以最小化平均寻道时间;

    • 访问耗时模型:精确量化机械硬件完成一次 I/O 读写所经历的寻道、旋转延迟与数据传输耗时。

  • 大白话:机械磁盘就像一台复古留声机。数据刻在同心圆音轨上,唱针(机械臂)前后换道极慢,转盘转动也要时间。磁盘调度的本质是只管唱针在不同同心圆(柱面/磁道)之间的径向移动,不让它瞎晃;而空闲管理就是一张座位表,标记哪一段还没刻歌。

核心内容

1. 磁盘调度算法调度的底层依据(核心认知)

  • 磁盘调度算法唯一优化的目标是寻道时间(Seek Time),即机械臂在半径方向上的机械移动。

  • 调度排序的硬核依据:只有柱面号(磁道号 Cylinder/Track)。

    • 磁臂是一体联动的,各盘面上的磁头同时进退。在同一个柱面内访问不同盘面只需切换磁头(电子切换,纳秒级),不需要机械寻道。

    • 盘片旋转等待扇区(旋转延迟)由硬件恒速旋转决定,操作系统软件调度算法无法预先优化扇区到达顺序(除非特定硬件支持带旋转感知的 SATF,但 408 统考不涉及)。

    • 若题干给出的是逻辑块号、扇区号或簇号,第一步必须先整除单柱面容量,换算为柱面号,再进行距离对比和调度排序。

2. 磁盘块空闲状态管理方式(如何根据参数秒选?)

空闲管理方式核心机制与结构试题题眼 / 判断特征优缺点 / 考点
位示图法(Bitmap)用内存连续二进制位(bit)与磁盘块一一映射(0 表示空闲,1 表示分配)给出的内存字节数换算成 bit 后,恰好等于磁盘块总数(如 )占用内存极小,易于在内存中快速检索连续空闲块(按字位搜索)
空闲表法类似动态分区分配,为每个连续空闲区建一行 <起始块号, 块数>适合连续分配系统;题目提及“按连续区分配”碎片较多时表项庞大,不适合离散分配
空闲链表法空闲块通过指针串成链表(空闲盘块链或空闲盘区链)每次分配零散单块,从链头摘取分配简单,但多次分配时需频繁修改磁盘指针并访盘
成组链接法UNIX 系统的标准管理法,每组首块记录下一组的块数及块号题干出现“堆栈”、“专设一个超级块”、“每 100 块一组”兼顾链表无限扩展能力与批量分配的高效率
  • 位示图核心计算通法:

    由字号 、位号 反推块号 (字长 位,从 0 计):

    由块号 反查位示图位置:

3. 四大经典磁盘调度策略全景对比

所有策略的决策均基于请求所在的柱面号(磁道号),与盘面号、扇区号无关。

设磁头当前在 100 号柱面,正向柱面号增大方向移动,待访问柱面队列为:[50, 90, 30, 120]。

调度策略核心调度依据与决策逻辑示例访问轨迹(柱面)优缺点 / 核心考点
FCFS(先来先服务)仅按请求到达时间先后调度,完全忽略柱面物理距离绝对公平,但磁臂在柱面间盲目穿梭,寻道性能最差
SSTF(最短寻道优先)贪心选取与当前磁头所在柱面号差值绝对值最小的请求寻道距离短,但边缘柱面易发生饥饿现象
SCAN(电梯算法)按柱面连续单向递增/递减服务,直到磁盘最外/最内边界柱面后再折返消除饥饿;两端柱面的平均响应时间略不均衡
C-SCAN(循环扫描)沿单一柱面方向单向服务,走到底后直接快速折返到最前端柱面,折返途中不服务任何请求柱面响应时间高度均匀;消除局部访问密集带来的不公
LOOK / C-LOOKSCAN/C-SCAN 的实用改良版:根据请求队列中的最大/最小柱面号决策,无更远柱面请求时立即折返轨迹同上(无需盲目冲到物理 0 号或极端边界柱面)实际操作系统中最常用的变体,省去边界空跑距离

4. 磁盘 I/O 读写耗时三元分解模型(终极通用公式)

完成一次磁盘扇区读写的总时延由三部分构成:

Plaintext

[寻道阶段] ───────────────────> [旋转等待阶段] ────────────> [数据传输阶段]
磁臂移动对准目标柱面/磁道         盘片旋转将目标扇区转到磁头下     磁头划过扇区读写数据
(调度算法优化的唯一阶段)         (纯硬件机械旋转,耗时固定)     (纯硬件机械旋转,耗时固定)
  • 寻道时间():

  • 旋转延迟(,题目常指平均旋转延迟):

    设盘片转速为 (转/分),转一整圈耗时 。

    随机读取时,平均只需等待转半圈:

  • 传输时间():

    设每磁道总扇区数为 ,读取 1 个扇区只占整圈旋转时间的 :

  • 单磁道上读写 1 个扇区的固有耗时:

5. 固态存储介质(Flash / SSD)为什么颠覆了调度策略?

  • 机械磁盘的物理瓶颈:机械臂跨柱面移动(寻道)和盘片旋转处于毫秒级(ms),比 CPU 慢五到六个数量级,因此必须耗费 CPU 算力以柱面号为依据计算复杂调度顺序以减少寻道。

  • Flash 半导体芯片的物理特性:

    • 纯电子电路寻址,无柱面、磁臂和旋转机械部件;

    • 随机访问任意物理地址的耗时完全相同(微秒级 );

    • 结论:以柱面为核心的复杂磁盘调度算法失去物理意义,反而徒增 CPU 计算开销。因此,先来先服务(FCFS) 或简单的 NOOP 调度成为最兼顾性能、极低开销与绝对公平的选择。

例题

  • 题目:

    某单面磁盘有 200 个柱面(编号 0~199),转速 6000 转/分,每磁道 100 扇区,相邻磁道移动时间 1 ms。磁头当前位于 100 号柱面,沿磁道号增大方向移动。请求队列的柱面号为 [50, 90, 30, 120],每磁道需读 1 个随机分布扇区。

    1)说明磁盘调度算法依据什么参数进行调度决策?

    2)若采用 C-SCAN 算法(采用 LOOK 改良规则,无更远请求即折返),求读完 4 个柱面上的扇区共需多少时间?写出计算过程。

    3)若替换为随机访问的 Flash 半导体存储器,是否有比 C-SCAN 更高效的调度策略?说明理由。

  • 分析:

    • 第 1 问:磁盘调度的本质是减少机械臂移动耗时,决策依据必须是柱面号(磁道号)。

    • 第 2 问:

      • 旋转一周时间:;

      • 平均旋转延迟:;

      • 单扇区传输时间:;

      • 4 个扇区固定读写耗时:。

      • 寻道轨迹由柱面号决定:当前 100 号向大号方向,先到 120,随后直接快速折返到请求队列最小柱面 30,再向大号方向依次访问 50、90。计算移动柱面总数即可求得寻道耗时。

    • 第 3 问:Flash 无寻道物理开销,选 FCFS 开销最小。

  • 答案:

    1)

    磁盘调度算法依据 请求所在的柱面号(磁道号)以及当前磁头的物理柱面位置与移动方向 进行调度决策。这是因为机械寻道只发生在柱面之间,同一柱面内部的盘面切换和扇区旋转不消耗机械寻道时间。

    2)

    盘片旋转一周耗时:

    单扇区固有读写耗时:

    4 个扇区的总读写操作耗时:

    C-SCAN 算法依据柱面号的访问顺序为:。

    移动的柱面总数:

    总寻道时间:

    读完 4 个扇区所需的总时间:

    3)

    有,采用 先来先服务(FCFS) 策略更为高效。

    理由:Flash 存储器属于电子半导体介质,没有机械磁臂寻道与盘片旋转延迟,各存储单元的随机访问时间恒定。C-SCAN 依据柱面位置对请求重新排序,白白增加了 CPU 算法计算和队列维护开销;而 FCFS 无调度计算开销、实现简单且能保证请求处理的绝对公平性。

⚠️ 易错点

Warning

  • 禁止直接拿逻辑块号、簇号或扇区号进行调度计算:磁臂径向移动只认柱面号。同一柱面内的不同簇或不同扇区寻道时间为 0。若题目给出簇号/块号,必须先通过带余除法换算成柱面号,再比对寻道距离;如果拿逻辑号直接做减法,会引入巨大数值偏置导致算法顺序彻底算错。

  • 混淆调度算法与寻道时间:调度算法只能优化寻道时间 ,无法优化旋转延迟 与传输时间 。计算每个扇区访问总耗时时,切勿漏算 (即转过单扇区耗时 )。

  • 混淆 SCAN 与 C-SCAN 的折返动作:SCAN 沿柱面单向走到底后掉头,折返途中边走边服务沿途柱面;C-SCAN 走到底后直接空跑直冲回另一端最小柱面,折返全程严禁服务任何请求。

  • C-SCAN 边界折返点过度脑补:题目若未强制指定“必须走到磁盘物理极限边界(如 0 号和 199 号)”,折返点默认取请求队列中的端点柱面(LOOK 改良模式),切忌自己脑补无意义的边界空跑。