LeetCode 1226. 哲学家进餐

2024-03-10 HGNULB 约 11 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 1226. 哲学家进餐

题意分析

五位哲学家围坐一桌，相邻两人之间共用一把叉子，共五把。一位哲学家想吃饭时必须同时握有左右两把叉子，吃完再把两把都放回去。题目把「拿左叉、拿右叉、吃、放左叉、放右叉」五个动作做成五个回调传进来，我们要实现 wantsToEat，让任意多线程并发调用时既不出错也不卡死。

这题不考算法，考的是并发安全的两个层面。第一层是互斥：一把叉子在同一时刻只能被一个人握着，所以每把叉子必须对应一个独占资源。第二层是无死锁：五个人五把叉子，如果每人都先抓左手边那把再去等右手边那把，就会出现「人人手里有一把、人人都在等下一把」的僵局，整个系统永久停摆。

判定死锁的经典四个必要条件是互斥、持有并等待、不可剥夺、循环等待。前三条在本题中都由题意锁死了——叉子天然互斥、必须两把齐了才能吃、拿到的叉子不能被别人抢走。唯一还能动手脚的就是第四条「循环等待」，这条约束直接指明了实现方向。

边界要留意编号的环形性：哲学家 i 的左叉是 i，右叉是 (i + 1) % 5。对 i = 0..3，左编号都小于右编号；唯独 i = 4 时左叉是 4、右叉是 0，左大于右。这个「唯一的反向者」正是环闭合的地方，也是所有正确解法必须特殊照顾的位置。

另外注意题目对输出顺序的要求：判题机校验的是回调调用序列的合法性（同一把叉子必须先 pick 后 put、成对出现），而加锁顺序是内部实现细节，与回调顺序无关。这一点想通了，实现会自由很多。

解法：统一叉子编号加锁

核心思路

最朴素的写法是「每人先锁左叉、再锁右叉」。这会死锁：想象五个线程同时执行到「已锁左叉、正要锁右叉」，此时叉子 0 被哲学家 0 持有、哲学家 4 在等它；叉子 4 被哲学家 4 持有、哲学家 3 在等它……等待关系首尾相接构成一个长度为 5 的环，谁都不放手，程序永久挂起。

另一个朴素补丁是「加一把全局大锁，把整个进餐过程串起来」。它确实不会死锁，但把并发度压成了 1——本可以同时进餐的哲学家 0 和 2（用的是 0、1 和 2、3 四把互不相干的叉子）也被迫排队。能过题，但在面试里是负分答案，因为它把并发问题降级成了串行问题。

关键观察：死锁的环之所以能闭合，是因为不同线程的加锁顺序不一致。哲学家 0 的顺序是「先 0 后 1」，哲学家 4 的顺序是「先 4 后 0」，两者在编号轴上一个升序一个降序，正好把链首尾接上。如果强制所有线程都按同一个全局顺序（叉子编号从小到大）申请锁，那么任何一条等待边都只能从「持有小编号、申请大编号」指向更大的编号，等待关系严格沿编号递增——严格递增的关系不可能成环，死锁的第四个必要条件被彻底破坏。

这就是资源有序分配法（resource ordering），它是死锁预防里最通用、也最容易在白板上讲清楚的一招。

不变量：任一线程在任一时刻持有的锁集合，其编号严格递增地被获取；因此若线程 A 正在等待线程 B 持有的某把叉子，必有 A 已持有的最大编号 < B 已持有的某个编号。沿等待链走，编号严格递增，链长不超过 5 且不可能回到起点，故不存在环，系统必然有线程能前进。

落到实现上：算出左右叉编号，取较小者为 firstFork、较大者为 secondFork，依次上锁；两把都到手后，再按题目要求的语义顺序依次调用五个回调；最后在 finally / defer 中释放。这里要特别理解一点——加锁顺序和回调顺序可以不同。哲学家 4 实际上先锁了编号 0 的右叉、后锁了编号 4 的左叉，但只要两把都拿到了，先调用 pickLeftFork 还是 pickRightFork 都不影响任何人的资源视图，判题机看到的仍是合法序列。

解题步骤

构造函数里初始化 5 把互斥锁，一把叉子一把锁。为什么按叉子建锁而不是按哲学家建锁：竞争的对象是叉子，锁必须和被保护的资源一一对应；按人建锁保护不了「相邻两人抢同一把叉子」这个真实冲突。

计算左右叉编号：leftFork = philosopher，rightFork = (philosopher + 1) % 5。取模是为了让 4 号的右叉绕回 0，形成闭环。

比较两个编号，先锁小的再锁大的。为什么这一步就足以杜绝死锁：它让全体线程在编号这条全序上保持一致的申请方向，等待关系只能单调递增，无法闭环。注意这里不需要任何 if (philosopher == 4) 的特判——min / max 自动把唯一的反向者掰正，代码里没有分支，也就没有分支写错的机会。

