引言
哲学家就餐问题（Dining Philosophers Problem）是计算机科学中最经典的并发问题之一，由艾兹赫尔·戴克斯特拉（Edsger Dijkstra）于1965年提出。五位哲学家围坐在圆桌旁，每两位之间有一根筷子。哲学家要么思考，要么就餐——就餐时必须同时拿到左右两根筷子。这个问题精妙地展示了多线程环境中 死锁（Deadlock）、饥饿（Starvation） 与 资源竞争 的核心矛盾。本文将用 Java 实现多种解决方案，深入剖析死锁避免算法。
问题建模
将问题抽象为以下约束：
1. 五位哲学家（线程）共享五根筷子（资源）
2. 每位哲学家需要同时获得左右两根筷子才能就餐
3. 筷子是互斥资源，同一时间只能被一位哲学家持有
4. 如果每位哲学家都先拿起左边的筷子，再等待右边的筷子——死锁必然发生
死锁产生的四个必要条件
- 互斥条件：筷子同一时间只能被一人使用
- 占有且等待：哲学家拿着一根筷子等待另一根
- 不可抢占：筷子不能被强制夺走
- 循环等待：哲学家们形成循环等待链
破坏任一条件即可避免死锁。
解决方案一：资源分级法（破坏循环等待）
为每根筷子编号，要求哲学家必须先拿编号小的筷子，再拿编号大的。最后一位哲学家（左右筷子编号逆序者）必须先拿右边的筷子。
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
/**
* 哲学家就餐问题 —— 资源分级法解决方案
* 通过破坏循环等待条件来避免死锁
*/
public class DiningPhilosophers {
private final int numPhilosophers;
private final Lock[] chopsticks; // 筷子数组，每根筷子是一个锁
public DiningPhilosophers(int n) {
this.numPhilosophers = n;
this.chopsticks = new Lock[n];
for (int i = 0; i < n; i++) {
chopsticks[i] = new ReentrantLock();
}
}
/**
* 哲学家线程
*/
class Philosopher implements Runnable {
private final int id;
private final int leftChopstick;
private final int rightChopstick;
private int eatCount = 0;
Philosopher(int id) {
this.id = id;
// 资源分级：总是先拿编号小的筷子
this.leftChopstick = Math.min(id, (id + 1) % numPhilosophers);
this.rightChopstick = Math.max(id, (id + 1) % numPhilosophers);
}
@Override
public void run() {
try {
while (eatCount < 5) { // 每位哲学家吃5次
think();
eat();
}
System.out.println("哲学家 " + id + " 已完成就餐，共吃了 " + eatCount + " 次");
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
private void think() throws InterruptedException {
System.out.println("哲学家 " + id + " 正在思考...");
Thread.sleep((long) (Math.random() * 1000));
}
private void eat() throws InterruptedException {
// 按编号顺序获取筷子，破坏循环等待条件
Lock first = chopsticks[leftChopstick];
Lock second = chopsticks[rightChopstick];
first.lock();
try {
System.out.println("哲学家 " + id + " 拿起了筷子 " + leftChopstick);
second.lock();
try {
System.out.println("哲学家 " + id + " 拿起了筷子 " + rightChopstick + "，开始就餐！");
Thread.sleep((long) (Math.random() * 500)); // 模拟就餐时间
eatCount++;
System.out.println("哲学家 " + id + " 放下筷子，思考人生...");
} finally {
second.unlock();
}
} finally {
first.unlock();
}
}
}
public void startDining() {
Thread[] philosophers = new Thread[numPhilosophers];
for (int i = 0; i < numPhilosophers; i++) {
philosophers[i] = new Thread(new Philosopher(i), "Philosopher-" + i);
philosophers[i].start();
}
for (Thread t : philosophers) {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("\n===== 所有哲学家就餐完毕，无死锁！ =====");
}
public static void main(String[] args) {
DiningPhilosophers dp = new DiningPhilosophers(5);
dp.startDining();
}
}
解决方案二：限制同时就餐人数（破坏占有且等待）
通过信号量限制最多只有四位哲学家同时尝试拿筷子，确保至少有一位能拿到两根筷子。
import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
/**
* 哲学家就餐问题 —— 限制就餐人数法
* 通过Semaphore限制同时竞争资源的哲学家数量
*/
public class DiningPhilosophersSemaphore {
private final int numPhilosophers;
private final Lock[] chopsticks;
private final Semaphore diningLimit; // 同时就餐人数上限
public DiningPhilosophersSemaphore(int n) {
this.numPhilosophers = n;
this.chopsticks = new Lock[n];
for (int i = 0; i < n; i++) {
chopsticks[i] = new ReentrantLock();
}
// 限制最多 n-1 位哲学家同时竞争，确保至少一人能拿到两根筷子
this.diningLimit = new Semaphore(n - 1);
}
class Philosopher implements Runnable {
private final int id;
private final int left;
private final int right;
Philosopher(int id) {
this.id = id;
this.left = id;
this.right = (id + 1) % numPhilosophers;
}
@Override
public void run() {
try {
for (int i = 0; i < 3; i++) {
think();
// 申请就餐许可
diningLimit.acquire();
try {
eat();
} finally {
diningLimit.release();
}
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
private void think() throws InterruptedException {
System.out.println("哲学家 " + id + " 思考中...");
Thread.sleep((long) (Math.random() * 800));
}
private void eat() throws InterruptedException {
// 尝试获取两根筷子，使用 tryLock 避免长时间阻塞
Lock leftLock = chopsticks[left];
Lock rightLock = chopsticks[right];
leftLock.lock();
try {
System.out.println(" 哲学家 " + id + " 拿起左筷 " + left);
rightLock.lock();
try {
System.out.println(" 哲学家 " + id + " 拿起右筷 " + right + "，用餐中...");
Thread.sleep((long) (Math.random() * 400));
System.out.println(" 哲学家 " + id + " 用餐完毕");
} finally {
rightLock.unlock();
}
} finally {
leftLock.unlock();
}
}
}
public void start() {
Thread[] threads = new Thread[numPhilosophers];
for (int i = 0; i < numPhilosophers; i++) {
threads[i] = new Thread(new Philosopher(i));
threads[i].start();
}
for (Thread t : threads) {
try { t.join(); } catch (InterruptedException e) { e.printStackTrace(); }
}
System.out.println("===== Semaphore方案执行完毕 =====");
}
public static void main(String[] args) {
new DiningPhilosophersSemaphore(5).start();
}
}
解决方案三：Chandy/Misra 分布式方案
每位哲学家维护一个请求队列，脏筷子（使用过的）必须交出，干净筷子可以保留。这破坏了”占有且等待”条件。
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;
/**
* Chandy/Misra 分布式解决方案
* 通过"脏/净"状态标记和请求队列避免死锁与饥饿
*/
public class DiningPhilosophersChandyMisra {
static class Chopstick {
final int id;
final ReentrantLock lock = new ReentrantLock();
volatile boolean clean = true; // true=净（新分配），false=脏（用过）
volatile int owner; // 当前持有者
Chopstick(int id, int initialOwner) {
this.id = id;
this.owner = initialOwner;
}
}
static class Philosopher implements Runnable {
final int id;
final Chopstick left, right;
final AtomicInteger eatCount;
volatile boolean running = true;
Philosopher(int id, Chopstick left, Chopstick right, AtomicInteger eatCount) {
this.id = id;
this.left = left;
this.right = right;
this.eatCount = eatCount;
}
@Override
public void run() {
while (running && eatCount.get() < 20) {
think();
// 尝试获取两根筷子
if (acquireChopsticks()) {
eat();
releaseChopsticks();
}
}
}
private void think() {
System.out.println("哲学家 " + id + " 思考中...");
try { Thread.sleep((long) (Math.random() * 600)); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}
private boolean acquireChopsticks() {
// 简化版：直接尝试获取两根筷子，若失败则发送请求
// 实际分布式实现需要消息传递
synchronized (left) {
if (left.owner != id && left.clean) {
return false; // 别人持有且是净的，无法获取
}
if (left.owner != id) {
left.owner = id;
}
left.clean = true;
}
synchronized (right) {
if (right.owner != id && right.clean) {
// 归还左筷
synchronized (left) { left.clean = false; }
return false;
}
if (right.owner != id) {
right.owner = id;
}
right.clean = true;
}
return true;
}
private void eat() {
System.out.println("哲学家 " + id + " 用餐中！");
eatCount.incrementAndGet();
try { Thread.sleep((long) (Math.random() * 300)); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}
private void releaseChopsticks() {
synchronized (left) { left.clean = false; }
synchronized (right) { right.clean = false; }
System.out.println("哲学家 " + id + " 放下筷子（变脏）");
}
}
public static void main(String[] args) {
int n = 5;
Chopstick[] chopsticks = new Chopstick[n];
for (int i = 0; i < n; i++) {
chopsticks[i] = new Chopstick(i, i); // 初始：哲学家i持有左筷
}
AtomicInteger totalEats = new AtomicInteger(0);
Thread[] threads = new Thread[n];
for (int i = 0; i < n; i++) {
threads[i] = new Thread(
new Philosopher(i, chopsticks[i], chopsticks[(i + 1) % n], totalEats)
);
threads[i].start();
}
// 运行一段时间后停止
try { Thread.sleep(5000); }
catch (InterruptedException e) { e.printStackTrace(); }
for (Thread t : threads) {
t.interrupt();
}
System.out.println("===== Chandy/Misra方案总就餐次数: " + totalEats.get() + " =====");
}
}
死锁检测：资源分配图算法
在更通用的场景中，可以通过构建资源分配图（Resource Allocation Graph, RAG）来检测死锁：
– 若图中存在环路，且环路上的资源都是单实例，则死锁发生
– 若资源是多实例，则需进一步使用死锁检测算法（类似银行家算法）
import java.util.*;
/**
* 资源分配图死锁检测算法
* 检测有向图中是否存在环路
*/
public class DeadlockDetector {
/**
* 使用DFS检测有向图是否存在环
* @param graph 邻接表表示的图（哲学家->请求的资源）
* @param numNodes 节点数量
* @return 是否存在环（死锁）
*/
public static boolean detectDeadlock(List<Integer>[] graph, int numNodes) {
boolean[] visited = new boolean[numNodes];
boolean[] recursionStack = new boolean[numNodes];
for (int i = 0; i < numNodes; i++) {
if (!visited[i]) {
if (dfsDetectCycle(graph, i, visited, recursionStack)) {
return true; // 发现环路，存在死锁
}
}
}
return false;
}
private static boolean dfsDetectCycle(List<Integer>[] graph, int node,
boolean[] visited, boolean[] recursionStack) {
visited[node] = true;
recursionStack[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
if (dfsDetectCycle(graph, neighbor, visited, recursionStack)) {
return true;
}
} else if (recursionStack[neighbor]) {
// 发现回边，存在环路
return true;
}
}
recursionStack[node] = false;
return false;
}
public static void main(String[] args) {
// 模拟死锁场景：5位哲学家各自持有左筷，请求右筷
// 节点 0-4 表示哲学家，5-9 表示筷子（简化模型）
int totalNodes = 10;
@SuppressWarnings("unchecked")
List<Integer>[] graph = new ArrayList[totalNodes];
for (int i = 0; i < totalNodes; i++) graph[i] = new ArrayList<>();
// 哲学家0持有筷子5，请求筷子6
graph[0].add(6); // Philosopher 0 -> Chopstick 6 (waiting)
graph[5].add(0); // Chopstick 5 -> Philosopher 0 (held by)
// 哲学家1持有筷子6，请求筷子7
graph[1].add(7);
graph[6].add(1);
// 哲学家2持有筷子7，请求筷子8
graph[2].add(8);
graph[7].add(2);
// 哲学家3持有筷子8，请求筷子9
graph[3].add(9);
graph[8].add(3);
// 哲学家4持有筷子9，请求筷子5 —— 形成环路！
graph[4].add(5);
graph[9].add(4);
boolean deadlock = detectDeadlock(graph, totalNodes);
System.out.println("死锁检测结果: " + (deadlock ? "存在死锁！" : "无死锁"));
}
}
方案对比
| 方案 | 破坏条件 | 优点 | 缺点 |
|---|---|---|---|
| 资源分级 | 循环等待 | 实现简单，无饥饿 | 编号固定，不灵活 |
| 限制人数 | 占有且等待 | 通用性强 | 并发度降低 |
| Chandy/Misra | 占有且等待 | 分布式，公平 | 实现复杂，消息开销 |
| 死锁检测 | 事后检测 | 不限制并发 | 检测有延迟，需恢复机制 |
总结
哲学家就餐问题生动展示了并发编程中的核心挑战。通过 Java 实现多种解决方案，我们可以看到：死锁避免的本质是破坏死锁四个必要条件中的至少一个。资源分级法以其简洁高效成为最常用方案，而 Chandy/Misra 方案则在分布式系统中展现了优雅的公平性。理解这些问题，是编写健壮多线程程序的必经之路。
