哲学家就餐问题

哲学家就餐问题是一个经典的同步问题，它是大量并发控制问题的一个例子。这个代表型的例子满足：在多个进程之间分配多个资源，而且不会出现死锁和饥饿。

本文内容主要是摘自《操作系统精髓与设计原理》

问题描述

假设有 5 个哲学家，他们的生活只是思考和吃饭。这些哲学家共用一个圆桌，每位都有一把椅子。在桌子中央有一碗米饭，在桌子上放着 5 根筷子。

当一位哲学家思考时，他与其他同事不交流。时而，他会感到饥饿，并试图拿起与他相近的两根筷子（筷子在他和他的左或右邻居之间）。一个哲学家一次只能拿起一根筷子。显然，他不能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时拥有两根筷子时，他就能吃。在吃完后，他会放下两根筷子，并开始思考。

需要设计一个礼仪，可以让每个哲学家都能吃饭，并且不会死锁和饥饿。

显然虽然有5个哲学家，但是能够同时吃饭的其实只有2个。

在这里 筷子就是共享资源，并且是互斥的。

使用信号量解决

每个哲学家先拿左边的筷子，再拿右边的筷子，然后吃饭。吃完后放下筷子。

当5个哲学家同时尝试坐下来就餐时，都拿起左边的筷子，然后都拿不到右边的筷子，死锁产生。

semaphore fork[5] = {1}; // 5根筷子。1表示只有一个人能用，即互斥。
int i;
// 第i个哲学家
void philosopher(int i) {
  while (true) {
    think();
    wait(fork[i]);//等左边的筷子
    wait(fork[(i+1) mod 5 ]); //等右边的筷子
    eat();
    signal(fork[(i+1) mod 5 ]);//放下右边的筷子
    signal(fork[i]);//放下左边的筷子
  }
}

void main() {
  parbegin(philosopher(0),philosopher(1),philosopher(2),philosopher(3),philosopher(4));
}

改进方案是增加筷子，或者限制同时就餐的哲学家人数最多为4， 这样至少有1人是能同时拿起2根筷子的。。这种方案就不会产生死锁了，。

代码如下：

semaphore fork[5] = {1}; // 5根筷子。1表示只有一个人能用，即互斥。
semaphore room = {4};//最多4人同时就餐, 共享资源，最多4人同时用。
int i;
// 第i个哲学家
void philosopher(int i) {
  while (true) {
    think();
    wait(room);
    wait(fork[i]);//等左边的筷子
    wait(fork[(i+1) mod 5 ]); //等右边的筷子
    eat();
    signal(fork[(i+1) mod 5 ]);//放下右边的筷子
    signal(fork[i]);//放下左边的筷子
    signal(room);
  }
}

void main() {
  parbegin(philosopher(0),philosopher(1),philosopher(2),philosopher(3),philosopher(4));
}

使用管程解决方案

类似于信号量解决方案，管程限制了同一时刻只有一个哲学家在吃饭。

monitor dining_controller;
cond ForkReady[5]; // 5个条件变量，标示筷子是否可用。不可用时，等待筷子的哲学家排队。
boolean fork[5] = {true};// 5根筷子是否可用。
//管城过程 获取2根筷子 
void get_forks(int pid) {
  int left = pid;
  int right = (++pid) % 5;
  if (!fork(left)) {
    cwait(ForkReady[left]); // 左边的筷子用不了，哲学家进入 排队
  }
  // 拿到了左边的筷子
  fork(left) = false;// 修改筷子的状态
  if (!fork(right)) {
    cwait(ForkReady[right]); // 右边的筷子用不了，哲学家进入 排队
  }
  // 拿到了右边的筷子
  fork(right) = false;// 修改筷子的状态
}
//管城过程 释放2根筷子
void release_forks(int pid) {
  int left = pid;
  int right = (++pid) % 5;
  if（empty(ForkReady[left])) // 没人排队了，表示筷子可用了。
    fork(left) = true;
  else
    csignal(ForkReady[left])); // 唤醒排队的哲学家。
  
  if（empty(ForkReady[right])) // 没人排队了，表示筷子可用了。
    fork(right) = true;
  else
    csignal(ForkReady[right])); // 唤醒排队的哲学家。
  
}

void philosopher[k=0 to 4] 
{
  <think>;
  get_forks(k);
  <eat>;
  release_forks(k);
}

因为管城只允许只有一个活跃进程。那么当哲学家拿起左边的筷子时，就一定可以拿起右边的筷子（右边的哲学家进不来）。