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

云惠网小编 2021年12月30日13:19:43
评论
2771字阅读9分14秒
摘要

哲学家就餐问题公众号:小成同学在coding文章如有问题欢迎指正5名哲学家,5根筷子,哲学家左右两边的筷子跟身边的人共享,只有同时拿起左手的筷子和右手的筷子,哲学家才可以夹菜。这个问题其实是一个死锁问题。当0号拿着a筷子的时候,它需要申请b这根筷子,才可以夹菜,但b这根筷子在被1号使用着,因此0号无法夹菜,这时候怎么办,需要等1号吃完,把b筷子放手,而1号想夹菜则需要申请c这根筷子,但c这根筷子又被2号使用着,所以每名哲学家左手都拿着筷子,而右手的筷子都在被使用中,形成了一个死锁环。

广告也精彩

哲学家就餐问题

image-20211015145428089

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

image-20211222214721246

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

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

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

代码实现

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

  • 线程粗化:一次性拿到所有资源,把锁的范围放大。

    • 我们可以看到,锁是有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个呢?依次解开需要花费很长的时间。

      image-20211225142722278

效率不高的解法

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

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

  • 模拟哲学家问题 OOA - OOD - DDD
  • class : 哲学家 class : 筷子
  • 筷子:编号
  • 哲学家:左手的筷子 右手的筷子 编号

image-20211223175417036

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

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

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

最优解法

image-20211222210919265

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

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

如图:

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

左撇子代码实现

本文转自 https://blog.csdn.net/weixin_53407527/article/details/122213349

腾讯云618
未分类
云惠网小编
SpringCloud -- Config、Bus解析

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
[深度解剖C语言] --关键字 static

[深度解剖C语言] –关键字 static

static ---最名不副实的关键字目录1.static修饰全局变量2.static修饰函数3.static修饰局部变量static的作用:1.static修饰全局变量我们创建两...
Java数据结构-认识顺序表

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论