操作系统文件管理实验：混合索引与位示图实现详解

1. 文件管理实验到底在练什么

操作系统原理这门课，理论部分讲文件系统的时候，很多人觉得概念都懂——FCB、索引节点、目录树、位示图、成组链接，考试也能默写。但一到实验环节，真正让你用代码去模拟一个文件系统的核心机制，很多人就卡住了。这个实验的核心目标不是让你写一个能用的文件管理器，而是让你亲手实现文件的物理结构映射和存储空间分配回收这两件事，把课本上那些抽象的结构图变成能跑起来的代码。

我带过几轮这个实验，发现一个规律：凡是理论课认真听了、但实验想糊弄过去的同学，最后在操作系统期末考的文件系统大题上基本都会丢分。原因很简单，文件管理这部分的知识点，光靠背是记不住的，必须自己动手算一遍磁盘块号、画一遍索引结构、模拟一次分配回收，才能真正理解为什么要有索引节点、为什么要分成多级索引、位示图和成组链接法各自的适用场景是什么。

这个实验适合两类人：一类是正在上操作系统课、需要完成实验报告的学生；另一类是想通过动手实践来真正理解文件系统底层原理的自学者。不管你是哪一类，接下来的内容会从设计思路、核心数据结构、完整实现流程到常见踩坑，一步步拆开讲清楚。

2. 实验的整体设计思路与方案选型

2.1 为什么选择模拟磁盘而不是操作真实磁盘

这个实验最关键的决策就是：到底是在真实磁盘上操作，还是用内存或文件来模拟一个虚拟磁盘。我的建议非常明确——用文件模拟磁盘。原因有三个：

第一，安全性。直接操作真实磁盘的扇区，一个参数写错就可能把分区表或者引导区覆盖掉，轻则系统崩溃，重则数据全丢。用文件模拟，最坏情况就是删掉那个模拟磁盘文件重新来过。

第二，可控性。模拟磁盘可以把容量设得很小，比如1MB，这样位示图只有256个字节，索引节点数量也有限，调试的时候一眼就能看出问题。真实磁盘动辄几百GB，你根本没法手工验证分配结果对不对。

第三，可观测性。模拟磁盘文件可以用十六进制编辑器打开，直接看到每个字节的变化。比如你分配了一个磁盘块，就能看到位示图对应位从0变成1，这种直观的反馈对理解原理帮助极大。

具体做法是创建一个固定大小的二进制文件，比如1MB，把它当作磁盘的原始扇区集合。然后在这个文件上划分出超级块、索引节点区、数据块区三个部分。超级块记录文件系统元信息，索引节点区存放每个文件的FCB，数据块区就是实际存文件内容的地方。

2.2 索引节点结构的设计取舍

索引节点是这个实验的核心数据结构，它决定了文件能有多大、访问速度有多快。课本上一般会讲三种物理结构：连续分配、链接分配、索引分配。这个实验我建议用混合索引，也就是直接索引加间接索引的组合。

为什么不用连续分配？因为连续分配虽然实现简单、读写快，但会产生外部碎片，而且文件扩展很麻烦。你想想，一个文件本来占第10到第20块，现在要扩展到第25块，但第21到第24块已经被别的文件占了，怎么办？只能整体搬迁，代价太大。

为什么不用纯链接分配？链接分配没有外部碎片，文件扩展也方便，但它只适合顺序访问。如果你想随机读取文件的第500个字节，链接分配必须从头开始沿着指针一个一个块找过去，效率太低。

混合索引就兼顾了两者。具体设计是这样的：索引节点里放12个直接块指针，再加1个一级间接指针、1个二级间接指针、1个三级间接指针。假设每个磁盘块大小是1KB，每个块号占4字节，那么一个间接块可以存256个块号。这样算下来：

这个结构跟经典的Unix文件系统是一致的，既保证了小文件的访问速度（12KB以内的文件直接通过直接索引就能定位），又支持大文件的扩展。

2.3 空闲空间管理：位示图还是成组链接

空闲空间管理有两种主流方案：位示图和成组链接法。这个实验我建议用位示图，原因是它更直观、更容易调试。

