外存空闲空间管理 · 融合风（象牙 + Obsidian 入口）

速查

文件系统用四种方法跟踪空闲块：空闲表法、空闲链表法、位示图法（最常用，$1$ 位表示 $1$ 个块，共需 $\lceil N/8\rceil$ 字节）、成组链接法（UNIX 传统方法，超级块存第一组块号）。

速查 ▾

项目	值
定义	跟踪磁盘上哪些块是空闲的
四种方法	空闲表法、空闲链表法、位示图法、成组链接法
最常用	位示图法（UNIX/Linux 使用）
大文件系统	成组链接法（UNIX 传统方法）

核心概念 ▾

外存空闲空间管理是文件系统中用于跟踪和分配磁盘空闲块的机制。四种常用方法各有取舍：

1. 空闲表法

用一个表记录所有连续空闲区的起始块号和长度。
类似内存管理的空闲分区表，适合连续分配。
缺点：表可能很大，不适合大磁盘。

2. 空闲链表法

将所有空闲块用指针链接成一个链表。
分配从链头取块，释放将块插回链头，简单高效。
缺点：指针占用空闲块的空间，大磁盘需多次 I/O 读取链表。

3. 位示图法（Bitmap）

用 1 位表示一个磁盘块的状态：$0=$空闲，$1=$已分配（或反之）。
所有位构成位图，存在连续的磁盘块中，最常用。
优点：空间效率极高（$1$ 位/块），查找连续空闲块方便。

4. 成组链接法（UNIX）

将空闲块分组，每组用一个空闲块存储下一组的块号。
第一组的块号存储在超级块中，减少 I/O 次数。
分配：从当前组取块，组空时读下一组；释放：加入当前组，组满时把当前组写入新释放的块。

关键性质 ▾

方法	空间开销	分配效率	适用场景
空闲表法	中（表）	连续分配快	小磁盘
空闲链表法	小（指针）	分配释放快	小磁盘
位示图法	固定（$1$ 位/块）	查找方便	通用
成组链接法	极小	分配释放快	大磁盘（UNIX）

常见考法 ▾

考法	解题套路
位示图计算	$1$ 位表示 $1$ 块，$N$ 块需要 $N$ 位 $= \lceil N/8\rceil$ 字节
成组链接法分配	从当前组取块 → 组空 → 读下一组 → 组满时释放写入新块
方法对比	位示图最通用，成组链接法最适合大文件系统
空闲表 vs 空闲链表	空闲表适合连续分配，空闲链表适合离散分配

易错点 ▾

注意

位示图中 1 位表示 1 个磁盘块——不是 $1$ 字节。
成组链接法中，超级块存储的是第一组的空闲块号（不是所有）。
成组链接法释放块时，若当前组已满，需将当前组信息写入新释放的块。
空闲链表法的指针占用空闲块的空间（每个空闲块前几个字节存指针）。
位示图本身也需要存储空间——通常放在超级块附近。

核心结论 ▾

必背

位示图法是最常用的空闲空间管理方法，空间效率高且查找方便。
成组链接法是 UNIX 的传统方法，适合大文件系统。
空闲表法适合连续分配，空闲链表法适合离散分配。
位示图空间开销：$N$ 个磁盘块需要 $N$ 位 $= \lceil N/8\rceil$ 字节。
成组链接法通过分组管理减少 I/O 次数（每组只需一次 I/O 读取）。

记忆卡片 ▾

四种空闲空间管理方法？

空闲表法、空闲链表法、位示图法、成组链接法。

最常用的方法？

位示图法（1 位表示 1 块，空间效率高）。

UNIX 使用什么方法？

成组链接法（将空闲块分组管理，超级块存第一组块号）。

位示图的空间开销？

$N$ 块需要 $N$ 位 $= \lceil N/8\rceil$ 字节。

成组链接法如何分配？

从当前组取块 → 组空 → 读下一组的块号 → 继续分配。

交互动画 · 四种空闲空间管理方法 ▾

空闲表法：连续空闲区用「起始块号 + 长度」描述

切换上方方法查看四种管理方式的差异；位示图法可点击格子体验分配/释放。