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

The following solution to the single producer single consumer problem uses semaphores for synchronization.

#define BUFFSIZE 100
buffer buf[BUFFSIZE];
int first = last = 0;
semaphore b_full = 0;
semaphore b_empty = BUFFSIZE

void producer()
{
while(1) {
    produce an item;
    p1:.................;
    put the item into buff (first);
    first = (first+1)%BUFFSIZE;
    p2: ...............;
    }
}

void consumer()
{
while(1) {
    c1:............
    take the item from buf[last];
    last = (last+1)%BUFFSIZE;
    c2:............;
    consume the item;
    }
}
  1. Complete the dotted part of the above solution.

  2. Using another semaphore variable, insert one line statement each immediately after $p1$, immediately before $p2$, immediately after $c1$ and immediately before $c2$ so that the program works correctly for multiple producers and consumers.

asked in Operating System by Veteran (59.6k points)
edited by | 1.2k views
+1

@arjun sir, Plz help.

Suppose 
semaphore b_full = 0;
semaphore b_empty = 0.

We can also make use of first and last variable to check whether the buffer is full or empty. The buffer array is a circular queue. And we declare queue is full with (n - 1) elements.

p1: If ( (first + 1) == last )   P(b_full);  // Now producer can't produce more, buffer is full.

p2: If ( (last + 1) == first )   V(b_empty);  // Producer has produced one item and consumer is free to consume it.


c1: If ( first == last )  P(b_empty); // Buffer is empty consumer can't consume more.

c2: If ( ( first + 1 ) != last )  V(b_full); // Now buffer is not fulled, producer is free to produce the item.

+1

First: it tells the slot, where producer can insert an item.
Last: it tells the slot no., from where consumer can start consuming an item.

The condition you have put is not correc! 
for example buffer[0 ...  99] and last=0 and first=99 now fIrst+1 = last, 99+1 !=0 though buffer is full but condition is failed.
you have to use the following condition:
   If ( (first + 1) mod buffersize == last )   then buffer is full.

p2: If ( (last + 1) == first )   V(b_empty); 
what if producer produces many items back to back. there are many wrong things with this solution in case of full buffer you are doing P(b_full) while t shoulld be P(b_empty)
 

1 Answer

+16 votes
Best answer

a) In Producer Consumer problem Producer produce item and makes the buffer full and after that Consumer consumes that item and makes the buffer empty   

Here b_empty and b_full are two semaphore values

p1: P(Empty) 

means, Producer have to wait only if buffer is full and it waits for consumer to remove at least one item. (See, Empty being initialized to BUFFSIZE)

p2: V(Full)

buffer is filled, now it gives signal to consumer that it can start consuming

c1: P(Full)

means here consumer have to wait only if buffer is empty, and it waits for Producer to fill the buffer

c2: V(Empty)

Now buffer is empty and Empty semaphore gives signal to the producer that it can start filling

It is same as giving water to a thirsty man.

Here u are giving water in a glass to that thirsty man, so u are producer here

and the man drinks and makes the glass empty, so he is consumer here

b) If there are multiple user we can use mutex semaphore, so that exclusively one could enter in Critical section at a time. i.e.

p1:P(Empty)
   P(mutex)

p2:V(mutex)
     V(Full)    

c1:P(Full)
    P(mutex)

c2: V(mutex)
     V(Empty)

PS: One thing to see is P(mutex) is after P(Full) and P(empty)- otherwise deadlock can happen when buffer is full and a producer gets mutex or if buffer is empty and a consumer gets mutex.

answered by Veteran (98.4k points)
edited by
+1
answer is correct. But explanation is not. Actually producer wait "only if buffer is full". Similarly consumer waits "only if buffer is empty". Even if there is one slot producer produces and even if there is one item, consumer consumes.
+1
ok,done sir
0

One thing to see is P(mutex) is after P(Full) and P(empty)- otherwise deadlock can happen when buffer is full and a producer gets mutex or if buffer is empty and a consumer gets mutex.

Plz explain this part

@Srestha

+1
what will happen even if multiple producer or consumer accesses the buffer?? why is mutex required. The semaphores full and empty can take care of the synchronization problem. I know is wrong. can u explain the need of mutex here?? what wrong can happen in its absence??
+3
@sushmita

the semaphores Empty and Full are only used to keep tracking of full and empty condition of buffer i.e consumer cannot consume if there is no item and producer cannot produce when the buffer is full....

as we know buffer is in shared mode..therefore there has to be a semaphore which will allow producer nd consumer to access the buffer in mutual exclusive manner or multiple producer and consumer to be accessing the buffer at a same time in mutual exclusive manner,otherwise leads to possibility of inconsistency..
0

P1:

while(b_full==BUFFSIZE);

Wait(b_empty);

P2:

Signal(b_empty)

C1: 

While(b_empty==BUFFSIZE);

Wait(b_full);

C2:

Signal(b_empty);

srestha Why you did not consider Buffer full and Empty case for Producer and Consumer resp.?

Please comment on my given solution.

+1
we just have to add 1 line in blank space

Not more than one line is allowed I think

Though ur code is also correct, but that doesnot make any difference in meaning of the code
0
It is a bounded buffer problem

We assume that the pool consists of n buffers.mutex semaphore provides ME for access to the buffer pool and initialize to the value 1. The empty and full semaphore count the number of empty and full buffers.The semaphore empty is initialize to value n and semaphore full is initialize to value 0
0
Yeah got it :)
0

@sushmita

Let P1 and P2 be two processes trying to produce item.

L1:while(1) {
L2:    produce an item;
L3:    P(b_empty);
L4:    put the item into buff (first);
L5:    first = (first+1)%BUFFSIZE;
L6:    V(b_full);
L7:    }

Now let P1 execute L3 and L4. So it puts item at first=0. Now P1 pre empts. P2 comes, produces an item executes L2 and L3 and again puts the item at buff(first) i.e. at 0th position replacing the P1's product. To avoid this we have to put a lock so that "first" is updated after any process puts an item and before any other process places it's item.

 

0
Can someone explain why we using first and last variable here? Is it to enter the produced item at appropriate location?

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

40,903 questions
47,560 answers
146,291 comments
62,306 users