哲学家就餐问题是由 Edsger Dijkstra 在 1965 年引入的一个经典同步问题。它生动地展示了并发编程中资源共享面临的挑战，例如死锁、饥饿和互斥。
!os
问题描述
- K 位哲学家围坐在一张圆桌旁。
- 每位哲学家都在“思考”和“进食”两种状态之间交替。
- 每两位哲学家之间放着一根筷子（总共 K 根筷子）。
- 一位哲学家必须拿起两根筷子（左手和右手各一根）才能进食。
- 同一时间只能有一位哲学家使用一根筷子。
面临的挑战： 设计一种同步机制，使哲学家们能够进食，同时不会导致 死锁（所有人永远等待）或 饥饿（有些人永远没有机会进食）。
问题中的难点
- 死锁： 如果所有哲学家都先拿起左边的筷子，就没有人能拿到右边的筷子了 —— 这就形成了循环等待。
- 饥饿： 如果其他哲学家一直占用筷子，某些哲学家可能永远没有机会进食。
- 并发控制： 必须确保没有两位相邻的哲学家同时进食。
我们可以使用 信号量（Semaphores） 来管理筷子并避免死锁。
算法
- 每根筷子被表示为一个二进制信号量（互斥锁）。
- 哲学家必须在进食前获取左手和右手的信号量。
- 进食结束后，哲学家释放两个信号量。
伪代码
> semaphore chopstick[5] = {1,1,1,1,1};
>
> Philosopher(i):
> while(true) {
> think();
> wait(chopstick[i]); // 拿起左边的筷子
> wait(chopstick[(i+1)%5]); // 拿起右边的筷子
>
> eat();
>
> signal(chopstick[i]); // 放下左边的筷子
> signal(chopstick[(i+1)%5]); // 放下右边的筷子
>
> }
解释：
- semaphore chopstick[5] = {1,1,1,1,1}; 每根筷子都是一个初始化为 1 的二进制信号量（表示可用）。
- think(); 哲学家花时间思考。
- wait(chopstick[i]); 尝试拿起左边的筷子。如果筷子是空闲的，哲学家就拿起它；否则等待。
- wait(chopstick[(i+1)%5]); 尝试拿起右边的筷子（使用取模运算来模拟圆桌）。
- eat(); 当两根筷子都拿到后，哲学家开始进食。
- signal(chopstick[i]); 和 signal(chopstick[(i+1)%5]); P 放下两根筷子，使它们对相邻的哲学家可用。
代码实现
C++
CODEBLOCK_d757932f
Java
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;
public class DiningPhilosophers {
private static final int N = 5; // 哲学家数量
private static final Semaphore[] chopstick = new Semaphore[N];
public static void main(String[] args) {
// 初始化筷子信号量
for (int i = 0; i < N; i++) {
chopstick[i] = new Semaphore(1);
}
// 创建哲学家线程
for (int i = 0; i < N; i++) {
new Thread(new Philosopher(i)).start();
}
}
static class Philosopher implements Runnable {
private final int id;
Philosopher(int id) {
this.id = id;
}
@Override
public void run() {
while (true) {
System.out.println("Philosopher " + id + " is thinking…");
sleep(1);
// 拿起左边的筷子
try { chopstick[id].acquire(); } catch (InterruptedException