外存空闲空间管理

2026 大纲 四（三）2 外存空闲空间管理方法。

要分一块盘出去，先得知道哪儿还空着

文件的物理结构讲了文件占用的块怎么记录，但它一直假设"需要块的时候就有块可拿"。这一节回答那半句：空闲的块记在哪儿。

这套结构和引导块、根目录、inode 区一样，是在高级格式化（逻辑格式化）时建立的。

四种方法看着各不相同，其实只由一个选择分开：用什么粒度描述空闲空间。

按"段"描述——记 (起始块号, 连续几块)。一条记录就能表达一大片，但它必须和"我要一整段"的请求对得上，所以配连续分配。这是空闲表法和空闲盘区链。

按"块"描述——每个块单独表态。空闲盘块链把指针放进块自己里，于是走一步就要读一次盘，最慢；位示图把每个块压成 1 个比特， $N$ 个块只要 $N / 8$ 字节。

位示图值得单独说一句，因为它有一条别的方法都没有的性质： 它占的空间只和磁盘容量有关，与用了多少、剩多少完全无关—— 不管盘是空的还是满的，位图都是那么大。别的方法都做不到这一点（空闲表和链表的规模随空闲区的多少浮动）。

最后一种成组链接法是 Unix 的方案，它把前两类拼在一起：用一个栈一次登记一批块号，栈空/栈满时才动一次磁盘。它的两个临界时刻各有一处顺序不能颠倒，是本节唯一需要小心的地方。

一、空闲表法与空闲链表法

空闲表法用一张表记录每个连续空闲区的起始块号和块数：

序号	起始块号	空闲块数
1	2	5
2	15	3
3	25	8

空闲盘块链把所有空闲块串成一条链，指针存在空闲块内部：

空闲链头 → 块3 → 块7 → 块12 → 块15 → null

分配 $k$ 个块要沿链走 $k$ 步、改 $k$ 次指针，而每走一步就要读一次盘——这是它效率最低的原因。

空闲盘区链把连续的空闲块先合成一个区再串起来，每个结点记起始块号、块数和后继指针：

空闲链头 → [块2, 5块] → [块15, 3块] → [块25, 8块] → null

拿 5 个连续块只要走一步。空闲表法与空闲盘区链存的信息几乎一样（都是 (起始块号, 块数)），差别只在组织形式：前者是连续存放的表、配合首次适应这类策略，对应连续分配；后者是链式组织，插入删除不必移动表项。

二、位示图法（Bitmap）

用一个二进制位图表示磁盘块的使用状态，每个磁盘块对应一个 bit：

位示图（假设每行 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

位示图逻辑上是一个二维数组 map[i][j]，而磁盘块号是一维的——所谓换算就是一维下标与二维下标的互转，和把一维数组按每行 $n$ 个折成矩阵完全是一回事（两种起点约定下的公式见下方「考点速记」第 6、7 条）。从 1 起编号时那句" $- 1$ 再 $+ 1$ "不是凑答案，是坐标系转换：块号 1 应落在第 1 行第 1 列，而 $⌊ 1 / 32 ⌋ = 0$ 会算成第 0 行。

所需空间： $N$ 个块需 $N$ bit $= N / 8$ 字节——这是四种方法里唯一能直接写出算式的空间开销：

磁盘容量	块大小	块数	位示图大小
1 GB	4 KB	$262 144$	$32 KB$
1 TB	4 KB	$268 435 456$	$32 MB$

边界：位示图小到可以常驻内存时才有上述好处。1 TB 盘的 32 MB 位示图已不适合整个常驻，实际系统会把它按块组切开、只驻留正在使用的那部分。

两种约定下的双向换算逐步走一遍：为什么行号有时差 1、有时不差（想亲手验证换算公式、或者拿不准起点该怎么处理时展开）

自造数据：某文件系统用位示图管理空闲块，位示图每行 32 位。

（1）约定 A——块号、行号、列号均从 0 起，块号 1000 在第几行第几列？

i = ⌊ \frac{1000}{32} ⌋ = 31, j = 1000 mod 32 = 8

即第 31 行第 8 列。从 0 起编号时， $b$ 就是"前面已经排过 $b$ 个"，商是排满了几整行、余数是在本行的第几个，不需要任何修正。

（2）约定 B——三者均从 1 起，同样是块号 1000？

i = ⌊ \frac{1000 - 1}{32} ⌋ + 1 = ⌊ \frac{999}{32} ⌋ + 1 = 31 + 1 = 32

