T-106.420 Concurrent programming Example solution for homework assignment 2

1. (a) The average of the array x[0...N − 1], N ≥ 1, is m:

m = (Σi : 0 ≤ i < N : x[i])/N

(b) The segment of the array x that is between indices p and q − 1 inclusive contains only zeroes: (∀i : p ≤ i < q : x[i] = 0)

(c) The index of the minimum value of the array x[0...N], N ≥ 0, is i: 0 ≤ i ≤ N ∧ (∀j : 0 ≤ j ≤ N : x[i] ≤ x[j])

(d) The value of each element in array x[0...N], N ≥ 1, is unique (within the array): (∀i, j : 0 ≤ i, j ≤ N : x[i] = x[j] ⇒ i = j) Or, equivalently: (∀i, j : 0 ≤ i, j ≤ N : i ≠ j ⇒ x[i] ≠ x[j])

2. (a) The solution does not work. For example one process flips the lock to 1 and enters the critical section. The other process flips the lock to 0 and enters the inner loop. Lock is 0, so go back and flip again to 1, and enter critical section.

(b) This solution works. One process flips the lock to 1 and enters the critical section. The other process flips the lock to 2 and spins in the inner loop until lock == 0, which happens when the first process exits the critical section. The solution works, but is not fair.