Assignment 8 Solutions

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.

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.

Tracks Moved	Move Time	Sectors Skipped
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

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.