哲学家进餐
难度:
标签:
题目描述
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
代码结果
运行时间: 39 ms, 内存: 17.3 MB
/*
* The solution uses Java Streams to handle the synchronization and actions of the philosophers.
* The approach ensures that the actions are executed in a synchronized manner to avoid deadlocks.
*/
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.IntStream;
public class DiningPhilosophersStream {
private final Lock[] forks = IntStream.range(0, 5)
.mapToObj(i -> new ReentrantLock())
.toArray(Lock[]::new);
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;
// Ensure we always pick up the lower numbered fork first to avoid deadlock
if (philosopher % 2 == 0) {
forks[leftFork].lock();
pickLeftFork.run();
forks[rightFork].lock();
pickRightFork.run();
} else {
forks[rightFork].lock();
pickRightFork.run();
forks[leftFork].lock();
pickLeftFork.run();
}
eat.run();
putLeftFork.run();
forks[leftFork].unlock();
putRightFork.run();
forks[rightFork].unlock();
}
}
解释
方法:
该题解使用信号量和锁来解决哲学家就餐问题。问题的核心在于避免死锁和饥饿。首先,一个信号量限制了同时尝试就餐的哲学家数量为4,这避免了所有哲学家同时拿起左边的叉子而造成的死锁。每个哲学家尝试拿起他们的右边叉子(philosopher编号的叉子)和左边叉子((philosopher + 1) % 5),用锁确保了同一时间内只有一个哲学家能够使用一根叉子。通过拿起右边叉子开始,然后是左边叉子,吃完饭后再依次放下叉子,确保了操作的原子性。此方法通过控制就餐哲学家的数量以及加锁机制有效避免了死锁和饥饿现象。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解决方案中,为什么选择让最多4个哲学家同时尝试就餐来避免死锁?是否有其他可能的数目可以实现同样的效果?
▷🦆
解决方案中提到,每个哲学家首先尝试拿起右边的叉子再拿左边的叉子,这种顺序是否有特别的原因?如果哲学家改为先拿左边的叉子会怎样?
▷🦆
使用信号量和锁的方式处理并发时,是否存在性能瓶颈或者潜在的效率问题?例如,频繁的锁操作会不会影响系统的整体性能?
▷