Appearance
外存空闲空间管理
考情分析
外存空闲空间管理在 408 真题中属于 🔥🔥 中高频考点，位示图的计算题是常考类型。
文件被删除后，它占用的磁盘块就变成了"空位"。操作系统怎么记住哪些块是空的、下次创建文件时该分配到哪？这就是空闲空间管理的核心问题。
空闲空间管理方法
文件被删除后，其占用的磁盘块需要被回收再利用。操作系统需要一种数据结构来跟踪哪些磁盘块是空闲的。
1. 空闲表法
用一张表记录每个连续空闲区的起始块号和块数：
| 序号 | 起始块号 | 空闲块数 |
|---|---|---|
| 1 | 2 | 5 |
| 2 | 15 | 3 |
| 3 | 25 | 8 |
分配：与内存连续分配类似，可用首次适应、最佳适应等策略。
回收：回收后需要检查能否与相邻空闲区合并。
适用场景：连续分配方式。
2. 空闲链表法
空闲盘块链
将所有空闲磁盘块组成一个链表，每个空闲块中存放指向下一个空闲块的指针。
空闲链头 → 块3 → 块7 → 块12 → 块15 → null- 分配：从链头取出所需数量的空闲块
- 回收：将回收的块挂到链尾
- 缺点：每次只能分配一个块，分配多个块需要多次操作
空闲盘区链
将连续的空闲块组成一个区，将所有空闲区链接起来。每个空闲区记录起始块号、块数和下一个空闲区指针。
空闲链头 → [块2, 5块] → [块15, 3块] → [块25, 8块] → null- 分配和回收的效率高于空闲盘块链
3. 位示图法（Bitmap）🔥🔥🔥
用一个二进制位图来表示磁盘块的使用状态。每个磁盘块对应位图中的一个 bit：
0= 空闲1= 已占用（也有教材规定相反）
位示图就像电影院座位图——1 表示有人坐，0 表示空位，一眼看出哪里有空。
位示图（假设每行 16 bit）:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
行0: 1 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1
行1: 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0位示图计算（常考题型）
设磁盘块号为 b（从 0 开始），位示图每行有 n 个 bit，则：
- 块号 → 位示图位置：
， - 位示图位置 → 块号：
编号起点
不同教材的块号、行号、列号的起始编号不同（有从 0 开始，有从 1 开始）。做题时务必看清题目约定。
若块号从 1 开始，行列也从 1 开始：
位示图所需空间：若磁盘有 N 个块，则位示图需要 N bit = N/8 字节。
示例：磁盘有 1024 个块，则位示图只需 1024 bit = 128 字节。
优点：
- 占用空间小
- 容易找到连续的空闲块（扫描连续的 0）
- 适合硬件操作（位运算高效）
4. 成组链接法（Unix 方案）
Unix 文件系统使用的方法，结合了空闲表和链表的思想：
超级块中的空闲块栈:
┌──────────────────┐
│ 空闲块数: 100 │
│ 块号: 201 │
│ 块号: 202 │
│ 块号: ... │
│ 块号: 300 │ ← 最后一个块号指向下一组
└──────────────────┘
│
▼
块300 中存储下一组:
┌──────────────────┐
│ 空闲块数: 100 │
│ 块号: 301 │
│ 块号: 302 │
│ 块号: ... │
│ 块号: 400 │ ← 继续指向下一组
└──────────────────┘工作原理：
- 将空闲块分成若干组，每组 100 个块（数量可配置）。成组链接就像把空教室清单分成多页纸，第一页贴在教务处门口（超级块），每页末尾写着下一页藏在哪间教室里
- 第一组的信息存放在超级块中
- 每组的最后一个块存放下一组的空闲块号（形成链）
分配：从超级块的空闲块栈中弹出块号；栈空时，读取最后一个块指向的下一组信息
回收：将回收的块号压入栈中；栈满时，将当前栈内容写入回收的块中，该块成为新组的链接块
四种方法对比
| 方法 | 空间开销 | 分配速度 | 适用场景 |
|---|---|---|---|
| 空闲表法 | 中等 | 较快 | 连续分配 |
| 空闲链表法 | 小 | 慢（盘块链）/中（盘区链） | 离散分配 |
| 位示图法 | 小（N bit） | 快 | 各种分配方式 |
| 成组链接法 | 中等 | 快 | Unix/大型文件系统 |
考研高频考点
- 🔥🔥🔥 位示图的块号与行列号转换计算
- 🔥🔥🔥 位示图所需的存储空间计算
- 🔥🔥 成组链接法的分配与回收过程
- 🔥🔥 四种空闲空间管理方法的对比
- 🔥 空闲表法的分配策略（首次/最佳适应）
空闲管理是单个文件系统内部的事，但操作系统可能同时挂载多种不同的文件系统。下一篇来看 VFS 如何把它们统一起来。