1. FAT文件系统基础概念FATFile Allocation Table文件系统是微软在1977年推出的经典文件系统结构至今仍广泛应用于U盘、SD卡等移动存储设备。它的核心设计思想是通过文件分配表来管理磁盘空间就像图书馆的图书索引卡片一样记录每个文件的存储位置。想象一下磁盘被划分成许多大小固定的小格子我们称之为簇每个文件可能占用一个或多个连续的簇。FAT表就是记录这些簇使用情况的账本0x00表示空闲簇0xFF表示文件结束簇其他数值表示下一个簇的编号举个例子假设有个文件存储在簇3、5、7那么FAT表中会这样记录簇3 → 5 簇5 → 7 簇7 → 0xFF这种链式结构就像寻宝游戏中的线索从一个簇指向下一个簇直到找到文件的所有部分。2. 虚拟磁盘结构设计我们先在内存中模拟一个微型磁盘。定义磁盘总大小为1024字节每个簇16字节这样共有64个簇#define MAX_DISK_SIZE 1024 #define BLOCKSIZE 16 u_char g_disk[MAX_DISK_SIZE]; // 虚拟磁盘空间磁盘布局如下表所示区域占用簇号用途说明FAT表区域0存储16个FAT表项每个1字节目录表区域1-4存储最多4个文件FCB文件数据区5-63实际存储文件内容这种设计下系统最多支持4个文件因为只有4个目录项每个文件最大可达(64-5)*16944字节。3. 关键数据结构实现3.1 FAT表结构每个FAT表项用1字节表示定义如下typedef struct _tagfat { u_char cluster; // 0x00:空闲 0xFF:结束 其他:下一簇号 } FAT, *PFAT;3.2 文件控制块(FCB)每个文件需要一个目录项记录元信息typedef struct _tagfcb { char f_name[10]; // 文件名(最长9字符) int f_size; // 文件大小(字节) int f_firstblock; // 起始簇号 } FCB, *PFCB;注意文件名限制为9字符留1字节给结束符\0这是为了简化实现。实际文件系统如FAT32支持长文件名但核心原理相同。4. 核心算法实现4.1 初始化虚拟磁盘void InitDisk() { memset(g_disk, 0, MAX_DISK_SIZE); // 标记前5个簇为已占用(系统保留) for(int j0; j4; j) { ((PFAT)(g_diskj))-cluster 0xFF; } // 初始化目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); pFCB-f_name[0] 0xE5; // 0xE5表示空闲目录项 } }这个初始化过程就像格式化一个新U盘清空所有数据并建立初始文件系统结构。4.2 文件创建流程创建文件的完整流程如下查找空闲目录项扫描目录表区域(簇1-4)找到第一个标记为0xE5的FCB计算所需簇数根据文件大小计算需要的簇数blockcount (f_size / BLOCKSIZE) 1查找空闲簇链在FAT表中寻找连续的可用簇更新FAT表将找到的簇链标记为已占用填充FCB写入文件名、大小和起始簇号写入文件内容将数据按簇分割写入对应位置关键代码片段int CreateFile(pchar f_name, pchar f_content, int f_size) { // 查找空闲目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); if(pFCB-f_name[0] 0xE5) { // 查找足够空闲簇 PNODE pListHead; initList(pListHead); for(int j5; jMAX_FAT; j) { if(((PFAT)(pFAT j))-cluster 0) { insert(pListHead, j); if(--blockcount 0) break; } } // 更新FAT表 PNODE pNode pListHead-pNext; while(pNode) { if(pNode-pNext NULL) { ((PFAT)(pFAT pNode-iValue))-cluster 0xFF; } else { ((PFAT)(pFAT pNode-iValue))-cluster pNode-pNext-iValue; } pNode pNode-pNext; } // 写入文件内容 pNode pListHead-pNext; int remainbyte f_size; for(int k0; kblockcount; k) { int write_size (remainbyte BLOCKSIZE) ? BLOCKSIZE : remainbyte; memcpy(getBlockAddr(pNode-iValue), f_content (BLOCKSIZE * k), write_size); remainbyte - write_size; pNode pNode-pNext; } return 0; // 成功 } } return 11; // 目录已满 }4.3 文件读取实现读取文件时需要顺着FAT表的簇链逐个读取数据块int displayFile(pchar filename) { // 查找目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); if(strcmp(pFCB-f_name, filename) 0) { // 读取第一个簇 printc((pchar)getBlockAddr(pFCB-f_firstblock), (pFCB-f_size BLOCKSIZE) ? BLOCKSIZE : pFCB-f_size); // 顺着FAT表读取后续簇 int next_block pFCB-f_firstblock; int remainbytes pFCB-f_size - BLOCKSIZE; while(((PFAT)(pFAT next_block))-cluster ! 0xFF) { next_block ((PFAT)(pFAT next_block))-cluster; printc((pchar)getBlockAddr(next_block), (remainbytes BLOCKSIZE) ? BLOCKSIZE : remainbytes); remainbytes - BLOCKSIZE; } return 0; } } return -1; // 文件未找到 }4.4 文件删除实现FAT系统的文件删除实际上只是标记相关结构为可用并不真正擦除数据int deleteFile(pchar filename) { // 查找目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); if(strcmp(pFCB-f_name, filename) 0) { // 标记目录项为空闲 pFCB-f_name[0] 0xE5; // 释放FAT表项 int next_block pFCB-f_firstblock; while(((PFAT)(pFAT next_block))-cluster ! 0xFF) { int temp ((PFAT)(pFAT next_block))-cluster; ((PFAT)(pFAT next_block))-cluster 0; next_block temp; } ((PFAT)(pFAT next_block))-cluster 0; return 0; } } return -1; }这种设计使得文件恢复成为可能也是为什么删除文件后如果立即恢复成功率较高的原因。5. 交互式命令行实现我们实现一个简单的shell界面来操作这个文件系统int main() { InitDisk(); printf(欢迎使用迷你文件系统\n); printf(命令列表\n); printf(mkfile - 创建文件\n); printf(dir - 列出文件\n); printf(type - 显示文件内容\n); printf(del - 删除文件\n); printf(quit - 退出系统\n); while(1) { printf(filesys ); scanf(%s, command); if(!strcmp(command,mkfile)) { // 处理文件创建 } else if(!strcmp(command,dir)) { // 列出目录 } else if(!strcmp(command,type)) { // 显示文件内容 } else if(!strcmp(command,del)) { // 删除文件 } else if(!strcmp(command,quit)) { break; } } return 0; }6. 测试案例与结果让我们测试文件系统的各项功能创建文件filesys mkfile 输入文件名(10字符): test.txt 输入文件内容: Hello FAT! 文件创建成功列出目录filesys dir My file system list: ---------------------------------------------- filename filesize ---------------------------------------------- test.txt 9 Bytes ---------------------------------------------- 总文件数:1 总字节数:9 剩余空间:1015 Bytes查看文件内容filesys type test.txt Hello FAT!删除文件filesys del test.txt 文件已删除 filesys dir 当前没有文件7. 扩展与优化建议这个基础实现还可以从以下几个方面进行优化支持子目录当前只支持根目录可以扩展为多级目录结构簇大小优化根据磁盘大小动态调整簇大小减少空间浪费文件属性增加创建时间、权限等元数据持久化存储将虚拟磁盘保存到实际文件中碎片整理定期重组文件簇链提高访问效率实现一个完整的文件系统需要考虑的细节远比这个示例复杂但这个模拟已经揭示了FAT文件系统的核心工作原理。通过这个项目我深刻体会到文件系统设计需要在空间效率、访问速度和实现复杂度之间做出平衡。
从零构建FAT文件系统：C语言模拟实现与核心算法解析
1. FAT文件系统基础概念FATFile Allocation Table文件系统是微软在1977年推出的经典文件系统结构至今仍广泛应用于U盘、SD卡等移动存储设备。它的核心设计思想是通过文件分配表来管理磁盘空间就像图书馆的图书索引卡片一样记录每个文件的存储位置。想象一下磁盘被划分成许多大小固定的小格子我们称之为簇每个文件可能占用一个或多个连续的簇。FAT表就是记录这些簇使用情况的账本0x00表示空闲簇0xFF表示文件结束簇其他数值表示下一个簇的编号举个例子假设有个文件存储在簇3、5、7那么FAT表中会这样记录簇3 → 5 簇5 → 7 簇7 → 0xFF这种链式结构就像寻宝游戏中的线索从一个簇指向下一个簇直到找到文件的所有部分。2. 虚拟磁盘结构设计我们先在内存中模拟一个微型磁盘。定义磁盘总大小为1024字节每个簇16字节这样共有64个簇#define MAX_DISK_SIZE 1024 #define BLOCKSIZE 16 u_char g_disk[MAX_DISK_SIZE]; // 虚拟磁盘空间磁盘布局如下表所示区域占用簇号用途说明FAT表区域0存储16个FAT表项每个1字节目录表区域1-4存储最多4个文件FCB文件数据区5-63实际存储文件内容这种设计下系统最多支持4个文件因为只有4个目录项每个文件最大可达(64-5)*16944字节。3. 关键数据结构实现3.1 FAT表结构每个FAT表项用1字节表示定义如下typedef struct _tagfat { u_char cluster; // 0x00:空闲 0xFF:结束 其他:下一簇号 } FAT, *PFAT;3.2 文件控制块(FCB)每个文件需要一个目录项记录元信息typedef struct _tagfcb { char f_name[10]; // 文件名(最长9字符) int f_size; // 文件大小(字节) int f_firstblock; // 起始簇号 } FCB, *PFCB;注意文件名限制为9字符留1字节给结束符\0这是为了简化实现。实际文件系统如FAT32支持长文件名但核心原理相同。4. 核心算法实现4.1 初始化虚拟磁盘void InitDisk() { memset(g_disk, 0, MAX_DISK_SIZE); // 标记前5个簇为已占用(系统保留) for(int j0; j4; j) { ((PFAT)(g_diskj))-cluster 0xFF; } // 初始化目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); pFCB-f_name[0] 0xE5; // 0xE5表示空闲目录项 } }这个初始化过程就像格式化一个新U盘清空所有数据并建立初始文件系统结构。4.2 文件创建流程创建文件的完整流程如下查找空闲目录项扫描目录表区域(簇1-4)找到第一个标记为0xE5的FCB计算所需簇数根据文件大小计算需要的簇数blockcount (f_size / BLOCKSIZE) 1查找空闲簇链在FAT表中寻找连续的可用簇更新FAT表将找到的簇链标记为已占用填充FCB写入文件名、大小和起始簇号写入文件内容将数据按簇分割写入对应位置关键代码片段int CreateFile(pchar f_name, pchar f_content, int f_size) { // 查找空闲目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); if(pFCB-f_name[0] 0xE5) { // 查找足够空闲簇 PNODE pListHead; initList(pListHead); for(int j5; jMAX_FAT; j) { if(((PFAT)(pFAT j))-cluster 0) { insert(pListHead, j); if(--blockcount 0) break; } } // 更新FAT表 PNODE pNode pListHead-pNext; while(pNode) { if(pNode-pNext NULL) { ((PFAT)(pFAT pNode-iValue))-cluster 0xFF; } else { ((PFAT)(pFAT pNode-iValue))-cluster pNode-pNext-iValue; } pNode pNode-pNext; } // 写入文件内容 pNode pListHead-pNext; int remainbyte f_size; for(int k0; kblockcount; k) { int write_size (remainbyte BLOCKSIZE) ? BLOCKSIZE : remainbyte; memcpy(getBlockAddr(pNode-iValue), f_content (BLOCKSIZE * k), write_size); remainbyte - write_size; pNode pNode-pNext; } return 0; // 成功 } } return 11; // 目录已满 }4.3 文件读取实现读取文件时需要顺着FAT表的簇链逐个读取数据块int displayFile(pchar filename) { // 查找目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); if(strcmp(pFCB-f_name, filename) 0) { // 读取第一个簇 printc((pchar)getBlockAddr(pFCB-f_firstblock), (pFCB-f_size BLOCKSIZE) ? BLOCKSIZE : pFCB-f_size); // 顺着FAT表读取后续簇 int next_block pFCB-f_firstblock; int remainbytes pFCB-f_size - BLOCKSIZE; while(((PFAT)(pFAT next_block))-cluster ! 0xFF) { next_block ((PFAT)(pFAT next_block))-cluster; printc((pchar)getBlockAddr(next_block), (remainbytes BLOCKSIZE) ? BLOCKSIZE : remainbytes); remainbytes - BLOCKSIZE; } return 0; } } return -1; // 文件未找到 }4.4 文件删除实现FAT系统的文件删除实际上只是标记相关结构为可用并不真正擦除数据int deleteFile(pchar filename) { // 查找目录项 for(int i1; i4; i) { PFCB pFCB (PFCB)getBlockAddr(i); if(strcmp(pFCB-f_name, filename) 0) { // 标记目录项为空闲 pFCB-f_name[0] 0xE5; // 释放FAT表项 int next_block pFCB-f_firstblock; while(((PFAT)(pFAT next_block))-cluster ! 0xFF) { int temp ((PFAT)(pFAT next_block))-cluster; ((PFAT)(pFAT next_block))-cluster 0; next_block temp; } ((PFAT)(pFAT next_block))-cluster 0; return 0; } } return -1; }这种设计使得文件恢复成为可能也是为什么删除文件后如果立即恢复成功率较高的原因。5. 交互式命令行实现我们实现一个简单的shell界面来操作这个文件系统int main() { InitDisk(); printf(欢迎使用迷你文件系统\n); printf(命令列表\n); printf(mkfile - 创建文件\n); printf(dir - 列出文件\n); printf(type - 显示文件内容\n); printf(del - 删除文件\n); printf(quit - 退出系统\n); while(1) { printf(filesys ); scanf(%s, command); if(!strcmp(command,mkfile)) { // 处理文件创建 } else if(!strcmp(command,dir)) { // 列出目录 } else if(!strcmp(command,type)) { // 显示文件内容 } else if(!strcmp(command,del)) { // 删除文件 } else if(!strcmp(command,quit)) { break; } } return 0; }6. 测试案例与结果让我们测试文件系统的各项功能创建文件filesys mkfile 输入文件名(10字符): test.txt 输入文件内容: Hello FAT! 文件创建成功列出目录filesys dir My file system list: ---------------------------------------------- filename filesize ---------------------------------------------- test.txt 9 Bytes ---------------------------------------------- 总文件数:1 总字节数:9 剩余空间:1015 Bytes查看文件内容filesys type test.txt Hello FAT!删除文件filesys del test.txt 文件已删除 filesys dir 当前没有文件7. 扩展与优化建议这个基础实现还可以从以下几个方面进行优化支持子目录当前只支持根目录可以扩展为多级目录结构簇大小优化根据磁盘大小动态调整簇大小减少空间浪费文件属性增加创建时间、权限等元数据持久化存储将虚拟磁盘保存到实际文件中碎片整理定期重组文件簇链提高访问效率实现一个完整的文件系统需要考虑的细节远比这个示例复杂但这个模拟已经揭示了FAT文件系统的核心工作原理。通过这个项目我深刻体会到文件系统设计需要在空间效率、访问速度和实现复杂度之间做出平衡。
