Homework 5 Solutions

22C:116, Fall 1995

1. The problem: Compare and contrast the following schemes.
   • Use a n-ary tree to index the sectors of each disk file. Here, if a file has S sectors, access to any given sector will involve references to ciel(log n(S)) index sectors (the integer greater than or equal to the log to the base n of S). As yet unreferenced sectors need not be allocated, so a sparse file will not occupy as much space, but the value of S that matters is the largest numbered sector in the file, not the number of sectors actually used.

   • Use a second disk file to index the sectors of each disk file. This scheme is exactly equivalent to the n-ary tree. The difference lies not in the data structure, but in the view taken by the software of that data structure. All of the answers for this scheme are therefore identical to those for the n-ary tree scheme.

   • Use a B-tree for each file, where the key used to organize the tree is the offset into the file. The B-tree will also offer a logarithmic access time, with the formula ciel(log n(S)) giving the expected access time, but with different values for n and S. The value of S that matters is the number of sectors in the file, not the highest addressed sector. Thus, for a sufficiently sparse file, this scheme will always win out over the simple n-ary tree. The value of n that matters will be the average number of pointers stored in each sector of the B-tree. Where the n-ary tree stored exactly n pointers per node, the B-tree will fill each index sector to approximately half full (in the stable state), and the entries in the index sectors will be "<"key,pointer">" pairs instead of pure pointers. Thus, for a given non-sparse file, a B-tree will have an expected value of n that is perhaps half that for a simple n-ary tree, implying longer access times resulting from traversing a deeper tree.

2. Background: Consider a system with a programmable interval timer. The interface to this has two registers. One register contains the time until next interrupt, and is constantly decremented by the hardware every microsecond. The other register is one bit, used to enable or disable the interval counter interrupt. The timer hardware attempts to request an interrupt whenever the time register is negative and interrupts are enbaled.

   The users of this system want two different timer services. First, users want to be able to issue a delayed signal to a semaphore. To issue such a signal, the user specifies a semaphore and a time interval, in microseconds, and the timer subsystem will signal that semaphore after that interval has passed. Second, users want to be able to inquire about the time and date, specified as a three word quantity, giving day number since the (arbitrarily established) beginning of time, seconds since midnight, and microseconds in the current second.

   The Problem, part A: Propose an implementation of a delayed signal primitive on a semaphore, using a programmable interval timer.

   hardware registers
      interval_timer_counter
      interval_timer_enabled
   
   software variables
      timer_head       -- a list of timer records
      current_interval -- record describing the current 
   
   types
      timer -- a record with the following fields
         sem      -- a semaphore
         interval -- time interval
         next     -- link to the next timer in the list
   
   delayed_signal(S, I)
      allocate new timer T
      T.sem = S
      T.interval = I
      schedule_timer(T)
      return
   
   schedule_timer(T)
      disable_interrupts
      if interval_timer_enabled
         T.interval = T.interval - interval_timer_counter
         if timer_head = null
            timer_head = T
            T.next = null
         else if T.interval < timer_head.interval
            T.next = timer_head
            timer_head.interval = timer_head.interval - T.interval
         else
            X = timer_head
            loop
               exit loop when X.next = null
               exit loop when X.next.interval > T.interval
               X = X.next
               T.interval = T.interval - X.interval
            endloop
   	 T.next = X.next
   	 X.next = T
            if T.next /= null
               T.next.interval = T.next.interval - T.interval
            endif
         endif
      else
         interval_timer_counter = T.counter
         current_interval = T
         set interval_timer_enabled
      endif
      enable_interrupts
      return
   
   timer_interrupt_service_routine
      disable_interrupts
      signal( current_interval.sem )
      if timer_head = null
         reset interval_timer_enabled
      else
         deallocate timer record current_interval
         interval_timer_counter = timer_head.interval
         current_interval = timer_head
         timer_head = timer_head.next
      endif
      enable_interrupts
      return
   

   The Problem, part B: Suggest an implementation for the time and date service:

   Note that intervals are probably limited to something less than the maximum date, so we need to deal with interval overflow.

   constant
      date_interval -- the delay between increments of date
   
   variables
      date     -- used to count time
      date_sem -- a semaphore
   
   count_time -- a process used to update date
      repeat
         delayed_signal( date_sem, max_interval )
         wait( date_sem )
         date = date + 1
      forever
   
   time_and_date( D, I )
      -- return , the time and date
      disable_interrupts
      D = date
      I = interval_timer_counter
      X = timer_head
      repeat
         I = I + X.interval
         X = X.next
      until X.sem = date_sem
      enable_interrupts