文件系统在管理磁盘空间时最绕不开的话题就是“空闲空间怎么记账”。这篇笔记是我OS学习系列的第37篇接着上一篇文件存储空间管理的大框架具体聊聊两种教科书必考的方法链接法和位示图法。简单说链接法就是拿链表把空闲块串起来位示图法则是用二进制位给每个盘块做状态标记。这两种方法不仅仅是应付考试的概念理解它们背后的设计取舍对动手做文件系统、阅读内核源码都很有帮助。这篇笔记适合正在学操作系统的同学也适合刚接触嵌入式文件系统、想自己写一个迷你文件系统的开发者。我会把分配和回收的流程拆开讲清楚给出可复现的换算公式和伪代码再结合我实际踩过的坑说说考试和实践里最容易出问题的地方。1. 文件存储空间管理到底在管什么1.1 两类核心对象盘块与盘区磁盘空间的管理对象可以分成两个粒度盘块和盘区。盘块是最小的分配单位通常是512字节、1KB、4KB这样固定大小盘区则是连续多个盘块组成的一个区间。管理文件存储空间核心就是回答三个问题哪些地方是空的、空的地方有多大、怎么把一个空的位置交给文件使用。这就像仓库管理员管理货架。货架上的每个格子是盘块管理员需要知道哪些格子空着哪些格子放着东西。文件要入库时从空着的格子里挑一个或多个出来文件删掉后格子重新变成空的状态。这个“记账”方式的好坏直接影响了文件系统的分配速度和空间利用率。1.2 为什么要将链接法和位示图法放在一起讲链接法和位示图法是两种完全不同的记账思路。链接法讲究“顺序追踪”用一个头指针记录第一个空闲块空闲块自己存放下一个空闲块的块号位示图法讲究“全局索引”用一张位图表一次性标记所有块的状态。把两者放在一起对比实际上是在比较两类经典的数据结构设计链表适合频繁顺序访问但是随机访问性能差位图适合快速判断某个位置的状态付出的代价是额外的位图存储空间。我从学习OS的第一天起就有一个感觉如果只背概念不对比考完就忘但只要把两种方案放在同一个“分配一个块”的场景里走一遍设计逻辑自然就明白了。2. 链接法用指针串起来的空闲盘块2.1 两种形态空闲盘块链与空闲盘区链链接法在教材里有两种常见形态。第一种叫空闲盘块链以盘块为单位。每个空闲盘块内部留出一小块空间存放下一个空闲盘块的块号磁盘上所有空闲块就这样被串成一条链。文件系统在内存里维护一个链头指针指向第一个空闲块。分配时从链头取一块头指针指向下一块释放时把释放的块挂到链头。这种设计的好处是只需要记录一个头指针非常省内存但缺点是每个空闲块都要牺牲几个字节存指针而且连续分配多个块时得到的物理块号并不连续。第二种叫空闲盘区链以盘区为单位。空闲盘区是连续空闲块组成的区间链上的每个节点不仅要记录下一个盘区的位置还要记录当前盘区的长度。分配时按大小匹配可以做到连续分配较大的文件。这种形态更接近内存管理里的可变分区分配。不过盘区链的维护复杂度明显更高分配前要遍历链找大小合适的盘区释放时还要考虑相邻盘区是否可以合并。2.2 分配一个空闲盘块的过程用空闲盘块链来走一遍分配流程。假设链头指针是free_head每一个空闲盘块的开头4个字节在4KB块上留8个字节也常见存有next_block_no。第一步读链头指针判断链是否为空为空则磁盘没有空闲块。第二步取出链头指向的块将该块作为分配给文件的物理块。第三步根据块内存储的next_block_no更新链头指针让它指向原来的第二块。第四步把更新后的链头指针写回内存并最终落盘。用伪代码表达就是int alloc_block() { if (free_head NULL) return -1; // 没有空闲块 int block_no free_head; free_head disk_read(block_no, NEXT_PTR_OFFSET); // 取下一块号 return block_no; }这里有一个实际操作中容易忽略的问题取出空闲块后块内的数据是无效的旧数据但文件系统必须保证块内至少那个指针字段是有效的直到该块被正式写入文件内容。如果中途系统崩溃很可能出现链头指针指向一块已经被分配走、内部内容又还没写完整的块恢复起来很麻烦。2.3 回收一个盘块的过程回收流程是分配的逆操作把释放的块挂到链头。核心步骤是拿到释放块号把它的next_block_no字段写成当前的free_head再把free_head改为这个释放块号。继续用伪代码表示void free_block(int block_no) { disk_write(block_no, NEXT_PTR_OFFSET, free_head); free_head block_no; }虽然代码很短但有个坑我在嵌入式环境里见过不止一次如果先改free_head再把旧头指针写进释放块中间一旦断电链会断掉或者形成循环。正确做法是先写释放块的指针字段再更新链头指针。另外如果释放的就是当前链头指向的块要特别小心不要在释放块的指针里写自己否则链会变成一条指向自身死循环的链表。2.4 优缺点与适用场景先说优点结构直观实现简单内存开销极低整个管理信息就是一个链头指针。在块数不多的小型存储设备上这个方案完全可以工作比如早期一些嵌入式设备的简易文件系统就是类似思路。缺点也很明显。第一每个空闲块要存指针实际可用空间变少了虽然比例不大但在小容量设备上不可忽略。第二分配多个块时无法保持物理连续性跨盘块读写文件会带来大量寻道性能下降。第三链表的遍历、维护和故障恢复都比较麻烦如果某个节点损坏后面整条链都可能丢失。第四文件系统需要频繁修改链头头指针在内存里还好但如果要落盘每次分配和释放都涉及两次以上磁盘写操作。所以现在的通用操作系统基本不会用单纯的空闲盘块链来管理整个磁盘但它背后的“链式索引”思想影响了后来的 FAT 表设计。FAT 本质上是一张将空闲块和文件块都纳入统一链表的表用表项代替盘块内的指针既保留了链表思想的简单又解决了指针丢失问题。3. 位示图法一bit一个盘块状态3.1 基本原理与大小计算位示图法也叫位图法思路是给每个盘块分配一个二进制位用来记录它是否空闲。一般约定1表示已分配0表示空闲也有教材或者文件系统反过来用1表示空闲、0表示占用学的时候必须先确认这个约定。这张位图本身也要占存储空间它常驻内存用一串连续的二进制位记录整个磁盘盘块的状态。位示图的大小很好算假设磁盘有 N 个盘块一个机器字有 W 位那么位示图需要的字数 M ceil(N / W)。比如一个2GB的磁盘盘块大小1KB那么盘块数N 2GB / 1KB 2,097,152块。如果字长32位M 65,536字换算成字节是256KB。这在一个现代磁盘的容量面前不算大但要注意如果盘块很小、磁盘很大位图占用的内存也会很可观。比如1TB硬盘、4KB块盘块数约2.68亿位图大小约32MB这样就不是轻松能常驻内存的数据了。位示图的优势在于判断任意一个盘块是否空闲只需要一次位运算速度快反过来要找一个空闲块可以顺序扫描位图找到第一个0。连续扫描的效率天然高于遍历链表。3.2 盘块号与字号、位号的换算这是位示图法里的核心计算。假设字长为32位位示图可以用一维数组表示也可以用二维矩阵表示。常见教材设定字号从1开始编号位号也从1开始编号第 i 个字第 j 位对应的盘块号是 b (i - 1) * 32 (j - 1)。如果采用从0开始的编号公式就更简洁b i * 32 j。这两种约定没有对错只是做题、写代码时一旦混用马上就会出错。我的建议是确定盘块号基准后再写代码如果磁盘块号本身从0开始就用后者如果磁盘块号按教材习惯从1开始就用前者。反过来根据盘块号 b 求它在位示图中的位置当块号从0开始时i b / 32j b % 32当块号从1开始、字号位号也从1开始时需要先把块号减一再做除法和取余即 i (b - 1) / 32 1j (b - 1) % 32 1。写代码时我会封装成两个函数避免在分配和回收两个流程里重复换算。3.3 分配与回收流程用位示图法分配一个盘块的基本流程顺序扫描位示图找到第一个值为0的二进制位。根据该位的字号 i 和位号 j利用换算公式得到盘块号 b。将位示图中该位置为1。把盘块 b 返回给文件系统。用伪代码表示int alloc_block(bitmap[], int words, int bits_per_word) { for (int i 0; i words; i) { if (bitmap[i] all_ones) continue; for (int j 0; j bits_per_word; j) { if ((bitmap[i] (1 j)) 0) { bitmap[i] | (1 j); return i * bits_per_word j; // 块号从0开始 } } } return -1; // 磁盘满 }回收一个盘块的过程是反向的根据盘块号 b算出对应的字号 i 和位号 j。将位示图中该位恢复为0。如果为了调试方便可以顺手做一次一致性检查确认该位原本确实是1。伪代码void free_block(int bno, int bits_per_word) { if (bno 0) return; int i bno / bits_per_word; int j bno % bits_per_word; bitmap[i] ~(1 j); }3.4 位示图的驻留与分组加载位示图必须驻留内存否则每次分配都得读磁盘性能完全没法接受。这是位示图与链表最大的不同链表的管理信息在磁盘上头指针在内存里位示图的管理信息整张都在内存。现代文件系统解决大位图内存问题的方式是“分组”。比如 ext 系列把磁盘划分成多个块组每个块组都有一张独立的块位图需要分配时只加载对应组的小位图这样内存压力和扫描范围都控制住了。这实际上就是位示图思想在工程化上的优化考试里如果问“位示图太大怎么办”可以从这个方向回答。3.5 优缺点与适用场景位示图法的优点很突出存储开销固定且可精确计算不管磁盘用得多满位图大小不变分配和回收只涉及少量位运算和内存拷贝能方便地找到连续空闲区域适合需要连续块分配的场景。缺点也不是没有分配时最坏情况要扫描整个位图如果磁盘快满了找到0的代价可能比较高位图必须常驻内存对超大磁盘不友好位图本身也是一块数据修改后需要持久化如果内存中的位图和磁盘上的真实状态不一致恢复起来比链表还复杂。由于位图速度快、结构规整很多文件系统都采用了类似思想。ext 系列用块位图和 inode 位图数据库系统也用位图做空间管理。学习时最好把它当作一种通用的空间管理数据结构来看而不只是OS课上的一个考点。4. 两种方法怎么选4.1 维度对比表我把链接法和位示图法的关键差异整理成一张表方便对照对比维度空闲盘块链位示图法内存开销仅一个链头指针整张位图常驻内存大小随盘块数线性增长分配逻辑取链头修改指针扫描位图找第一个0位运算置1回收逻辑挂链头修改指针位运算清零分配多个连续块不支持物理块号分散可以扫描连续多个0支持连续分配随机查询某块状态需要遍历查找效率低O(1)位运算直接判断故障一致性指针链易断恢复困难位图与真实状态可能不一致需要单独修复适用规模小磁盘、简单系统中大规模磁盘、现代文件系统从整体上看位示图法在现代操作系统中明显占优因为它把“管理信息”集中化了能够用空间换取时间和随机访问能力的提升。链接法则更适合慎用除非场景非常小、非常简单。4.2 真实文件系统里的影子学习概念时一定要跟真实系统挂钩不然就像背菜谱却不会点菜。空闲盘块链的影子可以在文件系统的 FAT 表里看到。FAT 表用链式索引管理文件占用的簇空闲簇也通过 FAT 表中的特殊标记来标识本质上是一个集中化、表格式的链表。链的思想依然在但它不再让每个块自己保存指针而是把指针统一存到一张表里这样即使链断了也可以通过全表扫描恢复。位示图法的影子更多。ext2/3/4 的每个块组都有一张数据块位图NTFS 也用位图文件管理卷上的簇还有一些简易文件系统课程设计直接用一张大位图解决所有空间管理问题。学位示图法时可以想想这些系统的位图是常驻内存还是按需加载为什么不直接做一张覆盖全盘的大位图。4.3 我自己的选择经验如果让我给一个课程设计做选择我会优先选位示图法。原因很实际代码量可控分配回收逻辑清晰测试时也好验证——把位图打印出来0 和 1 的分布一目了然而链表法调试时一旦断链排查指针问题要花很久。但如果资源极其受限比如内存只有几十KB盘块总数几百个用空闲盘块链反而更好因为它不需要为整个磁盘保留一张常驻位图。还有一种情况我也会考虑链表思路当系统对“分配速度”要求远高于“随机查询”时链头取块是真正的 O(1)比扫描位图更可控。只不过这种情况在现代通用系统里很少出现。5. 常见问题与避坑实录5.1 块号从0开始还是从1开始的坑这是位示图法最常见的出错点。如果磁盘块号从1开始分配的第一个空闲块对应位图的位置往往不是在0号字0号位而要从(1,1)开始。我曾经在写模拟文件系统时统一用从0开始的编号写代码但是磁盘初始化时把第一个块留给了引导区导致位图里第0位表示的真实块号和我公式算出来的对不上。建议在代码里定义清晰的常量磁盘块号基址和位图下标基址比如约定盘块号从0开始、位图下标从0开始这样公式最简单。如果教材用从1开始的约定就在换算函数里减1。不要一会儿用一套约定否则考前看十遍错十遍。5.2 位图语义“0和1”理解反了有的教材用1表示空闲0表示已分配这就会导致分配代码里找的从“0”变成找“1”。其实两种约定都行关键是代码内部自洽。我这里一直用1表示已分配因为实际文件系统里位图文件写入时需要把对应位置1来标记占用直觉上更自然。如果你看的是另一种约定先转换成自己的约定再写代码不要在代码里混着用。5.3 位图与真实状态不一致这是位示图法在实践中最大的隐患。假设内存中的位图已经置1表示某块已分配但文件数据还没落盘此时断电磁盘上实际的块可能是旧的垃圾数据而重启后位图仍然认为该块被占用就造成空间泄漏。反过来回收时位图清零了但数据还没真正清除也会造成该块被重新分配给别的文件时残留旧数据。真实文件系统会通过日志、事务或者开机时的fsck检查来修复这种不一致。自己做小系统时至少应该在每次正常卸载时把内存位图完整写回磁盘加载时再做一次位图更新标记。5.4 扫描大量零位时的性能问题位示图法分配时的最坏情况是扫描整张位图。如果磁盘几乎满了分配一个新块可能要扫过几百万个1这在每次分配时都发生性能会很差。工程上的优化是按字判断一个32位字如果等于 all-ones就跳过整个字如果存在空闲位再在字内逐位找。一些实现还用“下次分配位置”的游标来避免每次都从头扫描加快分配速度。5.5 链表法的指针断裂与自指陷阱空闲盘块链调试起来非常痛苦。块在分配给文件后原来存储“下一空闲块号”的位置会被文件数据覆盖释放后我们需要重新写入指针。如果释放块时恰好覆盖了指针字段而忘记了更新链头整条链就断了。更隐蔽的是自指问题把释放块挂到链头时如果它在链头位置又正好是原来链头后面的那块操作顺序稍有不对就会形成 A - B - A 的循环链。排查这类问题只能把整条链遍历一遍打印出来非常费时间。这些坑不是说这两种方法不可用而是提醒我们管理空闲空间不只是“记录哪些地方空着”还包括如何保证操作的原子性和一致性。理解这一点比记住某个方法更关键。我记这篇笔记时最大的体会是链表法和位示图法本质上就是“内存效率”和“时间效率”之间的一次选择题。前者用最少的元数据换来了最简单的结构后者用固定大小的位图换来了更快的判断和更好的连续分配能力。学习时不妨顺手写个小程序模拟在同一个磁盘上分别用两种方式分配、释放一批随机大小的文件再对比一下磁盘碎片率和分配耗时。亲手跑过一轮之后考试里那些“优缺点”就不再是背出来的词而是自己亲手验证过的结论。
