成组链接法

定义

成组链接法是一种文件存储空间管理方法，管理对象是磁盘上尚未分配出去的空闲盘块。它的做法是把空闲盘块按固定块数划分为若干组，把盘块号以栈的形式登记起来：当前可供分配的那一组盘块号与块数放进文件系统的超级块，其余各组的信息则由盘块本身承载，一块接着一块地把各组的盘块数和盘块号串接起来。^[1]

在磁盘空闲空间的管理手段里，成组链接法与位示图法并列，是实际系统中最常见的两种做法。^[1]

原理

如果把所有空闲盘块的块号放在同一个栈里，栈的规模可能达到上百万个盘块号，整栈读入内存的开销过大；成组链接法采取分组加链接的结构，正是为了化解这一矛盾。^[2] 划分组时通常以 100 个盘块号为一组，每一组里会有一个盘块承担记录任务，用来存放相邻一组的盘块数和盘块号。^[1]

分配空闲盘块从栈顶开始。系统先检查超级块是否上锁，未上锁时取走栈顶登记的一个空闲盘块号，把对应盘块交给申请者，并把可分配的空闲盘块数减 1。^[1]

如果取走的恰好是本组登记的最后一个盘块号，而这个盘块号又不是结束标记 0，那么该盘块中记有下一组的盘块数与盘块号，系统要先把这些内容读入超级块，之后才能把这个盘块分配出去；若栈顶登记的就是结束标记 0，则说明磁盘上已无空闲盘块可供分配。^[1]

回收空闲盘块的过程与分配相反。若超级块中的这一组尚未达到 100 块，回收块的块号直接登记到栈顶，空闲盘块数加 1；若这一组已经有 100 块，则先把超级块里的空闲盘块数与盘块号写进刚回收的盘块，再把这个盘块号作为栈中唯一的一项，该盘块由此成为新一组的起点。^[1]

应用

成组链接法用于操作系统对磁盘空闲存储空间的管理，与位示图法一起构成最常用的两类文件存储空间管理方式。^[1]

这种登记方式比较节省空间：除第一组空闲盘块之外，其他空闲盘块号的记录并不额外占用存储空间；超级块本身就是文件卷的第 1 块，安装磁盘时已被复制到内存，所以分配与回收绝大多数时候直接在主存里完成，速度较快。^[1]

以某磁盘的实际状态为例，其空闲空间被组织成四组：第一组有 2 块，第二组和第三组各有 100 块，第四组虽然登记为 100 块并放有结束标记 0，实际可用的是 99 块，全部空闲盘块合计 301 块。^[1]

局限

超级块中用于登记空闲盘块号的栈属于临界资源，对它的操作必须互斥进行，系统为此设置了一把锁；只要某个进程正在使用，其他进程就只能等待，分配过程无法完全并行。^[1]

分配也并非始终在内存中完成。当一组中只剩最后一个可分配的盘块时，必须先把记录在该盘块里的下一组信息读出到超级块，这一环节会带来一次额外的磁盘读取。^[1]

当栈顶登记的盘块号为结束标记 0 时，意味着磁盘上的空闲盘块已经用完，此后新的空间申请无法得到满足，只能等待或者由上层作报错处理。^[1]

参见

• 超级块 —— 文件系统中记录资源管理信息的数据结构，成组链接法把当前可分配的一组空闲盘块号登记在其中。

• 位示图法 —— 另一种常用的文件存储空间管理方法，与成组链接法并列。

• 文件系统 —— 成组链接法是文件系统管理磁盘空闲空间时可以选用的方法之一。

• 磁盘 —— 成组链接法管理的对象是磁盘上尚未分配出去的空闲盘块。