j = (1000 - 1) mod 32 + 1 = 999 mod 32 + 1 = 7 + 1 = 8

即第 32 行第 8 列。

（3）两个约定的结果为什么不能混用。 同一块号 1000，约定 A 是 $(31, 8)$ 、约定 B 是 $(32, 8)$ ——行号差 1、列号恰好相同。列号相同只是巧合：块号 992 在约定 A 下是 $(31, 0)$ ，在约定 B 下是 $(31, 32)$ ——这次行号反而一样，位置却完全对不上（A 下它是第 31 行的第一个，B 下它是第 31 行的最后一个）。

一般规律： $b$ 不是 $n$ 的整数倍时 $i_{B} = i_{A} + 1$ ； $b$ 恰是 $n$ 的整数倍时 $i_{B} = i_{A}$ （此时 $b - 1$ 掉回上一行， $+ 1$ 又补了回来）。行号差不差 1 本身就随块号变，所以两个约定绝不能混用。

（4）反向换算。 在约定 B 下，第 32 行第 8 列那一位被置为空闲，分配出去的是哪一块？

b = n \times (i - 1) + j = 32 \times (32 - 1) + 8 = 992 + 8 = 1000

与（2）互为逆运算。反向公式必须与正向用同一个约定。

三、成组链接法（Unix 方案）

空闲表法和空闲链表法都不适用于大型文件系统——表或链会长得离谱。成组链接法把两者各取一半：取"表"的一半是一次拿到一组块号（成批而非一次一个），取"链"的一半是组与组之间用链串起来（不需要一张全局大表）。

为什么能同时快又省：

快：绝大多数分配与回收只动内存里的那个栈，一次磁盘都不访问；只有"栈空要换下一组"和"栈满要写出去"这两个临界时刻才各读/写一次盘。平均分配代价约 $\frac{1}{组大小}$ 次磁盘 I/O——组大小 100 时，平均每 100 次分配才读一次盘。
省：不像位示图那样为全盘每一块都留一位——它只为空闲的块记块号，而这些块号本身就寄存在空闲块里，不额外占用任何已用空间。

栈空分配与栈满回收各走一遍完整过程（想在具体块号上看清"读盘与分配的先后顺序为什么锁死"时展开）

自造数据：某系统用成组链接法，每组 5 块。当前空闲盘块号栈中有 5 个块号 S.free(0)=201 … S.free(4)=205，N=5（N 兼作栈顶指针，栈顶是 S.free(N-1)）。块 201 中记着下一组：N=5，块号 206~210。

（1）连续申请 5 个块。 前 4 次栈里还有富余：

次序	从栈顶弹出	弹出后 N
第 1 次	205	4
第 2 次	204	3
第 3 次	203	2
第 4 次	202	1

栈在内存中的超级块里，弹栈只是改一个下标、完全不碰磁盘——这正是成组链接"快"的来源，绝大多数分配落在这一档。

第 5 次时 $N = 1$ ，栈里只剩 S.free(0)=201，它是栈底，而栈底那一块里存着下一组的清单，所以不能直接交出去：

发现"要弹的就是栈底" → 触发换组
读盘块 201，把里面的 N=5 与块号 206~210 复制进空闲盘块号栈——本次唯一的一次磁盘 I/O
块 201 里的有用数据已全部读进栈，于是把块 201 本身分配出去
栈现在是 206,207,208,209,210， $N = 5$

5 次分配依次得到 205, 204, 203, 202, 201，累计磁盘 I/O = 1 次。顺序不能颠倒——必须先把块 201 的内容读进栈，才能把它交出去；反过来先分配，文件一写数据就把下一组清单覆盖掉，后面所有空闲块全部丢失。

（2）承（1），此时栈已重新装满（206~210，N=5），现回收块 305。

发现栈满 → 触发换组
把当前栈中的 5 个块号连同计数 N=5 一起写入新回收的块 305——本次唯一的一次磁盘 I/O
清空栈，令 S.free(0)=305、N=1——块 305 成为新的栈底，它里面记着刚才那一组
回收完成

栈满时腾地方的办法不是丢弃，而是把这一整组"存"到刚回收的那块里去：那块正好是空闲的、内容无用，用它当载体一分钱不花。于是链又长了一节，下次栈空时按上面的流程原样读回来。

	触发条件	动作	磁盘 I/O
分配	栈中只剩栈底	读栈底那一块 → 装满栈 → 把栈底那块分配出去	1 次读
回收	栈已满	写当前整栈到被回收的那块 → 该块成为新栈底	1 次写

