1. Problem 3.3(a)
int s = 1
CSc 422, Fall 2020: Assignment 2 Solutions
Enter:
int flag = 0
Swap(s, flag)
while (flag == 0) {
Swap(s, flag)
}
Exit: s=1
The solution works because as said in class, most CS solutions using atomic instructions are implemented by having one shared variable that is initialized such that the first time the atomic action is applied, a local flag takes on a value, but all subsequent invocations of the atomic action result in a different (identical) value. Here, the first thread to execute Swap has its flag set to 1 (and s becomes 0), while all others have their flags set to 0. The exit protocol is to reset to the initial state.
2. Problem 3.16 Part (A)
The barrier works because it sequentializes incoming threads. Thread i cannot proceed until Thread i − 1 arrives. When Thread n arrives, it sets arrive[n] to 1, which allows all threads to proceed past the barrier.
Part (B)
This barrier is linear in the number of threads; the worst case is that the first thread arrives
last, and it then causes O(p) operations, where p is the number of threads.
1
3. Problem 4.3
The code is as follows:
Semaphore s = init value
P(Semaphore s) {
while (1) {
while (s <= 0) ;
if (FA(s, -1) >= 1)
break
FA(s, 1)
} }
V(Semaphore s) {
FA(s, 1)
}
The basic idea (disregarding the inner while loop for now) is that all threads execute an FA, decreasing s by 1. If the operation returns a value greater than or equal to 1, the thread should not block, and the semaphore value is properly decremented along with a break out of the outer while loop and therefore from P. On the other hand, any thread who would decrease the value below 0 (indicated by a return value less than or equal to 0) must undo its FA, which is why the second FA in P exists. The V operation is straightforward.
Now, the inner while loop is tricky. It is there to prevent a race condition. See if you can determine what that race condition is.
4. Problem 4.4(a)
Semaphore s[1:3] = {0,0,0}
Thread 1: V(s[1]); V(s[1])
Thread 2: P(s[1]); V(s[2])
Thread 3: P(s[1]); V(s[3])
Thread 4: P(s[2]); V(s[3])
Thread 5: P(s[3]); P(s[3])
2
5. Problem 4.31
Let the number of cars going south (north) be denoted ns (nn). Note I am showing only the south code (the north code is symmetric).
int ns := 0, nn := 0, ds := 0, dn := 0 sem mutex := 1, s := 0, n := 0
southEnter() { P(mutex);
// need mutual exclusion
// cars going north, better block
// increment number of delayed cars going south // release mutual exclusion
// block on south semaphore
}
}
if (nn > 0) { ds++;
V(mutex); P(s);
}
ns++;
if (ds > 0) {
ds−−; V(s);
}
// south going, record this
// other delayed southbound cars, let them in
// one fewer delayed southbound car // actually let south car go
// no southbound cars waiting, release mutex
else V(mutex);
southExit() { P(mutex);
// need mutual exclusion ns−−; // one southbound car off bridge
if (ns == 0 and dn > 0) { // last south car, north car waiting, let it go
dn−−; V(n);
else V(mutex);
// one fewer delayed north car // actually let north car go
// release mutual exclusion
3
}
6. Critical Section Problem Part (A)
This could lead to deadlock, given that flag[0] and flag[1] could both be true and therefore cause both threads to spin indefinitely. This is the same situation as in Attempt #2 from the notes. Additionally, it will have unnecessary delay if one thread exits in the same way as Attempt #1 from the notes.
Part (B)
Here, both flag variables would always be false, which clearly leads to two threads in the critical section whenever both want to enter the critical section.
Part (C)
This causes unnecessary delay if either thread exits in non-critical section code.
Part (D)
This allows (potentially) two threads in the critical section. Specifically, if T0 first sets turn to 0, it is allowed in the critical section; later, while T0 is in the critical section, if T1 sets turn to 1, it is also allowed in the critical section.
4