Homework 5 Solutions

22C:116, Fall 1999

Part A: How long would it take to read this sequence, in the order given, assuming no interleaving?

	track  sector 
       ================
	  1      1        
	            -- seek 7 tracks skips sectors 2,3
	  8      4    
	  8      5   
	            -- seek 1 track skips sector 6
	            -- therefore add 1 revolution
	  9      6
	            -- seek 1 track skips sector 7
	            -- add 1 revolution to get back to 6
	  8      6
	            -- seek 4 tracks skips sectors 7,8
	  3     12
	            -- seek 9 tracks skips sectors 13,14,15
	            -- add 1 revolution to get back to 3
	 14      3
	            -- seek 6 tracks skips sectors 4,5
	  8      7
	            -- seek 5 tracks skips sectors 8,9
	  3     13
	  3     14

	time is 3 and 13/16 revolutions

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?

	track  sector
       ===============
	  1      1        
	            -- seek 7 tracks skips sectors 2,3
	  8      4
		    -- latency adds 1 revolution
	  8      5
		    -- latency or seek adds 1 revolution
	  9      6
		    -- add 1 revolution
	  8      6
	  3     12
	            -- seek 9 tracks skips sectors 13,14,15
		    -- add 1 revolution to get back to 3
	 14      3
	            -- seek 6 tracks skips sectors 4,5
	  8      7
	            -- seek 5 tracks skips sectors 8,9
	  3     13
		    -- latency adds 1 revolution
	  3     14

	time is 5 and 13/16 revolutions

Part C: How long would it take to read this sequence assuming 2-way interleaving, plus the assumptions from part B:

We assume the following interleaving:

	0     1     2     3     4     5     6     7
           8     9    10    11    12    13    14    15
 
        0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

                   sector
	track  logical  real
       ======================
	  1      1       2
	            -- seek 7 tracks skips sectors 3,4
	  8      4       8
		    -- latency skips sector 9
	  8      5      10
		    -- latency and seek skip 11
	  9      6      12
		    -- add 1 revolution to get back to 12
	  8      6      12
		    -- add 1 revolution to get back to 9
	  3     12       9
	            -- seek 9 tracks skips sectors 10,11,12
		    -- add 1 revolution to get back to 6
	 14      3       6
	            -- seek 6 tracks skips sectors 7,8
	  8      7      14
	            -- seek 5 tracks skips sectors 15,0
		    -- add 1 revolution to get back to 11
	  3     13      11
		    -- latency skips sector 12
	  3     14      13

	time is 4 and 11/16 revolutions

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 everything else from parts B and C?

                   sector
	track  logical  real
       ======================
	  1      1       2
	            -- seek 2 tracks skips sectors 3
	  3     12       9
	  3     13      11
	  3     14      13
	            -- seek 5 tracks skips sectors 14,15
	            -- we finished 1 revolution
	  8      4       8
	  8      5      10
	  8      6      12
	  8      7      14
	            -- seek 1 tracks skips sectors 15
	            -- we finished 1 more revolution
	  9      6      12
	            -- seek 5 tracks skips sectors 13,14
	            -- we finished 1 more revolution
	 14      3       6

	time is 3 and 4/16 revolutions

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.

	sleep(n)
	   if n <= 0, return
	   t = -n (2's complement)
	   T1RL = low 8 bits of t
	   T1RH = next higher 8 bits of t
	   tH = highest 16 bits of t
	   T1ON = 1
	   repeat
	       do nothing until T1IF = 1
	       tH = tH + 1
	   until tH = 0
	   T1ON = 0
	   T1IF = 0
	   return

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.

	   r = new timer record
	   r.t = t
	   r.p = p
	   r.i = i
	   disable interrupts
	   if head = nil then
	      -- queue is empty
	      (T1RH | T1RL) = r.t
	      r.next = nil
	      head = r
	      T1IE = 1
	   else if (T1RH | T1RL) < r.t then
	      -- r goes at head of queue
	      head.t = (T1RH | T1RL) - r.t
	      (T1RH | T1RL) = r.t
	      r.next = head
	      head = r
	   else 
	      -- r goes deep in queue
	      r.t = r.t - (T1RH | T1RL)
	      temp = head
	      while temp.t < r.t do
	         r.t = r.t - temp.t
	         temp = temp.next
	      endloop
	      -- r goes before temp in list
	      temp.t = temp.t - r.t
	      r.next = temp
	      (predecessor of temp).next = r
	   endif
	   enable interrupts
	   return

	timer interrupt service routine
	   T1IF = 0
	   r = head
	   head = head.next
	   if head = not nil
	      (T1RH | T1RL) = head.t
	   else
	      T1IE = 0
	   endif
	   call r.p( r.i )
	   dispose of timer record r
	   return

The above pseudocode maintains relative times for all timers in the timer queue, and it does not address the issue of how the next pointer of the predecessor of an item in the queue is found during insertion. Also, the critical section in the enqueue routine is too long! With a little care, it can be shortened!