Skip to main content

Linux & C :- Producer Consumer Problem with pthreads using semaphores

Subscribe us for our YouTube channel and any kind of help

Producer Consumer Problem:-



            The “Producer-Consumer problem” is one of the best ways to make an example of issues found in Process Communication. To make a simple analogy of the problem , let’s consider a restaurant , with a client who eats what is served for him on the table and a cook that brings food to the table. The issue is that we want to avoid two unpleasant situations. First the cook might bring food to the table when the table is full and then it might fall off. Second we want to avoid the client trying to eat the table , because there is no food on it.
            In reality, the cook is a process known as a “producer” while the client is a process known as the “cosnumer”, the food is data, and the table is a buffer. The problem is also reffered to as the “bounded buffer problem” as we have a limited size buffer that must be shared by two processes (maybe part of the same program) that both add and remove data from it.

The Issue:-


The main issue in this situation has been discussed above, the producer needs room in the buffer to add data, while the consumer needs tha buffer to be non-empty. 

Solutions:-

1. Sleep-wakeup (also known as the inadequate soluiton)
The main ideea of this solution is to use a variable, counter, to count the elements stored in the buffer. To prevent overflows, the code checks if the buffer hasn’t reached maximum capacity. If the value of counter = N (where N=max) , the producer makes a system call, sleep() , to wait until at least one element is ‘consumed’ . If the buffer was empty , the producer notifyes the consumer of the existence of one element in the buffer (namely the one it just added). The consumer code functions on the same principle, it checks if it there is an element to consume, and if the buffer was full and its cycle freed up a position it notifyes the producer. It uses the sleep() system call to wait for an element to be added tot the buffer.

int itemCount

procedure producer() {
    while (true) {
        item = produceItem()

        if (itemCount == BUFFER_SIZE) {
            sleep()
        }

        putItemIntoBuffer(item)
        itemCount = itemCount + 1
       
        if (itemCount == 1) {
            wakeup(consumer)
        }
    }
}

procedure consumer() {
    while (true) {

        if (itemCount == 0) {
            sleep()
        }
       
        item = removeItemFromBuffer()
        itemCount = itemCount - 1
        
        if (itemCount == BUFFER_SIZE - 1) {
            wakeup(producer)
        }
       
        consumeItem(item)
    }
}

2. Semaphor

Using semaphors we can solve this problem better . In the solution below we use two semaphores, full and empty, to solve the problem. Full is incremented and empty decremented when a new item has been put into the buffer. This works great for only one producer and consumer.Given the following circumstances we may encounter and unsatisfactory solution:

Two producers decrement the semaphor empty.One of the prodecers dtermines the next empty slot in the buffer. The sencond producer determines the next empty slot and gets the same result as the first producer. Both producer write in the same spot.
semaphore full = 0
semaphore empty = BUFFER_SIZE

procedure producer() {
    while (true) {
        item = produceItem()
        down(empty)
        putItemIntoBuffer(item)
        up(full)
    }
 }

procedure consumer() {
    while (true) {
        down(full)
        item = removeItemFromBuffer()
        up(empty)
        consumeItem(item)
    }
}

3. Mutex
To solve this issue, we should create a new semaphory to solve the mutual exclusion problem (no more than one producer has access to the buffer at one given time.) , thus the variable semaphory is named “mutex”.

When a process wants to enter critical region , it uses the mutex_lock() to lock the the variable mutex. If mutex is locked it waits it’s turn. The mutex solution works well because it offers another processes to accesss the processor , simply because it avoids the busy waiting solution.

semaphore mutex = 1
semaphore full = 0
semaphore empty = BUFFER_SIZE

procedure producer() {
    while (true) {
        item = produceItem()
        down(empty)
        down(mutex)
        putItemIntoBuffer(item)
        up(mutex)
        up(full)
    }
 }

procedure consumer() {
    while (true) {
        down(full)
        down(mutex)
        item = removeItemFromBuffer()
        up(mutex)
        up(empty)
        consumeItem(item)
    }
}

4. Monitors
A solution to this problem is implementing monitors. A monitor is a collection of data , procedure , variables and data structures grouped into a packed/module. Although processes can always call a monitor’s procedures they DO NOT have access to a monitor’s internal structure. Monitors use a conditional variable , and perform two operations upon it : wait and signal .
            If a proccess can’t continue , a wait operation on the conditional variable blocks the current process. A signal will make it resume operation.
Since mutual exclusion is implicit with monitors, no extra effort is necessary to protect critical section. Monitors provide a kind of high-level synchronization.

monitor ProducerConsumer {
   
    int itemCount
    condition full
    condition empty
   
    procedure add(item) {
        while (itemCount == BUFFER_SIZE) {
            wait(full)
        }
       
        putItemIntoBuffer(item)
        itemCount = itemCount + 1
       
        if (itemCount == 1) {
            notify(empty)
        }
    }
   
    procedure remove() {
        while (itemCount == 0) {
            wait(empty)
        }
       
        item = removeItemFromBuffer()
        itemCount = itemCount - 1
       
        if (itemCount == BUFFER_SIZE - 1) {
            notify(full)
        }
       
        return item;
    }
}

procedure producer() {
    while (true) {
        item = produceItem()
        ProducerConsumer.add(item)
    }
}

