Assignment 11, due Apr. 30

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday). The only exceptions to this rule will be by advance arrangement unless there is what insurance companies call "an act of God" - something outside your control. Homework must be turned in on paper and in class! Late work may be turned in to the teaching assistant's mailbox, but see the late work policy. Never push late work under someone's door!

1. Background: Consider the following C implementation of a stack:

   void push( item * i; stack * s ) {
   	i->next = s->top;
   	s->top = i;
   }
   
   item * pop( stack s ) {
   	item * i;
   	i = s->top;
   	s->top = i->next;
   	return i;
   }
   

   Assume that stacks may be shared by multiple processes, but that, when a process is working with an item, that process never shares that item with any other process. Of course, when a process pushes an item on the stack, some other process might pop it off, so items are not permanently owned by processes.

   a) Identify the critical sections in this code. For each critical section, give an example showing how the interleaving of execution two processes could cause damage and describe the damage (typically, the loss of an item on the stack or the duplicate return of an item). (1.0 points)

   b) Modify the above code to include appropriate wait and signal operations on a semaphore or semaphores to protect these critical sections, and document where the semaphore or semaphores should be placed in the data structures and their initial values. (1.0 points)

2. Background: The load locked and store conditional machine instructions have been used on some modern multiprocessor (including multicore) computer architectures to support mutual exclusion and other parallel programming operations.
   -- load locked r,m is the same as load r,m except that it also starts the CPU monitoring references to memory location m by any other processor. Each CPU can only monitor one location.
   -- store conditional r,m is the same as store r,m except that, if memory location m has not been locked by this processor, or if some other processor has changed the contents of location m since this processor locked it, the store will fail. That is, this CPU will not change the contents of location m nor and it will indicate failure by setting a condition code.

   a) What does this instruction sequence do? (0.5 points)

             label:  load_locked       r1,m
                     increment         r1
                     store_conditional r1,m
                     branch_if_failure label 
   

   b) Design an instruction sequence using load locked and store conditional that implements spin locks on a lock variable stored in location m. The unlock instruction is a simple store of one to the lock variable. The lock operation must set the lock variable to zero and exit the locking loop if the former value was one. (0.5 points)