1. [30 Points] Consider a hard disk with the following specifications:
– The disk diameter is 3.5 inches.
– The disk has 16 surfaces, each having 100,000 tracks located at the outer 1 inch of the surface.
– A track consists of 256 blocks, a block consists of 8 sectors, and a sector is 512 bytes.
– Gaps occupy 10% (of tracks).
– Rotation speed is 8800 rounds per minute (RPM).
– The overhead to move the disk head is 1 ms.
– Time to move the disk head over 4000 tracks is 1 ms.
Using this information, answer the following questions (provide calculation details)

[20 Points] Suppose relations R(A,B) and S(B,C,D) have occupied 20,000 and 45,000 disk blocks, respectively. Also suppose a disk block fits 25 tuples of R or 30 tuples of S, and that the tuples are not stored in any specific order. If M is the number of main memory buffers available, then

a.Estimate the number of disk I/Os required to perform the natural join of R and S using the two-phase, multiway merge-sort method. Note that this query in SQL is expressed as: select * from R, S where R.B=S.B;

Sort:

Cost of sort=2*(Pass 0: read + write runs)+2*(Pass 1: read runs + write sorted relation)

Merge:

Read R + S blocks

In sum: 2(R+S)+2(R+S)+(R+S)=5(20000+45000)=325000 I/O operations

b.What is the effect on the cost of merging the runs (i.e., in Phase 2) if each main memory buffer fits n blocks, as opposed to the default n=1. The expected answer is a function of M, n, etc.

with default buffers n-1:

memory has M buffers

Phase 1 require B/M runs

Phase 2 require M-1

Number of passes= \( \log_{(M-1)} \frac{B}{M n} \)

Merge cost 2B*k

In Phase 2 Each I/O request transfers n blocks at once

Cost = \(\frac{2B}{n}k\)

3. [15 Points] We want to access k random disk blocks on the same track. Once the disk head is positioned on the desired track, determine, on average, how far (α) around the track should the r/w head pass to read those k blocks? Your answer would be α = 1, if the whole track has to pass under the r/w head, and α = 0.33, for instance, if 1/3 of the track has to pass. State any assumptions made to justify your answer.k

We assuming the k desired blocks are uniformly distributed around the track and the head is already positioned on the correct track; the starting phase is random.

If we read a random block, on average we expect half rotation which \(\frac{1}{k+1}\) α=0.5

If we read two random block, we have \(\frac{1}{k+1}+\frac{1}{k+1}=\frac{2}{k+1}\)
reading first α=1/3, second α=2/3

then we have \(1-\frac{1}{k+1}\)

checks

4. [15 Points] Suppose a computer system has a farm identical disk units, and we are using mirroring (RAID 1) scheme to protect against possible disk crashes. If the probability of a disk crash is 5%, what is the probability of a disk crash resulting in loss of data, assuming it would take 3 hours to rebuild a copy of the crashed disk?

Probability a disk crashes in a year = \(5\% = 0.05\). Rebuild time = \(3\) hours \(=\frac{3}{24\cdot365}=\frac{1}{2920}\) year.

Probability of the mirror crashing during restoration \(=\) (annual crash probability) \(\times\) (fraction of a year spent rebuilding).

\[ P \;=\; 0.05 \times \frac{1}{2920} \;=\; 1.7123\times 10^{-5} \;\approx\; 0.0017\% \;\approx\; \frac{1}{58{,}400}. \]

\[ P(\text{data loss during 3-hour rebuild}) \approx 1.7\times10^{-5} \;=\; 0.0017\% \; \]

5. [20 Points] A RAID 4 disk scheme includes 4 data disks and a redundant disk. For simplicity, assume each block size is 1 byte. In each of the following two cases, show the content of the redundant block, if the corresponding data blocks are as follows:
(a) 01010110, 11000000, 00110011, and 11111011.
(b) 11110000, 11111100, 00111111, and 00000001.
Furthermore, suppose the first block in both cases are changed to 11111111. Determine the changes required to make to other disks.

(a)

(b)

Update after changing the first data block to 11111111