The Dining Philosopher

compile.sh

#!/usr/bin/env bash

gcc dining_philosopher.c -o main -lpthread
./main

dining_philosopher.c

#include "dining_philosopher.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/* Globals */
static philosopher_t philosophers[N_PHILOSOPHERS];

static spoon_t spoons[N_PHILOSOPHERS];

/* Main Thread */
int main(int argc, char* argv[]) {
  pthread_attr_t attr;

  /* initialize spoons */
  int i;
  for (i = 0; i < N_PHILOSOPHERS; i++) {
    spoons[i].id = i;
    spoons[i].in_use = false;
    spoons[i].philosopher = NULL;
    pthread_mutex_init(&spoons[i].mutex, NULL);
    pthread_cond_init(&spoons[i].cv, NULL);
  }

  // default attrs of philosopher threads
  pthread_attr_init(&attr);
  pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

  /* initialize philosophers */
  for (i = 0; i < N_PHILOSOPHERS; i++) {
    pthread_t philos;

    philosophers[i].id = i;
    philosophers[i].eat_count = 0;

    pthread_create(
      &philosophers[i].thread, 
      &attr, 
      philosopher_routine, 
      &philosophers[i]
    );
  }

  pthread_exit(0);
  return EXIT_SUCCESS;
}

/**
 * @brief Philosopher thread routine
 * 
 * @param arg 
 * @return void* 
 */
void* philosopher_routine(void* arg) {
  philosopher_t* philos = (philosopher_t*)arg;

  printf("[philosopher %d] takes turn\n", philos->id);

  while (1) {
    if (can_acquire_both_spoons(philos)) {
      philos_dine(philos);
      philos_release_spoons(philos);

      // satisfy constraint
      sleep(1);
    }
  }
}

/**
 * @brief Get the right spoon object
 * 
 * @return spoon_t* 
 */
static spoon_t* get_r_spoon(philosopher_t* philos) {
  int philos_id = philos->id;
  
  if (philos_id == 0) return &spoons[N_PHILOSOPHERS - 1];

  return &spoons[philos_id - 1];
}

/**
 * @brief Get the left spoon object
 * 
 * @return spoon_t* 
 */
static spoon_t* get_l_spoon(philosopher_t* philos) {
  return &spoons[philos->id];
}

void philos_dine(philosopher_t* philos) {
  spoon_t *l_spoon = get_l_spoon(philos), 
          *r_spoon = get_r_spoon(philos);

  assert(l_spoon->philosopher == philos);
  assert(r_spoon->philosopher == philos);
  assert(l_spoon->in_use == true);
  assert(r_spoon->in_use == true);

  printf(
    "[philosopher %d] dining on the communal cake with spoons [%d,%d]\n", 
    philos->id,
    l_spoon->id,
    r_spoon->id
  );

  philos->eat_count++;
  
  // satisfy constraint
  sleep(1);
}

/**
 * @brief Release spoons in use by a given philosopher (if applicable); 
 * the philosopher here enacts the role of Producer, making available 
 * conditionally locked spoons
 * 
 * @param philos 
 */
void philos_release_spoons(philosopher_t* philos) {
  spoon_t* l_spoon = get_l_spoon(philos);
  spoon_t* r_spoon = get_r_spoon(philos);

  pthread_mutex_lock(&l_spoon->mutex);
  pthread_mutex_lock(&r_spoon->mutex);
  
  printf(
    "[philosopher %d] locks left spoon %d mutex preparing to release\n", 
    philos->id, 
    l_spoon->id
  );

  printf(
    "[philosopher %d] locks right spoon %d mutex preparing to release\n", 
    philos->id, 
    r_spoon->id
  );

  assert(l_spoon->philosopher == philos);
  assert(l_spoon->in_use == true);

  assert(r_spoon->philosopher == philos);
  assert(r_spoon->in_use == true);

  l_spoon->philosopher = NULL;
  l_spoon->in_use = false;

  printf(
    "[philosopher %d] releases left spoon %d, unlocking its mutex and signaling its condition variable\n", 
    philos->id, 
    l_spoon->id
  );

  // send signal to condition variable, unblocking philosopher(s) awaiting the spoon 
  pthread_cond_signal(&l_spoon->cv);
  pthread_mutex_unlock(&l_spoon->mutex);
  
  r_spoon->philosopher = NULL;
  r_spoon->in_use = false;

  printf(
    "[philosopher %d] releases right spoon %d, unlocking its mutex and signaling its condition variable\n", 
    philos->id, 
    r_spoon->id
  );

  pthread_cond_signal(&r_spoon->cv);
  pthread_mutex_unlock(&r_spoon->mutex);
}

