The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.6k views

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

semaphore n = 0; 
semaphore s = 1; 
void producer() 
{ 
    while(true) 
    { 
        produce(); 
        semWait(s); 
        addToBuffer(); 
        semSignal(s); 
        semSignal(n); 
    } 
} 
void consumer() 
{ 
    while(true) 
    { 
        semWait(s); 
        semWait(n); 
        removeFromBuffer(); 
        semSignal(s); 
        consume(); 
    } 
} 

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.
asked in Operating System by Veteran (105k points)
edited by | 2.6k views
0

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

4 Answers

+38 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)

answered by Boss (15.8k points)
edited by
+4
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?

+2
Yes, you are correct. I have updated the sequence. See now..
0
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
+1
@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.
+1
@Sonam Vyas

I could not understand why Option B is not correct. Please elaborate more.
+1
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) ...here consumer consumed 2 data item ...
+7 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
answered by (241 points)
+6 votes

..............

answered by Active (2.1k points)
edited by
+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.
answered by Loyal (8.6k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,491 questions
48,518 answers
154,897 comments
63,255 users