in Operating System edited by
6,031 views
20 votes
20 votes

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.

in Operating System edited by
6.0k views

4 Comments

edited by
see detailed explanation at the end of this page.
0
0
0
0
Note :

it is problem of strick alteration
0
0

3 Answers

30 votes
30 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 you are giving water in a glass to that thirsty man, so you are the producer here.

The man drinks and makes the glass empty. So he is consumer here.

(b) If there are multiple users we can use mutex semaphores so that exclusively one producer or one consumer can enter the Critical section at a time. We need one mutex for the set of producers and nother for the set of consumers.

p1: P(Empty)
    P(mutex1)

p2: V(mutex1)
    V(Full)    

c1: P(Full)
    P(mutex2)

c2: V(mutex2)
    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.

edited by

4 Comments

edited by

Difficult statement in above answer (understand below) :- 

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.

 

Understand above statement by below two cases :-

(CASE - I) Let P(mutex) is before P(Empty) in Producer's code. let currently buffer is full, so currently semaphore, Empty=0. let producer want to produce one more item, so new process is started and start executing Producer's code, initially mutex=1 so P(mutex) is executed successfully then we try to execute P(Empty) but currently Empty was 0, so when P is applied then Empty becomes -1, that why Producer process got blocked until any another process makes Empty  "greater than 0" but V on Empty is done by process which executing Consumer's code but because of mutex =0, any another process can't execute consumer's code. So deadlock occurred.


(CASE - II)  Let P(mutex) is before P(Full) in Consumer's code. let currently buffer is empty, so currently Full =0  (.....understand similarly as previous case).

2
2
Mutex variable is not allowing producer &consumer to work parlelly ,, so we use two mutex varaibles.. mutex1 for producer ,mutex2 for consumer.... Please some one edit this....
1
1
edited by
If you find any corrections please use the “flag” button. Answer is corrected now.
0
0
0 votes
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.

 

edited by

1 comment

@Nitesh Singh 2

I think this problem is different from Reader-Writer problem.

Here different consumers cannot consume from the same slot. Similarly different producers cannot add an item to the same slot. That's the reason why we are using mutex so that any operations that are performed on a slot happens in a mutuallyexclusive fashion.

Please do correct me if I'm wrong. :)

0
0
0 votes
0 votes

For Producer Process:

b_empty=BUFFSIZE; // means you can produce an item till there is space available 

P1: P(b_empty); // Perform down operation on buffer size since you are going to produce an item i.e reduce available space by 1.

if b_empty becomes less then 0 then all the producer process will get blocked here.

Now, Semaphore b_full=0; // means how many items are initially present in buffer.

P2: V(b_full); // perform Up operation on b_full because you have produced an item i.e increase the item count by 1.

For Consumer Process: 

C1: P(b_full);  // perform down operation on b_full since you are going to consume an item from buffer. 

if b_full becomes less than 0 then consumer process will have to wait for producer to produce an item in the buffer.

C2: V(b_empty); // perform up operation on b_empty because available buffer size has to increase by 1 since you have consumed an item.

For part (b), we can simply use the binary semaphore to ensure mutual exclusion in case of multiple producers and consumers.

 

Related questions