# Concurrent Programming 8893 Assignment 1

Due: Tuesday, February 10 at 9:00.

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.

Back to 8893 homepage