Concurrent Programming 8893
Assignment 1

Please submit all solutions in hard-copy (i.e., printed on paper).

1. (Based on Andrews 2.7 on p. 83.) Consider the problem of computing the sum of the elements in an array a[N]. Using Java, implement solutions in Java in the following styles:
   1. Iterative parallelism (while inside co) using PR processes.
   2. Recursive parallelism where the size of the problem is cut in half for each recursive step. Stop recursing when the problem size is less than or equal to a threshold T.
2. (Andrews 2.13 on p. 85.) Consider the following three statements:
   S1: x = x + y
S2: y = x - y
S3: x = x - y
Assume that x is initally 2 and that y is initally 5. For each of the following, what are the possible final values of x and y? Explain your aswers.
   1. S1; S2; S3;
   2. co < S1; > // < S2; > //< S3; > oc
   3. co < await (x > y) S1; S2; > // < S3; > oc
3. (Based on Andrews 2.16 on p. 86.) Consider the following program:
   

   
   int x = 0;
   co < await (x != 0) x = x -2; >
     // < await (x != 0) x = x - 3; >
     // < await (x == 0) x = x + 5; >
   oc
   

   Develop a proof outline that demonstrates that the final value of x is 0. Use the techniques of weakened assertions and excluded configurations (you may need to introduce one or more thought variables) to show non-interference.
4. (Andrews 3.7 on p. 144) Consider the following critical section protocol.
   

   
   int lock = 0;
   process CS[i = 1 to n] {
     while (true) {
       < await (lock == 0) >; lock = i; Delay;
       while (lock != i) {
         < await (lock == 0) >; lock = i; Delay;
       }
       critical section;
       lock = 0;
       noncritical section;
     }
   }
   

   1. Suppose the Delay code is deleted. Does the protocol have the four required properties of a CS protocol? Carefully explain your answer in each case.
   2. Suppose the processes execute with true concurrency on a multiprocessor. Suppose thte Delay code spins for long enough to ensure tha tevery process i that waits for lock to be 0 has time to execute the assignmetn statement that sets lock to i. Does the protocol now satisfy the CS requirements? Again carefully explain each of your answer.

Last modified: Mon 2004.02.02 at 16:59 NST by Dennis Peters