GATE CSE 2002 | Question: 20

Question

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;
    }
}

• A. Complete the dotted part of the above solution.

• B. 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.

Comments

see detailed explanation at the end of this page.

---

Similar question https://gateoverflow.in/3708/gate2004-it-65

---

Note :

it is problem of strick alteration

Answer 1

(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.

Comments

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.

---

ok,done sir

---

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

---

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??

---

@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..

---

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.

---

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

---

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

---

Yeah got it :)

---

@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.

 

---

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

---

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.

---

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).

---

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....

---

If you find any corrections please use the “flag” button. Answer is corrected now.

Answer 2

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.

 

Comments

@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. :)

Answer 3

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.