Idea: we begin with Implicit linked list allocation for multi-block files, and solve its main limitation, which is to make block lookups faster. What’s the fastest possible lookup place? Directly in memory.
Constructing the table
This is essentially a beefed up version of the block bitmap. Each table entry acts as a linked list node. Each node maps a block number to its next block location pointer. Like so:
| Block number | Next |
|---|---|
| 0 | BITMAP/SPECIAL |
| 1 | END |
| 2 | 6 |
| 3 | 9 |
| 4 | END |
| 5 | EMPTY |
| 6 | 3 |
Next, FAT is stored on the disk initially and loaded into memory when the computer starts. This is what gives us that lookup speedup that we desired.
- We need to remember to write the FAT back to disk whenever an entry is updated e.g. we extend a file to another block.
- The bitmap is not needed anymore because this table captures that information, and more.
Finding a file’s block
We don’t need to traverse physical blocks anymore to find the next pointer, because everything is contained within the FAT (which is in memory)! We just jump around the table until we get to the block number that we want.
Furthermore, we only need to perform one block read to the root Directory to find the file’s initial block, which was contiguous allocation‘s only redeeming trait.
While it still takes time to find the th block of the file, all of this is being performed in memory, which takes considerably less time.
Downsides
- FAT is really big and is in memory, so memory consumption goes up
- FAT replaces the bitmap which only used 1 bit per block number, FAT uses ~16 bits
- The bigger the disk, the bigger the FAT because we need one entry for each possible block, and each entry needs more bits to store the higher block numbers
- It’s highly likely the FAT takes up more than one block.