四、四种方法对比

方法	空间开销（可算的口径）	分配一个块的磁盘 I/O（均摊到每块）	找连续块	适用场景
空闲表法	表项数 = 空闲区段数，随删除碎片化而增长，无上界公式	表若常驻内存则 0 次	容易（表里直接记着块数）	连续分配
空闲盘块链	0 额外空间（指针寄存在空闲块内）	1 次（指针在盘上，走一步读一次）	很难（要沿链找相邻块号）	离散分配
空闲盘区链	0 额外空间（同上）	1 次，但一次拿一整段	较容易	离散分配
位示图法	$N / 8$ 字节（ $N$ = 全盘块数）；1 TB + 4 KB 块 → 32 MB	图常驻内存则 0 次	最容易（扫连续的空闲位）	各种分配方式
成组链接法	0 额外空间（块号寄存在空闲块内），栈占超级块中固定的一小段	平均 $\frac{1}{组大小}$ 次（组大小 100 时 ≈ 0.01 次）	难（组内块号未必相邻）	Unix / 大型文件系统

读这张表的方法：先看"空间开销"这一列——位示图是唯一与磁盘容量成正比、与使用情况无关的，其余三种都把信息寄存在空闲块自己身上，额外开销为 0，代价是要么访问磁盘、要么难以找连续块。再看"找连续块"这一列，就知道为什么连续分配只能配空闲表/位示图，而 Unix 这种纯离散分配的系统敢用成组链接。

考点速记

数据结构描述的粒度必须与分配请求的粒度对得上：空闲表与空闲盘区链记的都是"段"，前者配连续分配、后者配离散分配；空闲盘块链一个结点只有一个块，且指针在盘上，走一步读一次盘，所以最慢。
两种链的分界看"一个结点代表几个块"：盘块链一个结点 = 一个块，盘区链一个结点 = 一整段。
位示图：每块对应 1 bit（0 空闲 / 1 已占用，也有教材规定相反）。 $N$ 个块需 $N$ bit $= N / 8$ 字节。
⚠️位示图是唯一"占用空间与当前空闲块数量无关"的方法——它只由磁盘容量决定，盘空盘满都一样大。其余三种（空闲表、空闲盘块链、空闲盘区链）的规模都随空闲区的多少浮动。
位示图为什么好：空间小且只与容量有关；找连续空闲块最容易（扫连续的空闲位）；适合位运算，一次扫一个字长。
换算（全 0 起）： $i = ⌊ b / n ⌋$ ， $j = b mod n$ ， $b = i \times n + j$ （ $n =$ 每行 bit 数）。
换算（全 1 起）：先减 1 换回从 0 起的坐标系再算、算完行列各加 1： $i = ⌊ (b - 1) / n ⌋ + 1$ ， $j = (b - 1) mod n + 1$ ，反向 $b = n (i - 1) + j$ 。
⚠️做位示图换算前必须逐个确认三件事：块号从 0 还是从 1 起、行列从 0 还是从 1 起、0 和 1 哪个表示空闲。三处任一处默认错，答案就整体偏移。
成组链接法的两个临界时刻完全对称：栈空时先读栈底那块再把它分配出去（1 次读），栈满时先把整栈写进刚回收的那块（1 次写），其余时刻 0 次 I/O。⚠️先读后分配的顺序一旦颠倒，全部空闲块记录丢失。
能用来管空闲块的结构：位图、空闲磁盘块链、FAT 都可以（FAT 里用特殊标记表示空闲项）；⚠️索引结点不行——它描述的是"某个文件占了哪些块"，不描述"哪些块没人占"。

这一节在真题里被考过的形式：

五道题分成两类：三道位示图的计算，两道"哪种结构能干这件事"的判断。 计算那一类每年换一个包装，但步骤完全固定。

