CSc 422, Fall 2020: Assignment 1 Solutions
For this assignment, the point values are 10 points for each problem, with the point values for each problem evenly split over each part if there are multiple parts. The programming assignment (2.7) was 20 points.
1. Problem 2.7 Part (A)
int n, p // set to whatever is desired
int a[0:n-1], globArray[0:p-1]
int partialSum(int myId) {
int localSum := 0, i
int start := myId * n/p
int end := start + n/p – 1
for (i = start; i <= end; i++)
localSum += a[i]
return localSum
}
main() {
int i, sum = 0
initialize(a) // not shown
co i:= 0 to p-1
globArray[i] = partialSum(i)
oc
for i := 0 to p-1
sum += globArray[i]
print sum }
1
2. Problem 2.10.
Denote S1 and S2 as the two statements of the first thread, and S3 and S4 as the two state- ments of the second thread.
Part (A). We saw an example of a co statement with two arms and two atomic statements in class and agreed that there are six possible histories. (There are five unique histories, given that x=x+2 is in both arms of the co; that is, when x=x+2 can be the second or third statement in the linearization, two of the histories are indistinguishable.)
If one writes out these five histories, one finds that x is always 5, and y is either -2, -3, or -5.
Part (B). First, x must be at least 2 (which occurs if S3 executes first and loads x when it is zero, but then stores 2 into x after S1 and S2 execute to completion). In addition, x can be at most 5, which occurs if S1, S2, and then S3 execute to completion. Furthermore, x can take on both 3 and 4, because S1 and S3 can execute concurrently yet complete before S2; and in this case we know from class that x can be 1 or 2 after both S1 and S3 execute.
Second, y must be in the range [-1, -5]. Because x can take on values in the range [2, 5], y can takes on the values [-2, -5]. In addition, because S4 can execute from a start state when x is 1 (because S1 stores 1 to x and overwrites S3’s store), we add -1 to the range of values for y.
The total number of histories, using the formula H = (nm)!/(m!)n, where n is the number of threads and m is the number of atomic actions per thread, is H = (2 ∗ 6)!/(6!)2, which is 924.
3. Problem 2.12.
Part (A). The statements execute one after the other, so either x and y are 5 and 15, or x and y are 8 and 6.
Part (B). Note that the left arm of the co will always read x as 2, and the right arm will always read y as 3. If all loads occur before any stores, then x and y are 5 and 6. Otherwise, one of the arms is loading the “new” value. However, these are just the same two possibilities as in part (A), so we have (5, 15) and (8, 6) as possible answers also.
4. Problem 2.17
Clearly, any value of x larger than 6 means that the program does not terminate. This is because the third arm of the co blocks until x is 1, and there no chance of that happening. Any value of x less than 1 means all three arms will block indefinitely. If x is 2, only the second arm is eligible to execute in its await, so clearly x will become zero and the program hangs. If x is 3 or 4, there exists an order that leads to deadlock. If x is 5, x becomes zero and so termination is impossible.
This leaves only 1 and 6, and in these two cases, termination will always occur.
5. Problem 2.33. Parts (A and B). The program may not terminate under strongly fair schedul- ing, because x == 0 fails to become true infinitely often. Any program that may not termi- nate under strong fairness also may not terminate under weak fairness.
2
Part (C). Here, it is clear that x == 0 becomes true infinitely often, because every time x drops below 0, the third arm resets x to 10. Therefore, the program terminates under strong fairness, but not under weak fairness (as it could be that the thread represented by the first arm never sees x as 0).
3