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

@rahul sharma 5 @vupadhayay

"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"

I am not getting this, can u please explain? 

---

Interchange Wait(F) and Wait(S) in the Producer process.

Then run the producer and don’t let consumer have the access until you start the execution of the producer the second time. Here you will notice after using Wait(S), Wait(F) will be struct as F=0, presently even S = 0 because in the second iteration of producer Wait(S) have turned S to 0. Now consumer(in it’s first iteration itself) is also struct at Wait(S) after executing Wait(E). Hence, deadlock occurred. Hence, option A is correct.

---

Doubt :

if we read the question it says initially Free=n & Elements=0

and its a strict  alternation

 

therefore it can never make Free=0 & Elements=n

 

can someone pls help me with this

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

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.

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