Producer-Consumer Problem in C

printf (? Hello World! ?);

Producer-Consumer problem(or bound-buffer problem) is one of the most important classical problems of multi-process synchronization in Operating Systems. Best part about computer programming is that all the problems relate to the real-world; obviously computer programs and software are a solution for solving your?s and mine?s daily requirements from online food ordering, shopping, social media, ticket booking and what not!

At the end of this tutorial blog, you will not only learn this ?Producer-Consumer? problem in depth; but can also code it right along with thread programming in C!

So, lets get started. Suppose you are owner of a Bakery shop named ?Bakes and Bytes?; and you can make 50 cakes at max because you don?t have a big oven yet. Now, you have several customers to buy it, but let us consider only one customer. Your bakery is advanced and hence has great management system as the given code.

The Code of our ?Bakery Management System?:

//Reference: https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problemint OVEN_SIZE = 50;int cakes = 0;procedure baker() { while (true) { cakes = bake_cake(); if (cakes == OVEN_SIZE) { sleep(); } putCakeInDisplay(cake); cakes = cakes + 1; if (cakes == 1) { wakeup(consumer); } }}procedure customer() { while (true) { if (cakes == 0) { sleep(); } item = takeCakeFromBakery(); cakes = cakes – 1; if (cakes == OVEN_SIZE – 1) { wakeup(baker); } buy_cakes(cakes); }}

From the above code; intuitively we can understand the following:

1. If your bakery is has cakes==0; then you send a message to all your customers that ?sleep();?
2. Until your oven is not full (cakes != 50), your baker continues to make fresh cakes.
3. But, if oven is full, baker goes to sleep until customer buys a cake and cakes != 50. This sends the baker a message wakeup(baker);
4. And if your cakes == 1, then it sends the Customer a message that wakeup(customer);

But this management has some problems like:

1. Baker is producing the cake and at the same time customer wants to take it. At the same time; the customer thinks cake is ready while baker thinks the there are no cakes and hence is still producing. So, one can understand that it creates a mess!
2. Now, consumer just saw there are no cakes, then is about to go to sleep. Now, before it goes to sleep; what if baker produces a cake? And after the baker has just produced a cake; the bakery sends the message to the customer ?Wake up!?. But since, the customer is about to sleep(as he had got to know that there were no cakes), and hence he is still awake, so the ?Wake Up? call of the baker is wasted! Actually that Wake-Up call was to awake the ?Sleeping? Customer! But due to lack of Sync, this happened.
3. Now, as seen previously; when baker produced One cake, customer didn?t turn up; Baker continues to produce cakes until the Oven is full(50 cakes)! And as per our condition 4, the customer is awakened when the cakes==1; but here cakes gets incremented by the Baker; so cakes never will be equal to one and Customer goes into infinite sleep. This condition isn?t acceptable right?

Exactly. This is the Producer-Consumer problem. A random guy from the street can also understand this simple thing, right? But solution to this is definitely interesting.

Formal Explanation:

The producer consumer problem is a synchronization problem. There is a fixed size buffer (here, OVEN_SIZE) and the producer (the baker) produces items(cakes) and enters them into the buffer. The consumer(customer) removes the items from the buffer and consumes(buys) them.

A producer should not produce items into the buffer when the consumer is consuming an item from the buffer and vice versa. So the buffer should only be accessed by the producer or consumer at a time.

To solve this, there comes the concept of Semaphores.

A semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system such as a multitasking operating system. A semaphore is simply a variable. This variable is used to solve ?Critical Section? problems and to achieve process synchronization in the multi processing environment.

Important Semaphores:

1. Mutex Lock: If it is set as ?0?, it means it is locked by some process and has entered in Critical Region; while if it is ?1?, any process can lock it to ?0? and enter the Critical Section.
2. Wait and Signal: Wait is to decrement a semaphore if that has a value of ?S? greater than equal to 0. Signal is to increment.

