Homework 9

22C:116, Spring 2002

Due Monday Apr 22, 2002, in class

Assume the usual general instructions!

1. Background Consider the following two code snips, inspired by a typo (more properly, a "thinko") in the notes for lecture 24.

      Version 1:
           disable interrupts     -- prevent other activity on this CPU
           wait on spin lock      -- block if other CPU in critical section
           .. critical section ..
           release spin lock      -- allow other CPUs into critical section
           enable interrupts      -- allow other activity on this CPU
   
      Version 2:
           wait on spin lock      -- block if other CPU in critical section
           disable interrupts     -- prevent other activity on this CPU
           .. critical section ..
           enable interrupts      -- allow other activity on this CPU
           release spin lock      -- allow other CPUs into critical section
   

   The Problem In the event that some critical variable is updated in both an interrupt service routine and in a regular routine, one of these two code fragments is prone to deadlock. Which of the above is deadlock prone, and how does it deadlock?

2. Background The design of the DEMOS-like microkernel described in the notes for lecture 30 presents a data structure, the mailbox table, associated with each process. Given that synchronous message passing is used, and that the number of processes in the system is bounded, but that the number of mailboxes a process may maintain is unbounded, this poses some severe implementation problems (consider a file server that associates a mailbox with each I-node, or consider a process manager that associates a mailbox with each process ID).

   Therefore, we seek another implementation. Consider having a single list of processes that is shared by all processes attempting to send a message to any box of a given process.

   Part A: Outline the logic of the receive kernel call for this approach.

   Part B: Outline the logic of the send kernel call for this approach.

   Part C: In light of the above, what is the data structure of one process, at the level of detail presented in lecture 30 (only go into detail for those parts that are different from the notes for lecture 30).

3. Problems from the text:
   Do problem 22 and 25 on page 580.