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

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

@Arjun sir  @srestha @rohith1001 what happens when producer never intends to produce consumer is starving right he is not stopping anyone directly but he is becoming the cause of starvation and there will be no progress

---

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.

 

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

@Bikram Sir option B is looking also write when consumer does not consume x or relished s, then producer get block it is also Starvation.

---

@ 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.

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