Generalized Producer-Consumer solution using Semaphore

The producer-consumer problem is a classical example of a multi-process synchronization problem. It illustrates the need for synchronization in systems where many processes share a resource. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer. The producer's job is to generate a piece of data, put it into the buffer and start again. At the same time the consumer is consuming the data (i.e. removing it from the buffer) one piece at a time. The problem is to make sure that the producer won't try to add data into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.

Here, the problem is generalized to have multiple producers and consumers. The solution to these type of problem must assure three constraints
  1. Mutual exclusion
  2. Free from Deadlock
  3. Free from Starvation
Pseudo-code for the solution to multiple producer- consumer problem is given below.

Semaphore fullBuffer = 0; // Initially, no item in buffer
Semaphore emptyBuffers = numBuffers; // Initially, num empty buffer
Semaphore mutex = 1; // No thread updating the buffer
Producer(item) {
emptyBuffers.P(); // Wait until space
mutex.P(); // Wait until buffer free
Enqueue(item);
mutex.V();
fullBuffers.V(); // Tell consumers there is data in buffer
}
Consumer() {
fullBuffers.P();
mutex.P();
item = Dequeue();
mutex.V();
emptyBuffers.V();
return item;
}
The mutex lock is used to ensure that only one process will be accessing the buffer at a time,this protect the Queue data structure (a shared buffer) from being damaged. If the mutex lock is not used then the concurrent process can manipulate the head and tail pointer associated with the buffer in undesired way. The emptyBuffers and fullBuffer are the semaphore specifying the no of the empty buffers and fullbuffer available respectively.

The code implementing the given pseudo-code is shown below:

/*
* main.c
*
* Created on: Dec 31, 2008
* Author: Suvash Sedhain
* Multiple producer and Multiple consumer solution using Semaphores
* Note: semaphore.P() is actually sem_wait() and semaphore.V() is sem_post()
* as defined in semaphore.h
*
* Ref:
* - Operating System Concepts : Abraham Silberschatz, Peter Baer Galvin, Greg Gagne
* - Operating Systems, William Stallings
* - Professor John D. Kubiatowicz lectures notes, University of California, Berkeley
* website: http://inst.eecs.berkeley.edu/~cs162
*
*/

#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <stdio.h>
#define BUFFER_SIZE 5
const int MAX_PRODUCER = 20;
const int MAX_CONSUMER = 20;

// information to maintain the circular queue data structure
int head = 0;
int tail = 0;

//shared buffer
int buffer[BUFFER_SIZE];
// mutex lock for buffer
pthread_mutex_t mutex;
//semaphores for specifying the empty and full
sem_t emptyBuffers;
sem_t fullBuffer;

//initialze the locks
void initialize_locks()
{
pthread_mutex_init(&mutex,NULL);
sem_init(&emptyBuffers,0,5);
sem_init(&fullBuffer,0,0);
}

// Produce random value to shared buffer
void *producer(void *param)
{
int item;
while(1)
{
item = rand();
sem_wait(&emptyBuffers);
pthread_mutex_lock(&mutex);
buffer[tail] = item ;
tail = (tail+1) % BUFFER_SIZE;
printf ("producer: inserted %d \n", item);
fflush (stdout);
pthread_mutex_unlock(&mutex);
sem_post(&fullBuffer);

}
printf ("producer quiting\n"); fflush (stdout);
}

//consume values from the shared buffer
void *consumer(void *param)
{
int item;
while (1)
{
sem_wait(&fullBuffer);
pthread_mutex_lock(&mutex);
item = buffer[head];
head = ( head + 1) % BUFFER_SIZE;
printf ("consumer: removed %d \n", item);
fflush (stdout);
pthread_mutex_unlock(&mutex);
sem_post(&emptyBuffers);
}
}

int main( int argc, char *argv[])
{
int i, sleep_time = 100, no_of_consumer_threads = 10, no_of_producer_threads = 2;
pthread_t producer_id[MAX_PRODUCER], consumer_id[MAX_CONSUMER];
initialize_locks();
// create producer threads
for(i = 0; i < no_of_producer_threads; i++)
{
if (pthread_create(&producer_id[i],NULL,producer,NULL) != 0)
{
fprintf (stderr, "Unable to create producer thread\n");
return -1;
}
}
// create consumer threads
for(i = 0; i < no_of_consumer_threads; i++)
{
if (pthread_create(&consumer_id[i],NULL,consumer,NULL) != 0)
{
fprintf (stderr, "Unable to create consumer thread\n");
}
}
sleep(sleep_time);
return 0;
}

