FAT
| Depends on | Filing System Implementation |
|---|
Once used extensively in implementing filing systems this scheme has disadvantages in scaling which are alleviated in schemes such as i-nodes. Nevertheless:
- Forms of FAT are used in legacy Windows systems and many contemporary embedded systems.
- It is quite a straightforward scheme to explain … and (hopefully) comprehend.
The File Allocation Table (FAT) itself is an array of cluster pointers, one pointer corresponding to one cluster on the disk. It may be stored on a disk (e.g. an interchangeable floppy) but needs identifying and loading before use.
A “cluster” is a set of one or more of the disk’s data blocks.
The FAT pointers are then used to define linked lists – one list per
file. A reserved value acts as a NULL end of file marker. In this
way files can occupy an arbitrary set of clusters on the disk and can
grow in length as long as there are some free clusters left,
somewhere.
Files are located through directory entries which simply need to maintain the pointer to the first cluster of that file; this is (of course) a fixed size field. In practice, the directory entry will contain various attributes; only the length (in clusters) is shown here.
Directories can contain an arbitrary number of entries and there can be multiple directories, as desired.
The figure also illustrates the way in which files may become fragmented, which can lead to a loss of performance. This is due to the way the disk clusters are allocated, not a consequence of the FAT indexing scheme.
Question: Why have a separate FAT instead of keeping the pointers in the data clusters on the disk? Surely that is a more usual way of implementing a linked list?
AnswerIn memory (RAM) there is no particular restriction on the size of software structures. However there are excellent reasons for some structures (e.g. pages) to have sizes which are 2N bytes; this makes the binary addressing feasible. A similar argument can be applied to disk blocks.
In some circumstances it is very convenient to be able to move pages to and from disk blocks. This is straightforward if one is an integer-multiple size of the other. It would be very inconvenient if the disk blocks were just-a-bit-shorter because a few bytes were being used for the pointers. Hence the additional structure (FAT) compensates for this.
No doubt other arguments about efficiency can also be concocted.
Click on the numbers to replace that directory entry with a file with that many clusters. (‘0’ implicitly deletes the file.) The FAT entries should behave in the way described above.
For simplicity here there is no file appending – i.e. increasing the length of a file already in place – so in each file clusters will always ‘point’ left to right. Nevertheless, you should be able to create some examples of file fragmentation.
Remember: the FAT is a map and each FAT entry has a corresponding cluster of data on the disk.
Click on the numbers to replace that directory entry with a file with that many clusters. (‘0’ implicitly deletes the file.) The FAT entries should behave in the way described above.
For simplicity here there is no file appending – i.e. increasing the length of a file already in place – so in each file clusters will always ‘point’ left to right. Nevertheless, you should be able to create some examples of file fragmentation.
Remember: the FAT is a map and each FAT entry has a corresponding cluster of data on the disk.
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 14.4.2, pages 573-575 |
|---|
