File Allocation Table

To keep track of which cluster belongs in which file, DOS uses a File Allocation Table, or FAT, essentially a map of the clusters on the disk. When you read to a file, DOS automatically and invisibly checks the FAT to find all the clusters of the file; when you write to the disk, it checks the FAT for available clusters. No matter how scattered over your disk the individual clusters of a file may be, you-and your software-only see a single file.

FAT-based file systems simply number all the clusters in a manner similar to the way a disk drive numbers logical blocks. The operating system keeps track of which cluster number and in what order clusters have been assigned to a given file. The operating systems stores most of the cluster data in the file allocation table.

The FAT file system works by chaining together clusters. The directory entry of a file or subdirectory contains several bytes of data in addition to the file's name. Along with the date the file was last changed and the file's attributes is the number of the first cluster used to store the file or subdirectory.

When the operating system reads a file, it first checks the directory entry to find the first cluster number. In addition to reading the data from the cluster from the disk, the operating system also checks the file allocation table for the entry with the number corresponding to the first cluster number. This FAT entry indicates the number of the next cluster in the file. After reading that cluster, the operating system checks the entry corresponding to that cluster number to find the next cluster. If the file has no additional clusters, the cluster entry has a value of 0FF(Hex). The operating system assigns unused clusters-those available for adding to files to store data-the value of zero.

When the standard PC operating system, DOS, erases a file it merely changes the first character of the file name in the directory entry to 0E5(Hex) and changes all the FAT entries of the file to zero. Because the rest of the directory information remains intact (at least until DOS runs out of space for directory information and overwrites the entries of erased files), it can be recovered to help reconstruct accidentally erased files. Unerase and undelete utilities check the directory for entries with the first character of 0E5(Hex) and display what they find as candidates for recovery. From the remaining directory data, the unerasing program can locate the first cluster of the file. Finding the remaining clusters from the FAT is a matter of making educated guesses.

The FAT of a disk is so important that DOS (and Windows when it uses the FAT system) guards against losing its data by putting two complete (and identical) copies of the FAT end-to-end on the disk.