/**
 * @brief Attempt to acquire both spoons for a given philosopher;
 * the philosopher here enacts the role of Consumer, awaiting
 * the availability of each spoon
 * 
 * @param philos 
 * @return true 
 * @return false 
 */
bool can_acquire_both_spoons(philosopher_t *philos) {
  spoon_t* l_spoon = get_l_spoon(philos);
  spoon_t* r_spoon = get_r_spoon(philos);

  printf(
    "[philosopher %d] waits for left spoon %d mutex\n", 
    philos->id, 
    l_spoon->id
  );

  pthread_mutex_lock(&l_spoon->mutex);

  printf(
    "[philosopher %d] locks left spoon %d mutex\n", 
    philos->id, 
    l_spoon->id
  );

  // spoon in use, wait for cv signal
  while (l_spoon->in_use && l_spoon->philosopher != philos) {
    printf(
      "[philosopher %d] blocks while waiting for left spoon %d to become available\n",
      philos->id, 
      l_spoon->id
    );

    // await signal 
    pthread_cond_wait(&l_spoon->cv, &l_spoon->mutex);

    printf(
      "[philosopher %d] receives cv signal for left spoon %d\n",
      philos->id, 
      l_spoon->id
    );
  }

  // acquire spoon now that it is not in use
  l_spoon->in_use == true;
  l_spoon->philosopher == philos;
  pthread_mutex_unlock(&l_spoon->mutex);

  printf(
    "[philosopher %d] acquires left spoon %d and unlocks mutex\n",
    philos->id, 
    l_spoon->id
  );

  // and now the right spoon...

  printf(
    "[philosopher %d] waits for right spoon %d mutex\n", 
    philos->id, 
    l_spoon->id
  );

  pthread_mutex_lock(&r_spoon->mutex);

  printf(
    "[philosopher %d] locks right spoon %d mutex\n", 
    philos->id, 
    l_spoon->id
  );

  if (r_spoon->in_use == false) {
    r_spoon->philosopher == philos;
    r_spoon->in_use == true;
    pthread_mutex_unlock(&r_spoon->mutex);

    printf(
      "[philosopher %d] acquires right spoon %d and unlocks mutex\n",
      philos->id,
      l_spoon->id
    );

    return true;
  } else if (r_spoon->in_use == true) {
    if (r_spoon->philosopher != philos) {
      pthread_mutex_lock(&l_spoon->mutex);

      assert(l_spoon->in_use == true);
      assert(l_spoon->philosopher == philos);

      l_spoon->in_use = false;
      l_spoon->philosopher = NULL;

      pthread_mutex_unlock(&l_spoon->mutex);
      pthread_mutex_unlock(&r_spoon->mutex);

      printf(
        "[philosopher %d] releases left spoon %d because right spoon %d is not yet available\n",
        philos->id, 
        l_spoon->id,
        r_spoon->id
      );

      return false;
    } else {
      pthread_mutex_unlock(&r_spoon->mutex);

      printf(
        "[philosopher %d] already possesses right spoon %d\n",
        philos->id, 
        r_spoon->id
      );

      return true;
    }
  }
  
  // we'll never reach this point, but to make the compiler happy...
  assert(0);
  return true;
}
/*

o philosopher (pN)
|* spoon (sN)

   s0|*   p1  |*s1   p2
      ____o_________o_____
  p0 |                   |
  o |       .i.i.       |
   |        |||        | |* s2
  |___________________|
|*         o         o p3        
s4         p4    |*s3     

*/

dining_philosopher.h

#ifndef DINING_PHILOS_H
#define DINING_PHILOS_H

#include <pthread.h>
#include <stdbool.h>

#define N_PHILOSOPHERS 5

/* Structures */
typedef struct philosopher {
  int id;
  int eat_count; /* N times this thread has accessed the 'cake' resource */
  pthread_t thread;
} philosopher_t;

typedef struct spoon {
  int id;
  bool in_use; /* Indicative of this resource's status */
  philosopher_t* philosopher; /* The philosopher currently in possesion of this resource */
  pthread_mutex_t mutex; /* For mutual exclusion */
  pthread_cond_t cv; /* For thread synchronization for this resource */
} spoon_t;

/* Functions */
void* philosopher_routine(void* arg);

static spoon_t* get_right_spoon();

static spoon_t* get_left_spoon();

void philos_dine(philosopher_t* philos);

void philos_release_spoons(philosopher_t* philos);

bool can_acquire_both_spoons(philosopher_t *philos);

#endif /* DINING_PHILOS_H */