File Allocation TableFile Allocation Table (FAT) is a file system that was developed for MS-DOS and used in consumer versions of Microsoft Windows up to and including Windows ME. The FAT file system is considered relatively uncomplicated, and because of that, it is a popular format for floppy disks; moreover, it is supported by virtually all existing operating systems for personal computers, and because of that it is often used to share data between several operating systems booting on the same computer (a multiboot environment). It is also used on solid-state memory sticks and other similar devices.
HistoryThe FAT filesystem made its debut in August 1980 with the first version of QDOS, the ancestor of Microsoft's PC-DOS and MS-DOS. This initial version of FAT is now referred to as FAT12. As a filesystem for floppy disks it had a number of limitations including a lack of support for directories. It also used cluster addresses that were only 12-bits long, which limited the maximum space of the filesystem to approximately 2MB of space (however this is far more than a typical 360KB floppy could hold at the time). In 1983 Microsoft introduced a new version of the FAT filesystem with the release of MS-DOS version 2. This new version, now known as FAT16, included support for hard drives and sub-directories. Cluster addresses were increased to 16-bit, allowing for a greater number of clusters (approximately 65,500) and consequently much greater filesystem sizes. Even with 512-byte clusters, this could give up to 32MB of space - enough for the 10MB or 20MB XT hard drives that were typical at the time. As hard drives larger than 32MB were released, large cluster sizes were used. The use of 8,192-byte clusters allowed for filesystem sizes up to 512MB. However this increased the problem of internal fragmentation where small files could result in a great deal of wasted space, for example a 1-byte file stored in a 8,192-byte cluster results in 8,191-bytes of wasted space. One of the user experience goals for the designers of Windows 95 was the use of long file names in the new operating system. These were implemented using a work-around in the way directory entries are laid out (see below). The new version of the file system became known as VFAT (Virtual FAT), after its Windows 95 VxD device driver. VFAT is supported by Windows 95 and above and Windows NT 4.0 and above. By 1997, the cluster growth possibility was exhausted. The largest cluster size in Windows FAT was 32KB, giving a maximum volume size 2 gigabytes. Microsoft decided to implement a newer generation of FAT, known as FAT32, with 32-bit cluster numbers, of which 28 bits are currently used. In theory, this should support a total of approximately 268,435,438 clusters, allowing for drive sizes in the multi-terabyte range. However, due to limitations in Microsoft's ScanDisk utility, the FAT is not allowed to grow beyond 4,177,920 clusters, placing the volume limit at 124.55 gigabytes [1] (http://support.microsoft.com/default.aspx?scid=KB;EN-US;Q184006&). First supported in Windows 95 OSR 2 and Windows 2000, and incorporating several changes to other filesystem structures, this was a major improvement over previous versions, but is no longer sufficient to cope with today's largest drives. The alternative IBM PC operating systems, for example OS/2, Linux, FreeBSD, and BeOS, have all supported FAT, and most have gained support for VFAT and FAT32 shortly after the appropriate Windows versions were released. Early Linux distributions also supported a format known as UMSDOS, which was nothing more than FAT with the UNIX file properties (e.g. long file name and access permissions) stored in a separate file called --linux-.---. UMSDOS was mostly dropped after VFAT was released, although it still remains in the Linux kernel sources. The Mac OS X operating system also supports the FAT filesystems on volumes other than the boot disk. Since Microsoft has announced the discontinuation of the DOS line of succession with Windows ME, it remains unlikely that any new versions of FAT will appear. For most purposes, the NTFS file system that was developed for the Windows NT line is superior to FAT from the points of view of efficiency, performance and reliability. However, FAT is likely to stay for a long time as it is an ideal file system for small drives, like the floppies. It is also used on other removable storage for non-computer devices, such as flash memory cards for digital cameras, USB flash drives, and the like. Design and implementationA FAT file system is composed of four different sections.
File Allocation TableA partition is divided up into identically sized clusters, small blocks of contiguous space. Cluster sizes vary depending on the type of FAT file system being used and the size of the partition, typically cluster sizes lie somewhere between 2KB and 32KB. Each file may occupy one or more of these clusters depending on its size, a file is represented by a chain of these clusters (referred to as a singly linked list). However these chains are not necessarily stored adjacently on the disk's surface but are often instead fragmented throughout the Data Region. The File Allocation Table (FAT) is a list of entries that map to each cluster on the partition. Each entry records one of five things:
Each version of the FAT file system uses a different size for FAT entries. The size is indicated by the name, for example the FAT16 file system uses 16 bits for each entry while the FAT32 file system uses 32 bits. This difference means that the File Allocation Table of a FAT32 system can map a greater number of clusters than FAT16, allowing for larger partition sizes with FAT32. This also allows for more efficient use of space than FAT16, because on the same hard drive a FAT32 table can address smaller clusters which means less wasted space. Directory TableA Directory Table is a special type of file that represents a directory. Each file or directory stored within it is represented by a 32 byte entry in the table. Each entry records the name, extension, attributes (archive, directory, hidden, read-only, system and volume), the date and time of creation, the address of the first cluster of the file/directory's data and finally the size of the file/directory. Aside from the Root Directory Table in FAT12 and FAT16 file systems which occupies the special Root Directory Region location, all Directory Tables are stored in the Data Region. Long File Names (LFN) are stored on a FAT32 file system using a trick - adding phoney entries into the Directory Tables. The entries are marked with a Volume Label attribute which is impossible for a regular file and because of that they're ignored by most old MS-DOS programs. Each phoney entry can contain up to 13 UCS-2 characters (26 bytes), gaining about 15 bytes in addition to the old 8 + 3 by using fields in the record which contained file size or time stamps (but for security versus disk checking tools the starting cluster field is left unused with a 0 value). See 8.3 for additional explanations. FAT licensingOn December 3 2003, Microsoft announced it would be offering licenses for use of its FAT specification and "associated intellectual property". [2] (http://www.microsoft.com/mscorp/ip/tech/fat.asp) at the cost of a US $0.25 royalty per unit sold, with a $250,000 maximum royalty per license agreement. In particular, Microsoft targetted the producers of consumer devices (such as digital cameras and PDAs) which make use of removable solid state media that can also be inserted into home computers (such as Compact Flash cards and USB pen drives). To this end, Microsoft cited four patents on the FAT filesystem as the basis of its intellectual property claims. Several technical commentators hold[3] (http://yro.slashdot.org/article.pl?sid=03/12/04/1318212&tid=109&tid=155) that the FAT filesystem specification itself could not be patented. As Microsoft first derived it from CP/M in 1976, no patent could still apply to the original implementation. Analysis of the four patents show that all pertain to the "long filenames" backwards compatibility feature found in Windows 95.
Many technical commentators have concluded that these patents only cover FAT implementations that include support for long filenames, and that removable solid state media and consumer devices only using short names would be unaffected. Additionally, in the document "Microsoft Extensible Firmware Initiative FAT 32 File System Specification, FAT: General Overview of On-Disk Format" published by Microsoft (version 1.03, December 6, 2000), Microsoft specifically grants a number of rights, which many readers have interpreted as permitting operating system vendors to implement FAT. Re-opened investigationAs there has been widespread call for these patents to be re-examined, the Public Patent Foundation submitted evidence to the US Patent and Trade Office (USPTO) disputing the validity of these patents, including prior art references from Xerox and IBM. The USPTO acknowledged that the evidence raised "substantial new question[s] of patentability", and opened an investigation into the validity of Microsoft's FAT patents. On September 30 2004, the USPTO rejected all claims of patent 5,579,517, based primarily on evidence provided by the Public Patent Foundation. Dan Ravicher, the foundation's executive director, said "The Patent Office has simply confirmed what we already knew for some time now, Microsoft's FAT patent is bogus." Microsoft still has the opportunity to respond to the Patent Office's rejection. Typically, third party requests for reexamination, like the one filed by PUBPAT, are successful in having the subject patent either narrowed or completely revoked roughly 70% of the time. See alsoExternal links
de:FAT es:FAT fa:جدول تخصیص فایل fr:File Allocation Table he:FAT32 ja:File Allocation Table pl:FAT tr:Dosya Yerleşim Tablosu Categories: Computer file systems |
|
This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information. |