多线程面试题——哲学家就餐问题(Java)

哲学家就餐问题

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

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

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

多线程面试题——哲学家就餐问题(Java)

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

如图:

多线程面试题——哲学家就餐问题(Java)

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

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

  • 模拟哲学家问题 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 + " 号 哲学家已经吃完");
                }
            }
        }
    }
}

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

多线程面试题——哲学家就餐问题(Java)

死锁一般具有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个呢?依次解开需要花费很长的时间。

      多线程面试题——哲学家就餐问题(Java)

最优解法

  • 奇偶互反:偶数为左撇子,奇数为右撇子。

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

  • 两把锁合并一把锁(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 + " 吃完了!");
                    }
                }
            }
        }

多线程面试题——哲学家就餐问题(Java)

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

上一篇:JUC并发编程 -- ReentrantLock可重入锁(可重入 & 可打断 & 锁超时 & 锁超时-解决哲学家就餐)


下一篇:操作系统中经典的死锁的问题