baeldung 2024-01-08
1. 引言
哲学家就餐问题是用于描述多线程环境中同步问题的经典案例之一，常被用来演示解决这类问题的技术。该问题最初由 Dijkstra 提出，当时他用它来描述计算机访问磁带驱动器外设的情境。
当前的表述形式由 Tony Hoare 提出，他同时也是快速排序（quicksort）算法的发明者。在本文中，我们将分析这个著名的问题，并编码实现一种广为接受的解决方案。
2. 问题描述
五位沉默的哲学家（P1 – P5）围坐在一张圆桌旁，他们的一生都在吃饭和思考中交替度过。
桌上共有五把叉子（1 – 5），每位哲学家要想吃饭，必须同时拿到左右手边的两把叉子。吃完后，他会将两把叉子放下，以便其他哲学家可以拾起并重复这一过程。
我们的目标是设计一种方案或协议，使得哲学家们能够顺利地吃饭和思考，而不会因资源竞争导致“饿死”（即永远无法进餐）。
3. 一个初步解决方案
最直观的解决方案是让每位哲学家遵循以下协议：
while(true) {
// 初始状态：思考人生、宇宙以及一切
think();
// 思考结束，感到饥饿
pick_up_left_fork();
pick_up_right_fork();
eat();
put_down_right_fork();
put_down_left_fork();
// 不再饥饿，继续思考！
}
如上述伪代码所示，每位哲学家初始处于思考状态。经过一段时间后，他会感到饥饿并希望进餐。
此时，他会尝试拿起左右两边的叉子；一旦成功拿到两把叉子，就开始吃饭。吃完后，他将叉子放回原处，供邻座的哲学家使用。
4. 实现
我们将每位哲学家建模为一个实现了 Runnable 接口的类，以便作为独立线程运行。每位 Philosopher 都能访问其左侧和右侧的两把叉子：
public class Philosopher implements Runnable {
// 该哲学家左右两侧的叉子
private Object leftFork;
private Object rightFork;
public Philosopher(Object leftFork, Object rightFork) {
this.leftFork = leftFork;
this.rightFork = rightFork;
}
@Override
public void run() {
// 尚未实现此方法
}
}
我们还提供了一个辅助方法，用于指示哲学家执行某个动作——吃饭、思考，或拿起叉子准备进餐：
public class Philosopher implements Runnable {
// 成员变量及标准构造函数
private void doAction(String action) throws InterruptedException {
System.out.println(
Thread.currentThread().getName() + " " + action);
Thread.sleep(((int) (Math.random() * 100)));
}
// 其他之前定义的方法
}
如上所示，每个动作通过让当前线程随机休眠一段时间来模拟，以避免执行顺序仅由时间决定。
现在，我们来实现 Philosopher 类的核心逻辑。
为了模拟“拿起叉子”的行为，我们需要对叉子加锁，确保同一时间只有一位哲学家能持有它。
为此，我们使用 Java 的 synchronized 关键字获取叉子对象的内部监视器（monitor），防止其他线程同时获取。关于 Java 中 synchronized 关键字的详细说明可参考相关资料。接下来，我们完成 Philosopher 类中 run() 方法的实现：
public class Philosopher implements Runnable {
// 成员变量及之前定义的方法
@Override
public void run() {
try {
while (true) {
// 思考
doAction(System.nanoTime() + ": Thinking");
synchronized (leftFork) {
doAction(
System.nanoTime()
+ ": Picked up left fork");
synchronized (rightFork) {
// 吃饭
doAction(
System.nanoTime()
+ ": Picked up right fork - eating");
doAction(
System.nanoTime()
+ ": Put down right fork");
}
// 回到思考状态
doAction(
System.nanoTime()
+ ": Put down left fork. Back to thinking");
}
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
}
}
上述代码精确实现了前述协议：哲学家先思考一段时间，然后决定吃饭。
接着，他依次获取左右叉子并开始进餐。进餐结束后，他将叉子放回。我们还在每个动作中加入了时间戳，便于观察事件发生的顺序。
为了启动整个流程，我们编写一个客户端程序，创建 5 个哲学家线程并启动它们：
public class DiningPhilosophers {
public static void main(String[] args) throws Exception {
Philosopher[] philosophers = new Philosopher[5];
Object[] forks = new Object[philosophers.length];
for (int i = 0; i < forks.length; i++) {
forks[i] = new Object();
}
for (int i = 0; i < philosophers.length; i++) {
Object leftFork = forks[i];
Object rightFork = forks[(i + 1) % forks.length];
philosophers[i] = new Philosopher(leftFork, rightFork);
Thread t
= new Thread(philosophers[i], "Philosopher " + (i + 1));
t.start();
}
}
}
我们将每把叉子建模为一个普通的 Java 对象，并创建与哲学家数量相同的叉子。每位哲学家被传入其左右叉子，并尝试通过 synchronized 关键字锁定它们。
运行上述代码会产生类似如下的输出（具体输出可能因 sleep() 的随机时长而不同）：
Philosopher 1 8038014601251: Thinking
Philosopher 2 8038014828862: Thinking
Philosopher 3 8038015066722: Thinking
Philosopher 4 8038015284511: Thinking
Philosopher 5 8038015468564: Thinking
Philosopher 1 8038016857288: Picked up left fork
Philosopher 1 8038022332758: Picked up right fork - eating
Philosopher 3 8038028886069: Picked up left fork
Philosopher 4 8038063952219: Picked up left fork
Philosopher 1 8038067505168: Put down right fork
Philosopher 2 8038089505264: Picked up left fork
Philosopher 1 8038089505264: Put down left fork. Back to thinking
Philosopher 5 8038111040317: Picked up left fork
所有哲学家最初都处于思考状态。可以看到，Philosopher 1 拿起了左右叉子并进餐，随后放下叉子，接着 Philosopher 5 拿起了叉子。
5. 该解决方案的问题：死锁
尽管上述方案看似正确，但实际上存在死锁（deadlock）的风险。
死锁是指系统中多个进程相互等待对方持有的资源，导致所有进程都无法继续执行的状态。
我们可以通过多次运行上述代码来验证这一点：有时程序会完全卡住。以下是一个典型的死锁输出示例：
Philosopher 1 8487540546530: Thinking
Philosopher 2 8487542012975: Thinking
Philosopher 3 8487543057508: Thinking
Philosopher 4 8487543318428: Thinking
Philosopher 5 8487544590144: Thinking
Philosopher 3 8487589069046: Picked up left fork
Philosopher 1 8487596641267: Picked up left fork
Philosopher 5 8487597646086: Picked up left fork
Philosopher 4 8487617680958: Picked up left fork
Philosopher 2 8487631148853: Picked up left fork
在这种情况下，每位哲学家都拿起了自己左边的叉子，但无法拿到右边的叉子，因为右边的叉子已被其邻居持有。这种情形被称为循环等待（circular wait），是导致死锁的四个必要条件之一，会完全阻塞系统的进展。
6. 解决死锁
如前所述，死锁的根本原因是循环等待：每个进程都在等待另一个进程所持有的资源。因此，要避免死锁，关键在于打破循环等待条件。
有多种方法可以实现这一点，其中最简单的一种是：
所有哲学家先拿左边的叉子，唯独一位哲学家先拿右边的叉子。
我们在现有代码中做一处微小修改即可实现该策略：
public class DiningPhilosophers {
public static void main(String[] args) throws Exception {
final Philosopher[] philosophers = new Philosopher[5];
Object[] forks = new Object[philosophers.length];
for (int i = 0; i < forks.length; i++) {
forks[i] = new Object();
}
for (int i = 0; i < philosophers.length; i++) {
Object leftFork = forks[i];
Object rightFork = forks[(i + 1) % forks.length];
if (i == philosophers.length - 1) {
// 最后一位哲学家先拿右边的叉子
philosophers[i] = new Philosopher(rightFork, leftFork);
} else {
philosophers[i] = new Philosopher(leftFork, rightFork);
}
Thread t
= new Thread(philosophers[i], "Philosopher " + (i + 1));
t.start();
}
}
}
关键改动在第 17–19 行：我们让最后一位哲学家（即 i == 4）先尝试获取右边的叉子，而不是左边。这样就打破了循环等待链，从而避免了死锁。
以下是一次成功运行的输出示例，所有哲学家都能轮流思考和进餐，未发生死锁：
Philosopher 1 88519839556188: Thinking
Philosopher 2 88519840186495: Thinking
Philosopher 3 88519840647695: Thinking
Philosopher 4 88519840870182: Thinking
Philosopher 5 88519840956443: Thinking
Philosopher 3 88519864404195: Picked up left fork
Philosopher 5 88519871990082: Picked up left fork
Philosopher 4 88519874059504: Picked up left fork
Philosopher 5 88519876989405: Picked up right fork - eating
Philosopher 2 88519935045524: Picked up left fork
Philosopher 5 88519951109805: Put down right fork
Philosopher 4 88519997119634: Picked up right fork - eating
Philosopher 5 88519997113229: Put down left fork. Back to thinking
Philosopher 5 88520011135846: Thinking
Philosopher 1 88520011129013: Picked up left fork
Philosopher 4 88520028194269: Put down right fork
Philosopher 4 88520057160194: Put down left fork. Back to thinking
Philosopher 3 88520067162257: Picked up right fork - eating
Philosopher 4 88520067158414: Thinking
Philosopher 3 88520160247801: Put down right fork
Philosopher 4 88520249049308: Picked up left fork
Philosopher 3 88520249119769: Put down left fork. Back to thinking
通过多次运行代码可以验证，系统已不再出现之前那种死锁情况。
7. 结论
在本文中，我们探讨了著名的“哲学家就餐问题”，深入理解了循环等待和死锁的概念。我们首先实现了一个会导致死锁的简单方案，然后通过一个巧妙的调整（打破对称性）成功避免了死锁。这只是一个起点，现实中还存在更复杂、更高效的解决方案。