两把锁都拿到之后才开始执行回调。为什么不能拿一把就调 pickLeftFork：那会退化成「持有并等待」的原始版本，虽然靠有序加锁仍不死锁，但会输出「拿了左叉却迟迟不吃」的中间态，更重要的是它让锁的持有区间与回调区间错位，代码的意图不再清晰。

回调按题目语义顺序调用：拿左、拿右、吃、放左、放右。为什么可以不和加锁顺序一致：叉子的实际独占由锁保证，回调只是对外汇报动作，二者是不同层面的东西。

释放锁放进 finally / defer。为什么必须这样：回调是外部传入的 Runnable / 闭包，可能抛异常或 panic；一旦异常从中间穿出而锁没释放，这把叉子就永远没人能拿，整个系统卡死。把释放绑到栈退出上是唯一可靠的做法。

以「五个线程几乎同时调用 wantsToEat，哲学家编号分别为 0..4」走一遍，看死锁为什么不会发生。

计算各自的加锁序列：哲学家 0 是「先 0 后 1」，1 是「先 1 后 2」，2 是「先 2 后 3」，3 是「先 3 后 4」，哲学家 4 的左右叉是 4 和 0，取 min / max 后是「先 0 后 4」——注意这里被掰成了升序，正是关键一步。

假设调度让所有人同时去抢自己的第一把锁：叉子 0 被哲学家 0 和 4 同时争抢，只有一个能拿到，设为哲学家 0；哲学家 1、2、3 分别拿到叉子 1、2、3。此时哲学家 4 阻塞在叉子 0 上。

哲学家 0 接着申请叉子 1，被哲学家 1 持有，阻塞；哲学家 1 申请叉子 2，阻塞；哲学家 2 申请叉子 3，阻塞；哲学家 3 申请叉子 4——没有人持有叉子 4（原本会去抢它的哲学家 4 被挡在了叉子 0 上），成功拿到。

哲学家 3 两把齐全，执行五个回调后释放叉子 4 和 3。叉子 3 一放，哲学家 2 立刻拿到并开吃；接着 2 释放后哲学家 1 前进，1 释放后哲学家 0 前进，最后哲学家 0 释放叉子 0，哲学家 4 被唤醒，拿到 0 和 4 完成进餐。

整个过程没有任何一步陷入互相等待。对照来看，如果哲学家 4 保持「先 4 后 0」的原始顺序，上一步他就会先抢到叉子 4，于是哲学家 3 拿着 3 等 4、哲学家 4 拿着 4 等 0、哲学家 0 拿着 0 等 1……环闭合，五个线程全部永久阻塞。唯一的差别就是哲学家 4 的加锁顺序被翻转了。

代码实现

class DiningPhilosophers {
    private final java.util.concurrent.locks.ReentrantLock[] forks;

    public DiningPhilosophers() {
        forks = new java.util.concurrent.locks.ReentrantLock[5];
        for (int i = 0; i < forks.length; i++) {
            forks[i] = new java.util.concurrent.locks.ReentrantLock();
        }
    }

    public void wantsToEat(
        int philosopher,
        Runnable pickLeftFork,
        Runnable pickRightFork,
        Runnable eat,
        Runnable putLeftFork,
        Runnable putRightFork
    ) throws InterruptedException {
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % forks.length;
        int firstFork = Math.min(leftFork, rightFork);
        int secondFork = Math.max(leftFork, rightFork);

        // 所有线程按同一编号顺序加锁，破坏死锁所需的循环等待。
        forks[firstFork].lock();
        forks[secondFork].lock();
        try {
            pickLeftFork.run();
            pickRightFork.run();
            eat.run();
            putLeftFork.run();
            putRightFork.run();
        } finally {
            forks[secondFork].unlock();
            forks[firstFork].unlock();
        }
    }
}

type DiningPhilosophers struct {
    forks [5]sync.Mutex
}

func Constructor() DiningPhilosophers {
    return DiningPhilosophers{}
}

func (d *DiningPhilosophers) WantsToEat(
    philosopher int,
    pickLeftFork func(),
    pickRightFork func(),
    eat func(),
    putLeftFork func(),
    putRightFork func(),
) {
    leftFork := philosopher
    rightFork := (philosopher + 1) % len(d.forks)
    firstFork := leftFork
    secondFork := rightFork
    if firstFork > secondFork {
        firstFork, secondFork = secondFork, firstFork
    }

    // 所有协程按同一编号顺序加锁，破坏死锁所需的循环等待。
    d.forks[firstFork].Lock()
    d.forks[secondFork].Lock()
    defer d.forks[firstFork].Unlock()
    defer d.forks[secondFork].Unlock()

    pickLeftFork()
    pickRightFork()
    eat()
    putLeftFork()
    putRightFork()
}

复杂度分析