procedure consumer() {
    while (true) {
        item = ProducerConsumer.remove()
        consumeItem(item)
    }
}
l_ lass=MsoNormal> 

        if (itemCount == 0) {
            sleep()
        }
       
        item = removeItemFromBuffer()
        itemCount = itemCount - 1
        
        if (itemCount == BUFFER_SIZE - 1) {
            wakeup(producer)
        }
       
        consumeItem(item)
    }
}


            The “Producer-Consumer problem” is one of the best ways to make an example of issues found in Process Communication. To make a simple analogy of the problem , let’s consider a restaurant , with a client who eats what is served for him on the table and a cook that brings food to the table. The issue is that we want to avoid two unpleasant situations. First the cook might bring food to the table when the table is full and then it might fall off. Second we want to avoid the client trying to eat the table , because there is no food on it.

            In reality, the cook is a process known as a “producer” while the client is a process known as the “cosnumer”, the food is data, and the table is a buffer. The problem is also reffered to as the “bounded buffer problem” as we have a limited size buffer that must be shared by two processes (maybe part of the same program) that both add and remove data from it.



5. Messages

Messages sent between proccess is yet another way to solve the producer-consumer problem. We create a special structure , named a mailbox for both processes and messages are sent to these structures rather to memeory address . Thus the program is safer , with a high-end approach.


Usage
            The producer-cosnumer solves the issue of thread synchronization in operating systems, thus making sure there are no problems with stack overflows or inconsistent data addressing.
            Also, another possible application could be in reliable network protocols, to make sure data is delivered reliabley .


An Example:-

#include<stdio.h>
#include<pthread.h>
#include<sys/types.h>
#include<unistd.h>
#include<stdlib.h>
#include<semaphore.h>

sem_t empty,full,mutex;
char buf[10];
void* thread_fun1(void* arg)
{
int i;
//printf("inside producer\n");
for(i=0;i<10;i++)
{
sem_wait(&empty);
sem_wait(&mutex);
buf[i]=i;
printf("item produced is %d\n",buf[i]);
sem_post(&mutex);
sem_post(&full);
sleep(1);

}
pthread_exit("producer\n");

}
void * thread_fun2(void* arg)
{
int j;

printf("inside consumer\n");
for(j=0;j<10;j++)10
{
sem_wait(&full);
sem_wait(&mutex);
      // sleep(1);

j=buf[j];
printf("consumed item is:%d\n",buf[j]);
sem_post(&mutex);
sem_post(&empty);
sleep(5);


}

pthread_exit("consumer\n");
}



int main()
{
pthread_t pid1,pid2;

sem_init(&empty,0,10);
sem_init(&full,0,0);
sem_init(&mutex,1,1);

void *status;
pthread_create(&pid1,NULL,thread_fun1,NULL);
pthread_create(&pid2,NULL,thread_fun2,NULL);


pthread_join(pid1,&status);
printf("the exited status of 1st is %s\n",(char*)status);
pthread_join(pid2,&status);
printf("the exited status %s\n",(char*)status);





return 0;
}

Comments

Anonymous said…
wtf

Popular posts from this blog

CDAC COURSES AND PLACEMENTS, WHICH IS BETTER FOR YOU

Click here to ask questions regarding CDAC
Before going through this post, I would like to draw your attention towards the importance of this post. This page not only explains my experience in CDAC but also aims at answering the queries of you all who are going or looking to have a course from CDAC. Kindly post your queries at the bottom of this page and we will get back to you within 24 hours. Kindly do not post your queries as an Anonymous user and do not forget to subscribe via email so as to keep track of your query.

                        click below to know about the CCAT's This batch allotment                 click below to know about the CCAT's This batch allotment ______________________________________________
NOW a day lot of the graduates and post graduates are wondering most of the times on which course they should go for. What are the pros & cons of joining a particular centre of CDAC. Here is a comprehensive information on how to enroll ourselves for a cour…

CDAC CCAT Rank - Which Centre you Should go for...

Click here to ask questions regarding CDAC
1. C-DAC (Head Quarters) Pune 
CDAC's Admission Booklet- Process of Admission to Post Graduate Diploma Courses of C-DAC                         click below to know about the CCAT's This batch allotment
               click above to know about the CCAT's This batch allotmentRank 1-300
c-dac HQ has been the best from the start.

2. Sunbeam Pune

Rank 300-500
I got very positive feedback from my friends who are in c-dac banglure main campus,since there are many companies you may get more opportunities.

3. C-DAC Knowledge Park

Rank 400-700
It as very good faculty .Almost all the students get placed here every year.

4. C-DAC Hyderabad

Rank 200-1000 (It depends on the course which you select)
C-DAC hyderabad is very good for the course PG-DESD.
PG-DESD course is in hyderbad is better than pune HQ as per the past feedback.It as very good placement record in hyd for PG-DESD course.Rank for PG-DESD is 1-300.
PG-DAC as no good placement record from few yea…

Placement Statistics - 2011 & 2012

Post your queries below and we will get back to you in no more than 24 hours.  Click here to ask questions regarding CDAC                         click below to know about the CCAT's This batch allotment                     click above to know about the CCAT's This batch allotment
CDAC's Admission Booklet- Process of Admission to Post Graduate Diploma Courses of C-DAC

Click here to see placement statistics

About C-CAT, Exam Pattern and Books

No. of Seats Across Various Training Centres

Important Dates - 2014








Tags: CDAC, CDAC scope in future, CDAC placements, CDAC training, CDAC recruitment, CDAC training centres, DSSD, DESD, DAC, PGDSSD, PGDESD, PGDAC, DABC, PGDABC, VLSI, PGDITISS, PGDIVESD, PGDESD, PGDWiMC, placement statistics