Assignment 13, due Dec. 6

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

This is a "bonus" assignment. Only the top 10 homework scores will count toward the final grade. The material covered on this assignment will be a potential source of content for the final exam.

1. Background: Some modern computers have the following two special instructions, used to help synchronize operations in shared memory:

   LOADLOCK r,a

   This is exactly the same as LOAD r,a except that it also remembers the address a and sets an autonomous part of the CPU to work monitoring the address bus to see if any other processor writes the address a. The CPU can only monitor one address at a time, so there must be a special "monitor" register in the CPU to hold the address being monitored.

   STORECOND r,a

   If no other processor has written to memory address a since the CPU began monitoring address a, this instruction behaves exactly like STORE r,a, except that it also sets a condition code to indicate success. If, on the other hand, some other processor has interfered, the condition code is reset and no store operation takes place.

   If we assume that the STORECOND instruction reports failures in the C (carry) condition code, the following instruction sequence is equivalent to "exchange memory location AD and register R1" except that it uses an extra register to do the job.

         MOVE      R2,R1   -- copy R1 into scratch register R2
   LOOP:
         LOADLOCK  R1,AD   -- get previous value of AD into R1
         STORECOND R2,AD   -- try to complete the exchange
         BCR       LOOP    -- if it failed to store, try again
   

   An aside: Why these odd seeming instructions? Because they happen to be straightforward to implement on shared-memory multiprocessors (or multicore processors) that are based on "snooping cache" memory architectures.

   A problem: Give code using assembly language (or something like assembly language) to safely increment the contents of memory location AD by one, even in the context of other programs that might be trying to tinker with the same location. You can assume an ADDI r,c instruction that increments register r by the constant c, and you should assume that all arithmetic operations are register-only; that is, there is no increment or add instruction that can directly manipulate an operand in memory. (0.5 points)

2. Background: Consider this outline of a "secretary" process comparable to that in Monday's lecture, but including elements of a client-server system:

   void secretary() {
           available = TOTAL_SIZE_OF_RESOURCE;
           for (;;) {
                   m = dequeue_message();
                   select (m.type) {
                   case request: /* user requested a resource */
                           if (m.amount < available) {
                                   available = available - m.amount;
                                   send_reply( m );
                           } else {
                                   set_aside( m );
                           }
                           break;
                   case release: /* user released the resource */
                           available = available + m.amount;
                           break;
                   }
           }
   }
   

   Users send the secretary process messages requesting or releasing resources, and they indicate how much they are requesting or how much they are releasing. Ignore, for the moment, the actual allocation and deallocation problem: In a real system, the reply to a request message would obviously include some kind of handle on what was allocated, and the release message would include the handle for what is being released.

   There is something fundamental missing from the above code. (And it was missing in the lecture too).

   a) What is missing? Hint: Something was started above that was never finished. (0.5 points)

   b) Suggest the most appropriate place in the above code to finish it. (0.5 points)

   c) Describe the logic for finishing it. Use English or pseudocode, don't focus on syntax. (0.5 points)

3. Background: The article "Task Communicaton in Demos" is a free download to on-campus users or off-campus users who access the article through a VPN connection to campus. (It is free on campus because we are an institutional member of ACM.) Read it!

   a) Assume that process x running under DEMOS creates a new link, call it n. A user can then send a message over link n. What process will receive that message? (0.5 points)

   b) (0.5 points) Suppose processe x creates link n, and process x wants to give link n to process y. What tools does Demos provide to allow x to pass n to y?