CS322 Homework 3: Concurrent Processes and Programming

Due Monday February 28, 2000 at the start of class

1. Given the following series of statements, construct a precedence graph:

   	S1:	a := b + c;
   	S2:	d := e - f;
   	S3:	g := a;
   	S4:	h := g;
   	S5:	g := 0;
   	S6:	i := b * c;
   	S7:	j := h * i;
   

2. Given the following precedence graph:

   

   1. Construct an equivalent program fragment that makes maximum use of parallelism, using PARBEGIN .. PAREND. (Hint: you will need more than one PARBEGIN .. PAREND pair).

   2. Repeat, using FORK and JOIN. (Again, you will need more than one of each.)

   3. Suppose we now add to the graph an edge from S2 to S4. Explain why the full potential parallelism of the new graph cannot be realized using PARBEGIN .. PAREND.

   4. Show how the full parallelism possible in the new graph can be realized by using PARBEGIN .. PAREND in conjunction with semaphores.

3. Do problem 6.2 in the text.

4. Consider the following proposed solution to the critical section problem for two processes. Either present an argument that it is correct, or show an example that violates one of the three requirements for a solution to the critical section problem.

      (* The two processes P0 and P1 share the following variables *)
   
      var	flag: array[0..1] of boolean;  (* Initially false *)
   	turn: 0..1;
   
      (* Each process executes the following code, where i = 0 for process P0
         and 1 for process P1 *)
   
      repeat
   	flag[i] := true;
   	while turn <> i do
   	  begin
   	    while flag[1 - i] do skip;
   	    turn := i
   	  end;
   	...
   	(* critical section *)
   	...
   	flag[i] := false;
   	...
   	(* remainder section *)
   	...
      until forever
   

5. Suppose a certain machine has the swap instruction, defined as follows:

   SWAP s1, s2 -- interchanges the values of s1, s2 atomically

   Give code for this machine for the binary semaphore primitives P and V.