The GATE Grind

GATE 2021 CS – Question 56

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

Consider the following pseudocode, where S is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic.

1. int counter = 0;
2. Semaphore S = init(5);
3. void parop(void)
4. {
5.     wait(S);
6.     wait(S);
7.     counter++;
8.     signal(S);
9.     signal(S);
10.}

If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?

  1. The value of counter is 5 after all the threads successfully complete the execution of parop.
  2. The value of counter is 1 after all the threads successfully complete the execution of parop.
  3. The value of counter is 0 after all the threads successfully complete the execution of parop.
  4. There is a deadlock involving all the threads.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) The value of counter is 5 after all the threads successfully complete the execution of parop.; (B) The value of counter is 1 after all the threads successfully complete the execution of parop.; (D) There is a deadlock involving all the threads.

Explanation

Serial execution gives 5, and racy non-atomic increments can lose updates, giving 1 (but not 0, since every thread increments at least once). If each thread does one wait(S), all 5 units are taken and every thread blocks on its second wait, a deadlock.