理发师问题加强版-多个理发师问题
2018-06-03 本文已影响30人
北国雪WRG
写在前面：
这是睡眠理发师问题加强版的Java解决方案参考，是一次操作系统实验的分析报告。实验问题完整描述可参考实验完整描述以及要求文档。实验的完整代码可参考Demo。
理发师问题描述：
一个理发店由一个有n个椅子的等候室和一个有一个理发椅的理发室组成。
- 如果有没有顾客来服务，理发师就去睡觉了。
- 如果顾客走进理发店和所有的椅子被占用了，然后顾客离开了商店。
- 如果理发师很忙，但是椅子是可用的，那么顾客坐在一张免费的椅子上。
- 如果理发师睡着了，顾客就会叫醒理发师。
这是课本上的理发师问题，对于这个问题的解答网上有很多解法，可参考：CSDN 进程(线程)间同步互斥问题
(三) 熟睡的理发师问题
加强版的问题描述：
一个理发店由一个有n个椅子的等候室和一个有m理发椅的理发室组成。
- 如果有没有顾客可以服务，所有的理发师都去睡觉。
- 如果顾客走进理发店椅子被占用了，然后顾客离开了商店。
- 如果所有的理发师都很忙，但是椅子是可用的，然后顾客坐在一张免费的椅子上。
- 如果理发师睡着了，顾客就会醒过来的理发师。
实验完整问题描述以及要求文档链接
问题流程分析：
让我们先来看看一个理发师的场景再现：
理发师问题流程图.png
- 阳光明媚的早上，商店开门。店里面空空如也，理发师伸了个懒腰，睡回笼觉去了。
- 一位顾客来了，发现理发师都在睡觉，走到理发师面前，拍醒了理发师。
- 理发师醒了之后，十分抱歉，赶快给顾客理发。
- 理发完成，理发师告诉顾客：发理好了。
- 客户答到：好的！转身离开理发店。
- 理发师呼叫一下一个顾客
- 若发现理发店恢复了空空如也的状态，就继续去睡觉了
- 若在还有顾客在椅子上等待，理发师就去唤醒椅子上睡觉的顾客。
+ 顾客随理发师坐到理发椅上，等待理发师理发完成
+ 重复步骤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 下，离开用户和椅子数量关系
理发师数量为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;//理发师Id
private Customer myCus;//理发师当前的顾客
private Lock lock;//理发师的锁
private Condition condition;//理发师的条件变量
private boolean busy;//理发师忙碌状态
public class Customer {
private int id;//用户id
private 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;
}
@Override
public 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);//告诉理发师自己ID
barber.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<>();
}
}
