File Allocation Table
From Wikipedia, the free encyclopedia
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (March 2009)
FAT
Developer Microsoft
Full Name File Allocation Table
(12-bit version) (16-bit version) (32-bit version)
Introduced before 1980 (Microsoft Disk BASIC) November 1987, (Compaq DOS 3.31) August 1996 (Windows 95 OSR2)
Partition identifier 0x01 (MBR) 0x04, 0x06, 0x0E (MBR) 0x0B, 0x0C (MBR)
EBD0A0A2-B9E5-4433
-87C0-68B6B72699C7 (GPT)
Structures
Directory contents Table
File allocation Linked List
Bad blocks Cluster tagging
Limits
Max file size 4 GB minus 1 byte (or block size if smaller)
Max cluster count 4,077 (212-19) 65,517 (216-19) 268,435,437 (228-19)
Max filename size 8.3 filename, or 255 UTF-16 characters when using LFN
Max volume size 32 MB 2 GB
4 GB with 64KB clusters (not widely supported) 2 TB
8 TB (with 32KB clusters)
16 TB (with 64KB clusters, not widely supported)
Features
Dates recorded Creation, modified, access (accuracy to day only)
(Creation time and access date are only available when ACCDATE support is enabled)
Date range January 1, 1980 - December 31, 2107
Date resolution 2 s
Forks Not natively
Attributes Read-only, hidden, system, volume label, subdirectory, archive, (NetWare only) executable
Permissions Global/directory/file-based only with DR-DOS and Multiuser DOS, world/group/owner file permissions only with multiuser security No
Transparent compression Per-volume, Stacker, DoubleSpace, DriveSpace No
Transparent encryption Per-volume only with DR-DOS No
File Allocation Table or FAT is a computer file system architecture now widely used on many computer systems and most memory cards, such as those used with digital cameras. FAT file systems are commonly found on floppy disks, flash memory cards, digital cameras, and many other portable devices because of its relative simplicity. Performance of FAT compares poorly to most other file systems as it uses overly simplistic data structures, making file operations time-consuming, and makes poor use of disk space in situations where many small files are present.
For floppy disks, the FAT has been standardized as ECMA-107[1] and ISO/IEC 9293.[2][3] Those standards include only FAT12 and FAT16 without long filename support; long filenames with FAT is partially patented.
The FAT file system is relatively straightforward technically and is supported by virtually all existing operating systems for personal computers. This makes it a useful format for solid-state memory cards and a convenient way to share data between operating systems.
History
The FAT file system was developed by Bill Gates and Marc McDonald during 1976–1977.[4][5] It was the primary file system for various operating systems including DR-DOS, FreeDOS, MS-DOS, OS/2 (v1.1) and Microsoft Windows (up until Windows Me).
The FAT file system was created for managing disks in Microsoft Standalone Disk BASIC. In August 1980 Tim Paterson incorporated FAT into his 86-DOS operating system for the S-100 8086 CPU boards;[6] the file system was the main difference between 86-DOS and its predecessor, CP/M.
The name originates from the usage of a table which centralizes the information about which areas belong to files, are free or possibly unusable, and where each file is stored on the disk. To limit the size of the table, disk space is allocated to files in contiguous groups of hardware sectors called clusters. As disk drives have evolved, the maximum number of clusters has dramatically increased, and so the number of bits used to identify each cluster has grown. The successive major versions of the FAT format are named after the number of table element bits: 12, 16, and 32. The FAT standard has also been expanded in other ways while preserving backward compatibility with existing software.
FAT12
The initial version of FAT is now referred to as FAT12. Designed as a file system for floppy disks, it limited cluster addresses to 12-bit values, which not only limited the cluster count to 4078,[7] but made FAT manipulation tricky with the PC's 8-bit and 16-bit registers. (Under Linux, FAT12 is limited to 4084 clusters.[8]) The disk's size is stored as a 16-bit count of sectors, which limited the size to 32 MB.[9] FAT12 was used by several manufacturers with different physical formats, but a typical floppy disk at the time was 5.25-inch, single-sided, 40 tracks, with 8 sectors per track, resulting in a capacity of 160 KB for both the system areas and files. The FAT12 limitations exceeded this capacity by a factor of ten or more.
By convention, all the control structures were organized to fit inside the first track, thus avoiding head movement during read and write operations, although this varied depending on the manufacturer and physical format of the disk. At the time FAT12 was introduced, DOS did not support hierarchical directories, and the maximum number of files was typically limited to a few dozen. Hierarchical directories were introduced in MS-DOS version 2.0.[10]
A limitation which was not addressed until much later was that any bad sector in the control structures area, track 0, could prevent the disk from being usable. The DOS formatting tool rejected such disks completely. Bad sectors were allowed only in the file area, where they made the entire holding cluster unusable as well. FAT12 remains in use on all common floppy disks, including 1.44MB ones.
Initial FAT16
In 1984, IBM released the PC AT, which featured a 20 MB hard disk. Microsoft introduced MS-DOS 3.0 in parallel. (The earlier PC XT was the first PC with a hard drive from IBM, and MS-DOS 2.0 supported that hard drive with FAT12.) Cluster addresses were increased to 16-bit, allowing for up to 65,517 clusters per volume, and consequently much greater file system sizes, at least in theory. However, the maximum possible number of sectors and the maximum (partition, rather than disk) size of 32 MB did not change. Therefore, although technically already "FAT16", this format was not what today is commonly understood as FAT16. With the initial implementation of FAT16 not actually providing for larger partition sizes than FAT12, the early benefit of FAT16 was to enable the use of smaller clusters, making disk usage more efficient, particularly for files several hundred bytes in size, which were far more common at the time. Also, the introduction of FAT16 actually did bring an increase in the maximum partition size under MS-DOS, since the implementation of FAT12 for hard disks in MS-DOS 2.0 was limited to 15 MB. (That is, the initial FAT16 did not support larger drives than FAT12, but MS-DOS 3.0 using FAT16 did support larger drives than MS-DOS 2.0 using FAT12, by a factor of two.)[11]
A 20 MB hard disk formatted under MS-DOS 3.0 was not accessible by the older MS-DOS 2.0. (This was because MS-DOS 2.0 did not support version 3.0's FAT-16 and because it did not support hard disk partitions over 15 MB in size.) Of course, MS-DOS 3.0 could still access MS-DOS 2.0 style 8 KB-cluster partitions.
MS-DOS 3.0 also introduced support for high-density 1.2 MB 5.25" diskettes, which notably had 15 sectors per track, hence more space for the FATs. This probably prompted a dubious optimization of the cluster size, which went down from 2 sectors to just 1. The net effect was that high density diskettes were significantly slower than older double density ones.[dubious ]
Extended partition and logical drives
Apart from improving the structure of the FAT file system itself, a parallel development allowing an increase in the maximum possible FAT size was the introduction of multiple FAT partitions. Originally DOS was only prepared to handle one FAT partition, although it came with documentation and programming tools for the creation of installable device drivers to handle multiple partitions, and third-party suppliers quickly provided the missing software. Aside from that, partitions were used for sharing the disk between operating systems, typically DOS and Xenix at the time. Extra DOS partitions could not be used as boot partitions, because the installable device drivers were loaded (in config.sys) only after the first part of the DOS boot process. Later, third party tools became available that replaced the DOS master boot record (MBR) and directly loaded non-DOS drivers before DOS: such systems generally came with careful warnings that without the 3rd party software, the disk would not be compatible with DOS. Simply allowing several identical-looking DOS partitions could lead to naming problems: behaviour if more than one partition was marked active was undocumented (although well defined), as was the behaviour if there was more than one hard disk in the computer (which was machine dependent), or if the system was booted from a diskette.
To allow the use of more FAT partitions in a compatible way, a new partition type was introduced (in MS-DOS 3.2, January 1986), the extended partition, which is a container for additional partitions called logical drives. Originally only one logical drive was possible, permitting hard disks up to 64 MB. In MS-DOS 3.3 (August 1987) this limit was increased to 24 drives, equal to the maximum number of available letters for drive names (A and B being reserved for the first two floppy drives, at least one of which many, if not most, systems of the era were equipped with; where only one was installed, B always simulated a second drive using A). Logical drives are described by on-disk structures which closely resemble the Master Boot Record (MBR) of the disk (which describes the primary partitions), likely to simplify the implementation. Though some believe these partitions were nested in a way analogous to Russian matryoshka dolls, that isn't the case. They are stored as a row of separate blocks within a single box; these blocks are often referred to as being chained together, by the links in their extended boot record (EBR) sectors. Only one extended partition is allowed. Under MS-DOS, logical drives are not bootable, and the extended partition can only be created after the primary FAT partition, which removes all ambiguity but also eliminates the possibility of booting several DOS versions from the same hard disk. (A few systems other than MS-DOS can boot logical drives, and partitions can be created in any order using third party formatting tools.)