GATE CSE 2023 Q38: Minimum final X with binary vs counting semaphore

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?

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: C (official GATE 2023 final answer key)

Concept used: A binary semaphore gives mutual exclusion; a counting semaphore of 2 lets two threads race on X and lose updates.

First step: With I-1 every update takes effect: $10 + 5 - 3$ . With I-2, look for interleavings where increments are overwritten.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key