GATE IT 2008 | Question: 53

Question

The following is a code with two threads, producer and consumer, that can run in parallel. Further, $S$ and $Q$ are binary semaphores quipped with the standard $P$ and $V$ operations.

semaphore S = 1, Q = 0; 
integer x;

producer:                   consumer:
while (true) do             while (true) do
    P(S);                       P(Q);
    x = produce ();             consume (x);
    V(Q);                       V(S);
done                        done

Which of the following is TRUE about the program above?

• A. The process can deadlock
• B. One of the threads can starve
• C. Some of the items produced by the producer may be lost

• D. Values generated and stored in '$x$' by the producer will always be consumed before the producer can generate a new value

Comments

so in simple words,(d) means,

consumer will consume the produced item after that only producer will produce next item.

---

#easy solution

https://gateoverflow.in/3363/gate-it-2008-question-53?show=417148#a417148

---

Here, if the cs is empty and consumer process wants to enter into cs, then it cannot enter. This is because initially q=0 and it will get stuck in the while loop. So there is no progress. Bounnded waiting is satisfied because of strict alteration. For the system to be starvation free both progress and bounded waiting shold be satisfied. So one of the threads may starve. Then why option b cannot be true?

 

---

Ans - (D)

Here the S=1 and Q=0. Then when you want to run producer and consumer code, consumer stucked and producer works. When producer enter the critical section it makes the value of S=0 and produced.Before leaving the code, it makes the value of Q=1. Now again if producer and consumer both want to enter the critical section, producer stucked and consumer enter inside the code.Now the Q=0 and consumer consume product. Before leaving, it makes S=1.So this way producer make 1 product and consumer consume the product. Before consuming the product, producer can't produce another product and before producing a product , the consumer can't consume a product.So this condition is also called Strict Alteration.

 

Answer 1

Producer: consumer: while (true) do while (true) do $1$ $P(S)$; $1$ $P(Q)$; $2$ $x =$ produce $()$; $2$ consume $(x)$; $3$ $V(Q)$; $3$ $V(S)$; done done

Lets explain the working of this code.

It is mentioned that $P$ and $C$ execute parallely.

$P:1 2 3$

1. $S$ value is $1$, down on $1$ makes it $0$. Enters the statement $2$.
2. Item produced.
3. Up on $Q$ is done (Since the queue of $Q$ is empty, value of $Q$ up to $1$).

This being an infinite while loop should infinitely iterate.

In the next iteration of while loop $st 1$ is executed.

But $S$ is already $0$, further down on $0$ sends $P$ to blocked list of $S.P$ is blocked.

$C$ Consumer is scheduled.

Down on $Q.$ value makes $Q.$value$=0$;

Enters the statement $2$, consumes the item.

Up on $S$,now instead of changing the value of $S$. value to $1$, wakes up the blocked process on Q 's queue.Hence process P is awaken. $P$ resumes from statement $2$, since it was blocked at statement $1$. So, $P$ now produces the next item.

So, consumer consumes an item before producer produces the next item.

(D) Answer

(A) Deadlock cannot happen has both producer and consumer are operating on different semaphores (no hold and wait )

(B) No starvation happen because there is alteration between $P$ and Consumer. Which also makes them have bounded waiting.

Comments

No @svas7246 that’s not the correct way to analyze, as strict alteration is possible , hence starvation is not possible. Bounded waiting guaranteed.(1-bound)

---

@srestha

This is a strict alternation problem → so progress is fail . Bounded wait is guaranteed.

Also no starvation because only 2 process(producer & consumer) acting on this and this is alternating system.

 

---

This is a strict alternation problem & even if buffer size is 1 then also no overflow

Answer 2

D Consumer can consume only once the producer has produced the item, and producer can produce(except the first time) only once the consumer has consumed the item.

Comments

@ Brij Mohan Gupta 

No , option B can not possible.. as No starvation happen in our given code snippet,

  Because there is alteration between Producer  and Consumer.

Which also makes them have bounded waiting possible.

---

Thanks @Bikram sir.

---

@Bikram we are saying here that starvation is not possible. But there is this similar ques

https://gateoverflow.in/3788/gate-it-2005-question-41
here it was answered that both process can starve by the same logic as this ques one can also argue that here also no startvation or vice versa?

 

Answer 3

Hence option D  

________________

As we can see the code ,  the semaphore value of S=1 , Q=0 , then firstly producer will run then it will down S and then goes to critical section then up  Q .

there is a STRICT ALTERATION in the codes .

we see that producer will not produce more as after producing the item , then  consumer will consume .

if strick alteration then no dead lock and no starvation possible every process will get chance

Note :

even  if buffer size is 1 then also no overflow 
------------------------------------------------------

 

Don’t Forgot To Upvote

Answer 4

Producer can't decrement the Entry point of the consumer and vice-versa. So, no deadlock. Option A eliminated.

Producer holds the V operator of the consumer, and consumer holds the V operator of the producer. Both can't starve; in fact there's strict alteration. Option B eliminated.

Option C asks if producer can run twice consecutively (assuming there's no buffer, the most recent value would overwrite previous one). There's strict alteraton, so the answer is no. Option C eliminated.

Option D is correct; this is a proper working code of a one-item-only producer/consumer relationship.

Comments

@JashanArora can you please tell me why the “Producer can't decrement the Entry point of the consumer and vice-versa”

i am just thinking the reason might be they are threads,  so different s and q for both threads, but if they are global, then deadlock will occur for, but not sure of that

Answer 5

As we can see the code ,  the semaphore value of S=1 , Q=0 , then firstly producer will run then it will down S and then goes to critical section then up  Q . similarly , consumer will down Q and up S . so , we can see there is a STRICT ALTERATION in the codes . we see that producer will not produce more as after producing the item , then  consumer will consume . so , no overflow is there even if buffer size is 1 .

Hence option D .