GATE - 2016 | OS | Consider a non-negative counting semaphore S. The operation P(S)

GATE - 2016 [Operating System]

Question:

Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations, and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is _________.

A	7
B	8
C	9
D	10

     

Solution:

Option (A) is Correct.

We can assume the largest initial value of S for which at least one P(S) operation → X
P(S) operation remains in the blocked state therefore it will -1.
The negative value of the counting semaphore indicates the number of processes in the suspended list (or blocked).
Take any sequence of 20P and 12V operations, at least one process will always remain blocked.
So, X - 20 + 12 = -1
Here P(S) = 20 and V(S) = 12
X = 7

Thank You