CSE 120 Homework #4
Fall 2007
Out: 11/30
In: 12/6
One way to represent the locations of files on a disk is a file allocation table, or FAT. A FAT is a table of disk block addresses. It is used as follows:
- If the first block of a file is disk block b, then the next block is at FAT[b].
- If there is no block following b, then FAT[b] is 0.
- The free blocks are represented as a file starting at block 0. That is, FAT[0] is the first free block, FAT[FAT[0]] is the second free block, and so on.
For example, consider the following FAT:
| index | entry
|
|---|
| 0 | 3
|
| 1 | 0
|
| 2 | 1
|
| 3 | 6
|
| 4 | 7
|
| 5 | 4
|
| 6 | 8
|
| 7 | 0
|
| ... | ...
|
If the first block of a file is block 2, then the second block if 1, and this is the last block. Similarly, if the first block of a file is 5, then the second block is 4, the third (and last block) is 7. The free blocks are 3, 6, 8, and so on.
- Assume that the size of the disk is 2d bytes, and a disk block contains 2b bytes. How many bytes are required for the FAT for this disk? (Hint: you may find it easier to compute the exponent f for a FAT that takes 2f bytes.)
- File systems that use FATs often cache the entire FAT in virtual memory. Why would this be the case?
- If the entire FAT is to be cached in memory, then one might wish to keep the FAT relatively small. Consider an 8Gbyte disk and a 1Mbyte FAT. What is the minimum disk block size?
- Give a disadvantage of storing the free block list in the manner described above.
- Suppose that the file system maintains the consistency of metadata using a reliability induced synchronous write. Give the sequence of operations needed to allocate a new block to the end of the file whose first block is x. You can assume that the FAT is cached in memory. Be sure to make clear when the FAT needs to be written to disk, and which writes need to be synchronous.