C language

CS 201 Assignment #5: Synchronization and Deadlocks

Assigned Wednesday, 10/24; due Monday, 11/5 at 11:59 pm.

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:

philosopher 1

philosopher 2 philosopher 3

philosopher 4

philosopher 0

fork 0fork 1

fork 2

fork 3

fork 4

food

The processing is like this:

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.

1

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\n", *myID);

while ( 1 ) { pthread_mutex_lock(&(forks[leftIdx])); usleep(1000); pthread_mutex_lock(&(forks[rightIdx])); printf("P %d, eating for %d secs\n", *myID, EAT_TIME); sleep(EAT_TIME); pthread_mutex_unlock(&(forks[leftIdx])); pthread_mutex_unlock(&(forks[rightIdx])); printf("P %d, thinking for %d secs\n", *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<NUM_PHILOSOPHERS; ++i) { rtnval = pthread_mutex_init(&(forks[i]), NULL); if (rtnval != 0) { printf("error initializing mutex\n"); 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<NUM_PHILOSOPHERS; ++i) { id[i] = i; pthread_create(&(tid[i]), &attr, philosopher_good_2, &(id[i])); }

2

and then sleep for RUNTIME seconds.

After that, kill the threads:

for (i=0; i<NUM_PHILOSOPHERS; ++i) { pthread_kill(tid[i], 0); }

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

Or, you can think up your own solution.

I've thrown in more C derefencing stuff into this (such as &array[idx]). Don't panic. Build this out

slowly and carefully, and we can discuss in class any questions you have.

4