Question

In this assignment, you will be given a functioning program, called minor3.c, that simply reads user input keys and echoes them back to the screen using the producer-consumer paradigm. The single producer thread reads user input keys and adds them to the shared buffer while two consumer threads read the added keys from the buffer and echo them back to the screen. To complicate matters, each key is read and echoed by exactly one consumer thread. A shared variable, called shared_count, keeps track of the number of items in the shared buffer.

While this program does work (thanks to the mutex locks and unlocks already provided), it is unfortunately very inefficient. To see just how inefficient this program is, compile the original minor3.c program (using the pthread library) and execute the program. You should type in some keys and see them echoed back on the screen in their correct order. To see the inefficiency, though, run the top command from another shell (don’t just run the minor3.c program in the background and then run top, but actually open up another shell/window). Then check out the %CPU column in the top command and you should see your original minor3.c program using up a significant percentage of the CPU, which is not good.

Your goal for this assignment is to modify this program to use condition variables that will drastically reduce its CPU percentage usage. Here are the details: 

You will modify the original minor3.c file to add two condition variables, but not change the “spirit” of the program other than necessary changes that are needed for how conditional variables work, including handling of “spurious wakeup” discussed in class.

You will add two global pthread condition variables – one to handle when the shared buffer is full (and therefore, nothing else can be added to the buffer until a key is removed from the buffer) and one to handle when the shared buffer is empty (and therefore, nothing can be read/echoed back to the screen until a key is added to the buffer).

In the main function, you will initialize and destroy both of the condition variables.

You will modify the code in the producer function to wait on and signal the appropriate condition variable(s) based on what is happening with the shared variables (i.e., the shared buffer and shared counter). Note that this will require some small changes in logic to accomplish, but you should not change the lines that work with the prod_index variable.

You will modify the code in the consumer function to wait on and signal the appropriate condition variable(s) based on what is happening with the shared variables (i.e., the shared buffer and shared counter). Note that this will require some small changes in logic to accomplish, but you should not change the lines that work with the cons_index variable.

Be sure to run your solution along with the top command to verify that the program is more efficient (i.e., does not use nearly as much percentage of the CPU). It is required that you implement and utilize the condition variables effectively in a manner that significantly reduces the CPU utilization of this program and not gain the reduction in another way. Note that the grading rubric requires that the condition variables be implemented “logically correct”, which includes accounting for “spurious wakeup”, not just reducing the CPU utilization.

CODE

/*
* minor3.c - using producer-consumer paradigm.
*/

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define NITEMS 10       // number of items in shared buffer

// shared variables
char shared_buffer[NITEMS];   // echo buffer
int shared_count;       // item count

pthread_mutex_t mutex;       // pthread mutex
unsigned int prod_index = 0;    // producer index into shared buffer
unsigned int cons_index = 0;    // consumer index into shard buffer

// function prototypes
void * producer(void *arg);
void * consumer(void *arg);

int main()
{
   pthread_t prod_tid, cons_tid1, cons_tid2;

   // initialize pthread variables
   pthread_mutex_init(&mutex, NULL);
  
   // start producer thread
   pthread_create(&prod_tid, NULL, producer, NULL);

   // start consumer threads
   pthread_create(&cons_tid1, NULL, consumer, NULL);
   pthread_create(&cons_tid2, NULL, consumer, NULL);
  
   // wait for threads to finish
   pthread_join(prod_tid, NULL);
   pthread_join(cons_tid1, NULL);
   pthread_join(cons_tid2, NULL);
          
   // clean up
   pthread_mutex_destroy(&mutex);
  
   return 0;
}

// producer thread executes this function
void * producer(void *arg)
{
   char key;

   printf("Enter text for producer to read and consumer to print, use Ctrl-C to exit.\n\n");

   // this loop has the producer read in from stdin and place on the shared buffer
   while (1)
   {
       // read input key
       scanf("%c", &key);

       // this loop is used to poll the shared buffer to see if it is full:
       // -- if full, unlock and loop again to keep polling
       // -- if not full, keep locked and proceed to place character on shared buffer
       while (1)
       {
           // acquire mutex lock
           pthread_mutex_lock(&mutex);

           // if buffer is full, release mutex lock and check again
           if (shared_count == NITEMS)
               pthread_mutex_unlock(&mutex);
           else
               break;
       }

       // store key in shared buffer
       shared_buffer[prod_index] = key;

       // update shared count variable
       shared_count++;

       // update producer index
       if (prod_index == NITEMS - 1)
           prod_index = 0;
       else
           prod_index++;
      
       // release mutex lock
       pthread_mutex_unlock(&mutex);
   }

   return NULL;
}

