Homework 8

1. Efficiency of File Allocation Methods
   Consider a file consisting of 100 physical blocks. For each of the three file allocation methods (contiguous, linked, and indexed), how many disk I/O operations are needed in the following situations:
   (a) a block is added at the beginning
   (b) a block is added in the middle
   (c) a block is added at the end
   (d) a block is deleted from the beginning
   (e) a block is deleted from the middle
   (f) a block is deleted from the end
   
   For each answer, give the total number of operations and explain actions taken needed for each disk I/O operation (disk read or disk write). In some cases, you may need to qualify your answer with worst or best case scenarios.
   Example: for contiguous (a), Best case, ONE write operation is needed to add a block at the beginning. Worst case, 201 I/O operations - 100 reads and 100 writes to copy the file to new location plus one write for the new block.
   Assume that the disk directory, free space data structures, and the new block are all already in memory.
   Generalize and summarize your results in a table (rows are (a)-(f) and columns are the three file organization methods). Give the general complexity for each case.
   
   
2. Efficiency of the Address Mapping Algorithm
   Consider a sequential file with N blocks. The logical block address of a block is its location relative to the first block in the file, e.g. the 10th block has logical address 9, assuming the logical address of the first block is 0. The physical block address is the address of the block on disk. You are to figure out how the mapping from logical block address to physical block address is accomplished in each of the three systems: contiguous, linked, and indexed.
   More specifically,
   (a) Write a formula or pseudo code that computes the physical block address P from the logical block address L. Let S be the address of the first physical block on disk for the file. For indexed, assume two levels of indirection and that each index block has room for 100 block addresses.
   (b) Give the time complexity and space of each of your mapping algorithms. Space complexity is measured in the number of buffers needed, where each buffer hold one physical block.
   
   
3. File System Performance
   The EUNUCHS Operating System (which was obviously cloned from the UNIX Operating System) supports a file system with three types of pointers: direct, indirect, and double-indirect. If a file is of size N blocks, what is the effective access time to access a block in that file?? (This means on average, how long will it take?)
   Assumptions:
   
   • Assume the inode is already in memory, that each memory access takes m seconds and that each disk access takes d seconds. The disk access time d is the total time to transfer a complete physical block from disk to memory or memory to disk.
   • Assume that the disk blocksize is 1024 bytes and wordsize (to specify a block address) is 4 bytes. Thus 256 addresses can fit in one disk block.
   • Assume that the probability of referencing a given block in the file is 1/N, i.e., all references are equally likely.
   
   Effective access time is defined as the SUM over all blocks of the product ( probability that block is referenced * access time for that block).
   
   
4. (Extra credit) First Fit vs. Best Fit vs. Worst Fit
   (a) For contiguous file allocation, which of the three allocation algorithms is known to perform best, if any?
   (b) What do you think are reasonable criteria for "best"?
   (c) What famous computer scientist is known for doing the experiments that established the results for part (a)? Cite a paper or book that reports the results.