位示图的本质就是一个二进制位数组，每一位对应一个磁盘块，0表示空闲，1表示已分配。1MB的模拟磁盘，假设块大小1KB，总共1024个块，位示图只需要1024位，也就是128字节。你甚至可以在调试的时候把位示图打印出来，一眼就能看到哪些块被占了。

成组链接法更适合大容量磁盘，因为它不需要把整个位示图常驻内存。但在实验环境下，128字节的位示图完全可以一直放在内存里，没必要搞那么复杂。

不过这里有个细节要注意：位示图的位序和块号的对应关系。我建议用“第i位对应第i块”的简单映射，不要搞什么偏移量。有些教材上会用“字号×字长+位号”的公式，那个公式本身没错，但在代码里容易算错。直接用block_no / 8得到字节索引，block_no % 8得到位索引，简单明了。

3. 核心数据结构与关键实现细节

3.1 超级块的设计

超级块是文件系统的入口，它记录了整个文件系统的全局信息。在这个实验里，超级块至少需要包含以下字段：

struct SuperBlock { int block_size; // 磁盘块大小，比如1024字节 int total_blocks; // 总块数 int inode_count; // 索引节点总数 int free_blocks; // 空闲块数量 int free_inodes; // 空闲索引节点数量 int bitmap_start; // 位示图起始块号 int inode_start; // 索引节点区起始块号 int data_start; // 数据块区起始块号 };

这些字段里，bitmap_start、inode_start、data_start三个偏移量是最关键的。它们决定了文件系统的布局。我一般这样划分：第0块放超级块，第1块开始放位示图，位示图之后是索引节点区，最后是数据块区。

假设块大小1KB，总块数1024，索引节点数128个，每个索引节点占64字节，那么索引节点区需要128×64=8192字节，也就是8个块。位示图需要128字节，1个块就够了。所以布局是：块0超级块，块1位示图，块2到块9索引节点区，块10到块1023数据块区。

注意：索引节点区的大小必须是块大小的整数倍，否则跨块访问会很麻烦。如果算出来不是整数倍，就向上取整，多出来的空间浪费掉也比跨块处理好。

3.2 索引节点的字段定义

索引节点需要记录文件的所有元信息，除了前面说的混合索引指针，还需要：

struct Inode { int inode_no; // 索引节点号 int file_type; // 0表示普通文件，1表示目录 int file_size; // 文件大小（字节） int link_count; // 硬链接计数 int block_count; // 占用磁盘块数 int direct[12]; // 12个直接块指针 int indirect1; // 一级间接块指针 int indirect2; // 二级间接块指针 int indirect3; // 三级间接块指针 int create_time; // 创建时间戳 int modify_time; // 修改时间戳 int permission; // 权限位 };

这里有个容易忽略的点：目录也是文件。目录的索引节点file_type设为1，它的数据块里存的是目录项数组，每个目录项包含文件名和对应的索引节点号。这样设计的好处是目录和文件可以用同一套读写逻辑，代码复用率高。

3.3 目录项的结构

目录项的结构相对简单，但有一个坑：文件名长度不固定。如果直接用固定长度的字符数组，比如char name[256]，那每个目录项就要占260字节以上，一个1KB的块只能存3个目录项，太浪费了。

我的做法是用变长目录项：每个目录项的前两个字节存目录项总长度，然后是文件名长度、索引节点号，最后是文件名。读取的时候先读前两个字节知道这个目录项有多长，然后跳过相应字节读下一个。这样短文件名占空间少，长文件名也能支持。

struct DirEntry { short rec_len; // 目录项总长度 short name_len; // 文件名长度 int inode_no; // 索引节点号 char name[]; // 变长文件名 };

实操心得：变长目录项在删除文件时会产生空洞。比如删掉一个目录项后，它占的空间就空出来了。我的处理方式是把前一个目录项的rec_len扩展到覆盖这个空洞，这样空间就回收了。这个技巧在真实文件系统里也是这么做的。

4. 完整实操流程与核心环节实现

4.1 第一步：创建和格式化模拟磁盘

创建模拟磁盘就是创建一个固定大小的文件，然后写入初始的超级块、位示图和索引节点区。格式化的时候，所有索引节点的file_type设为-1表示空闲，位示图全部清零。

void format_disk(const char *path) { FILE *fp = fopen(path, "wb+"); // 写入超级块 struct SuperBlock sb; sb.block_size = 1024; sb.total_blocks = 1024; sb.inode_count = 128; sb.free_blocks = 1024 - 10; // 减去元数据区占用的块 sb.free_inodes = 128; sb.bitmap_start = 1; sb.inode_start = 2; sb.data_start = 10; fwrite(&sb, sizeof(sb), 1, fp); // 初始化位示图，元数据区对应的位设为1 unsigned char bitmap[128] = {0}; for (int i = 0; i < 10; i++) { bitmap[i / 8] |= (1 << (i % 8)); } fseek(fp, sb.bitmap_start * sb.block_size, SEEK_SET); fwrite(bitmap, 1, sizeof(bitmap), fp); // 初始化索引节点区 struct Inode inode; inode.file_type = -1; // 空闲 fseek(fp, sb.inode_start * sb.block_size, SEEK_SET); for (int i = 0; i < sb.inode_count; i++) { fwrite(&inode, sizeof(inode), 1, fp); } fclose(fp); }

这段代码的关键在于位示图的初始化。元数据区（超级块、位示图本身、索引节点区）占用的块必须标记为已分配，否则后续分配数据块时可能会覆盖掉元数据，导致文件系统损坏。

4.2 第二步：实现磁盘块的分配与回收

分配一个磁盘块的过程就是扫描位示图，找到第一个为0的位，把它置1，然后返回对应的块号。回收则是把对应的位清零。

int alloc_block(FILE *fp, struct SuperBlock *sb) { unsigned char bitmap[128]; fseek(fp, sb->bitmap_start * sb->block_size, SEEK_SET); fread(bitmap, 1, sizeof(bitmap), fp); for (int i = 0; i < sb->total_blocks; i++) { if (!(bitmap[i / 8] & (1 << (i % 8)))) { bitmap[i / 8] |= (1 << (i % 8)); fseek(fp, sb->bitmap_start * sb->block_size, SEEK_SET); fwrite(bitmap, 1, sizeof(bitmap), fp); sb->free_blocks--; return i; } } return -1; // 没有空闲块 }

这里有个性能问题：每次分配都要把整个位示图读进来再写回去。对于1MB的模拟磁盘，128字节的位示图读写很快，无所谓。但如果模拟磁盘很大，比如1GB，位示图就有128KB，每次都全量读写就太慢了。优化方案是在内存里维护一份位示图的副本，只在关闭文件系统时才写回磁盘。这个实验里为了简单，直接用全量读写就够了。

注意：分配块的时候一定要从data_start开始扫描，不要从0开始。否则可能分配到元数据区的块，把超级块或者索引节点覆盖掉。我见过有同学在这里踩坑，格式化之后第一次创建文件就把超级块写坏了，整个文件系统直接报废。

4.3 第三步：实现文件的创建与写入

创建文件需要做三件事：分配一个空闲索引节点、在父目录中添加一个目录项、初始化索引节点的各个字段。

int create_file(FILE *fp, struct SuperBlock *sb, int parent_inode, const char *name) { // 分配索引节点 int ino = alloc_inode(fp, sb); if (ino < 0) return -1; // 初始化索引节点 struct Inode inode; inode.inode_no = ino; inode.file_type = 0; inode.file_size = 0; inode.link_count = 1; inode.block_count = 0; memset(inode.direct, 0, sizeof(inode.direct)); inode.indirect1 = 0; inode.indirect2 = 0; inode.indirect3 = 0; write_inode(fp, sb, ino, &inode); // 在父目录中添加目录项 add_dir_entry(fp, sb, parent_inode, name, ino); return ino; }

写入文件内容的时候，需要根据写入位置计算应该用哪个索引指针。如果写入位置在12KB以内，直接用直接索引；如果在12KB到268KB之间，需要用一级间接索引；以此类推。

void write_file(FILE *fp, struct SuperBlock *sb, int ino, const char *data, int offset, int len) { struct Inode inode; read_inode(fp, sb, ino, &inode); int block_size = sb->block_size; int written = 0; while (written < len) { int logical_block = (offset + written) / block_size; int block_offset = (offset + written) % block_size; int physical_block = get_physical_block(fp, sb, &inode, logical_block); if (physical_block == 0) { physical_block = alloc_block(fp, sb); set_physical_block(fp, sb, &inode, logical_block, physical_block); } int write_len = block_size - block_offset; if (write_len > len - written) write_len = len - written; fseek(fp, physical_block * block_size + block_offset, SEEK_SET); fwrite(data + written, 1, write_len, fp); written += write_len; } inode.file_size = offset + len; write_inode(fp, sb, ino, &inode); }

这段代码里，get_physical_block和set_physical_block是两个核心辅助函数，它们负责根据逻辑块号找到对应的物理块号。对于直接索引，逻辑块号0到11直接对应inode.direct[0]到inode.direct[11]。对于一级间接，逻辑块号12到267对应间接块中的第0到255个条目。二级和三级间接的映射逻辑类似，只是多了一层跳转。

4.4 第四步：实现文件的读取与删除

读取的逻辑跟写入对称，根据逻辑块号找到物理块号，然后从对应位置读出数据。如果物理块号为0，说明这个逻辑块还没有分配，直接返回0或者空数据。

删除文件需要做四件事：释放索引节点、释放所有数据块、从父目录中删除目录项、更新位示图。释放数据块的时候要注意，不仅要释放直接索引指向的块，还要释放间接索引块本身以及它们指向的数据块。

void delete_file(FILE *fp, struct SuperBlock *sb, int ino) { struct Inode inode; read_inode(fp, sb, ino, &inode); // 释放直接索引块 for (int i = 0; i < 12; i++) { if (inode.direct[i] != 0) { free_block(fp, sb, inode.direct[i]); } } // 释放一级间接索引 if (inode.indirect1 != 0) { free_indirect_blocks(fp, sb, inode.indirect1, 1); } // 二级、三级间接索引类似处理 // 释放索引节点 inode.file_type = -1; write_inode(fp, sb, ino, &inode); sb->free_inodes++; }

实操心得：删除文件时最容易出的bug是漏释放间接索引块。比如一个文件用了二级间接索引，你只释放了数据块和一级间接块，忘了释放二级间接块本身，那这个块就永远泄漏了。调试的时候可以统计一下free_blocks的数量，删除前后对比，看看释放的块数对不对。

5. 常见问题与排查技巧实录

5.1 文件系统挂载失败或数据错乱

这是最常见的问题，表现是格式化之后第一次操作就报错，或者读写几次之后数据对不上。根本原因通常是元数据区的块被当成数据块分配出去了。

排查方法很简单：格式化之后，先打印位示图，确认前10个块（超级块、位示图、索引节点区）对应的位都是1。然后分配一个块，再打印位示图，看看新分配的块号是不是大于等于10。如果小于10，说明分配逻辑有问题。

还有一种可能是索引节点区的偏移量算错了。比如inode_start设成了2，但实际写入索引节点时用的偏移量是inode_start * block_size + ino * sizeof(struct Inode)，如果sizeof(struct Inode)不是64字节而是68字节，那第1个索引节点就会跨到第2个块，导致读写错位。解决办法是在代码里加一个编译期断言：_Static_assert(sizeof(struct Inode) == 64, "Inode size mismatch");。

5.2 大文件写入时数据丢失

小文件写入正常，但写入超过12KB的文件时数据丢失或者读出来是乱码。这个问题几乎可以肯定是间接索引的处理逻辑有bug。

排查步骤：先创建一个13KB的文件，写入已知内容（比如全是字符'A'），然后读出来对比。如果前12KB正确，第13KB开始出错，那就是一级间接索引的问题。检查get_physical_block函数中逻辑块号12对应的处理逻辑，确认它正确读取了间接块中的第0个条目。

还有一个隐蔽的坑：间接块本身也需要分配。有些同学只分配了数据块，忘了给间接块分配空间，结果间接块指针指向0，写入的时候直接写到了磁盘的第0块，把超级块覆盖了。这个bug的典型表现是写入大文件后整个文件系统崩溃。

5.3 目录遍历死循环

遍历目录时程序卡死或者无限循环，通常是因为目录项的长度字段不对。变长目录项的设计里，rec_len表示当前目录项的总长度，遍历时应该用offset += rec_len来跳到下一个目录项。如果某个目录项的rec_len是0，就会死循环。

排查方法：在遍历循环里加一个断言，如果rec_len <= 0就打印错误信息并退出。另外，删除目录项后留下的空洞，必须合并到前一个目录项的rec_len里，否则遍历时会读到空洞里的垃圾数据，可能把rec_len解析成一个很大的值，导致越界访问。

5.4 常见问题速查表

5.5 调试技巧：用十六进制视图验证

我强烈建议在实现过程中加一个调试函数，把模拟磁盘的任意块以十六进制形式打印出来。比如分配了一个数据块，就往里面写入一些已知数据，然后用十六进制视图看看数据是不是真的写到了预期的位置。

这个技巧在排查间接索引问题时特别有用。你可以直接看到间接块里存的块号是不是正确的，数据块里的内容是不是你写入的。比单纯看代码逻辑高效得多。

void hexdump_block(FILE *fp, struct SuperBlock *sb, int block_no) { unsigned char buf[1024]; fseek(fp, block_no * sb->block_size, SEEK_SET); fread(buf, 1, sb->block_size, fp); for (int i = 0; i < sb->block_size; i += 16) { printf("%04x: ", i); for (int j = 0; j < 16; j++) { printf("%02x ", buf[i + j]); } printf(" | "); for (int j = 0; j < 16; j++) { printf("%c", (buf[i + j] >= 32 && buf[i + j] < 127) ? buf[i + j] : '.'); } printf("\n"); } }

这个函数打印出来的格式跟常见的十六进制编辑器类似，左边是偏移量，中间是十六进制字节，右边是ASCII字符。调试的时候一眼就能看出数据对不对。

6. 从实验到理解的几个关键认知

做完这个实验，有几个认知上的转变是值得记录的。

第一个认知转变是关于索引节点和文件的关系。很多人在理论课上会把索引节点理解成文件的一部分，但实际上索引节点和文件数据是分离的。索引节点里存的是元数据和指针，文件数据存在数据块里。一个文件对应一个索引节点，但索引节点本身不包含文件内容。这个分离设计的好处是目录项只需要存文件名和索引节点号，不需要存文件的全部元信息，目录可以做得更紧凑。

第二个认知转变是关于空间分配策略的权衡。位示图简单直观，但位示图本身占空间，而且分配时需要扫描。成组链接法不需要常驻内存的位示图，但实现复杂。没有哪种方案是绝对好的，关键看场景。小文件系统用位示图就够了，大文件系统才需要成组链接。这个权衡思维在系统设计中到处都是。

第三个认知转变是关于间接索引的代价。直接索引访问一个块只需要一次磁盘IO，一级间接需要两次，二级间接需要三次，三级间接需要四次。这就是为什么小文件用直接索引，大文件才用间接索引。文件系统设计里处处都是这种空间和时间的权衡。

最后分享一个我自己的习惯：每次实现完一个功能，不要急着写下一个，先用十六进制视图把磁盘状态打印出来，手工验证一遍。比如创建了一个文件，就检查索引节点区的对应位置是不是写入了正确的数据，位示图对应位是不是变成了1，目录项是不是正确添加了。这个习惯能帮你提前发现80%的bug，比写完所有功能再调试效率高得多。

这个实验后续还可以继续扩展，比如加上文件权限检查、支持硬链接和软链接、实现文件系统的挂载和卸载。每加一个功能，你对文件系统的理解就会更深一层。文件管理这部分内容，光看课本是学不会的，必须自己动手把每个数据结构、每个指针跳转都实现一遍，才能真正掌握。