1. 介绍

哲学家就餐问题多线程同步问题的经典案例,用于描述并发环境中的资源争抢及解决方案。该问题最初由Dijkstra提出,用于类比计算机访问磁带驱动器外设的场景。当前通用版本由快速排序算法发明者Tony Hoare完善。本文将剖析这个问题并实现一个流行解决方案。

2. 问题描述

dp0

上图展示了问题核心:五位哲学家(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();

    // 吃饱了,继续思考
}

逻辑简单粗暴:

  1. 哲学家初始处于思考状态
  2. 随机时间后感到饥饿
  3. 尝试获取左右叉子
  4. 拿到双叉后进食
  5. 用餐结束放回叉子

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. 结论

本文通过哲学家就餐问题深入探讨了循环等待与死锁的核心概念。我们:

  1. 实现了一个直观但存在死锁风险的方案
  2. 通过打破循环等待条件解决了死锁
  3. 验证了修复后系统的稳定性

这只是一个基础方案,实际生产中还有更复杂的解决方案(如资源分级)。完整代码可在GitHub仓库获取。


原始标题:The Dining Philosophers Problem in Java