GATE IT 2006 | Question: 55

Question

Consider the solution to the bounded buffer producer/consumer problem by using general semaphores $S, F,$ and $E$. The semaphore $S$ is the mutual exclusion semaphore initialized to $1$. The semaphore $F$ corresponds to the number of free slots in the buffer and is initialized to $N$. The semaphore $E$ corresponds to the number of elements in the buffer and is initialized to $0$.
$$\small \begin{array}{|l|l|}\hline \textbf{Producer Process}  &  \textbf{Consumer Process}  \\\hline  \text{Produce an item;} & \text{Wait(E);} \\  \text{Wait(F);} & \text{Wait(S);} \\  \text{Wait(S);} & \text{Remove an item from the buffer;} \\\text{Append the item to the buffer;} & \text{Signal(S);} \\ \text{Signal(S);} & \text{Signal(F);} \\ \text{Signal(E);} & \text{Consume the item;} \\\hline \end{array}$$
Which of the following interchange operations may result in a deadlock?

1. Interchanging Wait $(F)$ and Wait $(S)$ in the Producer process
2. Interchanging Signal $(S)$ and Signal $(F)$ in the Consumer process

• A. (I) only
• B. (II) only
• C. Neither (I) nor (II)
• D. Both (I) and (II)

Comments

Here is the explanation for option 1 : 

---

how it is possible that f=0 in this question every prodeced item is consumed by consumer befor next production. right so if i produced 1 item and add to buffer agan if i want to produced next item insted of consuming it i am not able to produced due to no of free slot that are now n-1....how this term is 0
i am not able to understand    @DEEPAK_POONIA sir  @Shaik Masthan sir

---

every prodeced item is consumed by consumer befor next production

Why this to be true ? In the question it is not mentioned. 

So, there is a chance that first producer runs and produce all the items. After that, consumer come in picture.

Answer 1

Suppose the slots are full $\rightarrow F = 0 $ . Now, if Wait($F)$ and Wait$(S)$ are interchanged and Wait$(S)$ succeeds, The producer will wait for Wait$(F)$ which is never going to succeed as Consumer would be waiting for Wait$(S)$. So, deadlock can happen.

If Signal$(S)$ and Signal$(F)$ are interchanged in Consumer, deadlock won't happen. It will just give priority to a producer compared to the next consumer waiting. 

So, answer (A)

Comments

@Arjun sir how can we suppose that the buffer is FULL?? in the question F represents number of empty slots which is equal to N.  The condition should be written as 

1. Interchanging Wait (F) and Wait (S) in the Producer process will result in deadlock IF THE BUFFER  IS FULL. in this case it should be correct?

---

@Abhinnsoni Yes,you are correct but note that in the question it is being mentioned “MAY result in a deadlock”.

---

ONLY Interchanging Wait (F) and Wait (S) in the Producer process
 

Or ONLY Interchanging Wait (F) and Wait (S) in the Consumer  process.. or interchanging both together may Lead to Deadlock

Answer 2

To be more clear I will edit Arjun Sir answer a bit

Suppose the slots are full -> F = 0. Now, if Wait(F) and Wait(S) are interchanged and Wait(S) succeeds first, The producer will try to execute  Wait(F) which is never going to succeed as the buffer is full and no more item can be added to buffer.

As the Value of S is zero  Consumer would be trying to execute Wait(S) again which will never happen as remainder section of producer will not be executed (i.e Signal(s))).As the buffer is full consumer will never be able to consume the item as Semaphore variable S is occupied by producer So, deadlock can happen.

If Signal(S) and Signal(F) are interchanged in Consumer, deadlock won't happen. It will just give priority to a producer compared to the next consumer waiting. 

So, answer (A)

Comments

@vupadhayay ,can u please give an example of this statement

"If Signal(S) and Signal(F) are interchanged in Consumer, deadlock won't happen. It will just give priority to a producer compared to the next consumer waiting"

---

Can anyone explain how  Signal(S) and Signal(F) are interchange is giving priority to producer compared to the next consumer waiting ... ?

---

When producer do wait (s) it reduce the Value and prevent consumer to access now to access consumer producer need to increment s first so it give signal and consumer wake up see if sinnal (s) run in consumer first then consumer gets the priority but here producer get when interchange

---

Nilabja Sarkar Producer has to execute first and produce something for the consumer. you can't say producer has priority over the consumer. It has to happen.

---

I Need some clarification

even without inter-changing, the system would be in a deadlock , for the case F=0 (all slots are full)  ??

---

No it won't be in deadlock state if S and F are not interchanged for first case as here producer and consumer both have equal chances of taking over S.

---

your answer is better than arjun sir's answer

Answer 3

Interchanging Wait (F) and Wait (S) in the Producer process

Or  Interchanging Wait (F) and Wait (S) in the Consumer  process..WILL Lead to Deadlock

Comments

Please, could anyone explain it a little more brief..!?

Answer 4

Here is how a P() operation can be implemented.

Now, here's how a V() operation can be implemented.

As you can see, only in the implementation of the P() operation, a process can get blocked.

V() doesn't block processes, but rather generates a wakeup signal that unblocks the processes blocked by the P() operation. (Whether or not these newly unblocked processes immediately start running is dependent on scheduling)

 

PS: Please note that P() and V() are atomic operations, and we use techniques like compare.and.swap() or spinlock to enforce atomicity (We don't take hardware support, as semaphores are purely a software solution)

---

Switching the order of V() operations can never result in deadlock (because processes won't be blocked). It might prioritize one process over another or cause timing errors if used in the "wrong" order, though.

Hence, Statement II can't be correct. (In fact, it won't be correct in any context)

 

Switching carefully selected order of P() operations might result in a deadlock.

Statement I can cause a deadlock. I'll prove how.

Put N = 1.

Now, let the producer run once.

Now let the producer and consumer run in an interleaved manner. They both will get blocked. So, deadlock.

 

Option A

Answer 5

Case:2 interchanging the  signal(S) and Signal(F) will just give priority by waking up a producer to produce the item into the buffer slot.

And case:1 is explained here hope you get that..

Comments

Good Answer

 

Answer 6

Here, the signal exchange ie., V() exchange never causes any issue so we can ignore it conveniently but for the wait ie., P() we know that it can cause issues so we will have to cehck it here we see that F corresponds to empty slots which is 'N' intially while E is 0 and S is also 1.

Now, for F=N we can be rest assured as no deadlock can happen as only the producer process takes place but incase of F=0 and E=N we see that in producer process first is P(S) then only there is P(F) while incase of consumer process it is P(E) followed by P(S) which means here producer can get stuck after P(S), which will make S=0 which means that the consumer also will be stuck as it can cross P(E) but it can't process P(S) now as it will be S=0 which means it iwll be blocked there.

As we can see both the process are blocked causing deadlock here.

Hence option (A) is the answer