哲学家就餐问题

哲学家就餐问题是经典的进程同步问题，而以下解决思路也堪称经典。 

 

n  哲学家进餐问题

n  解决思路1：只允许4位哲学家同时拿筷子。此时必然有一个哲学家能拿到2根筷子。

n  如何保证只有4位哲学家同时拿筷子？

n  可以设置一个初值为4的资源信号量。比如，4张椅子，哲学家进餐之前必须先拿到椅子才能做到桌前拿筷子。进餐完毕后，不但要释放筷子，还要释放椅子。

n  哲学家进餐问题

n  解决思路1：只允许4位哲学家同时拿筷子。此时必然有一个哲学家能拿到2根筷子。

n  var chopstick: array[0…4] of semaphore :=(1,1,1,1,1);

n      chair: semaphore := 4;

n  philosopher(i): begin

n    repeat

n      think;

n      wait(chair); //拿椅子

n      wait(chopstick[i]);

n      wait(chopstick[(i+1) mod 5]);                                        

n      eat;                                      

n      signal(chopstick[i]);                     

n      signal(chopstick[(i+1) mod 5]);

n      signal(chair);//释放椅子                  

n    until false;

n  end

n  哲学家进餐问题：解决思路1

n  椅子这种资源信号量可以减少个数。极端的情况是chair初值为1，即只有一把椅子，那么每次只允许一个哲学家进餐，肯定不会饿死，但是效率低。

 

n  哲学家进餐问题：

n  解决思路2：只有哲学家同时能够拿起左右两边的筷子的时候，才允许拿筷子。

n  此思路最简单的办法是用AND信号量解决。不过本次我们考虑用记录型信号量解决的办法。

n  关键词：原子操作。我们想办法使得哲学家拿左边和右边筷子的过程变得不受打扰。

n  哲学家进餐问题：解决思路2

n  如何让拿两边筷子的动作变成一个原子操作？

n  桌边配备一名服务员，饥饿时招呼一个服务员过来帮哲学家拿筷子。服务员拿完左右两边的筷子就可以去帮助其他人服务。

n  哲学家进餐问题

n  解决思路2：只有哲学家同时能够拿起左右两边的筷子的时候，才允许拿筷子。

n  var chopstick: array[0…4] of semaphore :=(1,1,1,1,1);

n      mutex := 1;

n  philosopher(i): begin

n    repeat

n      think;

n      wait(mutex); //招呼服务员过来

n      wait(chopstick[i]);

n      wait(chopstick[(i+1) mod 5]);

n          signal(mutex);//服务员拿完筷子可以给其他人服务                                     

n      eat;                                      

n      signal(chopstick[i]);                     

n      signal(chopstick[(i+1) mod 5]);        

n    until false;

n  end

n  哲学家进餐问题：解决思路2

如果释放服务员的操作在释放筷子之后进行，而不是在吃饭前进行，则演变成了竞争椅子的极端情况（1把椅子）

n  哲学家进餐问题：解决思路2

n  这种方法的问题：假设0号哲学家正在用餐，此时1号和2号哲学家饥饿了，两者同时招呼服务员。最终服务员为1号服务，但因被0号哲学家占用的1号筷子未释放，因此1号哲学家无法就餐，但他也没有释放服务员。本来2号哲学家有机会吃饭的，但因为没有招呼到服务员，因此必须等待。

n  哲学家进餐问题：解决思路2

n  解决该问题的方法：服务员只有在确认左右两边哲学家都没就餐时才会帮该哲学家拿筷子，否则该哲学家释放服务员。

下面用类C实现这种方法，在该方法中，不使用筷子信号量，而是为每个哲学家设置一个状态位，该状态位可以为THINKING或EATING状态。状态位必须被互斥访问。

 

#define N 5  //哲学家数

#define LEFT (i+N-1) % N //第i个哲学家左邻居编号

#define RIGHT (i+1) % N //右邻居编号

#define THINKING 0  //思考状态

#define EATING 1     //吃饭状态

int state[N]; // 定义哲学家状态，初始值为0，即思考状态

semaphore mutex =1; //状态位的互斥信号量

void philosopher(int i){

  while(true){

    think();

    take_chop(i);//拿两支筷子

    eat();

    put_chop(i);//放下两支筷子

  }

}

 

void take_chop(int i){

  wait(mutex);//进入临界区

  if((state[LEFT]!=EATING) && (state[RIGHT]!= EATING)){

    state[i]=EATING;//如果左右两边哲学家都没吃饭，则i可吃饭

  }

  signal(mutex);

}

void put_chop(int i){

  wait(mutex);

  state[i] = THINKING;//吃完饭释放筷子

  signal(mutex);

}

 

 

n  哲学家进餐问题：

n  解决思路3：奇数号哲学家先拿左边筷子，偶数号哲学家先拿右边筷子。（或者相反）

n  此时五位哲学家总是先竞争奇数号筷子，获得后再竞争偶数号筷子。

n  var chopstick: array[0…4] of semaphore :=(1,1,1,1,1);

n  philosopher(i): begin

n    repeat

n      think;

n      wait(chopstick[(i+(i+1) mod 2) mod 5]);

n      wait(chopstick[(i+(i mod 2)) mod 5]);

n      eat;                                      

n      signal(chopstick[(i+(i+1) mod 2) mod 5]);      

n      signal(chopstick[(i+(i mod 2)) mod 5]);

n  until false;

n  end

n  哲学家进餐问题：解决思路3

n  思路3的一些变种：

n  任意一位哲学家与其他哲学家反方向申请筷子

先拿筷子的三位哲学家与后面两位哲学家反方向申请筷子。