CS245A PROBLEM SET #1
Due by 5pm, Tuesday, January 20, 1998.
4 problems, equal credit. 100 pts.

Problem 1: Seeking

Recall that the MEGATRON 747 disk has the following characteristics: Find the average seek time (i.e., the average time to move the heads between two randomly chosen blocks, not cylinders) on the assumption that the number of blocks per cylinder is a linear function of the cylinder radius. That is, the number of blocks on each cylinder is chosen so that the average number of blocks per track is 32 (256 sectors divided by 8 sectors per block), and yet the actual number of blocks on any track is proportional to the radius of that track. Do not worry about fractional blocks on a track. Show your reasoning.

Problem 2: Sorting and Buffering

Suppose we want to sort 100-byte records using 2PMMS as in class and the notes. We shall use a MEGATRON 747 disk, as in Problem 1 and the notes. The only difference between our situation and the notes is that the size of a block is variable. We shall assume that blocks consist of k sectors for some integer k, and that 5k records fit in one block. As a function of k, what is the largest number of records that can be sorted by 2PMMS?

Problem 3: Elevator Algorithm

Consider the elevator algorithm described in class and in Problem 1. Assuming a MEGATRON 747 disk, in each of the following 3 cases:
i)
There is 1 request per 100 cylinders.
ii)
There is 1 request per cylinder.
iii)
There are 2 requests per cylinder.
calculate:
a)
The average time it takes the disk to service a request, and
b)
The average time it takes a waiting request to be serviced (assuming that the head starts at one end of the disk, and no additional requests arrive).
Note that in case (iii) whichever request on a cylinder first reaches the head can be serviced first.

Problem 4: RAID Disks

Suppose we have 4 data disks and 3 redundant disks. Assume the redundant disks have their content determined using the Hamming matrix described in the notes. Recall that the Hamming matrix is:
1 1 1 0 1 0 0
1 1 0 1 0 1 0
1 0 1 1 0 0 1
In principle this system can handle up to 2 simultaneous failures. In some special cases, however, data can be recovered even if 3 disks fail at the same time.

First, show that if data disks 1, 2, and 3 fail we can still recover their contents using the remaining four disks (4-7). It is sufficient to show how 1 bit of disk 1, 2, and 3 can be computed from the corresponding bits of disks 4-7.

Then, prove that a RAID level 6 system based on the above Hamming code cannot handle all cases of three simultaneous failures by giving a counterexample. It is sufficient to find three disks (which shall call the failed disks) for which there are are two code words that agree on all the surviving disks but disagree on at least one of the three failed disks.

Note: the code words in question are not the three rows of the Hamming matrix. Rather, they are the 16 bit-vectors of length 7 that satisfy the constraints of the three rows. That is, the bit in position 5 (corresponding to the first redundant disk) must be the modulo-2 sum of the bits in positions 1, 2, and 3, and so on for the constraints of the second and third rows.

Last modified: Fri Jan 9 17:54:14 PST