文件存储空间管理
4.1.5 讲了”一个文件的块放在哪里”，但每次分配块时都要先回答一个前置问题：哪些块还是空的？
这一节讲四种记录空闲块的方法。它与 3.1.2 内存的空闲分区管理是同一类问题的两个场景，思路高度相似——只是内存按字节、磁盘按块。
本节是全章第二个计算题密集区，考点集中在位示图的行列换算与位图占多少空间两类。
机制
文件卷与两个区域
文件存储设备要分成若干文件卷（逻辑卷），一个文件卷可以是一整块物理磁盘，也可以是一块磁盘上的一个分区。
每个文件卷内部又分成两个区域：目录区主要存放文件目录信息（FCB、inode）以及用于磁盘存储空间管理的信息；文件区用于存放文件数据。
疑问点：外存文件区管理的主要目标
对外存文件区的管理应以（ ）为主要目标。 A. 提高系统吞吐量 B. 提高换入换出速度 C. 降低存储费用 D. 提高存储空间的利用率
答案 D。
文件区用于长期保存用户文件，这些文件一放就是几个月甚至几年，因此管理的重点是尽量少浪费空间。
选项 B 是对换区的目标，不是文件区的。 对换区服务于进程和页面的换入换出，用一次就走，追求的是速度而非利用率——所以对换区常采用连续分配（快但浪费），文件区则采用离散分配（省空间但稍慢）。
这组对照值得记住：文件区求”省”，对换区求”快”。
空闲表法
为所有空闲区建立一张空闲表，每个表项记录第一个空闲盘块号和空闲盘块数。
这套做法与 动态分区分配完全对应：分配时同样用首次适应、最佳适应、最坏适应等算法去找一个足够大的空闲区；回收时同样要检查前后是否有相邻的空闲区并合并。
空闲表法适用于连续分配方式，因为它天然以”连续的一段”为单位记账。
空闲链表法
把所有空闲盘区拉成一条双向链表。 有两种粒度：
空闲盘块链以盘块为单位，每个空闲盘块中存放指向下一个空闲盘块的指针。优点是分配与回收一个盘块的过程非常简单，摘一个或挂一个即可；缺点是为一个文件分配多个盘块时可能要重复很多次操作，效率低。
空闲盘区链以连续的空闲盘区为单位，每个盘区中除了指针还要记录本盘区的盘块数。优点是分配连续空间时效率高，缺点是分配与回收的过程相对复杂（要考虑合并）。
位示图法
用二进制的一位表示一个盘块的使用情况：0 表示空闲，1 表示已分配（也有系统反过来定义，以题目说明为准）。磁盘上所有盘块都有一个二进制位与之对应，这些位构成的集合称为位示图。
位示图通常被组织成
分配时：顺序扫描位示图，找到一个或一组值为 0 的位，把它们换算成盘块号，然后把这些位置为 1。回收时：把盘块号换算回字号与位号，把对应的位置为 0。
位示图法的最大优点是易于找到连续的空闲块——连续的空闲块在位图上就是连续的 0，扫描时一眼可见。这一点是空闲链表法做不到的。
成组链接法
疑问点：成组链接法的工作过程
成组链接法具体如何组织与运作。
空闲表法和空闲链表法都不适用于大型文件系统：表或链会长到无法全部装入内存。UNIX 采用的成组链接法把两者结合起来，做法是把空闲块每 100 个分成一组。
结构是这样组织的：
超级块中有一个”空闲盘块号栈”，用来存放当前第一组的全部空闲盘块号，以及栈中尚有的空闲盘块号数
其余各组的块号，则分别记录在上一组的某一个盘块中——也就是说，每一组都用自己的一个成员块来存放下一组的块号清单。最后一组的相应位置填 0，表示结束。
分配的过程：从栈顶取出一个盘块号分配出去，
回收的过程：把回收的盘块号记入栈顶，
这套设计的精妙之处在于：它把”下一组的清单”藏在了空闲块自己身上。 空闲块反正没被使用，用它来存管理信息不占用任何额外空间，而内存中始终只需保留一组（100 个）块号。用一个常数大小的内存开销，管理了任意大的磁盘。
边界
位示图的行列换算：编号从 0 还是从 1
疑问点：位示图定位中编号起点不一致导致的答案分歧
若用 8 个字（字长 32 位）组成的位示图管理内存，即位示图有 8 行、32 列，行号和列号均从 1 开始，则块号为 100 的内存块所对应位示图的位置是（ ）。 A. 字号为 3，位号为 5 B. 字号为 4，位号为 4 C. 字号为 3，位号为 4 D. 字号为 4，位号为 5
配套解析给出：
， ，并注明”若行号和列号从 0 开始，则答案不同”。两种口径何者为准。
两种口径都自洽，分歧不在公式而在”块号本身从几开始编号”。本题按块号从 1 开始处理，答案 B。
与其记两套公式，不如用一个不会错的通用做法：先把块号换算成序数（它是第几个块），再套一个固定公式。
第一步：块号 → 序数。
- 若块号从 1 开始编号，则块号 100 就是第 100 个块，序数
。 - 若块号从 0 开始编号，则块号 100 是第 101 个块，序数
。
第二步：序数 → 字号、位号（结果按从 1 开始编号）。
其中
代入本题（
答案 B。 若块号从 0 开始（
验算的办法很直观：第 4 行的第 1 个块是第
所以这道题真正的教训是：位示图题动笔前必须先确认三个编号起点——块号、行号、列号各自从几开始。 题干只说了行号列号从 1 开始，块号的起点要靠”配套解析怎么算”来反推，这是题目本身表述不严谨之处，不是理解上的问题。
位图需要占多少空间
疑问点：位图法管理 10GB 分区所需的簇数
【2014 统考真题】现有一个容量为 10GB 的磁盘分区，磁盘空间以簇为单位进行分配，簇的大小为 4KB，若采用位图法管理该分区的空闲空间，即用一位来标识一个簇是否被分配，则存放该位图所需的簇数为（ ）。
答案 80 个簇。 这类题的解法是一条固定的单位换算链：容量 ÷ 分配单位 → 位数 → 字节数 → 簇数。
① 分区一共有多少个簇。
② 每簇一位，故位图需要 2621440 位。转换成字节。
哪些结构可以用来管理空闲块
疑问点：可用于管理空闲磁盘块的数据结构
15.【2019 统考真题】下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（ ）。 I. 位图 II. 索引节点 III. 空闲磁盘块链 IV. 文件分配表（FAT）
答案 I、III、IV。
位图和空闲磁盘块链是本节明确介绍的方法，自然可以。
FAT 可以，理由在 4.1.5：FAT 中表项值为 FREE 的簇就是空闲簇，它天然兼任了空闲块管理，不需要另设结构。这正是 FAT 相对于索引分配的一项优势。
索引节点不行。 inode 描述的是某一个文件的属性和它的数据块地址，是文件级的结构；空闲块管理需要的是全盘级的结构。inode 只知道”我这个文件用了哪些块”，无从知道”整个磁盘还有哪些块没人用”。
判据：能回答”整个磁盘哪些块空着”的才算，只能回答”这个文件占了哪些块”的不算。
四种方法的适用边界
空闲表法适用于连续分配，因为它以”连续的一段”为记账单位。
空闲盘块链适合逐块分配（分配回收单块最简单），空闲盘区链适合连续分配（能一次拿到一整段）。
位示图适合需要找连续空闲块的场合——连续的 0 一目了然，这是链表做不到的。
成组链接法适合大型文件系统——它是四者中唯一不需要把全部空闲块信息装入内存的方法。
扩展：文件系统的一致性
疑问点：系统崩溃后的恢复手段
崩溃后如何恢复，涉及哪些知识点。
崩溃之所以会破坏文件系统，根源在 4.1.3 那条”创建与删除各是两件事”。 分配一个块要同时改位示图和inode，这两次写盘之间若断电，就会留下不一致：位图说这块已用、却没有任何 inode 指向它（空间白白丢失），或者两个 inode 同时指向同一块（数据互相覆盖，更严重）。
两类应对手段：
一致性检查（fsck）在系统重启后扫描全盘，重建一份”每个块被引用了几次”的统计表，与位示图对照，把不一致的地方修正过来。缺点是全盘扫描极慢，磁盘越大越不可接受。
日志文件系统则改变写入顺序：在真正修改磁盘之前，先把”我将要做哪几件事”作为一条事务记录写入日志区；全部做完后再把这条日志标记为完成。崩溃后只需检查日志——未完成的事务要么重做要么撤销，不需要扫描全盘。
这与数据库的预写日志是同一思想：先记意图，再做事；这样任何时刻断电，都能知道当时正在做什么。
408 中这部分属于疑难点，掌握到”为什么会不一致”和”两类手段的区别”即可。
对照速查
| 方法 | 记账单位 | 优点 | 适用 |
|---|---|---|---|
| 空闲表法 | 连续的一段（首块号 + 块数） | 与动态分区分配同套算法 | 连续分配 |
| 空闲盘块链 | 单个盘块 | 分配/回收单块最简单 | 逐块分配 |
| 空闲盘区链 | 连续盘区（含块数字段） | 分配连续空间效率高 | 连续分配 |
| 位示图 | 一位一块 | 易于找到连续空闲块 | 中小型系统 |
| 成组链接法 | 每 100 块一组 | 内存只需保留一组，管理任意大磁盘 | 大型文件系统（UNIX） |
| 位示图换算（通用做法） | |
|---|---|
| ① 块号 → 序数 | 块号从 1 开始则 |
| ② 字号 | |
| ② 位号 | |
| ③ 若要求从 0 编号 | 两个结果各减 1 |
| 位图空间计算链 | 例（10GB / 4KB 簇） |
|---|---|
| 容量 ÷ 分配单位 = 个数 | |
| 个数 ÷ 8 = 字节 | |
| 字节 ÷ 簇大小 = 簇数 |
| 文件区 | 对换区 | |
|---|---|---|
| 用途 | 长期保存文件 | 进程/页面换入换出 |
| 主要目标 | 提高存储空间利用率 | 提高换入换出速度 |
| 分配方式 | 离散分配 | 连续分配 |
| 成组链接法 | 关键动作 |
|---|---|
| 分配至 | 先把该块内容读入栈，再分配这个块本身 |
| 回收至栈满时 | 把栈中 100 个块号写入新回收块，令 |
考点
- 文件区求”省”（利用率），对换区求”快”（速度）
- 空闲链表法两种粒度：盘块链适合逐块，盘区链适合连续
- 位示图的优点是易于找连续空闲块
- 位示图换算先定三个编号起点；通用做法是”块号 → 序数 → 字号位号”
- 位图空间计算链：容量 ÷ 单位 → bit → B → 簇
- 成组链接法适用于大型文件系统，靠”把下一组清单藏在空闲块里”节省内存
- 成组链接的两个临界动作：
先读入再分配、栈满时新回收块当组长 - 可管理空闲块的是位图、空闲盘块链、FAT；inode 不行（2019 真题）
- 一致性：fsck 全盘扫描 vs 日志文件系统只查日志
链接
- 🏠 返回总览：操作系统第 4 章：文件管理总览
- ⬅️ 上一节：4.3.2 文件系统布局
- ➡️ 下一节：4.3.4 虚拟文件系统
- 🔗 FAT 兼管空闲块的原理，见 4.1.5 文件的物理结构
- 🔗 同类问题在内存中的版本，见 3.1.2 连续分配管理方式
- 📖 名词库：第 4 章名词库