GATE CSE 2016 Set 2 | Question: 49

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 _______

Comments

we are taking -1at rhs because semaphore is non_negative .when it reaches to -1 it voilets it's conditions and it is suspended.

---

because P(20) is incrementing so +20 and V(12) is decrementing so -12.

---

max 19 processes can be in CS as this question.

Answer 1

Answer: $(7)$. Take any sequence of $20P$ and $12V$ operations, atleast one process will always remain blocked.

Comments

Dekho if we think from back words

If s=8,then s-p(s)= 8-20= -12

An

-12 + v(s) = -12+12=0

Hence for one process to be blocked we need s max should be 7.

I.e. -13+12= - 1 ,one thread blocked

---

Can someone explain what is the meaning of "atleast one P(S) operation is blocked"?

---

for non-negative counting semaphore atleast one P(S) operation blocked means s<=-1

Answer 2

s-20+12<=-1

s<=7

Answer 3

If we get negative value then it must be in blocked state,

Nowwe have minimum -ve nummber is -1.

So, our equation will be S-20+12=-1 

So, S>7 for procees to be run successfully without blocked state!

Answer 4

Let us take a smaller example where P(S) = 5 and V(S) = 2, Now we need 2 more so that atleast one process will be blocked.So we can formulaize it as

Largest initial value of S so that atleast one get blocked = P(S) - V(S) = 1 + x and value of x is our answer.

here P(S) = 20 , V(S) = 12 

thus 20 - 12 = 1 + x

x=7 is answer