The first file system to be used in a Microsoft operating system was the FAT system, which uses a file allocation table. This table is actually an index that creates a list of disk contents to record the location of files on the disk. Since the blocks that make up a file are not always stored contiguously on the disk (a phenomenon called fragmentation), the allocation table allows the structure of the file system to be maintained by creating links to the blocks that make up the file.
The FAT system is a 16-bit system that allows files to be identified by a name consisting of up to 8 characters and a 3 character extension, this is the reason why the system is called FAT16.
Cluster addresses can not be bigger than 16 bits. The maximum number of clusters that can be referenced with the FAT system is therefore 216, (65536) clusters. Since a cluster consists of a fixed number (4,8,16,32, ...) of sectors of 512 contiguous bytes, the maximum size of FAT partition can be determined by multiplying the number of clusters by the size of a cluster. With 32Kb clusters, the maximum size of a FAT partition is therefore 2GB.
Furthermore, a file can only occupy an integral number of clusters, which means that if a file occupies several clusters, the last cluster will only be partially occupied and the unoccupied space will be unusable. As a result, the smaller the cluster size, the less wasted space. It is estimated that a file wastes, on average, half a cluster, which means that on a 2 GB partition, 16KB per file will be lost.
The File Allocation Table is a list of digital values that describes the allocation of the clusters of a partition. In other words, the state of each cluster of the partition in which it is located. In fact, each cell of the allocation table corresponds to a cluster.
Each cell contains a number that indicates if the cluster is used by a file and the location of the next cluster in the file. Finally, you end up with a FAT chain, a linked list of references pointing to the successive clusters up until the end of the file. Each FAT entry is 16- or 32-bits long (depending on whether it is FAT16 or FAT32).
The first two entries store information about the table itself, while the following entries reference the clusters. Certain entries may contain values indicating the state of the specific cluster.
For example, the value 0000 indicates that the cluster is not used, FFF7 marks a bad cluster (so that it will not be used) and values between FFF8 and FFFF specify that the cluster contains the end of a file. Each partition actually contains two copies of the table stored contiguously on the disk, so that it can be recovered if the first copy becomes corrupted.
Although VFAT was a clever system, it did not address the limitations of FAT16. As a result, a new file system (and not just better FAT management as was the case with VFAT) appeared with Windows 95 OSR2. This file system, called FAT32 uses 32-bit values for the FAT entries. In fact, only 28 bits are used, as 4 bits are reserved for future use.
With the appearance of the FAT32 file system, the maximum number of clusters per partition went increased from 65535 to 268,435,455 (228-1). FAT32 thus allows much bigger partitions (up to 8 Terabytes). Although the maximum theoretical size of a FAT32 partition is 8 TB, Microsoft has voluntarily limited it to 32 GB on Windows 9x systems to promote NTFS.
Since a FAT32 partition can contain many more clusters than a FAT16 partition, it is possible to reduce significantly the size of the clusters and thereby also limit wasted disk space. For example, with a 2GB partition, it is possible to use 4KB clusters with the FAT32 system (instead of 32KB clusters with FAT16), which reduces the wasted space by a factor of 8.
As the number of clusters is limited, the maximum size of a partition depends on the size of each cluster. Let's take a look at the maximum partition size according to the cluster size and file system used:
|Cluster size||FAT16 file system||FAT32 file system
|512 bytes||32 MB||64 MB|
|1 KB||64 MB||128 MB|
|2 KB||128 MB||256 MB|
|4 KB||256 MB||8 GB
|8 KB||512 MB||16 GB
|16 KB||1 GB||32 GB
|32 KB||2 GB||2 GB
When you format a hard disk, you might need to decide carefully which type of file system you are going to use and select the one that provides an amount of available space that is as close as possible to the desired size.