leetcode
leetcode 1151 ~ 1200
哲学家进餐

哲学家进餐

难度:

标签:

题目描述

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

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

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

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

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

 

哲学家从 04顺时针 编号。请实现函数 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个哲学家同时尝试就餐来避免死锁?是否有其他可能的数目可以实现同样的效果?
在解决方案中,限制最多4个哲学家同时尝试就餐是为了确保至少有一个哲学家能同时访问其两边的叉子,从而避免所有哲学家同时拿起一边的叉子而导致的死锁。如果所有5个哲学家都尝试同时吃饭,每个哲学家拿起左边的叉子,那么所有的叉子都会被占用,导致每个哲学家都无法拿起右边的叉子,从而发生死锁。限制为4个哲学家,总有一个叉子是空闲的,从而避免了这种情况。实际上,只要不是所有哲学家同时吃饭,就可以避免死锁,但允许4个是最高效的利用率。
🦆
解决方案中提到,每个哲学家首先尝试拿起右边的叉子再拿左边的叉子,这种顺序是否有特别的原因?如果哲学家改为先拿左边的叉子会怎样?
指定一个固定的顺序(如先右后左)可以防止循环等待,从而避免死锁。如果每个哲学家都遵循同一顺序拿叉子,则不会出现两个哲学家相互等待对方放下的叉子的情况。如果哲学家改为先拿左边的叉子,只要所有哲学家都遵守这一规则,结果仍然是相同的,避免了死锁。但如果哲学家中有的先拿左边叉子,有的先拿右边叉子,则可能会引发死锁,因为可能形成一个循环等待的环路。
🦆
使用信号量和锁的方式处理并发时,是否存在性能瓶颈或者潜在的效率问题?例如,频繁的锁操作会不会影响系统的整体性能?
使用信号量和锁确实可以引入性能瓶颈和效率问题,尤其是在高并发情况下。锁操作涉及到内核态的转换和线程的上下文切换,这些都是耗时的操作。当锁的竞争非常激烈时,线程可能会频繁地被挂起和唤醒,导致效率降低。此外,如果锁的保持时间过长,也会增加其他线程的等待时间,从而降低并发性能。设计良好的锁策略和尽可能减少锁的粒度是提升性能的关键。

相关问题