Penguin
Note: You are viewing an old revision of this page. View the current version.

A FileAllocationTable (FAT) is a map maintained by the FileSystem on a HardDisk to keep track of which DiskClusters a file has been stored in. If it spans several of them, they need not be sequential, but rather may be widely scattered over the disk.

MS-DOS (and the versions of MicrosoftWindows that sat on top of DOS) used FAT FileSystems... firstly FAT12, then FAT16, then FAT32.

The FAT is organized as an array as large as there are clusters on the disk, each entry in the array storing the cluster number of the next piece of a file. This way, the FileSystem driver can "hop" from cluster to cluster, collecting the pieces of the file.

While simple in concept, a FAT is unreliable. A single bit error may lead to inconsistencies with several files - they may become crosslinked, with one of the chains pointing to cluster in the other chain. Since allocation of disk space happens in the same step as assigning it to a file, a crash can easily lead to unduly or incompletely allocated space. A crash during rewriting or deleting a file can lead to the a part of the existing chain persisting, without any file pointing to it, thus leaving it inaccessible.

Microsoft tried to mitigate these problems by storing a backup version of the table on the partition, but only managed to exacerbate the problem by requiring a fragile procedure to succeed multiple times. In addition, there is no indication of which copy is authoritative, when they differ.

Better FileSystems manage disk space using a separate bitmap for allocation of clusters and Inodes for assigning them. The latest in advances are attempts replace all of these with BTrees.