In your group you are going to do the following:

First come up with a pseudocode solution to synchronize the actions of Producer and Consumer threads that add and remove items to a shared, fixed-capacity buffer:

  • Some number of Producer threads, each in a loop forever:

    1. produce the next item

    2. add it to the shared buffer (to one end of a circular queue)

  • Some number of Consumer threads, each in a loop forever:

    1. remove the next item from the front of the buffer

    2. consume it

1. Some questions to consider:

  • Are there actions that need to be made atomic (require mutually exclusive access)?

  • Are there any scheduling types of synchronization necessary?

  • What synchronization primitives do you need, and how are they used (by whom and when)?

  • Is any other state needed to synchronize the actions of threads?

2. Starting point assumptions

  1. You may assume the following shared global buffer state.

      static char *buff;     // the buffer
  static int  N;         // total buffer capacity
  static int  size;      // current num items in the buffer
  static int  next_in;   // next insertion index in the buffer
  static int  next_out;  // next remove index in the buffer
  static int  num_items; // number of items each tid should produce or consume

  2. There exist functions to add and remove items to the buffer as a circular queue (add to one end, remove from the other).

      void add_to_queue(char item);
  char remove_from_queue();

    These functions have no synchronization, nor do they check if there is space on an add or something to remove on a remove. They just add or remove to buff in a circular fashion and update other state variables as a result of their actions.

  3. Some pthread functions:

    pthread_mutex_lock(&mutex);
pthread_mutex_unlock(&mutex);
pthread_cond_wait(&mycond, &mutex);
pthread_cond_signal(&mycond);
pthread_barrier_init(&mybarrier, NULL, numtids);
pthread_barrier_wait(&mybarrier);

  4. When you are happy with your pseudo-code algorithm talk your algorithm through with one of the professors or ninjas before moving on to the next step.

  5. Together, try implementing your algorithm in pthreads. You can do this on paper (and in fact this might be the preferred way at least as a first step), or you can try implementing and testing it using some starting point code:

    cd ~/cs31/
mkdir inclass
cd inclass
cp -r ~adanner/public/cs31/inclass/w13/ ./
cd w13
ls
Makefile  prodcons.c

make
./prodcons 8 100 10
8 Producer and Consumer tids, each producing 100 items, buff size 10

    There are already routines to add and remove items from the circular buffer, and a debug print_buffer function (call fflush(stdout) after any debug output to force it to the terminal window).

    1. Implement code in main to spawn producer and consumer tids.

    2. Implement the producer and consumer main loop functions.

    3. Add all synchronization necessary to synchronize the actions of concurrent producer and consumer threads.

  6. Look at the man pages for pthread functions:

    man pthread_create
man pthread_join
man pthread_cond_init
man pthread_mutex_init

  7. Look at the weekly lab page for other pthread examples.

3. Sharing code

If you make edits to the code and wish to share them with your in class group, a quick way without git is to use mail

$ mail username1 < prodcons.c
$ mail username2 < prodcons.c
$ mail username3 < prodcons.c

4. Extensions

If you get your solution to this working and debugged, think about a slightly different version of this problem that does two things:

  1. Compute max in parallel when the number of threads, M, does not evenly divide the number of elements in the array, N.

  2. Compute the number of times the max value occurs in the array (also in parallel).

Your solutions should only spawn off worker threads one time and only join them when all parallel computation from both parts is done.