The MSDOS operating system uses a pair of tables to track files on its file system. It consists of two tables, a block access map that notes available unused space on the current drive partition and a file access table (FAT) that shows space allocated to the individual files stored on the partition.
Because MSDOS was originally designed for a small system with limited secondary storage, the size of the entries in the FAT were small. As the size of secondary storage improved, it became inpossible to keep track of every sector, the standard unit size, on the partition. To overcome this problem, the lower level access functions were designed to read a fixed number of consequetive sectors in a single access. This fixed number of sectors is called a cluster and is determined when the partition is initialized. Different MSDOS partitions may have different sized clusters.
While allowing larger drives to be used with a legacy operating system, there are shortcomings with clustering. All sectors that compose a cluster must exist on a single track, they cannot span a track boundry. As a result, if the number of tracks per cluster are not an integer divisor of the total number of sectors per track, there will be wasted sectors on each track. Additionally, a file will be allotted the whole cluster, even if it is only a few bytes in size.
To overcome this waste of storage, it is common to divide a disk into several partitions. This limits the total number of sectors on any one partition and allows the cluster sizes to be smaller.
The block access map (location of unused clusters) is a table of bits, 1 bit for each cluster on the partition. The bit is a simple flag that marks whether the cluster is in use or not. Since it is a bit table, it can be maintained and scanned very quickly for the next available cluster.
The file access table consists of chained links of cluster pointers. Each file is associated with one chain. When a file is created, the id of the first cluster used is saved in the file's entry in a directory file. The FAT entry for that cluster is either marked with an end of file marker to show that all of the file is stored in a single cluster or the id of the next cluster used to store the next block of file data is saved it the FAT entry. The index into the FAT table and the id of the cluster of interest are the same.
The next entry in the chain in the fat table is then initialzed with the end of file flag or the cluster id of the next file data cluster and fat entry.