The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.3k 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.7k points)
edited by | 1.3k 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)
 

0
see detailed explanation at the end of this page.

2 Answers

+18 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 (103k points)
edited by
+2
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?
0
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.

in the buffer(basically a queue) first will store produced item at rear node and last will remove or consume item at front node.
0 votes

In any PRODUCER-CONSUMER problem this 4 criteria must satisfy

(1)When a reader is reading, no writer must be allowed.
(2)Multiple readers should be allowed.
(3)When a writer is writing, no reader must be allowed.
(4)Multiple writers(more than 1) should not be allowed.

but here they are talking about only 1 producer-consumer & 

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


In the buffer(basically a queue) "first" will store produced item at rear node and "last" will remove or consume item from front node.

here 2 counting semaphores are used to keep track how much the buffer if empty or full they are b_full=0 ( means initially nothing in the buffer) & b_empty=100 (means initially empty cells in buffer is 100 or buffer is all empty)

now for P1 - Producer produced an item & he wants to insert into buffer but reader should not read meanwhile producer adding item to buffer but here no additional mutex is present for safety(so ignore it) now it downs the semaphore P(b_empty) means now buffer_empty=99 or there is 1 item inserted.

P2 - after inserting, it ups the semaphore V(b_full) means Buffer_full=1 or there is 1 item present in buffer.

now for C1 - it downs the "P(b_full)" semaphore means it has taken out 1 item from buffer and consumes item and up the "V(b_empty)" to state that one more cell of buffer is empty now.

 

answered by Junior (891 points)
edited by

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

44,256 questions
49,751 answers
164,121 comments
65,848 users