FOR FREE CONTENT

Producer-Consumer Problem Using Semaphores

This solution uses three semaphores: 

# Mutex is a binary semaphore used by the producer-consumer problem to access the buffer (critical section) in mutual exclusion manner i.e. producer and consumer do not access the buffer at the same time.

# Full is counting the semaphore variable for counting the number of slots that are full.

# Empty is counting the semaphore variable for counting the number of slots that are empty.

Full is initially 0.

Empty is initially equal to the number of slots in the buffer. 

Mutex is initially 1. Semaphores that are initialized to 1 and used by two or more processes to ensure that only one of them can enter its critical region at the same time are called binary semaphores.

Mutex 1(up) means buffer (critical section) is free.

Mutex 0(down) means buffer (critical section) is occupied by some other process.

Analysis of algorithm with an example

Producer

In this example 

empty = 5

full = 3 right now

We are going to produce item

down(empty) then empty = 4

down(mutex) then mutex = 0 (critical region closed)

Now,

in = (N + 1) mod N

then in = 4

Now,

up(mutex) then mutex = 1and up(full) then full = full + 1 i.e full = 4

Consumer

down(full) then full = 3

down(mutex) so, mutex = 0 (critical region closed)

Now,

out = (out + 1) Mod N

out = 1

now up(mutex) then mutex = 1and up(empty) then empty = 4

If Buffer is full

empty = 0

full =8

So, the producer is not allowed to produce by instruction down(empty).

So, the producer will halt right now.

If Buffer is empty 

empty = 8 (number of total slots)

full = 0

So, the consumer is not allowed to consume by instruction down(full).

Right now consumer will be halt.

Effect if we swap the down operation; down (empty) and down (mutex). 

void producer(void)

{

int item,in;

int=0;

  while(true) {

producer_item(item);

down(mutex);                             

down(empty);                               

Buffer[in]= item;

in = (in+1) Mod N;

up(mutex);

up(full);                                           

   }

 }

Producer is executing

# If we interchanged down(empty) and down(mutex) in the producer end, then 

# It first execute down(mutex)  then mutex = 0.

# Then execute next instruction down(empty) but if empty = 0, then producer will be suspended (blocked) here.

There is no change at the consumer end.

# Now consumer will be executed down(full).

# Then executes next instructions down(mutex) but mutex is already zero.

# As we know two processes can’t call down operation at a time.

# So, consumer will be blocked.

Both producer and consumer are blocked and deadlock occurs. 

But if we swap down operation down(full) and down(mutex) at consumer code and producer has no change then in that case deadlock will not occur.