edited by
13,235 views
38 votes
38 votes

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
  1. (I) only
  2. (II) only
  3. Neither (I) nor (II)
  4. Both (I) and (II)
edited by

5 Answers

Best answer
73 votes
73 votes

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)

edited by
16 votes
16 votes

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)

7 votes
7 votes

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

5 votes
5 votes

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

edited by
Answer:

Related questions

30 votes
30 votes
4 answers
2
Ishrat Jahan asked Oct 31, 2014
12,638 views
The arrival time, priority, and duration of the CPU and I/O bursts for each of three processes $P_1, P_2 $ and $P_3$ are given in the table below. Each process has a CPU ...
28 votes
28 votes
2 answers
3