1. 介绍
哲学家就餐问题是多线程同步问题的经典案例,用于描述并发环境中的资源争抢及解决方案。该问题最初由Dijkstra提出,用于类比计算机访问磁带驱动器外设的场景。当前通用版本由快速排序算法发明者Tony Hoare完善。本文将剖析这个问题并实现一个流行解决方案。
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
接口的独立线程。关键设计:
- 每位哲学家持有左右两把叉子(用
Object
表示) - 通过
synchronized
关键字实现叉子互斥访问
4.1 哲学家类基础结构
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() {
// 核心逻辑待实现
}
}
4.2 行为模拟方法
private void doAction(String action) throws InterruptedException {
System.out.println(
Thread.currentThread().getName() + " " + action);
Thread.sleep((int)(Math.random() * 100)); // 随机模拟耗时
}
⚠️ 通过Thread.sleep()
引入随机延迟,避免执行顺序被时间 deterministic 控制。
4.3 核心逻辑实现
@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;
}
}
4.4 启动类
public class DiningPhilosophers {
public static void main(String[] args) throws Exception {
Philosopher[] philosophers = new Philosopher[5];
Object[] forks = new Object[5];
// 初始化叉子
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();
}
}
}
4.5 典型输出示例
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
✅ 初始所有哲学家思考,随后P1成功获取双叉进食,放回后P5获取叉子。
5. 该方案的问题:死锁
上述实现存在致命缺陷——死锁。死锁指系统因循环等待资源而完全停滞。
死锁发生的典型场景:每个哲学家都拿到左叉,但无法获取右叉(因为右叉已被邻居占用)。
5.1 死锁输出示例
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
❌ 所有哲学家卡在"拿起左叉"状态,系统陷入死锁。
6. 解决死锁
死锁根源是循环等待(Circular Wait)。解决方案需打破这个条件:
6.1 破局策略
让其中一位哲学家改变取叉顺序:先取右叉再取左叉
6.2 修改启动类
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行特殊处理最后一位哲学家,打破循环等待链。
6.3 修复后输出示例
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. 结论
本文通过哲学家就餐问题深入探讨了循环等待与死锁的核心概念。我们:
- 实现了一个直观但存在死锁风险的方案
- 通过打破循环等待条件解决了死锁
- 验证了修复后系统的稳定性
这只是一个基础方案,实际生产中还有更复杂的解决方案(如资源分级)。完整代码可在GitHub仓库获取。