Differences between version 5 and predecessor to the previous major change of FileAllocationTable.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 5 | Last edited on Monday, August 18, 2003 4:17:46 pm | by AristotlePagaltzis | Revert |
| Older page: | version 2 | Last edited on Monday, August 18, 2003 12:07:18 am | by PerryLorier | Revert |
@@ -1,7 +1,11 @@
-A file allocation table
([FAT]) is a table that an OperatingSystem maintains
on a HardDisk that provides a map
of the
[clusters|
DiskCluster] (the basic units of logical storage on a hard disk) that
a file has been stored in. When you write a new file to a hard disk
, the file is stored in one or more clusters that are
not necessarily next to each other; they
may be rather
widely scattered over the disk. A typical cluster size is 2,048 bytes, 4,096 bytes, or 8,192 bytes. The operating system creates a FAT entry for the new file that records where each cluster is located and their sequential order. When you read a file, the operating system reassembles the file from clusters and places it as an entire file where you want to read it. For example, if you were to save this Wiki page to your hard disk, it may very well be stored on more than one cluster on your hard
disk.
+A FileAllocationTable
([FAT]) is a map maintained by the FileSystem
on a HardDisk to keep track
of which
[DiskCluster]s
a file has been stored in. If it spans several of them
, they need
not be sequential, but rather
may be widely scattered over the disk.
-Note that most modern OS's don't have a centralised
[FAT
] anymore, but use [Inode]s and bitmaps. an inode specifies where data for an individual file is
(by direct, indirect,
and double and triple indirect pointers), while
the bitmap is
of which blocks within a zone or group are in use. If you have a very sophisticated FileSystem then inodes may be created
on the fly, with others the maximum number
of inodes on a partition is fixed at format time
.
- df -i
.
-will show you how many inodes are free on a filesystem
. It is rare to run out of inodes unless you have a really weird partition (for instance a news spool)
.
+[MS-DOS
] (and the versions
of MicrosoftWindows that sat
on top
of DOS) used FAT FileSystems
... firstly [FAT12], then [FAT16], then [FAT32]
.
-Some much newer filesystems (such as
[ReiserFS
]) don't use
a [FAT] or inodes/bitmaps for their
allocation, but use
a tree structure
.
+The
[FAT
] is organized as an array as large as there are clusters on the disk, each entry in the array storing the cluster number of the next piece of a file. This way, the FileSystem driver can "hop" from cluster to cluster, collecting the pieces of the file.
+
+While simple in concept,
a [FAT] is unreliable. A single bit error may lead to inconsistencies with several files - they may become crosslinked, with one of the chains pointing to cluster in the other chain. Since
allocation of disk space happens in the same step as assigning it to a file, a crash can easily lead to unduly or incompletely allocated space. A crash during rewriting or deleting a file can lead to the a part of the existing chain persisting, without any file pointing to it, thus leaving it inaccessible.
+
+[Microsoft] tried to mitigate these problems by storing a backup version of the table on the partition
, but only managed to exacerbate the problem by requiring
a fragile procedure to succeed multiple times. In addition, there is no indication of which copy is authoritative, when they differ.
+
+Better FileSystems manage disk space using a separate bitmap for allocation of clusters and [Inode]s for assigning them. The latest in advances are attempts replace all of these with [BTree]s
.
