Log In
32 votes

Consider the procedure below for the Producer-Consumer problem which uses semaphores: 

semaphore n = 0; 
semaphore s = 1; 
void producer() 
void consumer() 

Which one of the following is TRUE?

  1. The producer will be able to add an item to the buffer, but the consumer can never consume it.
  2. The consumer will remove no more than one item from the buffer.
  3. Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
  4. The starting value for the semaphore $n$ must be $1$ and not $0$ for deadlock-free operation.
in Operating System
edited by

How people are deciding here "n" is a counting semaphore and "s" is a Binary Semaphore.It is nowhere mentioned in the question.

Producer can produce multiple items without consumer consuming it. So say producer produces 3 items, it means n = 3. Now consumer can consume each item one by one, so here n acts as a counting semaphore.
For option D, at any instant of time lets say there are 4 items in the Buffer and consumer consumed all for and gets blocked while remove_item from the buffer and now producer wakes up and wants to produce but it can not perform down(S) So both will be in a deadlock.

Either buffer is empty from the start or afterwards, deadlock can happen.
You are saying that consumer gets blcked while removing item from buffer and then process switch to producer .

Producer will not be able to execute due to wait(s) in beginning but there would be no issue in executing customer as it is only increasing value of s.

So this scenario is wrong for considering it a deadlock .


Deadlock happens when consumer tries to remove more than one item in a set with only one elements.

It is not explicitly given that it is a counting semaphore, but its intituitive.

option C says that “when buffer is empty” this means two things→

  1.  The first operation is consume.
  2.  Equal number of produce and consume has been performed and now the buffer is empty and we are consuming again.

If we simulate consumer(), when the buffer is empty,

S=1  N=0

semWait(s) →  s=0 

(means the next time we do semWait(s) the value of s will become <0 and the process will be put to sleep, however s=0 as of now so we can continue our execution)

semWait(n) → n=-1

(means the value of n has become <0 so we need to put consumer process to sleep)

Switching over to producer we encounter,

serWait(s) → s=-1

(since s<0 we must put the producer to sleep)

Both the producer and consumer are blocked so it is a Deadlock.

3 Answers

70 votes
Best answer
  1. False : Producer $=P$ (let), consumer $= C$(let)  , once producer produce the item and put into the buffer. It will up the $s$ and $n$ to $1$, so consumer can easily consume the item. So, option (A) Is false.
    Code can be execute in this way: $P :1 \ 2 \ 3 \ 4 \ 5| \ C: 1 \ 2 \ 3 \ 4 \ 5$. So, consumer can consume item after adding the item to buffer.
  2. Is also False, because whenever item is added to buffer means after producing the item, consumer can consume the item or we can say remove the item, if here statement is like the consumer will remove no more than one item from the buffer just after the removing one then it will be true (due $n=0$ then, it will be blocked ) but here only asking about the consumer will remove no more than one item from the buffer so, its false.
  3. is true , statement says if consumer execute first means buffer is empty. Then execution will be like this.
    $C:1$ (wait on s, $s=0$ now) $2$$($BLOCK $n =-1$$)$ |P : $1$ $2$ (wait on $s$ which is already $0$ so, it now block). So, $c$ wants $n$  which is held by producer or we can say up by only producer and $P$ wants $s$, which will be up by only consumer. (circular wait ) surely there is deadlock
  4. is false,  if $n=1$ then, also it will not free from deadlock.
    For the given execution: $C: 1 \ 2 \ 3 \ 4 \ 5 \ 1 \ 2$(BLOCK) $| P: 1 \ 2$(BLOCK) so, deadlock.
    (here, $1 \ 2 \ 3 \ 4 \ 5$ are the lines of the given code)

Hence, answer is (C)

1 flag
edited by
I cant see how your sequence for option D is correct: P : 1 2 3 4 5 | C: 1 2 3 4 5 1 2(BLOCK) | P: 1 2(BLOCK) Please tell me if am wrong in executing this as below. First thing I am not able to execute consumer's 2nd statement in 2nd pass as it gets blocked in 1st statement itself. Second thing, after executing 2nd statement of producer in 2nd pass does not blocks it. I mean system is still deadlock free after executing sequence you stated. @Arjun sir, am I wrong here?

Yes, you are correct. I have updated the sequence. See now..
option (b) explanation is confusing me, it is that Consumer cant be invoked consecutively??! and so false?


