Homework 4
Assigned 15 May 2006
Due 24 May 2006
30 points

Exercises 8-7, 8-8, and 8-12 from your text, pp 274-275.  
(8-7 and 8-8 are worth 3 pts, and 8-12 is worth 4 pts.)


M1, 5 pts.  Consider Dijkstra's dual pass ring termination
algorithm, as discussed in section 7.3.3 of your text.  Will the
algorithm still work correctly if processes can start jobs ahead
as well as behind in the ring?  If so give a brief justification, 
and if not, give an example of how the algorithm can fail.


M2, 5 pts.  Consider the following program:

   int x = 2, 
   int y = 3;
   par {
     x = x + y;
     y = x * y;
   }

(a.) Suppose the two statements in the par can each execute
atomically.  What are the possible final values of x and y?

(b.) Suppose the two statements in the par are implemented with
atomic actions: read a variable, add or multiply, and write a
variable.  Now what are the possible final values of x and y?

(Note: M2 is exercise 2.12 from G. R. Andrew's "Foundations of
Multithreaded, Parallel, and Distributed Programming, with minor
modifications.)


M3, 5 pts.  Briefly compare Monitors and Dijkstra-style
semaphores.  Give an example of where monitors would be the
better design choice, and an example of where Dijkstra's
semaphores would be preferable.


M4, 5 pts.  Message passing programs have an associated data-
flow graph where the nodes are processes and the edges are pairs
of processes (Pi, Pj), where Pi sends messages to Pj.  Do shared
memory programs have similar dataflow graphs?  If so, discuss how
they might be found automatically, for example by a complier, and
if not, explain why not.