算法设计：用信号量来解决哲学家问题

先决条件– 流程同步, 信号量, 使用监视器的餐饮哲学家解决方案

餐饮哲学家的问题–用餐哲学家问题指出, K位哲学家坐在圆桌旁, 每对哲学家之间有一根筷子。每个哲学家之间只有一根筷子。如果一个哲学家可以拿起他旁边的两根筷子, 他可能会吃东西。一根筷子可以由其相邻的任何一个跟随者捡起, 但不能同时被两个捡起。

餐饮哲学家的信号量解决方案–

每个哲学家都由以下伪代码表示：

process P[i]
 while true do
   {  THINK;
      PICKUP(CHOPSTICK[i], CHOPSTICK[i+1 mod 5]);
      EAT;
      PUTDOWN(CHOPSTICK[i], CHOPSTICK[i+1 mod 5])
   }

哲学家有三种状态：思维, 饥饿和进食。这里有两个信号量：互斥体和哲学家的信号量数组。使用互斥量使得没有两个哲学家可以同时访问取件或取件。该数组用于控制每个哲学家的行为。但是, 由于编程错误, 信号量可能导致死锁。

代码–

#include <pthread.h>
#include <semaphore.h>
#include <stdio.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 semaphores
     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);
}

注意 -下面的程序只能使用带有信号灯和pthread库的C编译器进行编译。

参考–

餐饮哲学家的解决方案– cs.gordon.edu

餐饮哲学家的解决方案– cs.indiana.edu

---