给分区容量和簇大小，问位图本身要占几个簇（2014-27）。三步：总簇数 $=$ 分区容量 $\div$ 簇大小 → 位图字节数 $=$ 总簇数 $\div 8$ → 位图簇数 $=$ 位图字节数 $\div$ 簇大小。10 GB / 4 KB $= 2.5 \times 10^{6}$ 个簇（按 $2^{31} / 2^{12} = 2^{19}$ 算），位图 $2^{19} / 8 = 2^{16}$ B，占 $2^{16} / 2^{12} = 16$ 个簇。⚠️ 最容易漏的是最后那次除以簇大小——题问的是"几个簇"不是"多少字节"。
给位图所在的盘块范围和一个要释放的块号，问该改的位在哪个盘块的第几个字节（2015-31）。⚠️ 这道题把速记第八条的三个陷阱全埋了：位图存在 32～127 号块（所以算出的相对块号要加上起始块号 32）、盘块和块内字节均从 0 开始编号（题目特意写明，就是提示你别默认从 1 起）。步骤：块号 $\div$ 8 得字节序号 → 字节序号 $\div$ 每块字节数得块内偏移与相对块号 → 相对块号 + 32。
问哪种记录空闲块位置的方法，占用外存空间与当前空闲块数量无关（2024-26）。答位示图。⚠️ 这是速记第四条的直接考法——另三种的规模都随空闲区多少浮动，只有位图是"每块一位、盘多大就多大"。
问哪些数据结构可用于管理空闲磁盘块（2019-26、2025-31）。答位图 + 空闲磁盘块链 + FAT 三样；⚠️索引结点不行——它记的是"某个文件占了哪些块"，方向正好相反。FAT 能干这件事是因为它为全盘每一块都建了项（文件的物理结构速记第五条），空闲块在表里用一个特殊值标记即可。

复习优先级：必须拿满，计算题要练熟。 位示图那三道题是同一套换算的三种包装，练到能默写第六、七条的公式；做题前先把速记第八条那三件事逐个在题干里确认一遍，这是唯一会翻车的地方。判断题靠第四、十条两句话。成组链接法至今没单独考过，把两个临界时刻的顺序理解一遍即可。

易错：算位图占多少空间时算到字节就停。题问"几个簇/几个块"时还要再除以簇大小。

易错：位示图换算时默认块号或行列从 1 起。题干会明确写，必须逐个确认。

易错：位图存在非 0 号块起时忘了加上起始块号。算出的是相对块号。

易错：默认 0 表示已占用。两种规定都有教材采用，以题目为准。

易错：认为索引结点也能管空闲块。它记的是"某文件占了哪些块"，方向正好相反。

易错：认为 FAT 不能管空闲块。FAT 为全盘每一块建项，空闲块用特殊值标记即可。

易错：认为空闲表法也和空闲块数量无关。只有位示图与使用量无关。

易错：成组链接法栈空时先分配再读栈底块。必须先读再分配，否则全部空闲块记录丢失。

教材出处

汤小丹《计算机操作系统》印刷版 p261（8.2.2 位示图法）：位示图用一位表示一个盘块，"当其值为 0 时表示对应的盘块空闲，为 1 时表示已分配。有的系统把 0 作为盘块已分配的标志，把 1 作为空闲标志"；盘块号与行列号的换算式为 $b = n (i - 1) + j$ 、 $i = (b - 1) DIV n + 1$ 、 $j = (b - 1) MOD n + 1$ （该书的块号与行列号均从 1 起）。
同书 p262–p263（8.2.3 成组链接法）：空闲盘块号栈"用来存放当前可用的一组空闲盘块的盘块号（最多含 100 个号）以及栈中尚有的空闲盘块数 $N$ ， $N$ 还兼作栈顶指针用"；分配时"若该盘块号已是栈底……须调用磁盘读过程将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去"；回收时"当栈中空闲盘块号数目已达 100 时，表示栈已满，便将现有栈中的 100 个盘块号记入新回收的盘块中，再将其盘块号作为新栈底"；最末一组只有 99 个盘块，S.free(0) 中存放 0 作为空闲盘块链的结束标志。

真题练习

2024Q262分 2015Q312分 2014Q272分

外存空闲空间管理

要分一块盘出去，先得知道哪儿还空着

一、空闲表法与空闲链表法

二、位示图法（Bitmap）

三、成组链接法（Unix 方案）

四、四种方法对比

考点速记

相关知识

真题练习

相关真题（3题）

相关文章

外存空闲空间管理 ​

要分一块盘出去，先得知道哪儿还空着 ​

一、空闲表法与空闲链表法 ​

二、位示图法（Bitmap） ​

三、成组链接法（Unix 方案） ​

四、四种方法对比 ​

考点速记 ​

相关知识 ​

真题练习 ​

相关真题（3题）

相关文章

外存空闲空间管理

要分一块盘出去，先得知道哪儿还空着

一、空闲表法与空闲链表法

二、位示图法（Bitmap）

三、成组链接法（Unix 方案）

四、四种方法对比

考点速记

相关知识

真题练习