Comp111: Operating Systems
Classroom Exercise 17 Answers
Disk I/O
Fall 2017

  1. Suppose that you have an Ext2 disk (as described in lecture) organized as 8192-byte blocks. What kinds of blocks are read from and/or written to disk when one creates a text file containing just "hello\n"? Hint: you must update the inode table and containing directory, too! It's all just disk!
    Answer: At least, one has to:

    Of course, this is a worst case estimate since many of these blocks may already be in memory and unnecessary to read from disk. So, it is a really easy question as to how much is written, but a very hard question as to how much is read!

    In practice, in a mounted filesystem, many of these reads are from the page cache and not from disk, because the blocks are accessed frequently enough that they're never flushed. So the answer above is likely more than ever happens in a realistic running system!

  2. In the previous question, suppose that the power fails without a disk page cache flush. How many states can the file be in as a result of the power-fail, assuming that nothing else is in the dirty page cache?
    Answer: Since the update (flush) process is completely asynchronous from the driver actions of requesting raw writes, more or less any subset of the writes may or may not have occurred as a result of the power failure. These have different names: Etc.
  3. (Advanced) Would writing to the filesystem be as efficient without the page cache in place? Why or why not?
    Answer: The page cache is absolutely essential due to the following principles of locality, enforced by the filesystem driver: Thus, the page cache accomplishes many new block and inode allocations without a disk read, because the appropriate block is already in cache.
  4. Suppose we have the multiple indirection scheme described in class, so that an inode contains the following fields:
     
    int first_thirteen[13]; 
    int *single_indirection; 
    int **double_indirection; 
    
    Please interpret each of these ints as a physical offset of a block on disk.
    1. Give an expression for the offset of the 5th block in the file (from block 0).
      Answer:: The block number is first_thirteen[5].
    2. Give an expression for the offset of the 15th block in the file (from block 0).
      Answer: Since the first thirteen blocks are in first_thirteen the 15th block is block 15-13=2 of the single indirection pointer. Thus an expression for it is single_indirection[2].

      (This might seem counter-intuitive until you consider the following: Counting from 0, blocks 0-12 are in first_thirteen and block 13 (from 0) is not. It is single_indirection[0]. )

    3. Assuming that the blocks are 8192 bytes long, ints are four bytes long, and an indirection block contains 4096 ints, give an expression for the offset of the 5000th block in the file (from block 0). The length of ints is 2 bytes. I messed this up in the original handout.
      Answer: I tend to do this by relative thinking.
      • First one subtracts 13 to get into the indirection block, leaving 5000-13 = 4987. This doesn't fit into the first indirection block.
      • Then, since there are 2048 ints in that block, we move into the double indirection block, at offset 4987 - 2048 = 2939.
      • In the double indirection block, we subtract one more block to get to block offset 2939 - 2048 = 891.
      Thus the offset of the block is logically located at double_indirection[1][891]. (presuming that we fetch double_indirection and double_indirection[1] into the page cache before computing double_indirection[1][891]).
    4. I claim that accessing the 5000th block is O(1). Why?
      Answer: Fetching block 5000 is a matter of reading four blocks into the page cache: the block containing the inode, the double indirection pointer block, and the double indirection block itself, followed by reading the actual targeted block. Thus it takes (up to) four disk fetches, depending upon what has already been cached. Four is a perfectly good constant, so that the disk access is constant time (O(1)).
  5. (Advanced) To save power, some current disk drives use a built-in flash drive as a journal instead of a stripe on disk. The hard disk is spun up and the journal flushed only when the journal is nearly full. Otherwise the hard disk stays spun down. This saves power when writing files but not when reading files. Why?
    Answer:

    As long as one is writing only, or reading only what one has already written, the journal suffices and the disk can stay powered off. But if you try to read something that is not in the journal, then the disk has to be spun up and you don't save power while doing the read.