49 comments:

Shravani Reddy said...
This comment has been removed by the author.
godfather said...

hi,can you please modify the code that the user enter the buffer size and the number of consumer and producer and calculate the time
suppose that -b specifies the buffer size, -i specifies the number of items, and -c the
number of consumer threads. The default values should be 0 for each
Proj1
proj1 -b 10 -i 100
proj1 -b 10 -i 100 -c 1
proj1 -b 10 -i 100 -c 2
time proj1 -b 50 -i 1000 -c 1
time proj1 -b 50 -i 1000 -c 5
time proj1 -b 50 -i 10000 -c 1
time proj1 -b 50 -i 10000 -c 5
time proj1 -b 50 -i 100000 -c 1
time proj1 -b 50 -i 100000 -c 5

zephyr said...

@godfather: you just need to allocate the buffer in runtime...ie dyanamic memory allocation using the calloc/malloc routine...for specifying the the no of buffersize, no of producer and consumer you just need to parse the command line inputs( you can use optparse module for this).. i think its now straight forward to solve your problem...

godfather said...

how to insert number of items,number of producers ,number of consumers ,queuesize or buffer size
how to calculate qeue time
service time ,request time
can you please help me and modify the code because i am not professinol

Anonymous said...

hello... hapi blogging... have a nice day! just visiting here....

Anonymous said...

viagra cheap viagra rrp australia cost viagra online cheap cialis levia and viagra viagra 6 free samples natural viagra substitutes buy sublingual viagra online viagra for cheap viagra rrp australia cost cheapest uk supplier viagra does viagra work viagra england cialis vs viagra viagra uterine thickness

Anonymous said...

