1. 文件物理结构与存储空间管理到底在解决什么问题文件系统这玩意儿平时用起来好像理所当然——你往硬盘里拖个文件它就存进去了你双击打开它就出来了。但真到了要自己设计一个文件系统或者面试被问到“一个10MB的文件在磁盘上到底是怎么放的”很多人就卡壳了。操作系统第四章的文件管理核心就两块文件的物理结构和文件存储空间管理。前者回答“文件的数据块在磁盘上怎么串起来”后者回答“磁盘上哪些块是空的、怎么找、怎么分配”。这两个问题之所以重要是因为它们直接决定了文件系统的读写性能、空间利用率和可靠性。你选连续分配顺序读飞快但文件不好扩展你选链式分配扩展容易但随机访问基本废了你选索引分配随机访问爽了但小文件浪费索引块。存储空间管理也一样空闲表简单但大磁盘下效率低位示图直观但占内存成组链接法兼顾了两者但实现复杂。每一种方案背后都是权衡没有银弹。这篇文章适合正在学操作系统课程的学生、准备面试的后端或系统方向求职者以及任何想搞清楚“文件到底怎么存”的开发者。我会从设计思路讲到具体实现把每种结构的优缺点、适用场景、参数计算都拆开揉碎再配上存储空间管理的几种经典方法最后给一份常见问题排查表。你跟着走一遍这块知识基本就通了。2. 文件的物理结构三种经典方案的设计逻辑与取舍2.1 连续分配最简单也最粗暴的方案连续分配的思路非常直白一个文件在磁盘上占一段连续的物理块。比如文件A需要5个块那就从第100号块开始占100、101、102、103、104。目录项里只需要记录起始块号和长度访问时用起始块号加上偏移量就能直接算出目标块。这种方案的好处是顺序访问和随机访问都很快。因为块是连续的磁头移动距离短寻道时间少。随机访问也简单第i个逻辑块直接对应起始块号i一次计算就到位。但问题也很明显文件扩展困难。如果文件A后面紧跟着文件BA想从5个块扩到8个块就得把A整体搬到别的地方或者把B挪走。频繁扩展会导致大量数据搬移性能急剧下降。另一个问题是外部碎片。磁盘上会出现很多小的空闲区单个可能只有几个块但没有任何一个文件能放进去。比如空闲区有3块、2块、4块但新文件需要6块就用不了。虽然可以用紧凑技术把空闲区合并但那需要移动大量数据代价很高。连续分配适合一次性写入、很少修改、对顺序读写性能要求高的场景比如早期的数据库文件、视频文件存储。实际计算时如果块大小为4KB文件大小10MB那需要2560个块。起始块号假设是5000那占用范围就是5000到7559。目录项里记录起始块号5000和块数2560即可。注意连续分配下文件的逻辑块号到物理块号的映射是线性的公式为物理块号 起始块号 逻辑块号。这个公式在考试和面试中经常被问到。2.2 链式分配像链表一样串起来链式分配把文件的数据块分散在磁盘各处每个块里留一个指针指向下一个块。目录项记录第一块的块号和最后一块的块号。这样文件扩展就很容易了——直接在空闲块里找一个把当前最后一块的指针指过去就行。链式分配分两种隐式链接和显式链接。隐式链接就是每个块里存下一个块的指针访问第i块必须从头开始遍历随机访问性能极差。显式链接把所有的指针集中放在一张文件分配表里整张表存在内存中访问第i块时查表就行不需要读磁盘。FAT文件系统就是典型的显式链接。链式分配的优点是没有外部碎片任何空闲块都能用文件扩展方便。缺点是随机访问慢隐式链接下而且指针占用空间。如果块大小4KB指针4字节那指针开销占比约0.1%看起来不大但小文件多的时候累积起来也可观。另外链式分配可靠性差——如果某个块的指针坏了后面的数据就全丢了。实际计算时假设块大小4KB文件10MB需要2560个块。隐式链接下访问第2560块需要读2560次磁盘每次读一个块。显式链接下FAT表有2560个表项每个表项4字节共10KB左右可以常驻内存访问第i块查一次表即可。2.3 索引分配用索引块解决随机访问问题索引分配给每个文件建一个索引块里面存放该文件所有数据块的块号。目录项记录索引块的块号。访问第i块时先读索引块找到第i个表项再读对应的数据块。这样随机访问只需要两次磁盘访问一次索引块一次数据块比链式分配好很多。索引分配的优点是支持随机访问、文件扩展容易、没有外部碎片。缺点是索引块本身占用空间。如果文件很小比如只有1个块那也得分配一个索引块浪费。如果文件很大一个索引块装不下所有块号就需要多级索引或混合索引。多级索引类似页表的多级结构。比如两级索引第一级索引块指向第二级索引块第二级索引块指向数据块。假设块大小4KB每个块号4字节那一个索引块能存1024个块号。两级索引能支持1024×10241M个数据块即4GB的文件。三级索引能支持4TB。混合索引是UNIX文件系统常用的方案。inode里直接放若干个直接块号比如12个再放一个一级间接块号、一个二级间接块号、一个三级间接块号。小文件用直接块中等文件用一级间接大文件用多级间接。这样既照顾了小文件的效率又支持了大文件。实际计算时假设inode有12个直接块、1个一级间接、1个二级间接、1个三级间接块大小4KB块号4字节。直接块能存12×4KB48KB。一级间接能存1024×4KB4MB。二级间接能存1024×1024×4KB4GB。三级间接能存1024×1024×1024×4KB4TB。总最大文件大小约4TB4GB4MB48KB。提示索引分配下访问第i个逻辑块时需要先判断i落在哪个范围。如果i12直接查inode的直接块如果12≤i121024查一级间接以此类推。这个判断过程在考试中经常要求写出计算步骤。2.4 三种方案的对比与选型建议方案随机访问文件扩展外部碎片空间开销适用场景连续分配快困难有无一次性写入、顺序读写链式分配慢隐式/中显式容易无指针开销文件频繁扩展、顺序访问索引分配快容易无索引块开销通用场景、随机访问多选型时如果文件大小固定且顺序访问为主连续分配最划算。如果文件频繁增长且以顺序访问为主链式分配更合适。如果随机访问频繁且文件大小差异大索引分配或混合索引是最佳选择。实际操作系统很少只用一种比如UNIX用混合索引Windows的NTFS用类似B树的结构本质上是索引分配的变种。3. 文件存储空间管理空闲块怎么找、怎么分3.1 空闲表与空闲链表最直观的两种方法空闲表法就是维护一张表记录每个空闲区的起始块号和长度。分配时用首次适应、最佳适应或最坏适应算法找合适的空闲区。首次适应从表头开始找第一个够大的最佳适应找最小的够用的最坏适应找最大的。释放时把相邻的空闲区合并。空闲表法的优点是实现简单适合空闲区数量不多的情况。缺点是表可能很大而且分配时需要遍历。如果磁盘有100万个块空闲区有10万个那表就有10万项遍历一次很慢。空闲链表法把空闲块串成链表。每个空闲块里存下一个空闲块的指针。分配时从链头取一块释放时把块插到链头。这种方法不需要额外的表但随机访问差而且链表指针占用空闲块本身的空间。如果块大小4KB指针4字节那每个空闲块实际可用空间少4字节。实际计算时假设磁盘有100万个块空闲块50万个。空闲表法下如果空闲区平均长度10块那表有5万项每项8字节起始块号长度共400KB。空闲链表法下50万个空闲块每个存4字节指针共2MB但这些指针存在磁盘上不占内存。3.2 位示图用二进制位标记空闲状态位示图用一个二进制位表示一个块的状态0表示空闲1表示占用或反过来。所有块的状态组成一个位向量。假设磁盘有100万个块那位示图需要100万位即125KB。这个大小可以常驻内存分配和释放都很快。位示图的优点是空间效率高、查找连续空闲块方便。找连续n个空闲块时可以用位运算快速扫描。缺点是位示图大小随磁盘容量线性增长。如果磁盘有10亿个块位示图需要125MB内存压力就大了。实际计算时块号从0开始位示图的第i位对应第i个块。如果字长为32位那第i位在第i/32个字第i%32位。分配时扫描位示图找0置1释放时置0。找连续空闲块时可以用循环移位和掩码操作加速。注意位示图法下块号的计算公式为字号 块号 / 字长位号 块号 % 字长。这个公式在考试中经常要求写出。3.3 成组链接法UNIX的经典方案成组链接法把空闲块分成若干组每组的第一块记录下一组的块号和本组的空闲块数。系统启动时把第一组的块号读入内存栈。分配时从栈顶取块如果栈空了就把下一组读入栈。释放时把块压入栈如果栈满了就把栈中所有块号写入新块作为新的一组。这种方法的优点是兼顾了空闲表和空闲链表的优点不需要大表也不需要遍历长链表。缺点是实现复杂需要处理栈满栈空的情况。UNIX文件系统就用这种方法。实际计算时假设块大小4KB每个块号4字节那一个块能存1024个块号。如果磁盘有100万个空闲块那需要约1000组。每组的第一块存下一组信息实际可用空闲块数略少。分配时从内存栈取栈空时读下一组最多读一次磁盘。3.4 三种方法的对比与选型建议方法内存开销分配速度释放速度连续块查找适用场景空闲表中中中方便空闲区少空闲链表低快快困难空闲块多且分散位示图高快快方便内存充足成组链接低快快中通用场景选型时如果内存充足且需要快速查找连续块位示图最合适。如果内存紧张且空闲块分散空闲链表或成组链接更合适。实际操作系统很少只用一种比如ext2用位示图ext3/ext4用位图加多块分配NTFS用位图加B树。4. 实操过程从零实现一个简单的索引分配文件系统4.1 环境准备与数据结构设计我们用Python模拟一个简单的索引分配文件系统。不需要真的读写磁盘用内存中的数组模拟磁盘块。定义块大小BLOCK_SIZE4096字节磁盘总块数TOTAL_BLOCKS1024。磁盘用一个列表表示每个元素是一个字节数组。BLOCK_SIZE 4096 TOTAL_BLOCKS 1024 disk [bytearray(BLOCK_SIZE) for _ in range(TOTAL_BLOCKS)] free_blocks set(range(TOTAL_BLOCKS)) # 空闲块集合索引块结构每个索引块存1024个块号因为4096/41024。用列表表示索引块每个元素是块号或-1表示空。INDEX_ENTRIES BLOCK_SIZE // 4 # 1024 def allocate_block(): if not free_blocks: raise Exception(No free blocks) return free_blocks.pop() def free_block(block_num): free_blocks.add(block_num)文件结构每个文件有一个inode记录索引块号、文件大小、直接块号列表简化版只用一级索引。class Inode: def __init__(self): self.index_block -1 self.size 0 self.data_blocks [] # 数据块号列表4.2 文件创建与写入的实现创建文件时分配一个索引块初始化索引块内容为-1。def create_file(): inode Inode() inode.index_block allocate_block() # 初始化索引块 index_data [-1] * INDEX_ENTRIES write_index_block(inode.index_block, index_data) return inode def write_index_block(block_num, index_data): # 把index_data写入磁盘块 data bytearray(BLOCK_SIZE) for i, val in enumerate(index_data): data[i*4:(i1)*4] val.to_bytes(4, little) disk[block_num] data def read_index_block(block_num): data disk[block_num] index_data [] for i in range(INDEX_ENTRIES): val int.from_bytes(data[i*4:(i1)*4], little) index_data.append(val) return index_data写入文件时按逻辑块号依次分配数据块更新索引块。def write_file(inode, data): # data是字节串 num_blocks (len(data) BLOCK_SIZE - 1) // BLOCK_SIZE index_data read_index_block(inode.index_block) for i in range(num_blocks): if i len(inode.data_blocks): block_num inode.data_blocks[i] else: block_num allocate_block() inode.data_blocks.append(block_num) index_data[i] block_num # 写入数据 start i * BLOCK_SIZE end min(start BLOCK_SIZE, len(data)) disk[block_num][:end-start] data[start:end] inode.size len(data) write_index_block(inode.index_block, index_data)4.3 文件读取与删除的实现读取文件时根据逻辑块号查索引块再读数据块。def read_file(inode): index_data read_index_block(inode.index_block) result bytearray() num_blocks (inode.size BLOCK_SIZE - 1) // BLOCK_SIZE for i in range(num_blocks): block_num index_data[i] if block_num -1: raise Exception(Block not allocated) start i * BLOCK_SIZE end min(start BLOCK_SIZE, inode.size) result.extend(disk[block_num][:end-start]) return bytes(result)删除文件时释放所有数据块和索引块。def delete_file(inode): index_data read_index_block(inode.index_block) for block_num in index_data: if block_num ! -1: free_block(block_num) free_block(inode.index_block) inode.index_block -1 inode.data_blocks [] inode.size 04.4 存储空间管理的集成我们把空闲块集合当作位示图的简化版。实际位示图可以用一个字节数组每个位表示一个块。分配时扫描找0置1释放时置0。class Bitmap: def __init__(self, total_blocks): self.total total_blocks self.bits bytearray((total_blocks 7) // 8) def allocate(self): for i in range(self.total): byte_idx i // 8 bit_idx i % 8 if not (self.bits[byte_idx] (1 bit_idx)): self.bits[byte_idx] | (1 bit_idx) return i raise Exception(No free blocks) def free(self, block_num): byte_idx block_num // 8 bit_idx block_num % 8 self.bits[byte_idx] ~(1 bit_idx) def is_free(self, block_num): byte_idx block_num // 8 bit_idx block_num % 8 return not (self.bits[byte_idx] (1 bit_idx))集成后allocate_block和free_block改用Bitmap。bitmap Bitmap(TOTAL_BLOCKS) def allocate_block(): return bitmap.allocate() def free_block(block_num): bitmap.free(block_num)4.5 测试与验证写个测试脚本创建文件、写入数据、读取数据、删除文件验证正确性。def test(): inode create_file() data bHello, file system! * 1000 write_file(inode, data) read_data read_file(inode) assert read_data data, Data mismatch delete_file(inode) # 验证所有块已释放 for i in range(TOTAL_BLOCKS): assert bitmap.is_free(i), fBlock {i} not freed print(All tests passed) test()实测下来这个简化版能正确处理文件创建、写入、读取、删除位示图也能正确管理空闲块。实际文件系统还要处理多级索引、目录、权限等但核心逻辑就是这样。5. 常见问题与排查技巧实录5.1 文件读写性能突然下降怎么排查如果文件系统突然变慢先看是不是碎片化严重。连续分配下文件被分散到多个不连续区域磁头移动距离增加。用磁盘碎片整理工具或查看文件分布。链式分配下如果链表指针分散随机访问会退化成顺序访问。索引分配下如果索引块分散读索引块也要多次寻道。排查步骤1. 用工具查看文件块分布2. 检查空闲块管理方法是否导致分配不连续3. 如果是位示图检查是否总是分配最低块号导致热点4. 如果是成组链接检查栈是否频繁切换组。提示实际生产环境中文件系统碎片化是性能下降的常见原因。定期整理或使用支持延迟分配的日志式文件系统可以缓解。5.2 磁盘空间足够但文件保存失败这种情况通常是外部碎片或索引块耗尽。连续分配下空闲区总大小够但单个空闲区不够。用紧凑技术合并空闲区或改用链式/索引分配。索引分配下如果索引块用完了小文件也存不了。检查空闲索引块数量必要时增加索引块或改用混合索引。另一个可能是inode耗尽。每个文件需要一个inode如果inode数量固定且用完了即使磁盘有空间也创建不了新文件。检查inode使用率调整文件系统参数。5.3 文件损坏或数据丢失的常见原因链式分配下指针损坏会导致后续数据全部丢失。索引分配下索引块损坏会导致整个文件不可读。位示图下位示图与实际情况不一致会导致块被重复分配或永久丢失。排查方法1. 用文件系统检查工具扫描一致性2. 检查日志如果有日志功能3. 对比位示图和实际块使用情况4. 对于索引分配检查索引块是否可读。注意实际文件系统通常有冗余机制比如备份超级块、日志、校验和。设计时要考虑容错。5.4 常见问题速查表问题可能原因排查方法解决方案读写慢碎片化查看块分布整理碎片或改分配方式保存失败外部碎片检查空闲区大小紧凑或改分配方式保存失败inode耗尽检查inode使用率增加inode或清理数据丢失指针/索引块损坏文件系统检查恢复备份或日志块重复分配位示图不一致对比位示图与实际修复位示图空间浪费索引块开销统计小文件数量改用混合索引5.5 独家避坑技巧第一不要在小文件多的场景用纯索引分配。每个小文件一个索引块浪费严重。用混合索引小文件用直接块。第二位示图不要用链表实现。位示图的核心优势是位运算快速扫描用链表就废了。用字节数组或整数数组。第三成组链接法的栈大小要合理。栈太大占内存太小频繁读磁盘。一般栈大小等于一个块能存的块号数。第四测试时要覆盖边界情况。文件大小为0、刚好一个块、刚好一个索引块能存的最大块数、超过一级索引范围等。这些边界最容易出bug。第五实际文件系统要考虑并发。多个进程同时分配块时位示图或空闲表要加锁。测试时单线程没问题多线程可能重复分配。6. 从理论到实践我的几点经验体会学文件物理结构和存储空间管理最容易犯的错是只记概念不记计算。面试官问“一个10MB文件用混合索引存访问第1000个逻辑块需要几次磁盘访问”你得能立刻算出来。我的建议是把每种结构的访问次数公式背熟连续分配1次隐式链接i次显式链接1次查内存表1次读数据索引分配2次读索引读数据混合索引根据范围判断。另一个体会是画图比死记强。把磁盘块画成方格文件块用不同颜色标出连续分配就是一段连续颜色链式分配就是散落颜色加箭头索引分配就是散落颜色加一个索引块指向它们。画一遍就记住了。最后动手写代码。我上面给的Python模拟虽然简单但写一遍你对索引块、位示图、分配释放的理解会深很多。实际文件系统代码几万行但核心逻辑就这些。你把这个简化版跑通再看ext2或FAT的源码会发现思路一模一样。这个内容后续还可以这样扩展研究日志式文件系统怎么保证一致性或者研究SSD上的文件系统怎么处理擦除块或者对比不同操作系统的文件系统实现差异。每一个方向都能写一篇长文。
1)
