Homework 4 Sample Solutions
CS338, Fall 2000, Jim Teresco
Answers here gathered from student submissions where possible.

Graded out of 20 points

1. The Dining Savages. A tribe of savages eats communal dinners from a
   large pot that can hold M servings of stewed missionary. When a
   savage wants to eat, he helps himself from the pot, unless it is
   empty. If the pot is empty, the savage wakes up the cook and then
   waits until the cook has refilled the pot. The behavior of the
   savages and cook is defined by the following processes:

    Savage i: while (1) { get serving from pot; eat; } 
    Cook: while (1) { sleep; put M servings in pot; } 

   Develop psuedocode for the actions of the savages and the cook. Use
   semaphores for synchronization.  Your solution should avoid
   deadlock and awaken the cook only when the pot is empty. (10 points)

semaphores: mutex=1, cook_needed=0, pot_filled=0;
integer servings_available=M; // 0 is just as valid

Cook process:

  while (1) {
    wait(cook_needed);
    servings_available=M;  // fill pot
    signal(pot_filled);
  }

Savage process (multiple instances possible):

  while (1) {
    wait(mutex);
    if (servings_available == 0) {
       signal(cook_needed);
       wait(pot_filled);
    }
    servings_available--;
    signal(mutex);
    // eat the serving here
  }

2. Recall the example from class on September 26 which showed an
   implementation of a producer/consumer interaction though a buffer
   of one integer using pthreads to create the producer and consumer,
   and used unix semaphores for synchronization. Modify this code (i)
   to allow the buffer to be of any size by a second command-line
   argument, and (ii) to allow the number of producer threads and
   consumer threads to be controlled by additional command-line
   arguments. Run it on the FreeBSD systems in the Williams CSLab and
   on the Origin 2000 at NCSA. Compare the performance for different
   numbers of threads and different buffer sizes in each case. What
   conclusions can you draw from these comparisons? (10 points)


/* Originally taken from Andrews,
   http://www.cs.arizona.edu/people/greg/mpdbook/lectures/pc.sems.c
   modified for use in CS 338, Williams College, Fall 2000

   Modifications are Copyright (C) James D. Teresco, All Rights Reserved

   a simple producer/consumer using semaphores and threads

   usage on Solaris:
     gcc thisfile.c -lpthread -lposix4
     ./a.out numIters

   Solaris supports shared semaphores, so sem_init may be passed the
   value SHARED (1)

   usage on FreeBSD:
     gcc -pthread thisfile.c
     ./a.out numIters

   FreeBSD does not support shared semaphores, so sem_init must be
   passed the value NOTSHARED (0)

 */
 
#include <pthread.h>
#include <stdio.h>
#include <semaphore.h>
#define NOTSHARED 0
#define SHARED 1

void *Producer(void *);  /* the two threads */
void *Consumer(void *);

sem_t empty, full;         /* the global semaphores */
int numIters;              /* total number of items to process */
int global_produced, global_consumed;
sem_t glob_prod_mutex, glob_cons_mutex; /* mutex these variables */
int *data;                 /* shared buffer         */
int bufsize;               /* size of the shared buffer */
int next_prod, next_cons;  /* pointers into the buffer */
sem_t next_prod_mutex, next_cons_mutex; /* mutex on buffer access */

/* main() -- read command line and create threads, then
             print result when the threads have quit */

int main(int argc, char *argv[]) {
  /* thread ids and attributes */
  pthread_t *pid, *cid;  
  pthread_attr_t attr;
  int numProd, numCons;
  int i;
  int retval;

  pthread_attr_init(&attr);
  pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

  if (argc != 5) {
    fprintf(stderr,"Usage: %s numIters bufsize numprod numcons\n", argv[0]);
    exit(1);
  }
  numIters = atoi(argv[1]);
  bufsize = atoi(argv[2]);
  numProd = atoi(argv[3]);
  numCons = atoi(argv[4]);

  sem_init(&empty, NOTSHARED, bufsize);  /* sem empty = bufsize */
  sem_init(&full, NOTSHARED, 0);   /* sem full = 0  */
  sem_init(&next_prod_mutex, NOTSHARED, 1);  /* sem prod_mutex = 1 */
  sem_init(&next_cons_mutex, NOTSHARED, 1);  /* sem cons_mutex = 1 */
  sem_init(&glob_prod_mutex, NOTSHARED, 1);  /* sem prod_mutex = 1 */
  sem_init(&glob_cons_mutex, NOTSHARED, 1);  /* sem cons_mutex = 1 */

  printf("main started, numIters=%d, bufsize=%d, numProd=%d, numCons=%d\n",
	 numIters, bufsize, numProd, numCons);
  data = (int *)malloc(bufsize*sizeof(int));
  pid = (pthread_t *)malloc(numProd*sizeof(pthread_t));
  cid = (pthread_t *)malloc(numCons*sizeof(pthread_t));

  global_produced=0;
  global_consumed=0;
  next_prod=0;
  next_cons=0;

  for (i=0; i<numProd; i++) {
    pthread_create(&(pid[i]), &attr, Producer, NULL);
  }
  for (i=0; i<numCons; i++) {
    pthread_create(&(cid[i]), &attr, Consumer, NULL);
  }

  /* while we are here, the producers and consumers are running */

  for (i=0; i<numProd; i++) {
    pthread_join(pid[i], (void **)&retval);
    printf("producer %d finished after producing %d items\n", i, retval);
  }
  for (i=0; i<numCons; i++) {
    pthread_join(cid[i], (void **)&retval);
    printf("consumer %d finished after consuming %d items\n", i, retval);
  }

  free(data);
  free(pid);
  free(cid);

  sem_destroy(&empty);
  sem_destroy(&full);
  sem_destroy(&next_prod_mutex);
  sem_destroy(&next_cons_mutex);
  sem_destroy(&glob_prod_mutex);
  sem_destroy(&glob_cons_mutex);
  
  printf("main done\n");
}

/* deposit items into the data buffer until */
void *Producer(void *arg) {
  int produced=0;

  printf("Producer created\n");
  while (1) {
    sem_wait(&glob_prod_mutex);
    if (global_produced == numIters) {
      sem_post(&glob_prod_mutex);
      pthread_exit((void *)produced);
    }
    global_produced++;
    sem_post(&glob_prod_mutex);
    produced++;

    sem_wait(&empty);
    sem_wait(&next_prod_mutex);
    data[next_prod]=produced;
    next_prod++; if (next_prod==bufsize) next_prod=0;
    sem_post(&next_prod_mutex);
    sem_post(&full);
  }
}

/* fetch numIters items from the buffer and sum them */
void *Consumer(void *arg) {
  int total = 0, consumed = 0;
  printf("Consumer created\n");

  while (1) {
    sem_wait(&glob_cons_mutex);
    if (global_consumed == numIters) {
      sem_post(&glob_cons_mutex);
      printf("for %d items consumed, the total is %d\n", consumed, total);
      pthread_exit((void *)consumed);
    }
    global_consumed++;
    sem_post(&glob_cons_mutex);
    consumed++;

    sem_wait(&full);
    sem_wait(&next_cons_mutex);
    total += data[next_cons];
    next_cons++; if (next_cons==bufsize) next_cons=0;
    sem_post(&next_cons_mutex);
    sem_post(&empty);
  }
}