GATE 2021 CS (CS1) – Question 56
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?
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
$S=5$; five threads each call `wait(S)` twice, increment `counter` (not atomic), then `signal(S)` twice.
- **(A) 5 is possible.** If threads run one after the other (or without harmful interleaving), all 5 increments take effect.
- **(B) 1 is possible.** Only a limited number of threads can be inside the critical part at once, but a thread can read `counter`, be descheduled, and write back an old value later. Example: thread $T_5$ reads 0 and stalls; threads $T_1$–$T_4$ run in turn and make `counter`$=4$; then $T_5$ writes $0+1=1$.
- **(C) 0 is impossible.** Every thread writes a value of at least 1.
- **(D) Deadlock is possible.** If every thread executes the first `wait(S)`, all 5 units are taken, and each thread then blocks at its second `wait(S)`. No one can proceed.
Answer: A, B, D.