第九章 磁盘存储器管理

9.1 外存组织方式

连续分配

• 目录项：文件名 + 起始盘块号 + 长度
• 优点：顺序访问快/支持随机访问
• 缺点：外碎片/需预知文件大小

链接分配

• 隐式链接：每个盘块含指向下一盘块的指针
  • 仅支持顺序访问
• 显式链接（FAT）：文件分配表放在内存中
  • FAT12（簇）/ FAT16（≤2048MB）/ FAT32（簇4KB,≤1TB,单文件≤4GB）/ NTFS
  • 支持随机访问

索引分配

• 单级索引：一个索引块记录所有盘块号
• 多级索引：索引块不够时,索引块指向索引块
• 增量式混合索引（UNIX）⭐：

地址项	类型	4KB块时可寻址容量
i.addr(0)~i.addr(9)（经典UNIX）	直接地址	10×4KB = 40KB
i.addr(10)	一次间接	1K×4KB = 4MB
i.addr(11)	二次间接	1K×1K×4KB = 4GB
i.addr(12)	三次间接	1K×1K×1K×4KB = 4TB

⚠️ 口径提示：本表采用经典UNIX教材口径；与上章ext2的12个直接块写法属于不同文件系统实现。

---

9.2 空闲空间管理

方法	原理	特点
空闲区表法	表项（起始块号+空闲块数），FF/BF分配	连续分配适用
空闲链表法	盘块链（效率低）/ 盘区链（FF,效率高）	链接分配适用
位示图法⭐	每个盘块1bit，0空闲/1占用	简单高效
成组链接法（UNIX）	空闲盘块号栈（100个），栈底指向下一组	大型文件系统

位示图计算公式⭐

盘块号 $b$ → 位示图位置 $(i, j)$：

$i = (b-1) \div n + 1, \quad j = (b-1) \mod n + 1$

位示图 $(i, j)$ → 盘块号 $b$：

$b = n \times (i-1) + j$

其中 $n$ 为位示图每行的位数。

⚠️ 编号约定：上述公式按“盘块号与位示图行列均从1开始编号”给出；若题目采用0起编号，需整体平移后再代入。

成组链接法（UNIX）

• 空闲盘块号栈：存放100个空闲盘块号
• 栈底（第一个单元）存放下一组100个空闲盘块号所在的盘块号
• 分配：从栈顶取一块；栈空则将栈底指示的下一组读入
• 回收：盘块号压入栈顶；栈满则将当前100个写入回收块,该块号成为新栈底

---

9.3 磁盘容错与RAID

RAID级别

• RAID 0：条带化,无冗余
• RAID 1：镜像,100%冗余
• RAID 5：分布式奇偶校验
• RAID 6：双校验

软件容错技术（SFT）

• SFT-I：双份目录、双份FAT、热修复重定向、写后读校验
• SFT-II：磁盘镜像/磁盘双工
• 基于集群的容错：服务器镜像

---

9.4 存储新技术

技术	连接方式	访问级别	特点
DAS	直连主机	块级	简单/成本低/容量有限
NAS	网络附加(NFS/SMB)	文件级	共享方便
SAN	存储区域网(光纤)	块级	高性能/高可靠

---

9.5 数据一致性

事务

• 原子性：要么全做要么全不做
• 日志记录：(事务名, 数据项名, 旧值, 新值)
• undo（事务未完成时恢复旧值）/ redo（事务已完成时重做新值）

检查点

• 定期在日志中记录检查点
• 恢复时只处理检查点之后的事务

并发控制

• 互斥锁 / 共享锁（类似读者-写者问题）

🎯 本章真题锚点与最短模板

• 高频题号（2009-2025）：2009Q29、2010Q45、2012Q32、2015Q31/Q32、2019Q44、2021Q28、2024Q32、2025Q32
• 优质例题：给定初始磁头位置与请求序列，分别按FCFS、SSTF、SCAN计算总移动磁道数。
• 最短解题模板：
  1. 先按算法确定访问顺序。
  2. 总移动量 = 相邻访问磁道差绝对值求和。
  3. 需要时间时再乘“每磁道移动时间”并加旋转/传输延迟。

⚡ 秒杀版口令卡（10秒回忆）

• 口令：先排顺序，再算移动量。
• 口令：时间=寻道+旋转+传输。
• 口令：SSTF快但可能饿死远端请求。

---