D64 Assignment #1 Solutions

For many of these problems there were different assumptions that could be made.  Those who clearly stated their assumptions and showed their work did better than those who did neither.

1. Grunt work

  1. (102400 bytes/track) / (512 bytes/sector) = 200 sectors/track
    surface capacity = 5000 track * 102400 bytes/track = 512x106 bytes = 488.3 Mb.

    disk capacity = surface capacity * 14 = 7.168x109 = 6.84Gb

  2. # cylinders = 5000
  3. Max rotational latency = 1/(10400 rotations/min) = 1/173.3 seconds/rotation = 5.77ms
  4. 1 track can be read in 5.77ms (ignoring 1 gap), so the throughput is 102400 bytes / 5.77ms = 16.93 Mb/s.

    If a cylinder can be read at the same time, the throughput is 14 times higher which is 236.98 Mb/s.

  5. The worst case seek time = 0.8ms (to start the head assembly) + (4999/600) * 1ms + 0.8ms (to stop the head assembly = 9.9ms.

    The average case seek time = 0.8ms + (5999/600/3) * 1ms + 0.8ms = 4.37ms.

2. Grunt work, cont.

  1. First, calculate how long it takes to read a block. A block is 8 sectors and 7 gaps so it's (8/200)*0.93 + (7/200)*0.07 = 0.03965 of the track. This will take 0.03965*5.77ms = .23ms to read.

    Worst case = 9.9ms (seek) + 5.77ms (rotational) + 0.23ms = 15.9ms

    Best case = 0.23ms

    Average = 4.37ms (seek) + 5.77ms/2 (rotational) + 0.23ms = 7.49ms

  2. Four contiguous blocks are 32 sectors and 31 gaps which take ((32/200)*0.93+(31/200)*0.07)*5.77ms = 0.92ms to read.

    Worst case = 9.9ms + 5.77ms + 0.92ms = 16.59ms

    Best case = 0.92ms

    Average case = 4.37ms + 5.77ms/2 + 0.92ms = 8.18ms

  3. Writing require the same time as a read plus one full rotation for verification.

    Worst case = 15.9ms + 5.77ms = 21.7ms

    Best case = 0.23ms + 5.77ms = 6.0ms

    Average case = 7.49ms + 5.77ms = 13.3ms

  4. Modification requires 1 read, 1 write, and 1 verify. The last two steps only require 2 full rotations. I'm not assuming that the disk arm is moved during the modify, although it would be reasonable to do so.

    Worst case = 21.7ms + 5.77ms = 27.47ms

    Best case = 6.0ms + 5.77ms = 11.77ms

    Average case = 13.3ms + 5.77ms = 19.07ms

3. RAID

  1. Disk#

    Sector 0 Value

    5

    0010100101

    6

    0001101011

    7

    1111000101

     
  2. First we repair disk 3 using disks 1,2, and 5.

    Next, we repair disk 7 using disks 1,3, and 4.

4. Stable storage

The proposed change would fix the problem of XR silently decaying. Even if the overhead of 1 bit per sector to know which copy to read first is too much, we can just alternatively read left and right copies and figure that the likelihood of always reading the same copy of a given sector is quite low. The proposed change does not introduce any correctness problems although it might hurt performance. If the two copies of each sector are not stored near each other on disk (which is a good idea for fault tolerance) then reading a single block may require moving the disk arm back and forth rather than reading a bunch of contiguous sectors which is faster. Note that alternating the order of writing sectors would cause problems. If the system crashed inbetween writing the two copies of the sector so that both were valid but only one was the new copy, we'd have no idea which was the new copy.