Homework 5

22C:116, Fall 1999

Due Friday Sept 24, 1999, in class

Background Consider a (very small toy) disk with one recording surface, 16 tracks and 16 sectors per track. The time taken to move the head from track to track is significant. Specifically, reading the next sector in sequence is possible only if the head does not move. If the head must move 1 to 3 tracks, 1 sector must be skipped. If the head moves 4 to 7 tracks, 2 sectors must be skipped, if the head moves 8 to 15 tracks, 3 sectors must be skipped.
In the following sections of this problem, consider this sequence of disk addresses, and assume the disk has just finished reading sector 1 of track 1:
```
	track  sector
       ===============
	  8      4
	  8      5
	  9      6
	  8      6
	  3     12
	 14      3
	  8      7
	  3     13
	  3     14
	  8      8
```
Assume that the disk rotates at constant speed and that all time measurement is made in 16ths of a disk revolution.
Part A: How long would it take to read this sequence, in the order given, assuming no interleaving.
Part B: How long would it take to read this sequence assuming no interleaving, and assuming that the I/O hardware latency time is slightly longer than the intersector gap, so that it is impossible to read two sectors in sequence even when they are on the same track.
Part C: How long would it take to read this sequence assuming 2-way interleaving, and assuming that the I/O hardware latency time is slightly longer than the intersector gap, so that it is impossible to read two sectors in sequence even when they are on the same track.
Part D: How long would it take to read this sequence assuming the 2-way elevator algorithm is used to select which sector to read next, assuming 2-way interleaving and assuming I/O hardware latency times as in parts B and C.

Background Consider the real-time clock interface for the Microchip PIC clocked at 16Mhz, (simplified). This has the following registers:

            _______________________________________
   PIR1    |    |    |    |    |    |    |    |T1IF|
           |____|____|____|____|____|____|____|____|
           T1IF -- timer 1 flag bit
                   set by carry out from T1RH
            _______________________________________
   PIE1    |    |    |    |    |    |    |    |T1IE|
           |____|____|____|____|____|____|____|____|
           T1IE -- timer 1 interrupt enable bit
                   if 1, T1IF causes interrupt
            _______________________________________
   T1RL    |    |    |    |    |    |    |    |    |
           |_______________________________________|
           Incremented once per microsecond when timer 1 on
            _______________________________________
   T1RH    |    |    |    |    |    |    |    |    |
           |_______________________________________|
           Incremented each time there is a carry out of T1RL
            _______________________________________
   T1CON   |    |    |  1 |  0 |  0 |  1 |  0 |T1ON|
           |____|____|____|____|____|____|____|____|
           T1ON -- timer control bit
                   if 1, timer 1 on

Part A Write pseudocode for a sleep(n) routine that directly uses this timer to wait n microseconds, using polling, where n may be a 32 bit constant.

Part B Write pseudocode for a timer interrupt service subsystem that takes requests through the following user interface:

	after( t, p, i )
	   after a delay of t microseconds (t is 16 bits)
	   call p(i), where p is a void function expecting
	   an integer parameter.

(Note: In real life, the PIC architecture cannot support multiple user processes, so we can't use semaphores. You have to assume, therefore, that it is safe for the interrupt service routine to call p directly.)