是什么
-
定义:操作系统对物理外存(机械硬盘/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-LOOK | SCAN/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 改良模式),切忌自己脑补无意义的边界空跑。