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

Problem 1: Disk Access (35 points)

The MEGATRON 777 disk has the following characteristics:
• 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.
Part 1 (25 points): Calculate the following parameters.
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).

Problem 2: Elevator Algorithm (30 points)

Consider the MEGATRON 777 disk in Problem 1. Suppose each I/O request asks for one block of data, and the start position of the disk arm is at the inner-most track of the disk.

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.
calculate:
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.

Problem 3: Buffer Management (15 points)

Recall the double buffering technique introduced in the class. Suppose that the time to read a block is 10ms, and the time to process a block is 5ms.

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.)

Problem 4: Fixed/Varying Length Fields/Records (20 points)

Show the pros and cons of using fixed fields vs. varying fields and using fixed records vs. varying records. Please itemize your answer.