Implement the Dining Philosophers.

Part I: in a naive fashion, in order to cause a deadlock Part II: in a way that prevents deadlocks

Here are the dining philosophers:

each philosopher picks up his left fork each philosopher picks up his right fork he eats for EAT_TIME he puts down his left fork

he puts down his right fork he thinks for THINK_TIME

And all five philosophers do this simultaneously. So for a Linux implementation, we can put each philosopher in a separate pthread.

Here are some constants for your program:

#define NUM_PHILOSOPHERS 5 #define RUNTIME 10 #define EAT_TIME 2 #define THINK_TIME 1 

Here's a global variable -- the array of forks (which are mutex locks):

pthread_mutex_t forks[NUM_PHILOSOPHERS]; 

The basic idea is to create NUM_PHILOSOPHERS pthreads, by calling pthread_create() five times.

Each philosopher function will look like this:

void *philosopher(void *param); 

and the param will be a pointer to an integer value in the range 0..NUM_PHILOSOPHERS-1, which will uniquely identify the thread.

Here's the processing inside the philosopher function:

int *myID; myID = (int *) param; 

leftIdx = *myID; rightIdx = (*myID + 1) % NUM_PHILOSOPHERS; printf("P %d start ", *myID); 

while ( 1 ) { pthread_mutex_lock(&(forks[leftIdx])); usleep(1000); pthread_mutex_lock(&(forks[rightIdx])); printf("P %d, eating for %d secs ", *myID, EAT_TIME); sleep(EAT_TIME); pthread_mutex_unlock(&(forks[leftIdx])); pthread_mutex_unlock(&(forks[rightIdx])); printf("P %d, thinking for %d secs ", *myID, THINK_TIME); sleep(THINK_TIME); 

}

The usleep(1000) says "sleep for 1000 microseconds" (i.e., 1 millisecond). This gives all of the philopher threads the chance to pick up their left fork when they first start, thus increasing the chances of deadlock.

There is no true or TRUE constant in C. That's why I have "while ( 1 )". Initialize the mutexes like this:

int rtnval;

for (i=0; i 
 printf("error initializing mutex "); 
 
return(8); }
 
}
 
Start each philosopher thread as you did in the multithreaded sorting assignment:
 
int id[NUM_PHILOSOPHERS]; thread_t tid[NUM_PHILOSOPHERS]; 
 
for (i=0; i 
}
 
2
 
and then sleep for RUNTIME seconds. After that, kill the threads:
 
for (i=0; i 
}
 
Part I
 
Build out the rest of the code to implement this. When you run it, you should see a deadlock. Here's what I get when I run:
 
$ a.out P 0 start P 3 start P 2 start P 4 start P 1 start 
 
(and then it just sits there).
 
Part II
 
Use some scheme to prevent deadlock. Create a different function philosopher_good():
 
void *philosopher_good(void *param); 
 
All of the infrastructure will be the same, but you'll do something different in your while (1) { } loop inside the philospher_good() function--specifically, something to prevent a deadlock, while letting all of the philophers make progress.
 
Here's what I get:
 
$ a.out P 0 start P 1 start P 3 start P 2 start P 4 start P 1, eating for 2 secs P 3, eating for 2 secs P 1, thinking for 1 secs P 3, thinking for 1 secs P 0, eating for 2 secs P 2, eating for 2 secs P 0, thinking for 1 secs P 4, eating for 2 secs P 2, thinking for 1 secs P 1, eating for 2 secs P 4, thinking for 1 secs 
 
3
 
P 3, eating for 2 secs P 1, thinking for 1 secs P 0, eating for 2 secs P 3, thinking for 1 secs P 2, eating for 2 secs P 0, thinking for 1 secs P 4, eating for 2 secs 
 
Here are a couple of things you can look at to give you ideas: * pthread_mutex_trylock() * Dijkstra's Resource Hierarchy Solution for deadlocks
  philosopher 0 fork 1 fork 0 philosopher 4 philosopher 1 food fork 4 fork 2 philosopher 2 philosopher 3 fork 3  philosopher 0 fork 1 fork 0 philosopher 4 philosopher 1 food fork 4 fork 2 philosopher 2 philosopher 3 fork 3