Consider the two functions incr and decr shown below. incr(){ wait(s); X =…
2023
Consider the two functions incr and decr shown below.
incr(){
wait(s);
X = X+1;
signal(s);
}
decr(){
wait(s);
X = X-1;
signal(s);
}
There are 5 threads each invoking incr once, and 3 threads each invoking decr once, on the same shared variable X. The initial value of X is 10.
Suppose there are two implementations of the semaphore s, as follows:
I-1: s is a binary semaphore initialized to 1.
I-2: s is a counting semaphore initialized to 2.
Let V1, V2 be the values of X at the end of execution of all the threads with implementations I-1, I-2, respectively.
Which one of the following choices corresponds to the minimum possible values of
V1, V2, respectively?
Answer: C. 12, 7 — Key insight: the binary semaphore (mutex) serializes all updates; the counting semaphore with value 2 allows at most two threads in the critical section,…
- A.
15, 7
- B.
7, 7
- C.
12, 7
- D.
12, 8
Attempted by 80 students.
Show answer & explanation
Correct answer: C
Key insight: the binary semaphore (mutex) serializes all updates; the counting semaphore with value 2 allows at most two threads in the critical section, which can cause pairwise races and lost updates.
Binary semaphore (initialized to 1):
The mutex ensures one thread at a time executes X = X + 1 or X = X - 1 without interference.
All five increments and three decrements are applied exactly once, so final X = 10 + 5 - 3 = 12.
Counting semaphore (initialized to 2):
At most two threads may be in the critical section at once, so races can occur only between pairs of threads.
Each two-thread race can change the final result by at most 1 compared with serialized execution (for example, two increments racing can produce +1 instead of +2; an increment and a decrement racing can produce −1 instead of 0 if the decrement wins).
With 8 operations total, you can schedule at most four disjoint two-thread races. To minimize final X, make three races each between an increment and a decrement where the decrement wins (losing 1 each compared to serialized), and make the remaining race between two increments (losing 1).
That yields a total reduction of 4 relative to the serialized result 12, so the minimum final X = 12 - 4 = 8.
Answer (minimum possible values): V1 = 12, V2 = 8.