The Dining Philosophers Problem by implementing a solution using Pthreads mutex locks and condition variables

The Dining Philosophers Problem
This problem will require implementing a solution
using Pthreads mutex locks and condition variables.
The Philosophers
Begin by creating five philosophers, each identified by a number 0 . . 4. Each
philosopher will run as a separate thread.  Philosophers alternate between thinking and eating.
To simulate both activities, have the thread sleep for a random period between
one and three seconds. When a philosopher wishes to eat, she invokes the
function pickup forks(int philosopher number)
where philosopher number identifies the number of the philosopher wishing
to eat. When a philosopher finishes eating, she invokes
return forks(int philosopher number)
Pthreads Condition Variables
Condition variables in Pthreads behave similarly to those described in Section
5.8. However, in that section, condition variables are used within the context
of a monitor, which provides a locking mechanism to ensure data integrity.
Since Pthreads is typically used in C programs—and since C does not have
a monitor— we accomplish locking by associating a condition variable with
a mutex lock. Pthreads mutex locks are covered in Section 5.9.4. We cover
Pthreads condition variables here.
Condition variables in Pthreads use the pthread cond t data type and
are initialized using the pthread cond init() function. The following code
creates and initializes a condition variable as well as its associated mutex lock:
pthread mutex t mutex;
pthread cond t cond var;
pthread mutex init(&mutex,NULL);
pthread cond init(&cond var,NULL);

The pthread cond wait() function is used for waiting on a condition
variable. The following code illustrates how a thread can wait for the condition
a == bto become true using a Pthread condition variable:

pthread mutex lock(&mutex);
while (a != b)
pthread cond wait(&mutex, &cond var);
pthread mutex unlock(&mutex);

The mutex lock associated with the condition variable must be locked
before the pthread cond wait() function is called, since it is used to protect
the data in the conditional clause from a possible race condition. Once this
lock is acquired, the thread can check the condition. If the condition is not true,
the thread then invokes pthread cond wait(), passing the mutex lock and
the condition variable as parameters. Calling pthread cond wait() releases
the mutex lock, thereby allowing another thread to access the shared data and
possibly update its value so that the condition clause evaluates to true. (To
protect against program errors, it is important to place the conditional clause
within a loop so that the condition is rechecked after being signaled.)
A thread that modifies the shared data can invoke the
pthread cond signal() function, thereby signaling one thread waiting
on the condition variable. This is illustrated below:
pthread mutex lock(&mutex);
a = b;
pthread cond signal(&cond var);
pthread mutex unlock(&mutex);
It is important to note that the call to pthread cond signal() does not
release the mutex lock. It is the subsequent call to pthread mutex unlock()
that releases the mutex. Once the mutex lock is released, the signaled thread
becomes the owner of the mutex lock and returns control from the call to
pthread cond wait().

Answer:

main_1_2_3_4.c

/**Solution to dining philosophers using POSIX mutexes and condition varaibles.*/

#include <pthread.h>
#include <stdio.h>
#include "dp.h"

pthread_t tid[NUMBER];

/**
 * Initialize all relevant data structures and
 * synchronization objects.
 */
void init()
{
int i;

	for (i = 0; i < NUMBER; i++) {
		state[i] = THINKING;
		thread_id[i] = i;
		pthread_cond_init(&cond_vars[i],NULL);
	}

	pthread_mutex_init(&mutex_lock, NULL);
}

void create_philosophers()
{
int i;

	for (i = 0; i < NUMBER; i++) {
		pthread_create(&tid[i], 0, philosopher, (void *)&thread_id[i]);
	}
}

int main(void)
{
int i;

	init();

	create_philosophers();

	for (i = 0; i < NUMBER; i++)
		pthread_join(tid[i],NULL);

	return 0;
}

eating.c

/**simulate eating*/

#include <stdio.h>

void eating(int sleep_time) 
{
	//printf("eating for %d seconds\n",sleep_time);
	sleep(sleep_time);
}

