 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:
 Four platters, eight surfaces
 Diameter = 3.5 inches; only outer 1 inch is occupied by tracks
 8192 cylinders
 512 bytes/sector
 Average 256 sectors/track
 Seek time = 1 ms plus another 1 ms per 500 cylinders moved.
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 100byte 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
(47). It is sufficient to show how 1 bit of disk 1, 2, and 3
can be computed from the corresponding bits of disks 47.
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 bitvectors 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 modulo2 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