带着死锁和饥饿的哲学家进餐

Question

这是Geeksforgeeks使用信号量解决用餐哲学家问题的方法：

#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/

这个代码死锁活锁和饥饿的概率很低，我想改变它，它将有死锁，活锁或饥饿的概率很高，我怎么做？

此外，我如何确保这个解决方案不会有任何这些问题100%（如果可能的话）

Answer 1

好的，首先，我所知道的解决哲学家就餐问题的最佳方案是（来自现代操作系统-第四版Tannebaum和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]);
  }
}

为了简单起见，我们省略了原型和一些函数，但问题是，如果您想创建一个完全不安全的就餐哲学家，解决方案是这样想的：

  #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);
    }
  } 

解释：这个程序很容易产生竞争条件，事实上两个哲学家会使用同一个叉子，这是因为我们不使用信号灯等待轮到我们吃东西，它也会产生饥饿，因为我们不使用test（）检查是否有人已经在使用我们的叉子，因此，如果你想修改你的程序来解决这个问题，你应该删除test（）和所有你使用过信号量和任何类型测试的代码。