what has to be there to make it true, "" the words used in above explanation are confusing
@Nit9 please execute consumer process then here define S=1 and N=0 then check it will set S=0 and N=0 and then go to Producers process s=0 then it will create a dead lock.
@Sonam Vyas

I could not understand why Option B is not correct. Please elaborate more.
see , option b says consumer can not consume more than 1 data item which is false

this is like ... i execute producer code 2 time means after this n=2 and s=1 , now i will execute consumer code line 1 2 (s=0) 3(n=1)4 5(s=1), again execute consumer code 1 2 (s=0)3 (n=0) 4 5 (s=1) consumer consumed 2 data item ...
Consumer can consume more than one item BUT not consecutively. It can consume again only after producer produces.
if suppose the producer executes its code 2 times .
So, 2 items will  be stored in the buffer .

and the value of n is 2.

now when the consumer executes removeFromBuffer() then if it consumes all the item in the buffer at once(let us assume) then the buffer will be empty.but the value of n will still not be  0.
Now if the consumer again tries to access the buffer it will be able to access the buffer.And this will be an error as nothing is present in the buffer.

Am I correct?
Another question:
here are we assuming that the function removeFromBuffer()
has a condition that handles the case where "the buffer is empty and the consumer still tries to access it ."

@Arjun Sir pls help here..check the seq for option c

C:12 | P:1

Here C holds S and is waiting for N

P is blocked as S=0. No cycle is forming then how can we say it's a deadlock. We may call it a deadlock because infinite waiting is possible but not because of a circular wait.


I think the correct explanation for Option B is as below. Let me know if there is any mistake here.

In the question it has been given that s and n are semaphores i;e they are counting semaphores.

Because of this n can take values 0,1,2,.....

Consider the procedure below for the Producer-Consumer problem which uses semaphores

So, it is possible for producer to produce multiple items in succession and it is also possible for the consumer to consume multiple items in succession.

P:1 2 3 4 5 | P:1 2 3 4 5 | C:1 2 3 4 5 | C:1 2 3 4 5


In the question it has been given that s and n are semaphores i;e they are counting semaphores.

you cant say they are counting semaphore. It is not mentioned properly in question.

Unless mentioned isn't the semaphore by default counting semaphore? Binary semaphore itself is counting semaphore bounded b/w 0 and 1.
Can anyone explain option a?producer can go on producing without giving any chance to consumer to consume the option a also is true in my opinion.can anyone explain what is wrong with this logic
8 votes
answer is C as when consumer  first acess the semaphore S it will down (s)  but for semaphore(n) , it has to wait for  producer to make it 1 but as for producer it can't acess the critical section b'coz semWait(s) is zero .
so it will cause deadlock
5 votes
Initially, there is no element in the buffer.
Semaphore s = 1 and semaphore n = 0.
We assume that initially control goes to the consumer when buffer is empty.
semWait(s) decrements the value of semaphore ‘s’ . Now, s = 0 and semWait(n) decrements the value of semaphore ‘n’. Since, the value of semaphore ‘n’ becomes less than 0 , the control stucks in while loop of function semWait() and a deadlock arises.
Thus, deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.

Related questions

55 votes
3 answers
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________
asked Sep 28, 2014 in Operating System jothee 11.6k views
34 votes
5 answers
Three processes $A$, $B$ and $C$ each execute a loop of $100$ iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU milliseconds and then initiates a single I/O operation that lasts for $t_{io}$ ... uses a time slice of $50$ milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.
asked Sep 28, 2014 in Operating System jothee 5.3k views
43 votes
4 answers
A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is $4$ bytes in size. Given a $100 \times 10^6$ bytes disk on which the file system is stored and data block size is $10^3$ bytes, the maximum size of a file that can be stored on this disk in units of $10^6$ bytes is _________.
asked Sep 28, 2014 in Operating System jothee 9.6k views
62 votes
10 answers
A computer has twenty physical page frames which contain pages numbered $101$ through $120$. Now a program accesses the pages numbered $\text{1, 2, ..., 100}$ in that order, and repeats the access sequence THRICE. Which one of the following page ... faults as the optimal page replacement policy for this program? Least-recently-used First-in-first-out Last-in-first-out Most-recently-used
asked Sep 28, 2014 in Operating System jothee 14.7k views