多线程面试题——哲学家就餐问题（Java）

2022-10-29 17:10:43

哲学家就餐问题

公众号：小成同学在coding
文章如有问题欢迎指正

5名哲学家，5根筷子，哲学家左右两边的筷子跟身边的人共享，只有同时拿起左手的筷子和右手的筷子，哲学家才可以夹菜。

这个问题其实是一个死锁问题。

当0号拿着a筷子的时候，它需要申请b这根筷子，才可以夹菜，但b这根筷子在被1号使用着，因此0号无法夹菜，这时候怎么办，需要等1号吃完，把b筷子放手，而1号想夹菜则需要申请c这根筷子，但c这根筷子又被2号使用着，所以每名哲学家左手都拿着筷子，而右手的筷子都在被使用中，形成了一个死锁环。

如图：

思考一下我们这道题都需要哪些类呢？

每一个哲学家应该是一个线程。

模拟哲学家问题 OOA - OOD - DDD

class : 哲学家 class : 筷子

筷子：编号

哲学家：左手的筷子右手的筷子编号

代码实现

package com.mashibing.juc.c_33_TheDinningPhilosophersProblem;

import com.mashibing.util.SleepHelper;

public class T01_DeadLock {
    public static void main(String[] args) {
        
        // 构建过程
        // 1.创建5根筷子
        ChopStick cs0 = new ChopStick();
        ChopStick cs1 = new ChopStick();
        ChopStick cs2 = new ChopStick();
        ChopStick cs3 = new ChopStick();
        ChopStick cs4 = new ChopStick();

        // 2.创建5个线程（哲学家）
        Philosohper p0 = new Philosohper("p0", 0, cs0, cs1);// 将cs0给第0号的左手，将cs1给第0号的右手
        Philosohper p1 = new Philosohper("p1", 1, cs1, cs2);// 将cs1也给第1号的左手，cs2给第1号的右手
        Philosohper p2 = new Philosohper("p2", 2, cs2, cs3);// ...
        Philosohper p3 = new Philosohper("p3", 3, cs3, cs4);
        Philosohper p4 = new Philosohper("p4", 4, cs4, cs0);

        p0.start();
        p1.start();
        p2.start();
        p3.start();
        p4.start();
    }

    // 哲学家就是一个线程，我们定义类的时候直接继承Thread类
    public static class Philosohper extends Thread {

        private ChopStick left, right;
        private int index;

        public Philosohper(String name, int index, ChopStick left, ChopStick right) {
            this.setName(name);
            this.index = index;
            this.left = left;
            this.right = right;
        }

        @Override
        public void run() {
            // 将左手的筷子上锁
            synchronized (left) {
                SleepHelper.sleepSeconds(1 + index);
                // 抢右手的筷子（锁定A再抢B）
                synchronized (right) {
                    SleepHelper.sleepSeconds(1);
                    System.out.println(index + " 号 哲学家已经吃完");
                }
            }
        }
    }
}

但是我们执行后，程序没有做任何的输出，说明死锁已经形成了。

死锁一般具有2把以上的锁，在锁定1把的时候等待另外1把锁。

效率不高的解法

线程粗化：一次性拿到所有资源，把锁的范围放大。
- 我们可以看到，锁是有5把的，5把锁互相之间做同步，太复杂了，我们干脆把5把锁合并成1把锁，线程只有抢到这1把大锁的时候才可以执行。我们可以把5个筷子存入数组，或者5个筷子的对象，直接锁定整个数组或者这个大对象。
- 但是这个效率是不高的，我们明明可以只拿到2个筷子就可以夹菜，但这样明显是拿到了5个筷子，只有1个人可以夹菜，效率比较低。
- 但有的人可能会想到：将5个筷子都存放在数组里，哲学家每次使用只从数组里拿出2个筷子，这样就可以保证不冲突了吗？肯定是不可以的，因为你没法保证这几个线程分别拿到的筷子是否冲突，这样的想法还是存在问题的。
最少保证（很简单的解法）：哲学家有一个是左撇子（先这么理解）。
- 因为之前哲学家都是先拿左手的筷子，再去抢右手的筷子，而此时，这个左撇子的哲学家，会先去拿右手的筷子，再去抢左手的筷子。当左撇子拿到了a筷子时，哲学家1号想拿左手边的筷子（也就是a筷子）是拿不到的，所以他一定不会去拿b筷子，2、3、4号三位哲学家分别都可以拿到左手边（也就是b、c、d）筷子，但要注意4号，e筷子这里分为两种情况，①：e筷子被4号拿到，此时4号已经有了两个筷子，4号吃完，将d、e筷子解锁，左撇子和3号都可以使用两个筷子了，从而死锁被解开。②：e筷子被左撇子拿到，死锁同样被解开。
- 但是这个效率也不是很高，因为只有一个人可以先吃，然后才能将锁依次解开，这里只有5个哲学家，假如有500个，5000个呢？依次解开需要花费很长的时间。

最优解法

奇偶互反：偶数为左撇子，奇数为右撇子。

哲学家就餐问题解决方案：

两把锁合并一把锁（5把， 5把锁合成一把锁，筷子集合，锁定整个对象）

混进一个左撇子（保证有一个人可以先吃到）

效率更高的写法，奇数偶数分开，混进一半的左撇子

左撇子代码实现

public void run() {
            // SleepHelper.sleepSeconds(new Random().nextInt(5));
            if (index == 0) { // 左撇子算法 也可以index % 2 == 0
				// index为0时，先锁左面再锁右面
                synchronized (left) {
                    SleepHelper.sleepSeconds(1);
                    synchronized (right) {
                        SleepHelper.sleepSeconds(1);
                        System.out.println(index + " 吃完了！");
                    }
                }
            } else {
                // index不为0时，先锁右面再锁左面
                synchronized (right) {
                    SleepHelper.sleepSeconds(1);
                    synchronized (left) {
                        SleepHelper.sleepSeconds(1);
                        System.out.println(index + " 吃完了！");
                    }
                }
            }
        }

我们可以看到，所有人都吃完了，程序不会再产生死锁了。

码农公寓

哲学家就餐问题

效率不高的解法

最优解法

相关文章