哲学家进餐问题

• 问题描述

一张圆桌旁坐了五个哲学家，每两名哲学家中间有一根筷子，每个哲学家面前有一碗米饭。哲学家重复的做思考和进餐两个操作。哲学家思考时不影响其他人，当哲学家饥饿时，才会试图拿起两边的筷子，筷子需要一根一根的拿起。只有拿起两根筷子才能进餐。

• 问题分析

相邻的哲学家对他们中间的筷子是互斥关系。解决问题的关键是如何让一名哲学家拿到左右两根筷子而不造成死锁或者饥饿现象。对哲学家和筷子进行编号。设置一个互斥信号量数组

semaphore chopstick[5]={1,1,1,1,1}
Pi(){
  do{
    P(chopstick[i])；
    P(chopstick[i+1])；
    // 进餐
    V(chopstick[i]);
    V(chopstick[i+1]);
    // 思考
  }while(1)
}

上述算法存在问题，当五个哲学家同时拿起左手边的筷子，再想拿起右手边的筷子时会死锁。为了解决这个问题，可以给哲学家拿筷子的动作进行一些限制。比如每个哲学家仅当可以左右手旁边的筷子都可用时才允许拿筷子，又或者对哲学家编号，让奇数号哲学家只能拿左手边筷子，偶数号只能拿右手边筷子。

• 解决方案1

当一名哲学家左右两边筷子都能用时才允许他拿起筷子。

semaphore chopstick[5]={1,1,1,1,1}
semaphore mutex=1;
Pi(){
  do{
    P(mutex);
    P(chopstick[i])；
    P(chopstick[i+1])；
    V(mutex);
    // 进餐
    V(chopstick[i]);
    V(chopstick[i+1]);
    // 思考
  }while(1)
}

这种方法就是将取左右两边筷子的行为定义成一个原子操作，拿筷子时只能一次同时拿起两根筷子。

• 解决方案二

semaphore chopstick[5]={1,1,1,1,1}
semaphore mutex=1;
Pi(int i){
  do{
    if(i % 2 == 0){
      P(chopstick[i])；
      P(chopstick[i+1])；
      // 进餐
      V(chopstick[i]);
      V(chopstick[i+1]);
      // 思考
    }else{
      P(chopstick[i+1])；
      P(chopstick[i])；
      // 进餐
      V(chopstick[i+1]);
      V(chopstick[i]);
    }
  }while(1)
}