操作系统实现之路：文件分配表

文件分配表（File Allocation Table，FAT）是文件管理系统用来记录每个文件所分配的磁盘物理空间的表格，它告诉操作系统或者用户，文件的具体内容存放在磁盘分区的什么地方。

FAT在分区上是紧接保留区域之后的。一般情况下，在一个分区上共有FAT表的两个副本，一个是基本FAT表，另一个是FAT表的备份。两者在磁盘上前后紧排在一起，其大小根据分区的大小不同而变化，一个原则就是，所有分区的簇，都必须在分区表中有对应的表项。在FAT12或者FAT16中，FAT表之后紧接着是根目录，根目录之后是数据区。而在FAT32文件系统中，FAT表之后即是文件数据区。

在分区上的每一个可用簇，都对应FAT表中的一个登记项。通过在对应簇号的登记项内填入特定值，来表明数据区中的该簇是否占用、空闲或者已损坏。损坏的簇是在格式化的过程中，通过FORMAT命令发现的。在一个簇中，只要有一个扇区有问题，该簇就被作为坏簇处理，不能够使用。

FAT文件系统是以簇为单位给文件分配存储空间的，每个簇在FAT表中占用一个表项。所以，在FAT表中，簇编号即对应FAT表项的编号。每一个FAT表项，都作为一个簇的标志信息而存在。针对FAT12、FAT16和FAT32等不同的FAT版本，对应的FAT表项的长度分别为1.5B、2B和4B。表12-2给出了不同FAT表项值的含义，虽然我们重点介绍FAT32，但是也顺便列出FAT12和FAT16的相关内容，供读者参考，如图12-3所示。

表12-2 特殊FAT表项的含义

下面举一个例子，进一步说明文件分配表的工作原理。假设有一个文件，共占用了4个簇，如图12-3所示。

图12-3 文件分配表的结构(www.xing528.com)

在文件的目录项中，存放了文件内容的起始簇号。在这个例子中，文件的起始簇号是4，因此分区上的第4个簇被这个文件占用。但是4号簇所对应的文件分配表中的表项值是6，则说明该文件占用的下一个簇是6。6号簇所对应的FAT表项值是8，则8号簇也分配给了该文件。8号簇的FAT表项值是5，说明5号簇也属于该文件。最后，5号簇对应的FAT表项值是EOC（0xFFFFFFF8到0xFFFFFFF之间的任意值），说明5号簇已是该文件的最后一个簇。

相信读者已经把FAT表的工作机理弄明白了。本质上，针对每个文件，都会有一个与之对应的簇链，这个簇链的第一个簇存放在文件目录项中，链中的每个簇的索引，都存放在其前一个簇的FAT表项中。不论对普通文件还是目录文件，都是以这种相同的方式来存储其内容。

这样在读取一个文件的时候，只要找到文件对应的目录项，从目录项中提取出其起始簇号，然后就顺藤摸瓜，按照簇链依次读取对应的磁盘簇即可。对于文件的写操作，则相对麻烦。因为要考虑是追加写—从文件的最后开始写，还是插入写—从文件的起始或中间开始写。如果是对文件进行追加写，则只需分配一个或一些空闲簇，把要写的内容写入这些簇，然后把这些簇连接到文件簇链的末尾即可。对于插入写，需要分三步进行：

（1）首先申请一个或几个空闲簇，然后连接到文件簇链的末尾。

（2）把从待写入位置开始、到文件结尾（写入前）的内容，向后移动与待写入内容长度相同的字节数。假设待写入位置为偏移100处，写入内容长度为20B，原始文件长度为300B。则需要把从偏移100处、长度为200B的原始文件数据，向后移动20B，空出待写入位置。

（3）把待写入数据写入待写入位置即可。

总之，文件分配表是FAT文件卷的最重要数据结构。一旦FAT表损坏，可能会导致大量的数据丢失，因此FAT文件系统规范定义了FAT表项的保护机制，即在同一个分区上，要有两个FAT表，一个作为主用，另外一个是主用的备份。在读取的时候，只从主用FAT表上读取相关内容即可，除非主用FAT表损坏。在写入的时候，要同时把cluster的使用情况写入主用和备用FAT表。FAT表也是访问频率最高的数据结构，为了提升访问速率，一般的FAT文件系统在实现的时候，都会为FAT表单独申请一些缓存，然后把整个FAT表或部分FAT表项读入缓冲区。这样在访问FAT表的时候，直接从缓冲区读取即可。