CS245 PROBLEM SET #1 Due by 5:30pm, Tuesday, July 6, 1999 |

- five platters, ten surfaces
- 10,000 cylinders
- 1000 sectors/track
- 2^9 bytes/sector
- 10,000 rpm
- Seek time = 1 ms plus another 1 ms per 1000 cylinders moved.

- a)
- The total capacity of the disk.
- b)
- The average seek time.
- c)
- The average rotational latency.
- d)
- The transfer time of a block (2^14 bytes).
- e)
- The average time for accessing 10 continuous blocks in one track on the disk.

Part 2 (10 points): Suppose you are told that half of the data on the disk are accessed much more frequently than another half, and you are given the choice to place the data on the disk to reduce the average seek time. Where do you propose to place the hot data, considering each of the following two cases? (Hint: Inner-most tracks, outer-most tracks, middle tracks, random tracks, etc). State your assumptions and show your reasoning.

- a)
- There are same number of sectors in all tracks (the densities of inner tracks are higher than those of the outer tracks).
- b)
- The densities of all tracks are the same (there are less sectors in the inner tracks than in the outer tracks).

Part 1 (10 points):
Assuming that the disk controller uses the *elevator algorithm* described in class
for disk scheduling, in each of the following cases,

- 1)
- There are 100 I/O requests evenly spread out on the disk to be serviced with one request every 100 cylinders.
- 2)
- There are 20,000 I/O requests evenly spread out on the disk to be serviced with two requests in every cylinder.

- a)
- The average time it takes the disk to service a request.
- b)
- The average time it takes for a waiting request to be serviced.

Part 2 (10 points):
Assuming that the disk controller is using the *first come first serve algorithm*
instead, recompute the parameters in Part 1.

Part 3 (10 points): What are the advantages and possible disadvantages of the elevator algorithm, comparing to the first come first serve algorithm? Name one possible improvement to the elevator algorithm, and show your reasoning.

Part 1 (5 points): Assuming that the system has one disk, what is the minimum time to read and process 100 blocks using single buffering and double buffering, respectively.

Part 2 (10 points): Suppose the system has two disks, and a data block can be read from each disk independently in 10ms. Can you design a simple algorithm that further reduces the time to read and process 100 blocks? What is the minimum time that your algorithm can achieve? At least how many buffers (each containing one block) are needed to achieve this minimum time? Briefly explain your algorithm. (Hint: Consider a slight modification of the double buffering algorithm.)