理发师问题加强版-多个理发师问题

2023-12-25 20:59

本文主要是介绍理发师问题加强版-多个理发师问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

写在前面:

这是睡眠理发师问题加强版的Java解决方案参考,是一次操作系统实验的分析报告。实验问题完整描述可参考实验完整描述以及要求文档。实验的完整代码可参考Demo。


理发师问题描述:

一个理发店由一个有n个椅子的等候室和一个有一个理发椅的理发室组成。

  1. 如果有没有顾客来服务,理发师就去睡觉了。
  2. 如果顾客走进理发店和所有的椅子被占用了,然后顾客离开了商店。
  3. 如果理发师很忙,但是椅子是可用的,那么顾客坐在一张免费的椅子上。
  4. 如果理发师睡着了,顾客就会叫醒理发师。

这是课本上的理发师问题,对于这个问题的解答网上有很多解法,可参考:CSDN 进程(线程)间同步互斥问题
(三) 熟睡的理发师问题


加强版的问题描述:

一个理发店由一个有n个椅子的等候室和一个有m理发椅的理发室组成。

  1. 如果有没有顾客可以服务,所有的理发师都去睡觉。
  2. 如果顾客走进理发店椅子被占用了,然后顾客离开了商店。
  3. 如果所有的理发师都很忙,但是椅子是可用的,然后顾客坐在一张免费的椅子上。
  4. 如果理发师睡着了,顾客就会醒过来的理发师。

实验完整问题描述以及要求文档链接


问题流程分析:

让我们先来看看一个理发师的场景再现:
8923455-35de4129c2e6d63e.png
理发师问题流程图.png
  1. 阳光明媚的早上,商店开门。店里面空空如也,理发师伸了个懒腰,睡回笼觉去了。
  2. 一位顾客来了,发现理发师都在睡觉,走到理发师面前,拍醒了理发师。
  3. 理发师醒了之后,十分抱歉,赶快给顾客理发。
  4. 理发完成,理发师告诉顾客:发理好了。
  5. 客户答到:好的!转身离开理发店。
  6. 理发师呼叫一下一个顾客
    • 若发现理发店恢复了空空如也的状态,就继续去睡觉了
    • 若在还有顾客在椅子上等待,理发师就去唤醒椅子上睡觉的顾客。
      + 顾客随理发师坐到理发椅上,等待理发师理发完成
      + 重复步骤4
      ....
当有多个理发师的时候会怎么样呢。言语有点难以描述了,但可以看作多个单理发师的理发师店共享等待椅子队列。每个理发师,访问同一个的等待椅子队列,但是,理发的时候互不影响。

技术需求

在Java中对于多线程同步的支持有很多方案。除了简单的锁对象(Class Lock),和条件对象(Class Condition)搭配使用之外,还有Synchronization关键字用来保护一个代码片段,避免多个线程同时修改临界区内容,也可以使用阻塞队列等。我感觉锁和条件对象比较适合这一题的解答。
锁和条件对象的的使用:

 private Lock lock=new ReentrantLock();lock.lick();//获取这个锁,如果这个锁被另外一个线程拥有则阻塞lock.unlock();//释放锁private Condition condition = lock.newCondition();condition.await();//阻塞当前线程condition.signalAll();//释放拥有因为condition.await()的线程,将其放到等待队列。该线程释放锁的时候执行。condition.siginal();//在阻塞队列中随机释放一个线程,将其放到等待队列。该线程释放锁的时候执行。

那么问题来了,我们需要哪些锁呢?我们再看一个理发师的情况:

  • 理发师在没有顾客的时候,调用自己的Condition.await()。
  • 用户来的时候调用Barber.Condition.singalAll();并调用 自己的Condition.await()即可;
  • 理发师线程释放之后进一步向前推进,直达下一次和客户沟通的时候,挂起自己,唤醒客户线程。
  • 重复上述就可完成理发师线程和用户线程的沟通了。

一个理发师锁,一个用户锁,一个互斥锁就行了。

那么多个理发师的时候,每个理发师都有自己的用户,理发师和用户之间的信息交换是1对1的,那么也就是说每个理发师都有自己的锁和条件对象,以供顾客调用。与此同时,每个顾客应该也有自己的锁和对象让理发师调用。毕竟理发师们只不过是共享了用户队列。


