Dining Philosopher’s problem is a famous problem in OS2. A deadlock may happen w

Question

Dining Philosopher’s problem is a famous problem in OS2. A deadlock may happen when all philosophers want to start eating at the same time and pick up one chopstick and wait for the other chopstick. We can use semaphores to simulate the availability of chopsticks.

To prevent the deadlock; we have discussed this solution:

1. Allow a philosopher to pick up her chopsticks only if both are available.

Based on the program, please implement the above solution to prevent the deadlock.

#include<stdio.h>

#include<semaphore.h>

#include<pthread.h>

#define N 5 //the number of philosophers

sem_t S[N]; //semaphores for chopsticks

void * philospher(void *num);

void take_chopsticks(int);

void put_chopsticks(int);

int phil_num[N]={0,1,2,3,4}; //philosopher ID

int main()

{

int i;

pthread_t thread_id[N];

for(i=0;i<N;i++)

sem_init(&S[i],0,1);

for(i=0;i<N;i++)

pthread_create(&thread_id[i],NULL,philospher,&phil_num[i]);

for(i=0;i<N;i++)

pthread_join(thread_id[i],NULL);

}

void *philospher(void *num)

{

while(1)

{

int *i = num;

take_chopsticks(*i);

put_chopsticks(*i);

}

}

void take_chopsticks(int ph_num)

{

printf("Philosopher %d is Hungry ",ph_num);

sem_wait(&S[ph_num]); //take the left chopstick

printf("Philosopher %d takes chopstick %d ",ph_num, ph_num);

sleep(1);

sem_wait (&S[(ph_num+1)%N]); //take the right chopstick

printf("Philosopher %d takes chopstick %d ",ph_num,(ph_num+1)%N);

printf("Philosopher %d is eating ",ph_num);

sleep(1);

}

void put_chopsticks(int ph_num)

{

sem_post (&S[ph_num]); //put the left chopstick

printf("Philosopher %d putting chopstick %d ",ph_num, ph_num);

sleep(1);

sem_post (&S[(ph_num+1)%N]); //put the right chopstick

printf("Philosopher %d putting chopstick %d ",ph_num,(ph_num+1)%N);

printf("Philosopher %d is thinking ",ph_num);

sleep(1);

}

Explanation / Answer

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

#define N 5 // The number of philosophers
#define THINKING 2
#define HUNGRY 1
#define EATING 0
#define LEFT (ph_num + 4) % N
#define RIGHT (ph_num + 1) % N

int state[N];
int phil_num[N] = {0,1,2,3,4}; //philosopher ID

sem_t mutex;
sem_t S[N]; // Semaphores for chopsticks