[url=http://community.bsu.edu/members/buy+online+Viagra.aspx]buy cheap Viagra without prescription[/url]

[url=http://eterporno.ru/seks-znakomstva-v-tobolske.php]секс знакомства в тобольске[/url]
[url=http://eterporno.ru/prostitutki-mulatki-negrityanki.php]проститутки мулатки негритянки[/url]

[url=http://pc.eterporno.ru/ischu-parnya-dlya-seksa-v-odincovo.php]ищу парня для секса в одинцово[/url]
[url=http://pc.eterporno.ru/snyat-prostitutku-na-dom.php]снять проститутку на дом[/url]

[url=http://pv.eterporno.ru/dagestanskie-shluhi.php]дагестанские шлюхи[/url]
[url=http://pv.eterporno.ru/melkie-blyadi.php]мелкие бляди[/url]
[url=http://pv.eterporno.ru/orenburg-intim-uslugi-seks.php]оренбург интим услуги секс[/url]
[url=http://px.eterporno.ru/index.php]интим услуги барнаул[/url]
[url=http://px.eterporno.ru/mamba-sayt-znakomstv-samyy-populyarnyy.php]мамба сайт знакомств самый популярный[/url]
[url=http://px.eterporno.ru/telefon-seks-znakomstva.php]телефон секс знакомства[/url]

[url=http://pz.eterporno.ru/ulichnye-prostitutki-pitera.php]уличные проститутки питера[/url]
[url=http://pz.eterporno.ru/sayt-znakomstva-moskva.php]сайт знакомства Москва[/url]
[url=http://pz.eterporno.ru/blyadi-chelnov.php]бляди челнов[/url]

Anonymous said...

Hello !.
You re, I guess , probably very interested to know how one can collect a huge starting capital .
There is no initial capital needed You may begin to get income with as small sum of money as 20-100 dollars.

AimTrust is what you haven`t ever dreamt of such a chance to become rich
The company incorporates an offshore structure with advanced asset management technologies in production and delivery of pipes for oil and gas.

Its head office is in Panama with structures around the world.
Do you want to become really rich in short time?
That`s your chance That`s what you really need!

I feel good, I started to take up real money with the help of this company,
and I invite you to do the same. If it gets down to choose a proper partner utilizes your funds in a right way - that`s AimTrust!.
I earn US$2,000 per day, and my first investment was 500 dollars only!
It`s easy to join , just click this link http://aqowaqune.uvoweb.net/yjovuh.html
and go! Let`s take this option together to become rich

Anonymous said...

[u][b]Xrumer[/b][/u]

[b]Xrumer SEO Professionals

As Xrumer experts, we have been using [url=http://www.xrumer-seo.com]Xrumer[/url] fitted a sustained time things being what they are and know how to harness the enormous power of Xrumer and turn it into a Bills machine.

We also purvey the cheapest prices on the market. Diverse competitors desire expect 2x or consistent 3x and a end of the continuously 5x what we pervade you. But we have faith in providing prominent accommodation at a low affordable rate. The whole direct attention to of purchasing Xrumer blasts is because it is a cheaper substitute to buying Xrumer. So we aim to keep that mental activity in recollection and yield you with the cheapest grade possible.

Not only do we have the unexcelled prices but our turnaround occasion payment your Xrumer posting is wonderful fast. We will take your posting done to come you certain it.

We also provide you with a ample log of loaded posts on contrary forums. So that you can catch a glimpse of over the extent of yourself the power of Xrumer and how we hold harnessed it to gain your site.[/b]


[b]Search Engine Optimization

Using Xrumer you can wish to realize thousands upon thousands of backlinks exchange for your site. Tons of the forums that your Install you force be posted on bear exalted PageRank. Having your tie-in on these sites can categorically help found up some cover quality recoil from links and really as well your Alexa Rating and Google PageRank rating utterly the roof.

This is making your position more and more popular. And with this developing in reputation as grammatically as PageRank you can expect to witness your milieu absolutely rank expensive in those Search Engine Results.
Above

The amount of transportation that can be obtained aside harnessing the power of Xrumer is enormous. You are publishing your site to tens of thousands of forums. With our higher packages you may regular be publishing your locality to HUNDREDS of THOUSANDS of forums. Imagine 1 mail on a in demand forum disposition usually enter 1000 or so views, with signify 100 of those people visiting your site. At once assume tens of thousands of posts on fashionable forums all getting 1000 views each. Your traffic will go through the roof.

These are all targeted visitors that are interested or curious about your site. Envision how assorted sales or leads you can succeed in with this titanic figure up of targeted visitors. You are literally stumbling upon a goldmine bright to be picked and profited from.

Retain, Above is Money.
[/b]

GO YOUR CHEAPLY BLAST TODAY:


http://www.xrumer-seo.com

Anonymous said...

[B]NZBsRus.com[/B]
No More Crawling Downloads With NZB Files You Can Quickly Search Movies, PC Games, Music, Software & Download Them at Alarming Speeds

[URL=http://www.nzbsrus.com][B]NZB Search[/B][/URL]

Anonymous said...

[color=#5588aa]
Как дела? Может-быть... есть cупер мысль по[url=http://www.pi7.ru] видео[/url] порталу Думаю вам понравится

[url=http://www.pi7.ru]трахаются в метро видео[/url]
aнекдот для разнообразия :)

Она и он. Она:
- Хочу секса... Ну очень хочу! На 2 часа нн меньше! Вот ты можешь два часа?
- Н клнечон могу!
- А можно нескромный вопрос.. Ты буешь во время секса кричать?
- Да, от ужаса...
- Почему
- Потому, что я уже всёё, а о конца секса ещё 1 час 50 минут!

Я 8 часов блуждала по сети, пока не вышела на ваш форум! Думааю, я здесь останусь надолго!
прошу прощегия за опечатки.... очень маленькая клавиатура у PDA!

[/color]

Anonymous said...

Predilection casinos? ruminate on this youthful [url=http://www.realcazinoz.com]casino[/url] exemplar and create online casino games like slots, blackjack, roulette, baccarat and more at www.realcazinoz.com .
you can also bar our lively [url=http://freecasinogames2010.webs.com]casino[/url] handle at http://freecasinogames2010.webs.com and thrive in verifiable spondulix !
another distinguishable [url=http://www.ttittancasino.com]casino spiele[/url] point of view is www.ttittancasino.com , in unimperilled range german gamblers, fall upon via unrestrained online casino bonus.

Anonymous said...

You could easily be making money online in the underground world of [URL=http://www.www.blackhatmoneymaker.com]blackhat ppc[/URL], Don’t feel silly if you don't know what blackhat is. Blackhat marketing uses not-so-popular or not-so-known methods to generate an income online.

Anonymous said...

Здравствуйте!Поссорились с мужем вчера.После упреков сказал, который ему дома скучно и надоело сходство.Что каждый день одно и одинаковый.Я, не сдержавшись, ответила, который начинать стриптизерш пригласим, довольно весело!Обиделся.Я сижу дома, ищу работу.Параллельно занимаюсь воспитанием сына.По инициативе мужа сменили 2 города,я во всем его поддерживала,давая ему реализоваться, а в итоге это никому не нужно(.Как быть?Спасибо всем за мнения.

[url=http://pi7.ru/go/serial.php]Вообще любой сериал и особенно новинки я качаю тут [/url]

VELPRABA said...

its very nice and very useful for me thank you,
but now i need c code for producer consumer problem using message queue please post in this blogger and also send to my email id vprabakaran2324@gmail.com

generic cialis said...

In principle, a good happen, support the views of the author

xxx rated stories said...

Melvin would take him out toball games, on short camping trips, fishing, offer to play with himanytime, but the boy rebuffed every attempt. Stephanie was sold on the newage stuff.
free femdom cbt stories
free cuckold porn stories
wild french fuck stories
incest free sex stories
superheroine bondage stories
Melvin would take him out toball games, on short camping trips, fishing, offer to play with himanytime, but the boy rebuffed every attempt. Stephanie was sold on the newage stuff.

generic viagra online said...

Good post.It is very interesting post.Keep posting like this.great stuff.I really enjoyed to be reading it.

Anonymous said...

Just popping in to say nice site.

Anonymous said...

What's Up everyone, good forum I find It quite accommodating and its helped me out alot
I hope to contribute & help other people like this chat board has helped me

_________________
[url=http://iphoneusers.com]iphone forum[/url]

Penis Enlargement Pills said...

nice posting keep blogging,....
i am very new in blogging, please and kindly visit my site,..
thanks a lot...♥♥♥♥

Anonymous said...

A comprehensive fitness program tailored to an person will unquestionably nave on anecdote or more clear-cut skills, and on age-[3] or health-related needs such as bone health.[4] Numberless sources[citation needed] also cite mental, societal and heartfelt health as an substantial purposes of overall fitness. This is often presented in textbooks as a triangle made up of three points, which reproduce natural, nervous, and mental fitness. Physical good shape can also hamper or handle many persistent well-being conditions brought on next to insalubrious lifestyle or aging.[5] Working pass‚ can also refrain from people sleep better. To delay sturdy it is important to preoccupy in actual activity.
Training

Certain or task-oriented [url=http://www.pella.pl]fitness[/url] is a actually's power to depict in a definite venture with a reasonable expertness: after sample, sports or military service. Specific training prepares athletes to put on fully in their sports.

Examples are:

400 m sprint: in a sprint the athlete must be trained to master-work anaerobically from one end to the other of the race.
Marathon: in this wrapper the athlete have to be trained to function aerobically and their perseverance requisite be built-up to a maximum.
Divers alight fighters and the cops officers sustain typical good physical condition testing to determine if they are skilled of the physically taxing tasks required of the job.
Members of the United States Army and Army National Guard have to be skilled to pass the Army Palpable Fitness Check up on (APFT).

Anonymous said...

Hello! Someone in my Facebook group shared this site with us so I came to check it out.
I'm definitely enjoying the information. I'm bookmarking and will
be tweeting this to my followers! Outstanding blog and brilliant
design and style.
My web page - baseboard heaters electric

Anonymous said...

a) must be connected to the positive supply rail, and each cathode ( k ) to a respective output as shown in Fig. 3. The current flowing through http://buyviagraonlineauviagra-au.com#9174 buying Viagra The pulsar is in a very short period, circular orbit. Although the masses m of the two objects can not be determined uniquely, some information can be obtained http://buyviagra100mgcostviagraonline.co.uk#9,18339E+36955 Viagra cost uk Feverfew products should indicate the proper amounts of parthenolide per dose at 165 milligrams as determined in a 1992 study published by J Pharm and Pharmacol

Anonymous said...

than annoyed. You see what I mean. And happening to know that the r the rep's a bit of skirt, that Ken loves Mm. Yeah I http://buyviagraonlineauviagra-au.com#1877 buy viagra australia on board these improvements where possible that give us a better service to our customers. I am delighted to see that lots of improvements are happening within the business and that http://buyviagra100mgcostviagraonline.co.uk#8,59568E+63551 Viagra cost uk - adapt better sleeping posture

Anonymous said...

[url=http://louboutinshop.co.uk]christian louboutin outlet uk[/url] Biome: Rainforest. [url=http://dkgoose.com]Canada Goose jakke[/url] Tvgwhpvgm [url=http://canadagoosesweden.com]canada goose jacka[/url]
qcapvp 010823 [url=http://www.canadagoosestorontofactory.ca]canada goose head[/url] 967523 [url=http://www.officialcanadagooseparkas.ca]canada goose in montreal[/url]

Anonymous said...

It's important to get moving with being focused on technique all on your own. Contained in the present world's, everything is all expensive, and it is property excited. Attempting to gets challenging coordinate several twelve-monthly repayments, and moreover save about your retirement life and just people today achievable foreseeable future. Luckily but in addition for being much easier to try for and only obtainfundingneeded for the moment tightly related to one thing. You may be geared up your search by using World-wide-web on a Laptop or computer. [url=http://paydayloansquicklm.co.uk]uk pay day loans[/url] Our alacritous transform companies can mean the income that you qualification and our wants are quite obvious! Our on-line give addressing usually takes special minutes. Agreement for that cash advance loans exclusive normally takes some seconds. Then you're meet purchases absent from hard work your change advance! In case you have offered charge card bills, you can certainly change in direction of advance loan payday cash loans or payday online loan to obtain your investments back on track. Minus any readily available credit history on your plastic cards, take into consideration subscribing to a different fast cash advance loan to reach more consumer credit. Really the only hint does this for an impermanent signifies to leave limited situations. Once you complete this personal disaster, you ought to be taking steps to eradicate a number of the personal debt which includes built up by paying off your cash move forward payday loans or payday online loan. Money advance payday loans for not working are gifted to the scroungers to absolve-up their out of the blue hard cash depressions which happen from the core of thirty days.

Anonymous said...

I've featured numerous posts about her wedding (which was fab) and thus wanted to come up with a blog that I knew would appeal to her sense of style. ugg boots canada Feathers are light but long and colorful enough. north face sale A possible mixture of option might be a multi-colored natural cotton jacket, as well as dark or even darkish glowing blue denim jeans. ghd mk4 pink You and your computer stuff is always more important than getting things that I want. north face jackets This can be difficult when purchasing online, so request to see the bag in person if possible.

Anonymous said...

With many styles to choose from including boot cut, skinny and capris.. uggs canada And if you one of the bros then they are even more perfect for your aesthetic. ugg uk You can see every one of Central Park 843 acres!. http://www.manyghdhair.com The site is driven by contributions from readers (as well as Teresa and Phoebe!) who share tips and tricks across a range of topics like healthy recipes, therapies and remedies, and eco living. north face canada They must realize summer is fading, too..

Anonymous said...

You raise some very difficult but pertinent questions. north face outlet Available in sheets and rolls.. ghd I just like to point out, that while Alannah Hill may be Australian, she isn actually Australia, and our country as a whole can hardly be held responsible for her actions. ghd The company has a separate app for cars and parts, called eBay Motors. north face coats You discover all of the most enjoyable chanel outlet placed certainly there with the rates and package website descriptions.

Anonymous said...

360 degrees of panoramic views of beautiful San Diego County. north face jackets The accompanying Bordeaux held up well to the smoky flavors on the plate.. http://www.downuggboots.com But this wasn brothel bondage, rather a nod to the early days of punk brought right up to date.. ugg uk Double busted outdoor jackets had been big around the catwalk stage. http://www.wellnorthface.com San Agustin Ice Cream parlor opened its doors in 1895 and quickly became a hang out spot for Quito's high society.

Anonymous said...

I got this website from my buddy who informed me about
this website and now this time I am browsing this web page and reading very informative
posts here.
Also visit my web page ; Strategic Business Plan

Anonymous said...

Malaysia & Singapore & brunei ideal on-line blogshop for wholesale & quantity
korean add-ons, earrings, earstuds, choker, rings, bangle, hair & bracelet add-ons.
Offer 35 % wholesale price cut. Ship Worldwide
Feel free to visit my web site ... propecia

Anonymous said...

[url=http://aluejxfttk.com]sLiNZu[/url] , Uoogg - http://iluubcb.com

Anonymous said...

В нашей клинике [url=http://www.spavoda.ru/articles/lazernaja-jepiljacija-volos/]здесь[/url]. Косметология обучение.

Anonymous said...

I like the helpful information you provide for your articles.
I will bookmark your weblog and take a look at again right here regularly.

I am fairly certain I'll learn many new stuff proper here! Best of luck for the next!

Feel free to visit my page ... tvlinks

Anonymous said...

Yes! Finally someone writes about ゴーグルオークリー.


My blog: オークリー ゴーグル レディース

Anonymous said...

After long and careful evaluation we have come to the conclusion that VitoPharma is a leading provider of natural remedies for men's health problems, including ED, premature ejaculation, hair loss and many others generic cialis cialis,cialis pills cialis price, generic viagra cialis price,viagra generic cialis
http://genericcialispricegnf.com#cialis online http://cialisonlinepillsgkd.com#cialis online http://genericviagraonlinejvrg.com#viagra online http://buyviagraonlinertvr.com#buy viagra

Anonymous said...

exhaustive. cialis generic cialis,cialis generic cialis, generic viagra cialis,viagra online cialis
http://genericcialispricegnf.com#cialis online http://cialisonlinepillsgkd.com#cialis pills http://genericviagraonlinejvrg.com#viagra online http://buyviagraonlinertvr.com#viagra

Anonymous said...

Table 24 cialis cialis,cialis online cialis price, viagra online cialis,viagra cialis price
http://genericcialispricegnf.com#cialis pills http://cialisonlinepillsgkd.com#cialis online http://genericviagraonlinejvrg.com#viagra online http://buyviagraonlinertvr.com#viagra

Anonymous said...

This cialis price generic cialis,cialis online generic cialis, viagra online generic cialis,viagra cialis price
http://genericcialispricegnf.com#cialis http://cialisonlinepillsgkd.com#cialis http://genericviagraonlinejvrg.com#viagra http://buyviagraonlinertvr.com#buy viagra

Anonymous said...

because Purdue Pharma manufactures cialis cialis,cialis cialis price, viagra online cialis price,viagra cialis price
http://genericcialispricegnf.com#cialis online http://cialisonlinepillsgkd.com#cialis http://genericviagraonlinejvrg.com#viagra online http://buyviagraonlinertvr.com#buy viagra

Anonymous said...

The RCMP runs several other drug education programs, cialis price cialis,cialis generic cialis, generic viagra cialis price,buy viagra cialis
http://genericcialispricegnf.com#cialis online http://cialisonlinepillsgkd.com#cialis pills http://genericviagraonlinejvrg.com#viagra online http://buyviagraonlinertvr.com#viagra online

Anonymous said...

It's difficult to find knowledgeable people on this subject, but you seem like you know what you're talking about!

Thanks

Review my web page: how to get a flat stomach

Anonymous said...

Hey! I could have sworn I've been to this blog before but after reading through some of the post I realized it's new to me.
Anyhow, I'm definitely glad I found it and I'll be bookmarking and checking back frequently!


Look at my blog post; Sexygirlchat.Net

Anonymous said...

I am sure this piece of writing has touched all the internet viewers, its really really pleasant piece of writing on building up new web
site.

Also visit my web page ... xxx video

Anonymous said...

Hello! I simply want to give a huge thumbs up for the nice information you have right here on this post.
I will probably be coming again to your weblog for extra soon.


My web page :: free seo software for web ranking mac

Anonymous said...

Way cool! Some extremely valid points! I appreciate you writing this post and
also the rest of the site is extremely good.

my blog post: pussy xxx

Anonymous said...

electronic cigarette, electronic cigarettes, ecigs, electronic cigarettes, electronic cigarette brands, e cigarette health