Assignment 8 Solutions

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

  1. Given a disk with 5 sectors per track, where the physical sector numbers are 0-1-2-3-4, if 2-way interleaving is used, the corresponding logical sector numbers are 0-3-1-4-2. For this problem, assume a disk with 16 sectors per track.

    a) What is the order of logical sectors with 5-way interleaving?

    0-1-2-3-4-5-6-7-8-9-A-B-C-D-E-F -- no interleaving (1-way)
    0-B-6-1-C-7-2-D-8-3-E-9-4-F-A-5 -- 3-way interleaving
    0-D-A-7-4-1-E-B-8-5-2-F-C-9-6-3 -- 5-way interleaving
    0-7-E-5-C-3-A-1-8-F-6-D-4-B-2-9 -- 7-way interleaving

    b) How many distinct interleaving factors are there for this disk? That is, interleaving factors that lead to distinct sector orders.

    1, 3, 5, 7, 9, 11, 13, 15. These are all numbers from 1 to 16 that share no common factors with 16 except 1.

  2. Do problem 5 from chapter 11 in the notes.

    If one sector rotates by the head every 138 microseconds and it takes 100 microseconds for the software to start the next disk transfer after the previous one has finished, and if the head positioning latency is 0.005 seconds times the square root of the number of tracks moved, make a table of the number of sectors which must be skipped before the next transfer can begin as a function of the number of tracks the head must move, from 0 to at least 15 tracks.

    0 0 1
    1 5000 37
    2 7071 52
    3 8660 63
    4 10000 73
    5 11180 82
    6 12247 89
    7 13229 96
    8 14142 103
    9 15000 109
    10 15811 115
    11 16583 121
    12 17321 126
    13 18028 131
    14 18708 136
    15 19365 141

  3. Do problem 11 from chapter 11 in the notes.

    Exactly what damage could occur if an interrupt occurred at the wrong time during the critical section in the diskread routine in Figure 11.7? Between which instructions would this interrupt have to occur, and what observable consequences would result from the damage?

    The critical section is marked by disableints and enableints at the enc of diskread. The problem occurs because, just before the interrupt service routine exits, it sets the disk control register (an interface register). Suppose the disk was idle, and the interrput occurred just before diskread was about to set the control register. The interrupt service routine, finding a disk request, starts a read or write, and then returns. The read routine immediately changes the control register back to its previous state (idle, but with interrupts enabled), and it is possible that the disk controller, under these circumstances, would abort the input/output operation.

    Do problem 14 from chapter 11 in the notes.

    For each of the disk scheduling policies, what should be done when a request is posted for the track the head is currently processing? What alternatives are there, if any, and what undesirable consequences would result from the use of these alternatives?

    a) shortest-seek-time-first

    Posting the request to the current track does nothing interesting here, so speaking of alternatives is not interesting.

    b) cyclic-scan

    Here, if we allow a request to be posted to the list of pending operations in the current track, we could prevent the cyclic scan from advancing to the next track, ever. This is bad, so we seek an alternative.

    A useful alternative is to not process new requests for the current track until the next visit to this track, after visiting all other tracks with pending requests.

    c) elevator

    The situation here is the same as with part b.