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

max 19 processes can be in CS as this question.

---

Final value  = initial value -  Newly Blocked processes + Newly Unblocked processes
if final value <0 process blocked
if final value => 0 processes unblocked

---

Let the initial vaue of S be x 

it is given that s is non negative means 

x - 20(P operations ) + 12 (V opeartions ) >= 0

x - 8 >= 0  , x >= 8 (for x greater than equal to 8 non of the P opearations will be blocked 

therefor x=7 there will be atleast 1 P operation will be blocked 

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!

Comments

nice intution

---

Yes perfect, -20 +12 = -8     and we need atleast one blocked means atleast one -1

Hence, -8 + x = -1
                    x = -1 + 8
                    x = 7

But if they had said that atleast one process should be free or not blocked 
then         min = 8

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

Answer 5

The largest initial value of SS for which at least one P(S)P(S) operation will remain blocked is ..

"that means largest value of "S" in which one operation is in suspended list

so S=20-12-1=7 in which one operation is in suspended list

Comments

good

Answer 6

After performing down operation if the process is getting suspended then it is called unsuccessful down operation .The down operation of the counting semaphore is successful if the initial value of semaphore s>=1.For 1 process to be in suspended list after subsequent p and v operations the value should be equal to -1 .So,
S-20+12=-1
So,S=7