Midterm Practice Solutions CSc 422, Fall 2020
October 5, 2020
1
Concurrency
Consider the following code fragment. Give all possible outputs and clearly and concisely explain your answer. Note that in this example threads call functions with zero parameters.
int x;
Lock l; Semaphore s = 0;
void foo( ) { x = x + 1;
V(s);
}
void bar( ) { P(s); P(s);
x = x * 2;
}
void baz( ) { Acquire(l); x = x + 2;
V(s);
Release(l);
}
main() { x = 0;
Thread t, u, v;
ThreadCreate(&t, foo);
ThreadCreate(&u, bar);
ThreadCreate(&v, baz);
ThreadJoin(&t); ThreadJoin(&u); ThreadJoin(&v); // block until threads complete print(x);
}
Answer: The lock has no effect because only one thread uses it. Because the thread that invokes bar invokes P(s) twice, and the initial value of s is zero, the multiplication is only executed after both of the additions in the other two threads are executed. Clearly, there is a race on variable x between the threads that invoke foo and baz, and from class, we know that the possible outputs given this pattern are 1, 2, and 3. Therefore, the possible outputs of the program are 2, 4, and 6. (Note that 0 is not a possible output because the main thread joins on each forked thread before printing x.)
// fork t; t calls foo when it runs
2
Semaphores
The following is a correct two-thread symmetric barrier using semaphores.
// s is a two element array, with indices 0 and 1
sem s[2] = {0,0}
Thread 0: V(s[0]); P(s[1])
Thread 1: V(s[1]); P(s[0])
A. Suppose we instead propose the following solution:
// s is a two element array, with indices 0 and 1
sem s[2] = {0,0}
Thread 0: P(s[1]); V(s[0])
Thread 1: P(s[0]); V(s[1])
Is this solution correct? Briefly explain.
Answer: This solution will deadlock. Both threads execute a P operation on a zero-valued semaphore.
B. Suppose we instead propose the following solution:
// s is a two element array, with indices 0 and 1
sem s[2] = {0,0}
Thread 0: V(s[0]); P(s[1])
Thread 1: P(s[0]); V(s[1])
Is this solution correct? Briefly explain.
Answer: This solution works. Either thread 0 or thread 1 arrives first. In the former case, the V operation on s[0] will increment its value to 1, which allows thread 1 to proceed past its P operation. In the latter case, the P operation will block thread 1, but thread 0¡¯s V operation will unblock thread 1. Combining these, we know that thread 1 cannot proceed past the barrier until thread 0 arrives. Then, the same exact argument, but reversing the roles of the threads, shows that thread 0 cannot proceed past the barrier until thread 1 arrives.
3
Consider a proposed four-thread symmetric barrier.
// s is a four element array, with indices 0, 1, 2, and 3
sem s[4] = {0,0,0,0}
Thread 0: V(s[0]); P(s[1]); V(s[0]); P(s[2])
Thread 1: V(s[1]); P(s[0]); V(s[1]); P(s[3])
Thread 2: V(s[2]); P(s[3]); V(s[2]); P(s[0])
Thread 3: V(s[3]); P(s[2]); V(s[3]); P(s[1])
C. What can go wrong with this proposed solution? Do not attempt to fix the problem; merely state what can go wrong.
Answer: Without loss of generality, threads 0, 2, and 3 may arrive at the barrier, while thread 1 is late. In such a case, thread 0 will V(s[0]) to announce its arrival at the barrier, while threads 2 and 3 arrive and proceed through the first stage. Then, thread 2 is paired with thread 0, but thread 2 can proceed past P(s[0]) because of the V(s[0]) previously executed by thread 0. Hence, thread 2 leaves the barrier even though thread 1 has not arrived yet.
4