wait(S){while(S<=0); // busy waitingS–;}signal(S){S++;}

Let us try to code along with understanding this Problem in C-Language Environment. Lets get Started!

1 Producer, 1 Consumer Problem:

// PART 1/4Assumption: Buffer SIZE = 1#include<stdio.h>#include<pthread.h>#include<semaphore.h>#define SHARED 1void *Producer(); // Make Declaration of Producervoid *Consumer(); // Make Declaration of Consumersem_t empty, full; //Declare semaphores to be usedint data; // data variable

C language is powerful. It has great libraries for Thread Programming. As here in our case; the problem is of process synchronization, we need multiple processes running at the same time. So we use include different header files like pthread.h and semaphore.h apart from our favorite ?Studio.h? (did I just misspell?) Do you love C langauge?

//PART 2/4int main(){pthread_t ptid, ctid; // Line 1printf(“nMain Started”);sem_init(&empty, SHARED, 1); // Line 2sem_init(&full, SHARED, 0); // Line 3sem_init(&amp;sm, SHARED, 1);// Line 4pthread_create(&ptid,NULL,Producer,NULL); // Line 5pthread_create(&ctid,NULL,Consumer,NULL); // Line 6pthread_join(ptid,NULL); // Line 7pthread_join(ctid,NULL); // Line 8printf(“nMain donen”);}

Explanation:

Line-1: Make instances of ptid(parent process ID) and ctid(child process ID) of the pthread_t

Line 2, 3 and 4: We initialize the declared semaphores as empty = 1 and full = 0. Meaning, that initially the buffer is empty (so empty=1) and it is not full (so full=0) and a mutex lock as sm initialized as 1.

Line 5 and 6:

• System call pthread_create(&ptid, NULL,Producer,NULL); creates the thread ptid which will be executing till it?s in producer method.
• Similarly system call pthread_create(&ctid, NULL,Consumer, NULL); creates the thread ctid which will be executing till it?s in Consumer method.

Line 7 and 8:

• The system call pthread_join (ptid,NULL); ensures that the next thread completes its execution only after the completion of the given thread ptid.
• The system call pthread_join (ctid,NULL); ensures that the next threadcompletes its execution only after the completion of the given thread ctid.

//PART 3/4void *Producer(){//ITEM PRODUCED…int produced;printf(“nProducer created”);printf(“nProducer id is %ldn”,pthread_self()); //print thread idfor(produced=0;produced<100;produced++){sem_wait(&empty);// LOCK-starts sem_wait(&sm); //CRITICAL SECTION STARTS data=produced; //CRITICAL SECTION ENDS sem_post(&sm);//LOCK-endssem_post(&full);printf(“nProducer: %d”,data);}}

Explanation:

The Producer Function works as follows:

• After the item is produced, wait operation is carried out on empty. If it not empty(empty=0), then it is under busy waiting state; until empty=1.
• Now, this indicates that the empty space in the buffer has decreased by 1. Then wait operation is carried out on ?sm? so that consumer process cannot interfere as any process can enter the critical section if lock=1.
• But since, wait function is applied on lock, it decrements to zero and hence no other process can enter.
• After the item is put in the buffer, signal operation(sem_post) is carried out on ?sm? and full. The former indicates that consumer process can now act and the latter shows that the buffer is full by 1.

//PART 4/4void *Consumer(){int consumed, total=0;printf(“nConsumer createdn”);printf(“nConsumer id is %ldn”,pthread_self());for(consumed=0;consumed<100;consumed++){sem_wait(&full);//LOCK-starts sem_wait(&sm); //CRITICAL SECTION STARTS total=total+data; //CRITICAL SECTION ENDS sem_post(&sm);//LOCK-endssem_post(&empty);printf(“nConsumed: %d”,data);}printf(“nThe total of 100 iterations is %dn”,total);}

Explanation:

• The wait operation is carried out on full. This indicates that items in the buffer have decreased by 1. Then wait operation is carried out on mutex so that producer process cannot interfere.
• Then the item is removed from buffer. After that, signal operation is carried out on lock ?sm?, indicating that lock is removed as work is done; and the signal on ?empty? shows that the empty space in the buffer has increased by 1.

In this way; one can understand that even if multiple processes run at the same time; due to proper use of semaphores; the ?Race-Condition? and the ?Critical Section Problem? is avoided.

Congratulations!

1 Producer, 3 Consumers Problem:

Since, now we are clear with basic thread programming of Producer-Consumer Problem, let us dive deeper into some Real World Problem. In practical life, there are can be ? n? consumers for a single producer like our Bakery Shop, or online shopping, or Railway Reservation or what not. All of those problems can be solved with these types of programming techniques.

Below code snippets illustrate the 1 Producer and 3 Consumer Problem.

PART 1/4Assumption: Buffer Size = 1We manually define the 3 consumers the consume exactly one-third of the items produced by the Producer for ease of Understanding.#include<stdio.h>#include<pthread.h>#include<semaphore.h>#define SHARED 1void *Producer();void *Consumer();sem_t empty, full,sm;int data;

Explanation:

When there are multiple consumers, actual synchronization problem comes up. For that we will write the logic of our code with some assumptions:

1. The Buffer-size is equal to 1. (you can implement ?n? sized buffer with the help of an array. But by keeping the code neat and simple; we can understand this problem much better)
2. We explicitly define that the all the 3 consumers will take exactly 1/3rd part of the produced items (for ? n? consumers, 1/nth part) in order to avoid use of multiple semaphores.

int main(){pthread_t ptid, ctid1, ctid2, ctid3;int x=1,y=2, z=3;int *a = &x;int *b = &y;int *c = &z;sem_init(&empty, SHARED, 1);sem_init(&full, SHARED, 0);sem_init(&sm,SHARED,1);pthread_create(&ptid,NULL,Producer,NULL);pthread_create(&ctid1,NULL,Consumer,(void*)a);pthread_create(&ctid2,NULL,Consumer,(void*)b);pthread_create(&ctid3,NULL,Consumer,(void*)c);pthread_join(ptid,NULL);pthread_join(ctid1,NULL);pthread_join(ctid2,NULL);pthread_join(ctid3,NULL);printf(“nMain donen”);}

Explanation:

Here, 4 different threads are created namely Producer(ptid) and Consumer( with ctid1, ctid2, ctid3). Along with creating we pass a unique identification number as variables a,b and c to each respective consumer threads.

After that, by using pthread_join, all threads are called and executed in order defined by the ?Scheduling Policy? of OS.

Important Points to Note:

• Any of the ?called? threads can be executed in any order by OS.
• If empty=0; and Producer Thread is called, then it goes into ?Busy Waiting? state; and OS calls other thread.
• If full=0; and any of the Consumer Threads are called; then respective thread goes into Busy Waiting and control is transferred to another thread.
• Suppose Producer Thread went into Busy Waiting first, then Consumer Thread was executed and increments empty=1; so after its execution, the Producer Thread comes out of Busy Waiting State and can produce if it is given charge. Similarly for other threads also.
• Producer loops for a total of 30 times. Consumer-1, Consumer-2,Consumer-3 will loop exactly for 10 times and will consume exactly 10 items each.
• Mutex Lock is used for each process.

void *Producer(){int produced;printf(“nProducer created”);printf(“nProducer id is %ldn”,pthread_self());for(produced=0;produced<30;produced++){sem_wait(&empty);sem_wait(&sm);data=produced;sem_post(&sm);sem_post(&full);printf(“nProducer: %d”,data);}}void *Consumer(void *no){int consumed, total=0;int *thread = (int*)no;printf(“nConsumer created, Thread number: %dn”, *thread);printf(“nConsumer id is %ldn”,pthread_self());for(consumed=0;consumed<10;consumed++){sem_wait(&full);sem_wait(&sm);total=total+data;printf(“nThread: %d, Consumed: %d”, *thread, data);sem_post(&sm);sem_post(&empty);}printf(“nThe total of 10 iterations for thread %d is %dn”,*thread, total);}

Note:

Before scrolling down, I would strongly recommend you to try the whole code by yourself and analyze it.

If you don?t have Linux installed on your PC, you can run it on:https://www.onlinegdb.com/online_bash_shell

OUTPUT in console:

//Output tested on: https://www.onlinegdb.com/online_bash_shellConsumer created, Thread number: 3Consumer id is 140167270151936Consumer created, Thread number: 1Consumer id is 140167286937344Producer createdProducer id is 140167295330048Producer: 0Thread: 3, Consumed: 0Producer: 1Thread: 1, Consumed: 1Producer: 2Thread: 3, Consumed: 2Producer: 3Thread: 1, Consumed: 3Producer: 4Thread: 3, Consumed: 4Producer: 5Thread: 1, Consumed: 5Producer: 6Thread: 3, Consumed: 6Producer: 7Thread: 1, Consumed: 7Producer: 8Thread: 3, Consumed: 8Producer: 9Thread: 1, Consumed: 9Producer: 10Thread: 3, Consumed: 10Producer: 11Thread: 1, Consumed: 11Producer: 12Thread: 3, Consumed: 12Producer: 13Thread: 1, Consumed: 13Producer: 14Thread: 3, Consumed: 14Producer: 15Thread: 1, Consumed: 15Producer: 16Thread: 3, Consumed: 16Producer: 17Thread: 1, Consumed: 17Producer: 18Thread: 3, Consumed: 18The total of 10 iterations for thread 3 is 90Producer: 19Thread: 1, Consumed: 19The total of 10 iterations for thread 1 is 100Producer: 20Consumer created, Thread number: 2Consumer id is 140167278544640Thread: 2, Consumed: 20Producer: 21Thread: 2, Consumed: 21Producer: 22Thread: 2, Consumed: 22Producer: 23Thread: 2, Consumed: 23Producer: 24Thread: 2, Consumed: 24Producer: 25Thread: 2, Consumed: 25Producer: 26Thread: 2, Consumed: 26Producer: 27Thread: 2, Consumed: 27Producer: 28Thread: 2, Consumed: 28Producer: 29Thread: 2, Consumed: 29The total of 10 iterations for thread 2 is 245Main done

Congratulations! You?ve successfully completed this lesson!

That?s it for this tutorial!

I hope it was informative and explained you this concept well and now its time for a CODING CHALLENGE!

?Implement the concept we just studied to improvise our BAKERY for ? n? Consumers and 1 Producer. Make sure it is well-synchronized.?

You can email the solution to: [email protected]; I will announce the best codes in my next Upcoming Blog!

Also if you have any suggestions or queries, do write me on that E-mail.

Until then,

Stay safe, Stay Healthy and Happy Coding 🙂