dining philosophers with deadlock livelock and starvation

Question

this is a solution for the dining philosophers problem from geeksforgeeks using semaphores:

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

#define N 5 
#define THINKING 2 
#define HUNGRY 1 
#define EATING 0 
#define LEFT (phnum + 4) % N 
#define RIGHT (phnum + 1) % N 

int state[N]; 
int phil[N] = { 0, 1, 2, 3, 4 }; 

sem_t mutex; 
sem_t S[N]; 

void test(int phnum) 
{ 
    if (state[phnum] == HUNGRY 
        && state[LEFT] != EATING 
        && state[RIGHT] != EATING) { 
        // state that eating 
        state[phnum] = EATING; 

        sleep(2); 

        printf("Philosopher %d takes fork %d and %d\n", 
                    phnum + 1, LEFT + 1, phnum + 1); 

        printf("Philosopher %d is Eating\n", phnum + 1); 

        // sem_post(&S[phnum]) has no effect 
        // during takefork 
        // used to wake up hungry philosophers 
        // during putfork 
        sem_post(&S[phnum]); 
    } 
} 

// take up chopsticks 
void take_fork(int phnum) 
{ 

    sem_wait(&mutex); 

    // state that hungry 
    state[phnum] = HUNGRY; 

    printf("Philosopher %d is Hungry\n", phnum + 1); 

    // eat if neighbours are not eating 
    test(phnum); 

    sem_post(&mutex); 

    // if unable to eat wait to be signalled 
    sem_wait(&S[phnum]); 

    sleep(1); 
} 

// put down chopsticks 
void put_fork(int phnum) 
{ 

    sem_wait(&mutex); 

    // state that thinking 
    state[phnum] = THINKING; 

    printf("Philosopher %d putting fork %d and %d down\n", 
        phnum + 1, LEFT + 1, phnum + 1); 
    printf("Philosopher %d is thinking\n", phnum + 1); 

    test(LEFT); 
    test(RIGHT); 

    sem_post(&mutex); 
} 

void* philospher(void* num) 
{ 

    while (1) { 

        int* i = num; 

        sleep(1); 

        take_fork(*i); 

        sleep(0); 

        put_fork(*i); 
    } 
} 

int main() 
{ 

    int i; 
    pthread_t thread_id[N]; 

    // initialize the mutexes 
    sem_init(&mutex, 0, 1); 

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

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

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

        // create philosopher processes 
        pthread_create(&thread_id[i], NULL, 
                    philospher, &phil[i]); 

        printf("Philosopher %d is thinking\n", i + 1); 
    } 

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

        pthread_join(thread_id[i], NULL); 
}

https://www.geeksforgeeks.org/dining-philosopher-problem-using-semaphores/

this code have a low probability for deadlock livelock and starvation, i want to change it that it will have deadlock,livelock or starvation with high probability, how can i do that?

also how i can ensure this solution will not have any of those problems for 100% (if possible)

score 0 · Answer 1 · answered May 31 '20 at 20:01

Ok, first, the best solution i know for the dinning philosophers problem is this (from modern operating systems - 4th edition of Tannebaum and Bos):

#define TRUE 1
#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2

typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];

void
philosopher(int i){
  while(TRUE){
    think();
    take_forks(i);
    eat();
    put_forks(i)
  }
}

void
take_forks(int i){
  down(&mutex);
  state[i] = HUNGRY;
  test(i);
  up(&mutex);
  down(&s[i]);
}

void
put_forks(i){
  down(&mutex);
  state[i] = THINKING;
  test(LEFT);
  test(RIGHT);
  up(&mutex);
}

void
test(int i){
  if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
    state[i] = EATING;
    up(&s[i]);
  }
}

Off course for simplicity prototypes and some function are omitted, but the point is that if you want to create a completely unsafe dining philosopher, the solution is a think like this:

  #define N 5

  void philosopher(int i){
    while(TRUE){
      think();
      take_fork(i);
      take_fork((i+1)%N);
      eat();
      put_fork(i);
      put_fork((i+1)%N);
    }
  }

explanaiton: This program will produce pretty easly a race condition, infact two philosopher will take the same fork, this because we don't use semaphores for wait our turn for eat and it will also produce a starvation because we don't use test() for check if some one were using already our fork, so if you want to modify your program for have this problems you should remove the test() and all the pieces of code where you have used semaphores and any kind of test.

dining philosophers with deadlock livelock and starvation

1 Answers1