Question

Consider the two functions incr and decr below. Five threads each call incr once and three threads each call decr once on the same shared variable \(X\) (initially \(10\)). There are two semaphore implementations:

I-1: \(s\) is a binary semaphore initialized to \(1\).
I-2: \(s\) is a counting semaphore initialized to \(2\).

Let \(V_1, V_2\) be the values of \(X\) at the end of all threads for I-1 and I-2, respectively. Which choice gives the minimum possible values of \(V_1, V_2\)?

incr(){              
  wait(s);           
  X = X + 1;         
  signal(s);         
}

decr(){
  wait(s);
  X = X - 1;
  signal(s);
}

• A. 15, 7
• B. 7, 7
• C. 12, 7
• D. 12, 8

Hint:

With a counting semaphore \(=2\), at most two threads race at once. The best way to minimize the final value is to let each decrement overwrite a concurrent increment (making a pair worth \(-1\)), and make the leftover increments collide with each other (worth \(+1\)). You cannot reduce all five increments because only three decrements exist and at most two threads can overlap at any instant.

Answer 1

The Correct Option is D

Step 1: I-1 (binary semaphore \(s=1\))
Binary semaphore enforces mutual exclusion; each update to \(X\) is atomic.
Net effect \(=\) \(5\) increments and \(3\) decrements \(= +2\).
So the final value is \(V_1 = 10 + 2 = 12\).
Step 2: I-2 (counting semaphore \(s=2\)) — race possible
At most two threads may be in the critical section simultaneously. Lost-update patterns can occur:
\(\bullet\) inc\(+\)inc overlap: both read the same \(v\), both write \(v+1\) \(\Rightarrow\) net \(+1\) instead of \(+2\) (lose one increment).
\(\bullet\) inc\(+\)dec overlap (dec last): both read the same \(v\); if the decrement writes last, final is \(v-1\) \(\Rightarrow\) net \(-1\) instead of \(0\).
\(\bullet\) dec\(+\)dec overlap: both read \(v\), both write \(v-1\) \(\Rightarrow\) net \(-1\) instead of \(-2\) (this hurts minimization, so we avoid it).
To minimize \(X\): pair each of the \(3\) decrements with an increment (schedule decrement’s write last) to get three \(-1\) effects. That uses \(3\) increments and \(3\) decrements.
The remaining \(2\) increments can overlap with each other to yield only \(+1\) (rather than \(+2\)).
Hence the minimum total change is \(-1-1-1 + 1 = -2\).
Therefore \(V_2 = 10 - 2 = 8\).
\[ \boxed{(V_1,V_2) = (12,8)} \]