讨论题:

1.理发师数量为 1 下,离开用户和椅子数量关系
8923455-31303b91df195619.png
理发师数量为1的时候.png
理论分析:

理发师的数量为 1 的时候,每增加 n 把椅子,用户等待数量缓冲区增加 n,即滞留用户离开数量减少 n。

实验数据证明:

结合图标可知,该拟合曲线为的斜率近似于-1 的直线,即每增加 n 把椅子,被滞留而离开用户的数量减
少 n,理论分析成立。


2.椅子为零,离开用户和理发师数量关系
8923455-c6696f1ea0a03b3d.png
椅子数量为0时.png
理论分析:

假设理发师理发速度为 V,则 N 位理发师的理论上的理发速度为 NV。设 N 的 1 时候,滞留离开的用户为
M;那么 N 大于 1 时候,被滞留的用户大致为 M/N。但是,用户达到时间间隔随机(0~keepTime),好比,给了
理发师休息的机会,所以被滞留的用户数量应该少于 M/N。变化速率近似于 f(x)=-lgx 函数。

数据证明:

结合图形的拟合曲线以及各店的数据分析可知,该理论分析成立。


下面就上代码了,一大波代码正在靠近,请耐心。(get和Set方法等方法略,完整代码可参考demo)

Demo地址

public class Barber {private int id;//理发师Idprivate Customer myCus;//理发师当前的顾客private Lock lock;//理发师的锁private Condition condition;//理发师的条件变量private boolean busy;//理发师忙碌状态
public class Customer {private int id;//用户idprivate int myBarber;//用户的理发师private Lock lock;//用户锁private Condition condition;//用户条件变量
}
public class Driver {private static Shop shop;private static int serviceTime;//服务时间private static int nBarbers;//理发师数量private static int nChairs;//椅子数量private static int nCustomers;//用户数量public static void main(String[] args) throws InterruptedException {//略输入函数:接受用户输入:理发师数量,椅子数量,用户数量,服务时间shop=new Shop(nBarbers, nChairs);//创建理发师线程for(int i=0;i<nBarbers;i++) {BarThread barThread=driver.new BarThread(i);barThread.start();}//创建客户线程Vector<Thread> threads = new Vector<>();  for(int i=0;i<nCustomers;i++) {CusThread cusThread=driver.new CusThread(i);Random random=new Random();Thread.sleep(random.nextInt(10));threads.add(cusThread);cusThread.start();}// 保证 shop.getDropsoff()在所有线程结束的时候调用for (Thread thread : threads) {  try {  thread.join();} catch (InterruptedException e) {  e.printStackTrace();  }  }  System.out.println("没有理发离开的用户数量为:"+shop.getDropsoff());}//理发师线程private class BarThread extends Thread{private int id;public BarThread(int id) {this.id=id;}public void run() {while(true) {try {shop.helloCustomer(id);sleep(serviceTime);//理发时间shop.byeCustomer(id);} catch (InterruptedException e1) {e1.printStackTrace();}}   }}//客户线程private class CusThread extends Thread{private int id;private int barber=-1;public CusThread(int id) {this.id=id;}@Overridepublic void run() {try {if((barber=shop.visitShop(id))!=-1)shop.leaveShop(id, barber);} catch (InterruptedException e) {e.printStackTrace();}}}
}
public class Shop {private static int nDropsoff;//未接受服务退出的人数private int nBarbers;//理发师数量private int nChairs;//椅子数量private ArrayList<Barber> barList;//理发师队列private ArrayList<Customer> cusList;//客户等待队列private Lock lock=new ReentrantLock();//互斥锁//用户调用public int visitShop(int  id) throws InterruptedException {lock.lock();//进入临界区int barId;Barber barber;Customer customer=new Customer(id);//没有空余椅子了,用户离开了if(cusList.size()>nChairs) {System.out.println("顾客\t"+id+"\t离开了理发店因为没有空位置了");nDropsoff++;lock.unlock();return -1;}//没有空闲理发师的时候if(getSleepBarber()==-1) {cusList.add(customer);//坐到椅子上System.out.println("客户\t"+id+"\t就座,"+"\t就坐的位置是 "+cusList.size());lock.unlock();//离开临界区customer.getLock().lock();customer.getCondition().await();//阻塞当前线程,用户睡觉customer.getLock().unlock();//被理发师激活lock.lock();//再次进入临界区barId=customer.getBar();//查询自己的理发师barber=barList.get(barId);System.out.println("顾客 \t"+id+"\t走到理发师\t\t"+barId);}else {//有空闲的理发师barId=getSleepBarber();//找到正在睡觉的理发师customer.setBarber(barId);barber=barList.get(barId);barber.setCustomer(customer);//告诉理发师自己IDbarber.setBusy(true);//设置理发师为忙碌System.out.println("顾客 \t"+id+"\t叫醒理发师\t\t"+barId);}lock.unlock();barber.getLock().lock();barber.getCondition().signalAll();//让理发师开始理发理发师barber.getLock().unlock();return barId;}//用户调用public void leaveShop(int cusId,int barId) throws InterruptedException {lock.lock();Barber barber=barList.get(barId);Customer customer=barber.getCustomer();System.out.println("顾客\t"+cusId+"\t等待理发师\t\t"+barId+"\t完成理发");//等待理发师理通知发结束lock.unlock();customer.getLock().lock();customer.getCondition().await();customer.getLock().unlock();//顾客得知理发完成lock.lock();System.out.println("客户\t"+cusId+"\t回答“好的”然后离开");barber.getLock().lock();barber.getCondition().signalAll();//离开barber.getLock().unlock();lock.unlock();}public void helloCustomer(int id) throws InterruptedException {lock.lock();Barber barber=barList.get(id);Customer customer;barber.getLock().lock();//店里面没有顾客if(cusList.size()==0) {System.out.println("理发师\t"+id+"\t去睡觉了因为没有客户");barber.setBusy(false);//等待顾客叫醒自己lock.unlock();barber.getLock().lock();barber.getCondition().await();barber.getLock().unlock();//顾客叫醒自己lock.lock();customer=barber.getCustomer();//查询顾客ID}else {//理发师叫醒顾客customer=cusList.get(0);cusList.remove(0);customer.setBarber(id);//告诉用户自己的位置barber.setCustomer(customer);//叫醒顾客lock.unlock();//释放锁customer.getLock().lock();;customer.getCondition().signalAll();//激活椅子上的客户customer.getLock().unlock();//等待顾客走过来barber.getLock().lock();barber.getCondition().await();barber.getLock().unlock();//顾客就座,开始理发lock.lock();}System.out.println("理发师\t"+id+"\t正在服务客户 \t"+customer.getId());lock.unlock();}public void byeCustomer(int id) throws InterruptedException {lock.lock();Barber barber=barList.get(id);Customer customer=barber.getCustomer();System.out.println("理发师\t"+id+"\t告诉用户 \t\t"+customer.getId()+"\t发理好了");//通知顾客理发完成lock.unlock();customer.getLock().lock();customer.getCondition().signalAll();//通知客户理发完了customer.getLock().unlock();//等待顾客离开barber.getLock().lock();barber.getCondition().await();barber.getLock().unlock();lock.lock();//顾客离开呼叫下一个顾客System.out.println("理发师\t"+id+"\t理发完成,呼叫下一个用户");lock.unlock();}public void addDropsoff() {nDropsoff++;}public int getDropsoff() {return nDropsoff; }//查询睡觉的理发师public int getSleepBarber() {lock.lock();for(Barber b:barList) {if(b.getBusy()==false) {lock.unlock();return b.getId();}}lock.unlock();return -1;}public Shop(int b,int c) {nBarbers=b;nChairs=c;barList=new ArrayList<>();for(int i=0;i<nBarbers;i++) {barList.add(new Barber(i));}cusList=new ArrayList<>();}
}

这篇关于理发师问题加强版-多个理发师问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/536919

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

基于Flask框架添加多个AI模型的API并进行交互

《基于Flask框架添加多个AI模型的API并进行交互》:本文主要介绍如何基于Flask框架开发AI模型API管理系统,允许用户添加、删除不同AI模型的API密钥,感兴趣的可以了解下... 目录1. 概述2. 后端代码说明2.1 依赖库导入2.2 应用初始化2.3 API 存储字典2.4 路由函数2.5 应

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图