理发师问题加强版

理发师问题加强版

写在前面：

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

---

理发师问题描述：

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

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

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

---

加强版的问题描述：

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

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

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

---

问题流程分析：

让我们先来看看一个理发师的场景再现：

理发师问题流程图.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 = wCondition();condition.await();//阻塞当前线程condition.signalAll();//释放拥有因为condition.await()的线程，将其放到等待队列。该线程释放锁的时候执行。condition.siginal();//在阻塞队列中随机释放一个线程，将其放到等待队列。该线程释放锁的时候执行。

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

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

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

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

---

讨论题：

1.理发师数量为 1 下，离开用户和椅子数量关系

理发师数量为1的时候.png

理论分析：

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

实验数据证明：

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

---

2.椅子为零，离开用户和理发师数量关系

椅子数量为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&#w BarThread(i);barThread.start();}//创建客户线程Vector<Thread> threads = new Vector<>();  for(int i=0;i<nCustomers;i++) {CusThread cusThread&#w CusThread(i);Random random=new Random();Thread.Int(10));threads.add(cusThread);cusThread.start();}// 保证 Dropsoff()在所有线程结束的时候调用for (Thread thread : threads) {  try {  thread.join();} catch (InterruptedException e) {  e.printStackTrace();  }  }  System.out.println("没有理发离开的用户数量为："&#Dropsoff());}//理发师线程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();//离开临界区Lock().lock();Condition().await();//阻塞当前线程，用户睡觉Lock().unlock();//被理发师激活lock.lock();//再次进入临界区barId&#Bar();//查询自己的理发师barber&#(barId);System.out.println("顾客 t"+id+"t走到理发师tt"+barId);}else {//有空闲的理发师barId=getSleepBarber();//找到正在睡觉的理发师customer.setBarber(barId);barber&#(barId);barber.setCustomer(customer);//告诉理发师自己IDbarber.setBusy(true);//设置理发师为忙碌System.out.println("顾客 t"+id+"t叫醒理发师tt"+barId);}lock.unlock();Lock().lock();Condition().signalAll();//让理发师开始理发理发师Lock().unlock();return barId;}//用户调用public void leaveShop(int cusId,int barId) throws InterruptedException {lock.lock();Barber barber&#(barId);Customer customer&#Customer();System.out.println("顾客t"+cusId+"t等待理发师tt"+barId+"t完成理发");//等待理发师理通知发结束lock.unlock();Lock().lock();Condition().await();Lock().unlock();//顾客得知理发完成lock.lock();System.out.println("客户t"+cusId+"t回答“好的”然后离开");Lock().lock();Condition().signalAll();//离开Lock().unlock();lock.unlock();}public void helloCustomer(int id) throws InterruptedException {lock.lock();Barber barber&#(id);Customer Lock().lock();//店里面没有顾客if(cusList.size()==0) {System.out.println("理发师t"+id+"t去睡觉了因为没有客户");barber.setBusy(false);//等待顾客叫醒自己lock.unlock();Lock().lock();Condition().await();Lock().unlock();//顾客叫醒自己lock.lock();customer&#Customer();//查询顾客ID}else {//理发师叫醒顾客customer&#(0);ve(0);customer.setBarber(id);//告诉用户自己的位置barber.setCustomer(customer);//叫醒顾客lock.unlock();//释放锁Lock().lock();;Condition().signalAll();//激活椅子上的客户Lock().unlock();//等待顾客走过来Lock().lock();Condition().await();Lock().unlock();//顾客就座，开始理发lock.lock();}System.out.println("理发师t"+id+"t正在服务客户 t"&#Id());lock.unlock();}public void byeCustomer(int id) throws InterruptedException {lock.lock();Barber barber&#(id);Customer customer&#Customer();System.out.println("理发师t"+id+"t告诉用户 tt"&#Id()+"t发理好了");//通知顾客理发完成lock.unlock();Lock().lock();Condition().signalAll();//通知客户理发完了Lock().unlock();//等待顾客离开Lock().lock();Condition().await();Lock().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) {Busy()==false) {lock.unlock();Id();}}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<>();}
}