T-106.420 Concurrent programming Homework assignment 1 (Sep. 29, 2003)

The deadline for this exercise is Friday, Oct. 10, 2003, 04:00 pm (16:00).

1. Consider the following three statements:

S_{1} : x = x + y; S_{2} : y = x − y; S_{3} : x = x − y;

Assume that x is initially 2 and that y is initially 5. For each of the following, what are the possible final values of x and y? Explain your answers.

(a) S_{1}; S_{2}; S_{3};

(b) co ⟨S_{1}; ⟩ ∥ ⟨S_{2}; ⟩ ∥ ⟨S_{3}; ⟩ oc

(c) co ⟨await (x > y) S_{1}; S_{2} ⟩ ∥ ⟨S_{3}; ⟩ oc

2. Consider the following program:

int x = 0; co ⟨await (x ! = 0) x = x − 2; ⟩ / ∗ S_{1} ∗ / ∥ ⟨await (x ! = 0) x = x − 3; ⟩ / ∗ S_{2} ∗ / ∥ ⟨await (x == 0) x = x + 5; ⟩ / ∗ S_{3} ∗ / oc

(a) Does the program terminate? If so, what are the possible final values of x? If not, why not?

(b) Suppose the atomic await statements are changed to non–atomic if statements. Does the program terminate then? If so, what are the possible final values of x? If not, why not?

3. Consider the following program:

co ⟨await (x > 0) x = x − 1; ⟩ / ∗ S_{1} ∗ / ∥ ⟨await (x < 0) x = x + 2; ⟩ / ∗ S_{2} ∗ / ∥ ⟨await (x == 0) x = x − 1; ⟩ / ∗ S_{3} ∗ / oc

For what initial values of x does the program terminate, assuming scheduling is weakly fair? What are the corresponding final values? Explain your answer.