// consumer thread executes this function
void * consumer(void *arg)
{
   char key;

   long unsigned int id = (long unsigned int)pthread_self();

   // this loop has the consumer gets from the shared buffer and prints to stdout
   while (1)
   {
       // this loop is used to poll the shared buffer to see if it is empty:
       // -- if empty, unlock and loop again to keep polling
       // -- if not empty, keep locked and proceed to get character from shared buffer
       while (1)
       {
           // acquire mutex lock
           pthread_mutex_lock(&mutex);

           // if buffer is empty, release mutex lock and check again
           if (shared_count == 0)
               pthread_mutex_unlock(&mutex);
           else
               break;
       }

       // read key from shared buffer
       key = shared_buffer[cons_index];
      
       // echo key
       printf("consumer %lu: %c\n", (long unsigned int) id, key);

       // update shared count variable
       shared_count--;

       // update consumer index
       if (cons_index == NITEMS - 1)
           cons_index = 0;
       else
           cons_index++;
  
       // release mutex lock
       pthread_mutex_unlock(&mutex);
   }

   return NULL;
}

Answer 1

Hello! :)

Here's the updated code to solve the assignment:

minor3.c:

/*
* minor3.c - using producer-consumer paradigm.
*/

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define NITEMS 10       // number of items in shared buffer

// shared variables
char shared_buffer[NITEMS];   // echo buffer
int shared_count;       // item count

pthread_mutex_t mutex;       // pthread mutex
unsigned int prod_index = 0;    // producer index into shared buffer
unsigned int cons_index = 0;    // consumer index into shard buffer

pthread_cond_t cond_full;   // condition variable to handle when the shared buffer is full
pthread_cond_t cond_empty;  // condition variable to handle when the shared buffer is empty

// function prototypes
void * producer(void *arg);
void * consumer(void *arg);

int main()
{
   pthread_t prod_tid, cons_tid1, cons_tid2;

   // initialize pthread variables
   pthread_mutex_init(&mutex, NULL);
   pthread_cond_init(&cond_full, NULL);
   pthread_cond_init(&cond_empty, NULL);
  
   // start producer thread
   pthread_create(&prod_tid, NULL, producer, NULL);

   // start consumer threads
   pthread_create(&cons_tid1, NULL, consumer, NULL);
   pthread_create(&cons_tid2, NULL, consumer, NULL);
  
   // wait for threads to finish
   pthread_join(prod_tid, NULL);
   pthread_join(cons_tid1, NULL);
   pthread_join(cons_tid2, NULL);
          
   // clean up
   pthread_mutex_destroy(&mutex);
   pthread_cond_destroy(&cond_full);
   pthread_cond_destroy(&cond_empty);
  
   return 0;
}

// producer thread executes this function
void * producer(void *arg)
{
   char key;

   printf("Enter text for producer to read and consumer to print, use Ctrl-C to exit.\n\n");

   // this loop has the producer read in from stdin and place on the shared buffer
   while (1)
   {
       // read input key
       scanf("%c", &key);

       // acquire mutex lock
       pthread_mutex_lock(&mutex);

       // this loop is used to poll the shared buffer to see if it is full:
       // -- if full, unlock and sleep until signalled, and loop again to handle spurious wakes
       // -- if not full, keep locked and proceed to place character on shared buffer

       // loop to account for spurious wakes
       while (!(shared_count < NITEMS))
       {
           // if buffer is full, release mutex lock
           // and sleep until signalled
           pthread_cond_wait(&cond_full, &mutex);
       }

       // store key in shared buffer
       shared_buffer[prod_index] = key;

       // update shared count variable
       shared_count++;

       // update producer index
       if (prod_index == NITEMS - 1)
           prod_index = 0;
       else
           prod_index++;
      
       // signalling the condition variable
       // since the shared buffer is not empty
       pthread_cond_signal(&cond_empty);

       // release mutex lock
       pthread_mutex_unlock(&mutex);
   }

   return NULL;
}

// consumer thread executes this function
void * consumer(void *arg)
{
   char key;

   long unsigned int id = (long unsigned int)pthread_self();

   // this loop has the consumer gets from the shared buffer and prints to stdout
   while (1)
   {
       // acquire mutex lock
       pthread_mutex_lock(&mutex);

       // this loop is used to poll the shared buffer to see if it is empty:
       // -- if empty, unlock and sleep until signalled, and loop again to handle spurious wakes
       // -- if not empty, keep locked and proceed to get character from shared buffer

       while (!(shared_count > 0))
       {
           // if buffer is empty, release mutex lock
           // and sleep until signalled
           pthread_cond_wait(&cond_empty, &mutex);
       }

       // read key from shared buffer
       key = shared_buffer[cons_index];
      
       // echo key
       printf("consumer %lu: %c\n", (long unsigned int) id, key);

       // update shared count variable
       shared_count--;

       // update consumer index
       if (cons_index == NITEMS - 1)
           cons_index = 0;
       else
           cons_index++;

       // signalling the condition variable
       // since the shared buffer is not full
       pthread_cond_signal(&cond_full);
  
       // release mutex lock
       pthread_mutex_unlock(&mutex);
   }

   return NULL;
}

Here is a snapshot of a demo run:

As you can see, it's working as expected and it shows a 0.0% CPU usage.

Hope this helps! :)