1226. 哲学家进餐

题目描述

5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）

所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。

假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。

设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。

问题描述和图片来自维基百科 wikipedia.org

哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：

• philosopher 哲学家的编号。
• pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
• eat 表示吃面。
• putLeftFork 和 putRightFork 表示放下左边或右边的叉子。
• 由于哲学家不是在吃面就是在想着啥时候吃面，所以思考这个方法没有对应的回调。

给你 5 个线程，每个都代表一个哲学家，请你使用类的同一个对象来模拟这个过程。在最后一次调用结束之前，可能会为同一个哲学家多次调用该函数。

示例：

输入：n = 1
输出：[[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
解释:
n 表示每个哲学家需要进餐的次数。
输出数组描述了叉子的控制和进餐的调用，它的格式如下：
output[i] = [a, b, c] (3个整数)
- a 哲学家编号。
- b 指定叉子：{1 : 左边, 2 : 右边}.
- c 指定行为：{1 : 拿起, 2 : 放下, 3 : 吃面}。
如 [4,2,1] 表示 4 号哲学家拿起了右边的叉子。

提示：

• 1 <= n <= 60

解法

Java

ReentrantLock 和 Condition 的区别

• ReentrantLock: 用于保护共享资源的互斥访问
• Condition: 用于在已获取锁的线程之间进行协调和通信

为什么使用 ReentrantLock 而不是 Condition

1. 资源模型匹配

   • 5根forks是独立的物理资源
   • 每个fork需要独立的互斥保护
   • ReentrantLock直接对应这种资源保护,而condition是某个资源共享的通信

2. 问题本质

   • 哲学家就餐问题是典型的资源竞争问题
   • 关键在于如何避免死锁地获取多个资源
   • 不涉及复杂的线程间协调逻辑

3. Condition 的适用场景

   • 通常用于生产者-消费者模式
   • 需要等待特定条件满足的场景
   • 例如：等待队列非空、等待缓冲区有空间等

代码示例说明

// 当前实现 - 直接使用 ReentrantLock 保护资源
private final Lock[] forks = new Lock[5];

// 如果使用 Condition，通常会是这样：
private final Lock lock = new ReentrantLock();
private final Condition condition = lock.newCondition();

在哲学家问题中，我们有5个独立的共享资源（叉子），所以使用5个ReentrantLock是最直接有效的方案。

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

class DiningPhilosophers {

    // 创建5个可重入锁，分别代表每根叉子
    private final Lock[] forks = new Lock[5];

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new ReentrantLock();
        }
    }

    // philosopher: 哲学家编号 (0-4)
    // pickLeftFork: 拿起左叉
    // pickRightFork: 拿起右叉
    // eat: 进食
    // putLeftFork: 放下左叉
    // putRightFork: 放下右叉
    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        
        // 获取左右叉子的索引
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;

        // 总是先获取编号较小的叉子，打破循环等待条件，预防死锁
        if (leftFork < rightFork) {
            forks[leftFork].lock();
            forks[rightFork].lock();
        } else {
            forks[rightFork].lock();
            forks[leftFork].lock();
        }

        try {
            // 执行操作
            pickLeftFork.run();
            pickRightFork.run();
            eat.run();
            putLeftFork.run();
            putRightFork.run();
        } finally {
            // 释放锁
            forks[leftFork].unlock();
            forks[rightFork].unlock();
        }
    }
}

Java

• 直接获取的问题（会导致死锁）
• 如果直接获取左右叉子，可能会出现以下情况：
• 哲学家0: 先获取叉子0，再获取叉子1
• 哲学家1: 先获取叉子1，再获取叉子2
• 哲学家2: 先获取叉子2，再获取叉子3
• 哲学家3: 先获取叉子3，再获取叉子4
• 哲学家4: 先获取叉子4，再获取叉子0
• 这时如果每个哲学家都拿到了第一根叉子，都在等待第二根叉子，就会形成循环等待，导致死锁。
• 有序获取的好处
• 通过总是先获取编号较小的叉子：
• 哲学家0: 获取顺序 0→1
• 哲学家4: 获取顺序 0→4（而不是4→0）
• 这样就破坏了循环等待的条件，因为哲学家4会先等待叉子0，而不是先占用叉子4再等待叉子0，从而避免了死锁。

总结

这种策略属于资源有序分配法，是解决死锁问题的经典方法之一，通过打破"循环等待条件"来预防死锁的发生。

class DiningPhilosophers {
    
    // 使用Object数组表示5根叉子，每个叉子是一个锁对象
    private final Object[] forks = new Object[5];
    
    public DiningPhilosophers() {
        // 初始化5个锁对象，每个代表一根叉子
        for (int i = 0; i < 5; i++) {
            forks[i] = new Object();
        }
    }

    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        
        // 计算左右叉子的索引
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;
        
        // 为了避免死锁，总是先获取编号较小的叉子
        Object firstFork;
        Object secondFork;
        if (leftFork < rightFork) {
            firstFork = forks[leftFork];
            secondFork = forks[rightFork];
        } else {
            firstFork = forks[rightFork];
            secondFork = forks[leftFork];
        }

        // 同步块确保原子性操作
        synchronized (firstFork) {
            synchronized (secondFork) {
                // 拿起叉子
                pickLeftFork.run();
                pickRightFork.run();
                
                // 进食
                eat.run();
                
                // 放下叉子
                putLeftFork.run();
                putRightFork.run();
            }
        }
    }
}