题目

有 n（n ≥ 3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m（m ≥ 1）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的 P、V 操作（wait()、signal() 操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

解析

回顾传统的哲学家就餐问题，假设餐桌上有 n 个哲学家、根筷子，那么可以用这种方法避免死锁：限制至多允许 n-1 个哲学家同时“抢”筷子，那么至少会有 1 个哲学家可以获得两根筷子并顺利进餐，于是不可能发生死锁的情况。

本题可以用碗这个限制资源来避免死锁：当碗的数量 m 小于哲学家的数量 n 时，可以直接让碗的资源量等于 m，确保不会出现所有哲学家都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量大于等于哲学家的数量时，为了让碗起到同样的限制效果，我们让碗的资源量等于 -1，这样就能保证最多只有 n-1 个哲学家同时进餐，所以得到碗的资源量为 min{n-1, m}。在进 PV 操作时，碗的资源量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行 P 操作。具体过程如下：

// 限制哲学家能同时拿到盘子的数量
semaphore fork[n] = {1};
// 并发盘子数量 < n
semaphore plate = min(m, n-1);
philosopher(int i) {
  while (1) {
    think();
    P(plate);
    P(fork[i]);
    P(fork[(i + 1) % n]);
    eat();
    V(fork[i]);
    V(fork[(i + 1) % n]);
    V(plate);
  }
}