The GATE Grind

GATE 2023 CS – Question 38

Operating System · Concurrency and Synchronization · 2 marks · Multiple choice

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?

  1. 15, 7
  2. 7, 7
  3. 12, 7
  4. 12, 8

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 12, 7

Explanation

A binary semaphore gives mutual exclusion, so V1 = 10+5−3 = 12 always. A counting semaphore of 2 lets two threads race, causing lost updates. Losing increments in favour of decrements gives a minimum of 10−3 = 7.