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.

Su

Question

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?

Accepted Answer

12, 7. The correct option is 12 for V1 because with a binary semaphore, only one thread can modify X at a time, allowing for all increments to occur before any decrements, resulting in 10 + 5 - 3 = 12. For V2, the counting semaphore allows two threads to access X simultaneously, but even with this concurrency, the maximum value achievable after all operations is 10 + 5 - 3 = 12, but the minimum possible value is 7 due to potential interleaving of operations.

Solution

Related GATE Technical questions