Assignment 8, Solved

Part of the homework for 22C:50, Summer 2003
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

  1. That old 14-inch diameter disk I showed to the class had 20 recording surfaces, 400 cylinders and 24 sectors per track. Each sector was 512 bytes, and the drive spun that disk at 20 revolutions per second. The seek time from the innermost track to the outermost track was about 1/10 second. Seeks involved constant acceleration for half the seek, and then constant deceleration for the other half of the seek, so seeking 400 cylinders took twice as long as seeking 100 cylinders.

    Part a) What is the capacity of that disk in bytes.

    20 surfaces × 400 cylinders = 8,000 tracks
    24 sectors per track × 512 bytes per sector = 12,288 bytes per track
    12288 bytes per track × 8000 tracks = 98,304,000 bytes

    It is safe to bet that they sold it as a 100 megabyte disk! The 512 bytes per sector is, of course, the data capacity of the formatted sector, and if you add the number of bytes in the header and trailer of each sector, you almost certainly break 100 megabytes.

    Part b) What was the approximate data transfer rate, while reading data, in bytes per second? Your answer will be approximate because you don't know the size of the prefix and suffix on each sector.

    20 revolutions per second means it can read 20 tracks per second.
    20 tracks per second × 12,288 bytes per track = 245,760 bytes per second

    Part c) What was the rotational latency time?

    20 revolutions per second means the maximum rotational latency time is 1/20 of a second or 0.05 seconds. The minimum is zero, in the rare case that the I/O request arrives just as the desired sector comes by the head. Split the difference to get the average, giving 0.025 seconds or 25 milliseconds.

    Part d) What was the approximate time to seek from one track to the adjacent track? (I know you've had calculus! You can do the math!) In this case, your answer will be approximate because the data I gave for the maximum seek time was only approximate.

    We know that seek time grows with the square root of the distance moved, so seeking 4 times as far takes 2 times as long and seeking 2 times as far takes 1.414 times as long. So, we can make the following table by quartering distances and and halving times:

    1/10 second to move 400 cylinders,
    1/20 second to move 100,
    1/40 second to move 25,
    1/80 second to move 6.25,
    1/160 second to move 1.5625
    (1/160)/1.414 second to move 0.78125
    Now, we didn't get an exact answer, but it's worth noting that moving 1 cylinder is between moving 0.78 and 1.56, so our answer should be between 0.0044 and 0.00625 seconds. In round numbers, 5 milliseconds would be a nice way of putting it.

    Going back to Highschool physics or freshman Calculus, the formula for distance moved is:

    d = (1/2)at2.

    Filling in the numbers we know,

    400 = (1/2)a(1/10)2

    Solve for the constant of proportionality and we get:

    (1/2)a = 400 / (1/10)2 = 400 / (1/100) = 40000

    Now, rework it to get t as a function of d to get:

    t2 = d / (1/2)a
    t = sqrt(d / (1/2)a)

    Finally, we substitute in the numbers we're interested in

    t = sqrt( 1 / 40000 ) = 1 / sqrt( 40000 ) = 1/200

    So, we can move one track in 1/200 which is 5 milliseconds! (confirming our more intuitive solution exactly!)

  2. The queues used for data to and from a low performance device such as a keyboard or serial port are ususally implemented using bounded buffers. The queues used for disk and tape interfaces are usually implemented using linked lists of buffers. Why?

    With a bounded buffer of characters, the overhead of copying characters, one at a time, from producer to buffer and from buffer to consumer is modest compared to the cost of actual input or output through an interrupt handler that is called once per character.

    On the other hand, with direct memory access channels that can transfer thousands of bytes per interrupt, the overhead of memory-to-memory copying is high compared to the time taken by the interrupt service routine, so we try to minimize such copying, using the programmer's original buffer whenever possible, and using a queue organization that allows the interrupt handler to operate identically whether the buffer is a system buffer or a user buffer. This works well with a linked list of buffers.

  3. The queues used for low performance devices and for sequential high performance devices such as tape drives and network interfaces are almost always simple FIFO queues. For disks, we use far more complex scheduling disciplines to determine the order in which elements in the queue are dequeued. What is the advantage of using disciplines more complex than FIFO for disk queues?

    Non-FIFO queues allow disk scheduling to minimize the maximum waiting time of users or to maximize throughput (disk operations per unit time).