// Function to check the Philosopher state
void check(int ph_num)
{
// Checks if the philosopher state is hungry and its left philosopher state is not eating and right philosopher state is not eating
if (state[ph_num] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
{
// Assigns the state eating to the index ph_num philosopher state
state[ph_num] = EATING;
// Wait 200 milliseconds
_sleep(200);

// Displays philosopher number and taken chopsticks numbers
printf("Philosopher %d takes chopsticks %d and %d ", ph_num + 1, LEFT + 1, ph_num + 1);
// Displays the philosopher number who is eating now
printf("Philosopher %d is Eating ", ph_num + 1);
// Assigns the philosopher number to semaphore chopsticks
sem_post(&S[ph_num]);
}// End of if condition
}// End of function

// Function to take up chopsticks
void take_chopsticks(int ph_num)
{
// Calls the sem_wait function with mutex address to check the mutex value
sem_wait(&mutex);

// Assigns state hungry to the philosopher number ph_num index position
state[ph_num] = HUNGRY;

// Displays the philosopher number who is hungry
printf("Philosopher %d is Hungry ", ph_num + 1);

// Calls the function to eat if neighbours are not eating
check(ph_num);

// Calls the sem_wait function with mutex address to check the mutex value
sem_post(&mutex);

// If unable to eat wait to be Signalled
sem_wait(&S[ph_num]);

// Wait 100 milliseconds
_sleep(100);
}// End of function

// Function to put down chopsticks
void put_chopsticks(int ph_num)
{
// Calls the sem_wait function with mutex address to check the mutex value
sem_wait(&mutex);

// Assigns state thinking to the philosopher number ph_num index
state[ph_num] = THINKING;

// Displays the philosopher number who is putting the chopsticks down with chopsticks numbers
printf("Philosopher %d putting chopsticks %d and %d down ", ph_num + 1, LEFT + 1, ph_num + 1);
// Displays the philosopher number who is thinking
printf("Philosopher %d is thinking ", ph_num + 1);
// Calls the function to checks left and right status
check(LEFT);
check(RIGHT);

sem_post(&mutex);
}// End of function

// Function for each philosopher operation
void *philospher(void* num)
{
// Loops infinitely
while (1)
{
int* i = num;
// Wait 100 milliseconds
_sleep(100);
// Calls the function for taking chopsticks
take_chopsticks(*i);
// Wait 100 milliseconds
_sleep(0);
// Calls the function for putting chopsticks
put_chopsticks(*i);
}// End of while loop
}// End of function

// main function definition
int main()
{
// Loop variable
int count;
// Creates thread for number of philosophers
pthread_t philosopherID[N];

// Initializes the semaphores
sem_init(&mutex, 0, 1);

// Loops till number of philosophers
for (count = 0; count < N; count++)
// Initialize all semaphore chopsticks to zero for available
sem_init(&S[count], 0, 0);

// Loops till number of philosophers
for (count = 0; count < N; count++)
{
// Create philosopher processes
pthread_create(&philosopherID[count], NULL, philospher, &phil_num[count]);
printf("Philosopher %d is thinking ", count + 1);
}// End of for loop
// Loops till number of philosophers
for (count = 0; count < N; count++)
// Joints the thread
pthread_join(philosopherID[count], NULL);
}// End of main function

Sample Output:

Philosopher 1 is thinking
Philosopher 2 is thinking
Philosopher 3 is thinking
Philosopher 4 is thinking
Philosopher 5 is thinking
Philosopher 2 is Hungry
Philosopher 1 is Hungry
Philosopher 4 is Hungry
Philosopher 3 is Hungry
Philosopher 3 takes chopsticks 2 and 3
Philosopher 3 is Eating
Philosopher 5 is Hungry
Philosopher 5 takes chopsticks 4 and 5
Philosopher 5 is Eating
Philosopher 3 putting chopsticks 2 and 3 down
Philosopher 3 is thinking
Philosopher 2 takes chopsticks 1 and 2
Philosopher 2 is Eating
Philosopher 5 putting chopsticks 4 and 5 down
Philosopher 5 is thinking
Philosopher 4 takes chopsticks 3 and 4
Philosopher 4 is Eating
Philosopher 3 is Hungry
Philosopher 2 putting chopsticks 1 and 2 down
Philosopher 2 is thinking
Philosopher 1 takes chopsticks 5 and 1
Philosopher 1 is Eating
Philosopher 5 is Hungry
Philosopher 4 putting chopsticks 3 and 4 down
Philosopher 4 is thinking
Philosopher 3 takes chopsticks 2 and 3
Philosopher 3 is Eating
Philosopher 2 is Hungry
Philosopher 1 putting chopsticks 5 and 1 down
Philosopher 1 is thinking
Philosopher 5 takes chopsticks 4 and 5
Philosopher 5 is Eating
Philosopher 4 is Hungry
Philosopher 3 putting chopsticks 2 and 3 down
Philosopher 3 is thinking
Philosopher 2 takes chopsticks 1 and 2
Philosopher 2 is Eating
Philosopher 1 is Hungry
Philosopher 5 putting chopsticks 4 and 5 down
Philosopher 5 is thinking
Philosopher 4 takes chopsticks 3 and 4
Philosopher 4 is Eating
Philosopher 3 is Hungry
Philosopher 2 putting chopsticks 1 and 2 down
Philosopher 2 is thinking
Philosopher 1 takes chopsticks 5 and 1
Philosopher 1 is Eating
Philosopher 5 is Hungry
Philosopher 4 putting chopsticks 3 and 4 down
Philosopher 4 is thinking
Philosopher 3 takes chopsticks 2 and 3
Philosopher 3 is Eating
Philosopher 2 is Hungry
Philosopher 1 putting chopsticks 5 and 1 down
Philosopher 1 is thinking

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.