Consider the classic lock-based solution to the dining philosophers problem (acc
ID: 3743185 • Letter: C
Question
Consider the classic lock-based solution to the dining philosophers problem (according to Wikipedia):
Five silent philosophers sit at a table around a bowl of spaghetti. A fork is placed between each pair of adjacent philosophers.
Each philosopher must alternately think and eat. Eating is not limited by the amount of spaghetti left: assume an infinite supply. However, a philosopher can only eat while holding both the fork to the left and the fork to the right (an alternative problem formulation uses rice and chopsticks instead of spaghetti and forks).
Each philosopher can pick up an adjacent fork, when available, and put it down, when holding it. These are separate actions: forks must be picked up and put down one by one.
The problem is how to design a discipline of behavior (a concurrent algorithm) such that each philosopher won't starve, i.e. can forever continue to alternate between eating and thinking.
In this implementation, there are n philosophers with id number i, and each thread runs the following pseudocode based on an array of pthread_mutex_t structures called fork_lock:
fork_lock[i].acquire();
fork_lock[(i+1)%n].acquire();
// eat
fork_lock[i].release();
fork_lock[(i+1)%n].release();
this solution can deadlock, though it might not right away.
In fact, there are four causes to this deadlock, which must be simultaneously met for deadlock to actually occur:
Mutual Exclusion: two or more threads (philosophers) want the same resource (fork), and if one has it, the other(s) do not
No Preemption: Once the fork is picked up, it cannot be taken away to resolve the “fight”
Circular Dependency: Thread A wants resource X and is holding resource Y, while Thread B wants resource Y and is holding X
Hold-And-Wait: Each thread holds one (or more) of the needed resources while waiting for the other(s)
Correcting any of these four conditions removes the deadlock situation. Fix the above solution to the dining philosophers problem by correcting the “hold-and-wait” condition. That is, if a philosopher picks up a single fork, that philosopher is guaranteed to pick up both forks, or else the philosopher will not attempt to pick up any forks (by blocking). You may introduce additional pthread_mutex_t locks, or change the pseudocode. Explain your changes.
Explanation / Answer
CODE
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
void dine(void );
int chopsticks[5];
pthread_mutex_t mutex;
pthread_cond_t cond[5]; //one for each philosopher
int main(int argc, char *argv[])
{
int i, rc;
pthread_mutex_init(&mutex, NULL);
pthread_t philsophers[5];
srand(time(NULL));
/ Initialize chopsticks and cond vars /
for (i=0; i<5; ++i)
{
pthread_cond_init(&cond[i], NULL);
chopsticks[i]=0;
}
/ Spawn threads /
for (i=0; i<5; ++i)
{
if( (rc=pthread_create( &philsophers[i], NULL, dine, &i)) )
printf("Thread creation failed: %d ", rc);
sleep(1);
}
/ Wait for thread completion /
for (i=0; i<5; ++i)
pthread_join( philsophers[i], NULL);
exit(0);
}
void think(int pnum)
{
printf("philosopher %d is thinking ", pnum);
}
void eat(int pnum)
{
pthread_mutex_lock(&mutex);
//if chopstick isnt available, unlock the mutex and wait for chopstick
if(chopsticks[pnum])
pthread_cond_wait(&cond[pnum], &mutex);
printf("philosopher %d picked left chopstick ", pnum);
chopsticks[pnum] = 1;
//if chopstick isnt available, unlock the mutex and wait for chopstick
if(chopsticks[(pnum + 1) % 5])
pthread_cond_wait(&cond[(pnum + 1) % 5], &mutex);
printf("philosopher %d picked right chopstick ", pnum);
chopsticks[(pnum + 1) % 5] = 1;
//lets use the chopsticks
printf("philosopher %d is eating ", pnum);
//done using
chopsticks[pnum] = 0;
chopsticks[(pnum + 1) % 5] = 0;
printf("philosopher %d put both chopsticks down ", pnum);
pthread_cond_signal(&cond[pnum]);
pthread_cond_signal(&cond[(pnum + 1) % 5]);
pthread_mutex_unlock(&mutex);
}
void dine(void pnum_ptr)
{
int pnum = *(int*)pnum_ptr;
printf("Created philosopher thread %d ", pnum);
while (1)
{
think(pnum);
sleep(rand() % 3 + 1); //wait for 1 or 2 or 3 seconds
eat(pnum);
sleep(rand() % 3 + 1);
}
}
Sample Output
Created philosopher thread 0
philosopher 0 is thinking
philosopher 0 picked left chopstick
philosopher 0 picked right chopstick
philosopher 0 is eating
philosopher 0 put both chopsticks down
Created philosopher thread 1
philosopher 1 is thinking
Created philosopher thread 2
philosopher 2 is thinking
Created philosopher thread 3
philosopher 3 is thinking
philosopher 0 is thinking
philosopher 2 picked left chopstick
philosopher 2 picked right chopstick
philosopher 2 is eating
philosopher 2 put both chopsticks down
philosopher 1 picked left chopstick
philosopher 1 picked right chopstick
philosopher 1 is eating
philosopher 1 put both chopsticks down
philosopher 3 picked left chopstick
philosopher 3 picked right chopstick
philosopher 3 is eating
philosopher 3 put both chopsticks down
Created philosopher thread 4
philosopher 4 is thinking
philosopher 0 picked left chopstick
philosopher 0 picked right chopstick
philosopher 0 is eating
philosopher 0 put both chopsticks down
philosopher 1 is thinking
philosopher 0 is thinking
philosopher 2 is thinking
philosopher 4 picked left chopstick
philosopher 4 picked right chopstick
philosopher 4 is eating
philosopher 4 put both chopsticks down
philosopher 3 is thinking
philosopher 1 picked left chopstick
philosopher 1 picked right chopstick
philosopher 1 is eating
philosopher 1 put both chopsticks down
philosopher 3 picked left chopstick
philosopher 3 picked right chopstick
philosopher 3 is eating
philosopher 3 put both chopsticks down
philosopher 0 picked left chopstick
philosopher 0 picked right chopstick
philosopher 0 is eating
philosopher 0 put both chopsticks down
philosopher 2 picked left chopstick
philosopher 2 picked right chopstick
philosopher 2 is eating
philosopher 2 put both chopsticks down
philosopher 4 is thinking
philosopher 1 is thinking
philosopher 4 picked left chopstick
philosopher 4 picked right chopstick
philosopher 4 is eating
philosopher 4 put both chopsticks down
philosopher 3 is thinking
philosopher 0 is thinking
philosopher 2 is thinking
philosopher 2 picked left chopstick
philosopher 2 picked right chopstick
philosopher 2 is eating
philosopher 2 put both chopsticks down
philosopher 1 picked left chopstick
philosopher 1 picked right chopstick
philosopher 1 is eating
philosopher 1 put both chopsticks down
philosopher 3 picked left chopstick
philosopher 3 picked right chopstick
philosopher 3 is eating
philosopher 3 put both chopsticks down
philosopher 4 is thinking
philosopher 1 is thinking