X

LEETCODE 1226. The Dining Philosophers 解题思路分析

题目大意:

哲学家进餐

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

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

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

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

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

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

给你 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
 a 哲学家编号。
 b 指定叉子:{1 : 左边, 2 : 右边}.
 c 指定行为:{1 : 拿起, 2 : 放下, 3 : 吃面}。
 如 [4,2,1] 表示 4 号哲学家拿起了右边的叉子。 

提示:

  • 1 <= n <= 60

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1226

解题思路分析:

这又是一道多线程的题目,没做过相关题目的话,可以参考一下我之前的文章, LEETCODE 1115. Print FooBar Alternately 解题思路分析,其解题思路主要用到了Semaphore这个类(对应C++中的mutex)。 Semaphore 主要有两个方法:acquire()和release(),分别代表获取运行权限和释放运行权限。在 C++ 这两个方法被称为lock()和unLock()。

本题有5个哲学家,每人吃面时需要2个叉子,但桌上只有5把,也就是说相邻的两个人无法同时用餐,我们可以定义5个Semaphore控制5把叉子。哲学家0可以使用的叉子为0和1,哲学家1可以使用的叉子为1和2,以此类推。每把叉子最多拥有一个使用权限,当一个哲学家准备吃饭时,他先获得两把叉子的权限,以保证其他人无法使用,用完之后在释放权限即可。

实现代码如下:

Semaphore[] arr = new Semaphore[5]; // 定义5个Semaphore
public DiningPhilosophers() {
    for(int i = 0;i<5;i++){ // 初始化每个Semaphore
        arr[i] = new Semaphore(1);
    }
}

// call the run() method of any runnable to execute its code
public void wantsToEat(int philosopher,
                       Runnable pickLeftFork,
                       Runnable pickRightFork,
                       Runnable eat,
                       Runnable putLeftFork,
                       Runnable putRightFork) throws InterruptedException {
    // 得到左右两把叉子的index
    int left = philosopher, right = (philosopher+1) % 5;
    arr[left].acquire(); // 获得左叉子权限
    arr[right].acquire(); // 获得右叉子权限
    pickLeftFork.run(); // 拿起左叉子
    pickRightFork.run(); // 拿起右叉子
    eat.run(); // 吃面
    putLeftFork.run(); // 放下左叉子
    putRightFork.run(); // 放下左叉子
    arr[left].release(); // 释放左叉子权限
    arr[right].release(); // 释放右叉子权限
}

这种解法可以通过,执行时间为9或者10ms左右。不过这种解法存在一定的bug,由于5位哲学家会被分配到5个线程,他们可能会同时执行wantsToEat方法,这时如果他们同时拿起左叉子的话,就会造成每个人手里都只有1把叉子进而任何一个人都不法吃面,同时Semaphore又没有机会被释放,从而造成死锁现象,为了解决这个问题,我们应该优化一下逻辑,让单数的人先拿右叉子,双数人先拿左叉子,这样程序开始后,哲学家0和1会同时抢夺1号叉子,哲学家2和3抢夺3号叉子,哲学家4去拿0号叉子,这样就不会发生死锁问题。修改后的代码如下:

Semaphore[] arr = new Semaphore[5];
public DiningPhilosophers() {
    for(int i = 0;i<5;i++){
        arr[i] = new Semaphore(1);
    }
}

// call the run() method of any runnable to execute its code
public void wantsToEat(int philosopher,
                       Runnable pickLeftFork,
                       Runnable pickRightFork,
                       Runnable eat,
                       Runnable putLeftFork,
                       Runnable putRightFork) throws InterruptedException {
    int left = philosopher, right = (philosopher+1) % 5;
    if(philosopher % 2 == 0){
        arr[left].acquire(); // 双数哲学家先拿左叉子
        arr[right].acquire();
    }else{
        arr[right].acquire(); // 单数哲学家先拿右叉子
        arr[left].acquire();
    }
    pickLeftFork.run();
    pickRightFork.run();
    eat.run();
    putLeftFork.run();
    putRightFork.run();
    arr[left].release();
    arr[right].release();
}

本题解法执行时间为10ms。

Runtime: 10 ms, faster than 61.81% of Java online submissions for The Dining Philosophers.

Memory Usage: 41 MB, less than 100.00% of Java online submissions for The Dining Philosophers.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1226-the-dining-philosophers-解题思路分析/
Categories: leetcode
kwantong: