哲学家就餐问题

问题描述

假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。即使没有死锁，也有可能发生资源耗尽。

分析考虑两种实现的方式，如下：
(1) 在什么情况下5 个哲学家全部吃不上饭？
A. 算法描述：
` void philosopher(int i) /i：哲学家编号，从0 到4/
```
  { 
  while (TRUE) { 
  think( ); /*哲学家正在思考*/ 
  take_fork(i); /*取左侧的筷子*/ 
  take_fork((i+1) % N); /*取左侧筷子；％为取模运算*/ 
  eat( ); /*吃饭*/ 
  put_fork(i); /*把左侧筷子放回桌子*/ 
  put_fork((i+1) % N); /*把右侧筷子放回桌子*/ 
  } 
  }    `    <br>
```
分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。

B．算法描述：
规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子搜索，等一段时间再重复整个过程。
但是：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。

(2) 描述一种没有人饿死（永远拿不到筷子）算法。
考虑了四种实现的方式（A、B、C、D）：
A．原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。
伪码：
` semaphore chopstick[5]={1，1，1，1，1};
```
  semaphore room=4; 
  void philosopher(int i) 
  { 
  while(true) 
  { 
  think(); 
  wait(room); //请求进入房间进餐 
  wait(chopstick[i]); //请求左手边的筷子 
  wait(chopstick[(i+1)%5]); //请求右手边的筷子 
  eat(); 
  signal(chopstick[(i+1)%5]); //释放右手边的筷子 
  signal(chopstick[i]); //释放左手边的筷子 
  signal(room); //退出房间释放信号量room 
  } 
  }    `
```
B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。
方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足FIFO 的要求，因此不会出现饥饿的情形。
伪码：
` semaphore chopstick[5]={1，1，1，1，1};
```
  void philosopher(int I) 
  { 
  while(true) 
  { 
  think(); 
  Swait(chopstick[(I+1)]%5,chopstick[I]); 
  eat(); 
  Ssignal(chopstick[(I+1)]%5,chopstick[I]); 
  } 
  }    `   <br>
```
方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。
伪码：
` semaphore mutex = 1 ;
```
  semaphore chopstick[5]={1，1，1，1，1}; 
  void philosopher(int I) 
  { 
  while(true) 
  { 
  think(); 
  wait(mutex); 
  wait(chopstick[(I+1)]%5); 
  wait(chopstick[I]); 
  signal(mutex); 
  eat(); 
  signal(chopstick[(I+1)]%5); 
  signal(chopstick[I]); 
  } 
  }    `   <br>
```
C．原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。
伪码：
` semaphore chopstick[5]={1，1，1，1，1};
```
  void philosopher(int i) 
  { 
  while(true) 
  { 
  think(); 
  if(i%2 == 0) //偶数哲学家，先右后左。 
  { 
  wait (chopstick[ i + 1 ] mod 5) ; 
  wait (chopstick[ i]) ; 
  eat(); 
  signal (chopstick[ i + 1 ] mod 5) ; 
  signal (chopstick[ i]) ; 
  } 
  Else //奇数哲学家，先左后右。 
  { 
  wait (chopstick[ i]) ; 
  wait (chopstick[ i + 1 ] mod 5) ; 
  eat(); 
  signal (chopstick[ i]) ; 
  signal (chopstick[ i + 1 ] mod 5) ; 
  } 
  }    `   <br>
```
D．利用管程机制实现（最终该实现是失败的，见以下分析）：
原理：不是对每只筷子设置信号量，而是对每个哲学家设置信号量。test()函数有以下作用：
a. 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态，则当前哲学家通过test()函数试图进入吃饭状态。
b. 如果通过test()进入吃饭状态不成功，那么当前哲学家就在该信号量阻塞等待，直到其他的哲学家进程通过test()将该哲学家的状态设置为EATING。
c. 当一个哲学家进程调用put_forks()放下筷子的时候，会通test()测试它的邻居，如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态。
由上所述,该算法不会出现死锁，因为一个哲学家只有在两个邻座都不在进餐时，才允许转换到进餐状态。
该算法会出现某个哲学家适终无法吃饭的情况，即当该哲学家的左右两个哲学家交替处在吃饭的状态的时候，则该哲学家始终无法进入吃饭的状态，因此不满足题目的要求。
但是该算法能够实现对于任意多位哲学家的情况都能获得最大的并行度，因此具有重要的意义。
伪码：
` #define N 5 /* 哲学家人数*/
```
  #define LEFT (i-1+N)%N /* i的左邻号码 */ 
  #define RIGHT (i+1)%N /* i的右邻号码 */ 
  typedef enum { THINKING, HUNGRY, EATING } phil_state; /*哲学家状态*/ 
  monitor dp /*管程*/ 
  { 
  phil_state state[N]; 
  semaphore mutex =1; 
  semaphore s[N]; /*每个哲学家一个信号量，初始值为0*/ 
  void test(int i) 
  { 
  if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING && 
  state[RIGHT(i)] != EATING ) 
  { 
  state[i] = EATING; 
  V(s[i]); 
  } 
  } 
  void get_forks(int i) 
  { 
  P(mutex); 
  state[i] = HUNGRY; 
  test(i); /*试图得到两支筷子*/ 
  V(mutex); 
  P(s[i]); /*得不到筷子则阻塞*/ 
  } 
  void put_forks(int i) 
  { 
  P(mutex); 
  state[i]= THINKING; 
  test(LEFT(i)); /*看左邻是否进餐*/ 
  test(RIGHT(i)); /*看右邻是否进餐*/ 
  V(mutex); 
  } 
  } 
  哲学家进程如下： 
  void philosopher(int process) 
  { 
  while(true) 
  { 
  think(); 
  get_forks(process); 
  eat(); 
  put_forks(process); 
  } 
  }     `
```