第 21 讲：磁盘组织、调度与空闲空间

磁盘管理之所以有专门算法，根源在机械运动：移动磁头的寻道和等待盘片转到目标扇区的时间，往往比真正传输少量数据更贵。OS 因此不仅要记“读哪个块”，还要安排请求顺序、管理空闲块并用缓存掩盖延迟。

从物理磁盘到逻辑块

• 盘片/盘面：磁性介质表面，每个盘面有对应磁头；
• 磁道（track）：某盘面上一圈同心环；
• 柱面（cylinder）：所有盘面上相同半径磁道的集合，不移磁臂即可切换磁头访问；
• 扇区（sector）：磁道上的物理记录单元，除用户数据外还有同步、标识、间隔和 CRC；
• 逻辑块 LBA：将物理几何包装成从 0 开始的一维可寻址块数组。

较早系统用 CHS（Cylinder/Head/Sector）表示位置，现代接口主要向 OS 暴露 LBA，磁盘内部控制器负责实际映射、缺陷扇区重映射等。课件介绍的 P 表/G 表分别记录出厂与使用期发现的缺陷，用备用扇区替换。

MBR 是磁盘组织与启动的交叉点

传统 MBR 位于磁盘首扇区，512 B 中通常有 446 B 引导代码、64 B 分区表与 2 B 签名。每个分区项 16 B，所以传统格式只有 4 个主分区项；扩展分区/逻辑分区是绕过该限制的历史方案。

分区不是文件系统：分区只划出一段逻辑块范围，这段范围里可以再存 FAT、Ext2 或其他格式的超块、索引节点和数据块。

一次磁盘请求慢在哪里

用户看到的响应时间至少包含队列等待和设备服务：

$$T_{response}=T_{queue}+T_{service}.$$

机械磁盘的服务时间可近似：

$$T_a=T_s+T_r+T_t.$$

寻道时间

磁臂移动 $n$ 条磁道，可用简化线性模型：

$$T_s=s+mn,$$

$s$ 是启动/定位固定开销，$m$ 是每条磁道移动时间。真实设备曲线可非线性，但题目给参数时按给定模型。

旋转延迟

转速 $r$ 用“转/秒”表示，随机目标平均等半圈：

$$T_r=\frac{1}{2r}.$$

7200 RPM $=120$ 转/秒，平均旋转延迟为

$$\frac{1}{2\times120}\text{ s}\approx4.17\text{ ms}.$$

传输时间

若每磁道有 $N$ 字节，传输 $b$ 字节：

$$T_t=\frac{b}{rN}.$$

小请求中，寻道+旋转往往远大于传输，所以把相邻数据合成大块顺序 I/O 能更高效地摊薄固定延迟。

磁盘调度算法

设当前磁头在柱面 53，等待队列按到达顺序为：

98, 183, 37, 122, 14, 124, 65, 67

磁盘范围 0–199，SCAN/C-SCAN 初始向大号柱面。

FCFS

原顺序服务，总移动：

$$|53-98|+|98-183|+|183-37|+|37-122|$$ $$+|122-14|+|14-124|+|124-65|+|65-67|=640.$$

简单且按到达公平，但磁头可在内外圈之间大幅摆动。

SSTF

每次选离当前磁头最近的请求：

53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183

总移动：

$$12+2+30+23+84+24+2+59=236.$$

平均寻道显著改善，但若磁头附近不断来新请求，远处请求可长期饥饿。

SCAN 与 LOOK

SCAN 像电梯，先向一边移动，沿途服务，到端点后反向。本例严格 SCAN：

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14

移动为 $(199-53)+(199-14)=331$。LOOK “看一眼”该方向最远请求，到 183 就反向，不空跑到 199：

$$(183-53)+(183-14)=299.$$

课件提醒，有些题目把 SCAN 默认写成 LOOK 实现；必须看清是到物理端点还是到最远请求。

C-SCAN 与 C-LOOK

C-SCAN 只在一个方向服务，到高端后快速回到 0，返程不服务：

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199
   -> 0 -> 14 -> 37

这样各柱面等待时间分布更均匀。C-LOOK 在最高请求 183 后直接跳到最低请求 14，再向上服务 37，不必到 199 和 0。“快速返回”的移动距离在计算总磁头行程时仍应算入，只是返回路上不处理请求。

N-Step-SCAN 与 FSCAN

将当前请求冻结成一批扫描，新请求进另一队，可防止某个局部热点不断来请求，让磁头“粘”在该区域。N-Step-SCAN 每批最多 $N$ 个；FSCAN 使用两条队列交替，扫描当前队时新请求全进另一队。

这些算法是机械磁盘课件范围的核心。SSD 没有磁头寻道，不应原样搬用“移动柱面最少”作为主要目标。

空闲块管理

位图

每个磁盘块一位，课件约定 1 表示空闲、0 表示已分配。位图容易用按字并行操作找空闲位，也容易判断连续块；但大磁盘的位图本身也要占空间并缓存。

若每个字有 $w$ 位，字号 $i$、字内位 $j$对应块号常为：

$$block=i\times w+j,$$

具体还要按题目是从 0 还是 1 编号修正。

空闲表

一项记录 (起始块号, 连续块数)，适合大片连续空间，但碎片很多时表会变长。

空闲链表与成组链接

单纯将所有空闲块串起来无需大表，但逐块遍历链很慢。成组链接在一个空闲块内存一组其他空闲块号，最后一项再指向下一组，把“链长”从每块一跳降为每组一跳，并可在内存中用栈式批量分配/回收。

索引块能表示多大文件

若 inode 有 12 个直接指针、1 个一级、1 个二级、1 个三级间接指针；块大小 $B=8$ KiB，每指针 4 B，一块可存

$$K=\frac{8192}{4}=2048$$

个块号。最大逻辑数据大小是：

$$B(12+K+K^2+K^3),$$

近似 64 TiB。小文件只用直接指针，不付多级查找代价；大文件才逐步启用间接层。若块号字段本身只有 31 位且块为 1 KiB，可寻址空间又受 $2^{31}\times1$ KiB $=2$ TiB 上限；真实上限要取各约束中最小者。

提高磁盘 I/O 性能

• 磁盘高速缓存：保留近期块，命中时避免设备 I/O；
• 连续/局部布局：文件数据相邻，inode 与数据距离近，减少寻道；
• 预读：顺序访问时异步读入后续块；
• 延迟写/批量写：先改缓存，合并、排序后再落盘，性能好但突然断电的丢失窗口变大；
• 轨道缓冲/skip sector 等布局：利用旋转顺序，为处理留出时间；
• RAM 盘：用内存模拟块设备，内容由用户/上层明确存放；与由 OS 自动保留磁盘副本的 cache 不同。

缓存中“指针交付”可避免数据拷贝，但需要严格管理页/缓冲块的生命期和所有权；“直接拷贝”边界简单，却多一次内存带宽开销。

磁盘题的三个易错点

1. RPM 先除 60 换成转/秒，再代旋转延迟公式；
2. SCAN 和 LOOK、C-SCAN 和 C-LOOK 是否走到物理端点，要按题设区分；
3. 调度只改变寻道路线，总响应时间还可包括排队、旋转和传输，不能把“磁头移动 236 柱面”直接当成 236 ms。