CS 450 Update Log

Your solutions to this assignment must be typed up, printed, and submitted by July 22nd at the beginning of lecture. Internet students should submit their work via Blackboard by the same date.

1. Suppose that we would like to use a File Allocation Table (FAT) based filesystem to support a 4TB (4 x 10¹² byte) drive.

   • If files are to be allocated in 4KB (4096 byte) blocks (i.e., 4KB is the minimum granularity of allocation, and correspond to a single FAT entry), how large, at a minimum, must the FAT structure itself be? Justify your answer. (5 points)
   • If files are allocated in 1MB (2²⁰ byte) blocks, how large must the FAT structure be? (5 points)

2. Consider an i-node based filesystem such as UFS with the following properties:

   • Blocks are 8KB large
   • Block pointers are 64-bits in size

   • Each I-node consists of the following:

     • 4 single indirect block pointers
     • 2 double indirect block pointers
     • 1 triple indirect block pointer

   What is the maximum file size supported by the file system described above? Show your work. (10 points)

3. Assume that, in a RAID 3 system with byte level parity and a dedicated parity disk, that we have lost one of the 4 RAID-ed disk drives. Compute and fill in the column below with byte values recovered using the parity drive: (5 points)

   

4. Suppose that you’ve been asked by a database administrator to help recommend a RAID implementation to support a high throughput file system. Single drive failure must be tolerated, at a minimum. Due to limited funding, you are restricted to purchasing a maximum of 20 1TB drives, and it’s crucial that the final setup allow for at least 75% of the full capacity.

   Can you recommend a setup consisting of nested RAID levels, or a hybrid approach? Justify your answer. (5 points)

5. Consider a filesystem that supports the strategies of contiguous, linked, and index allocation. What criteria should be used in deciding which strategy is best used for a particular file? Use examples to justify your answer. (5 points)

6. Give an example of how Isolation (of the ACID properties) might be important in the context of a file system. (5 points)

7. Consider a filesystem with journaling support. Upon reboot following a crash, the following entries are discovered in the journal:

   <transaction>
     <del /home/lee/foo>
     <free 319>
     <free 12019>
   </transaction>
   <transaction>
     <del /home/lee/bar>
     <free 40
   

   Describe what must have happened before the filesystem crashed. What actions should be taken to ensure the filesystem is consistent? Is it possible to carry out any of logged transactions? (5 points)

8. Consider that the throughput of a file system implementation is closely tied to how well it allows for contiguous access to the data blocks of a file. While it is theoretically possible for both FAT and UFS filesystems to contain large amounts of fragmentation, the latter is typically seen as more “resistant” to the problem.

   What about the UFS filesystem makes it inherently easier to allocate file blocks in such a way as to lessen file fragmentation? What makes it more difficult when using FAT? (5 points)

9. Consider the following set of block address requests, arriving in the order specified, with a constant inter-arrival time of 5ms: 20, 11, 40, 19, 5, 6

   There is a single head, and there are 50 cylinders, each of which contains a single sector/block. Head movement (seek) time is linear in the number of sectors n to traverse, and can be described with the formula 5 + n; e.g., seeking across 4 cylinders requires 5+4=9ms. Access times are ignored for this problem.

   Given a current head position of 14, and that the previous block accessed was 8, compute the total seek time for each of the following head scheduling algorithms over the block requests given above.

   • SSTF (4 points)
   • LOOK (4 points)
   • C-LOOK (4 points)