philosopher.c

/**General structure of a dining philosopher*/

#include <pthread.h>
#include <stdio.h>
#include <time.h>
#include "dp.h"

void *philosopher(void *param)
{
	int *lnumber = (int *)param;
	int number = *lnumber;
	int sleep_time;
	int times_through_loop = 0;

	srandom((unsigned)time(NULL));

	while (times_through_loop < 5) {
		sleep_time = (int)((random() % MAX_SLEEP_TIME) + 1);
		thinking(sleep_time);

		pickup_forks(number);

		printf("Philosopher %d is eating\n",number);

		sleep_time = (int)((random() % MAX_SLEEP_TIME) + 1);
		eating(sleep_time);

		printf("Philosopher %d is thinking\n",number);
		return_forks(number);
		
		++times_through_loop;
	}
}

thinking.c

/**simulate thinking*/

#include <stdio.h>

void thinking(int sleep_time) 
{
	//printf("thinking for %d seconds",sleep_time);
	sleep(sleep_time);
}

dining.c

/**Solution to dining philosophers using POSIX mutexes and condition varaibles.*/

#include <pthread.h>
#include <stdio.h>
#include "dp.h"

/* return the left neighbor */
int left_neighbor(int number)
{
	if (number == 0)
		return NUMBER - 1;
	else
		return number - 1;
}

/* return the right neighbor */
int right_neighbor(int number)
{
	if (number == NUMBER - 1)
		return 0;
	else
		return number + 1;
}

void test(int i)
{
	/** 
	 * Basic idea is this:
	 * If I'm hungry, and my left and right neighbors aren't eating, then let me eat.
	 */
	if ( (state[left_neighbor(i)] != EATING) && (state[i] == HUNGRY) && (state[right_neighbor(i)] != EATING) ) {
		state[i] = EATING;
		pthread_cond_signal(&cond_vars[i]);
	}
}

/** A philosopher calls this when it wants to pick up its forks.*/

void pickup_forks(int number)
{
	pthread_mutex_lock(&mutex_lock);

	state[number] = HUNGRY;
	test(number);

	while (state[number] != EATING) {
		pthread_cond_wait(&cond_vars[number], &mutex_lock);
	}

	pthread_mutex_unlock(&mutex_lock);
}

/** A philosopher calls this when it wants to return its forks.*/

void return_forks(int number)
{
	pthread_mutex_lock(&mutex_lock);

	state[number] = THINKING;
	test(left_neighbor(number));
	test(right_neighbor(number));

	pthread_mutex_unlock(&mutex_lock);
}

dp.h

/**Header file for dining philosophers*/

#include <pthread.h>

// the number of philosophers
#define NUMBER 		5

// the maximum time (in seconds) to sleep
#define MAX_SLEEP_TIME	5

// different philosopher states
//#define THINKING		0
//#define HUNGRY			1
//#define EATING			2

// the state of each philosopher (THINKING, HUNGRY, EATING)
//int state[NUMBER];
enum {THINKING, HUNGRY, EATING} state[NUMBER];

// the thread id of each philosopher (0 .. NUMBER - 1)
int thread_id[NUMBER];

// condition variables and associated mutex lock
pthread_cond_t		cond_vars[NUMBER];
pthread_mutex_t 	mutex_lock;

void *philosopher(void *param);

Makefile_1_2_3_4_5_6_7 file

# To run, enter
# make all

all: diningphilosophers

diningphilosophers: main.o dining.o eating.o thinking.o philosopher.o
	gcc -lpthread -o diningphilosophers main.o dining.o thinking.o eating.o philosopher.o

main.o: main.c dp.h
	gcc -lpthread -c main.c

dining.o: dining.c dp.h
	gcc -lpthread -c dining.c

philosopher.o: philosopher.c dp.h
	gcc -lpthread -c philosopher.c

eating.o: eating.c
	gcc -lpthread -c eating.c

thinking.o: thinking.c
	gcc -lpthread -c thinking.c