时间复杂度：单次 wantsToEat 的自身工作量是 $O(1)$。凭什么：无论有多少线程，每次调用只做两次取模与比较、两次加锁、五次回调、两次解锁，全是固定次数的操作，不随并发规模增长。真实耗时取决于锁竞争与调度，不属于算法复杂度范畴。

空间复杂度：$O(1)$。凭什么：叉子锁数组固定为 5 个，是与输入无关的常数；每次调用只用四个局部整型，且没有任何按线程数分配的结构。

关键点总结

处理死锁先背清四个必要条件（互斥、持有并等待、不可剥夺、循环等待），再逐条检查哪一条在本题里还有操作空间。本题前三条被题意锁死，答案只能从破坏循环等待入手——这套推理过程本身就是面试想听的东西。

资源有序分配法是最通用的死锁预防手段：给所有资源定一个全局序，强制所有线程按该序申请。它的正确性证明只有一句话——等待关系沿全序严格递增，递增关系不成环。这句话务必能脱口而出。

「加一把全局大锁」能过题但是负分答案，因为它把并发度压到 1。面试中要主动对比：有序加锁允许不相邻的哲学家真正并行进餐，而全局锁不能。

锁的粒度要对齐真实竞争的资源：竞争对象是叉子就按叉子建锁，按人建锁保护不了相邻者之间的冲突。这个判据可以迁移到任何「多个执行者争抢共享资源」的设计题。

加锁顺序与业务动作顺序是两回事：前者是为了正确性而设的内部约定，后者是对外的语义要求，二者不必一致。看穿这一点才能放心地对编号排序。

锁释放必须绑定到作用域退出（Java 的 finally、Go 的 defer），因为临界区里调用的是外部传入的代码，随时可能异常退出。这在工程里比在判题机上更重要。

易错点总结

固定按「先左后右」加锁：五个线程同时进入并各自拿到左叉时，哲学家 0..4 分别持有叉子 0..4 且都在等下一把，等待关系闭合成环，程序永久挂起，判题机报超时而不是报错——最难排查的一类错误。

对哲学家 4 手写特判却写错方向，例如「philosopher == 4 时先锁右叉」：右叉正是 0，这条特判等于把原本就该翻转的那个人又翻了回去，4 变成「先 0 后 4」以外的顺序时环重新闭合。用 min / max 无分支处理才不会踩这个坑。

右叉编号忘记取模：philosopher = 4 时算出右叉为 5，Java 抛 ArrayIndexOutOfBoundsException、Go 直接 panic，第五个线程还没开始就崩了。

只锁一把叉子就执行全部回调：两位相邻的哲学家会同时进入「吃」的阶段并共用同一把叉子，判题机检测到同一把叉子被重复 pick 而未 put，判为非法序列。

把锁建在哲学家身上而不是叉子上：wantsToEat(0, ...) 与 wantsToEat(1, ...) 锁的是两个不同对象，完全不互斥，叉子 1 被两人同时握住，仍然输出非法序列。

用一把全局锁包住整个方法：能通过判题，但哲学家 0 和 2 明明用的是四把互不相干的叉子却被迫串行，吞吐量降到理论值的五分之一；面试官问「并发度是多少」时无法自圆其说。

解锁写在回调之后但没有 finally / defer 保护：只要 eat.run() 抛出任何异常，两把叉子的锁就永远不会释放，后续所有涉及这两把叉子的调用全部阻塞，系统雪崩。

Java 里用 synchronized(forks[first]) 嵌套却把两层写反成 synchronized(forks[left]) 再 synchronized(forks[right])：synchronized 的嵌套顺序就是加锁顺序，写成左右序等价于回到最原始的死锁版本，块结构还让人误以为「有语法保护就安全」。

误以为 ReentrantLock 的可重入性能救死锁：可重入只解决「同一线程重复获取同一把锁」，而死锁发生在不同线程之间，可重入完全无关；换成 ReentrantLock 而不改加锁顺序，照样死锁。

试图用「限制最多 4 人同时就餐」的信号量方案但把计数写成 5：信号量法的正确性完全依赖「同时申请叉子的人数少于叉子数」，写成 5 等于没限制，五个人照样围成环；这类方案的容量参数必须是 n - 1。

相似题目

题目	难度	考察点
1114. 按序打印	简单	只需强制三个线程的先后次序，用信号量或 `CountDownLatch`，不涉及死锁
1115. 交替打印 FooBar	中等	两个线程严格轮转，靠一对信号量互相唤醒，考的是同步而非资源分配
1116. 打印零与奇偶数	中等	三线程按 `0x0y` 模式轮转，需要一个线程唤醒两个不同的下游
1195. 多线程 Fizz Buzz	中等	四线程按数值条件抢占执行权，重点是避免忙等与漏唤醒
1188. 设计有限阻塞队列	中等	生产者消费者模型，考条件变量的等待与唤醒，容量约束替代了资源环
1242. 多线程网络爬虫	中等	并发任务分发 + 共享集合去重，重点在线程池与结果合并而非互斥顺序