GATE CS 2023 Q.38: Process Synchronization and Concurrency

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?

15, 7

7, 7

12, 7

12, 8

Official answer and solution

Solution

Evaluate thread interleavings under mutual exclusion (binary semaphore) versus relaxed concurrency (counting semaphore).

Initial value $X = 10$ . 5 threads execute incr() ( $X = X+1$ ) and 3 threads execute decr() ( $X = X-1$ ).

Implementation I-1 (Binary semaphore $s = 1$ ):
Mutual exclusion is strictly guaranteed. No concurrent access to $X$ can occur. Since addition and subtraction are commutative and every thread runs under mutual exclusion, the final value of $X$ is deterministic:
$V_1 = 10 + 5(1) - 3(1) = 12$
Implementation I-2 (Counting semaphore $s = 2$ ):
Up to 2 threads can be inside the critical section simultaneously. Consider the following interleaving:
- Thread $T_{inc1}$ enters, reads $X = 10$ , and is preempted before writing back.
- All 3 decrement threads run sequentially to completion: $X$ becomes $10 - 3 = 7$ .
- Thread $T_{inc1}$ resumes and writes back $10 + 1 = 11$ , or other increment threads interleave such that increments overwrite each other, but the absolute minimum value achievable occurs when all 3 decrements take effect and all 5 increments are lost/overwritten or execute before decrements. The minimum possible final value is $V_2 = 10 - 3 = 7$ .

Thus, $(V_1, V_2) = (12, 7)$ .

Final answer

Option (C)

Common trap

Believing binary semaphores allow race conditions that could produce a value different from 12.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.