LeetCode 1226. 哲学家进餐

约 5 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 微软
标签
多线程

题目描述

✅ 1226. 哲学家进餐

image-20260928230428458

image-20261003004605008

image-20260928230428460

题意分析

五位哲学家共享五把叉子，每人只有同时占用左右两把才能进餐，同一把叉子不能被两人同时使用。题目给出的拿叉、进餐、放叉函数只是回调，需要我们安排它们在并发调用中的执行时机。

只保证每把叉子互斥还不够：如果所有人都先占用左叉，再等待右叉，就可能每人持有一把、谁也无法继续。还必须规定一致的资源申请顺序。

解法：统一叉子编号加锁

核心思路

[!blue]

给五把共享叉子各分配一把锁。代码把编号为 p 的哲学家的左右叉分别记为 p 和 (p + 1) % 5，相邻哲学家因此会访问同一把叉子的同一个锁。

每次调用先锁两把叉子中编号较小的一把，再锁较大的一把。等待第一把锁时，线程还没有占用叉子；持有第一把再等待第二把时，只可能从较小编号等待较大编号。若发生循环等待，就要求编号沿环严格递增后又回到起点，这是不可能的，所以不会死锁。

得到两把锁以后，才依次调用拿左叉、拿右叉、进餐、放左叉、放右叉。加锁顺序按资源编号决定，回调名称仍表示哲学家的左右方向，不能因为交换了加锁顺序就混淆回调含义。

放叉回调执行完之前一直持有锁，防止相邻哲学家提前使用同一把叉子。Java 用 finally、Go 用 defer 释放锁；不共享叉子的两个人仍可以并行进餐。

解题步骤

  1. 在共享对象中初始化五把叉子锁，所有调用复用这些锁。
  2. 根据哲学家编号计算左右叉，再得到 firstFork 和 secondFork，保证前者编号更小。
  3. 依次获取两把锁，全部取得后执行两次拿叉、一次进餐和两次放叉回调。
  4. 通过可靠的退出路径释放两把锁，允许其他等待者继续申请；Go 的 defer 按后登记先执行的顺序解锁。

代码实现

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();
        }
    }
}

import "sync"

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()
}

复杂度分析

  • 时间复杂度：单次自身同步工作 $O(1)$，实际等待与回调耗时另计。
  • 空间复杂度：固定五把锁及每次调用的常数局部状态。

关键点总结

[!green]

  • 统一资源顺序防止死锁，不等同于保证每个人的等待时间有上界。
  • 互斥保护的是叉子，不是哲学家编号。

易错点总结

[!yellow]

  • 每人固定先拿左叉，五人可能形成环形等待。
  • 只锁一把叉子就进餐，相邻两人可能同时使用另一把。
  • 回调后没有可靠释放路径，会在异常退出时留下锁。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/67168940
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！