GATE 2023 CS – Question 38
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) 12, 7
Explanation
**I-1: binary semaphore (value 1).** Only one thread is in the critical section at any time, so no update is lost. Final value $=10+5-3=12$ regardless of order. So $V_1=12$.
**I-2: counting semaphore initialised to 2.** Two threads can be inside the critical section together, so a read-modify-write can interleave. For example, a thread running `X = X+1` reads 10 while another thread reads 10 and then writes 9 (`X = X-1`). The first then writes 11, losing the decrement.
To get the **minimum**, we want the decrements to take effect and the increments to be lost. All three decrements applying while every increment is overwritten gives $10-3=7$. It cannot go lower, since only decrements reduce the value and there are only three of them.
$V_2^{min}=7$. Answer: (12, 7), option (C).