新建 文本文档.txt

理发师睡觉问题两种实现方法

说明: 一个理发店配有n个椅子的等候室和1个理发椅的理发室。
如果没有客户，理发师去睡觉。如果客户来了，等候室人满，客户离开，否则在等候室等待。如果等待室空闲，理发师去睡觉。如果理发师睡觉，客户来了叫醒理发师。
这里假设有六条椅子即n=6.
源程序:

#include <iostream>
using namespace std;
//模拟理发店问题
class HaircutShop{
 //理发师的两种状态 
 enum BarberType{
 BUSY,
 SHEEP
 };
public:
 //构造函数n代表椅子数目
 HaircutShop(int n){
  MAXnum = n;
  num = 0;
  Barber = SHEEP;
 }
 //进入一个客户
 void InputCustomer();
 //服务一个客户
 void ServiceCustomer();
private:
 //理发师处理
 BarberType Barber;
    //理发店座位情况
 int num;   //当前使用数目
 int MAXnum;//最大使用数目 
};

void HaircutShop::ServiceCustomer(){
 if(num==0){
  cout<<"没有客户在，理发师继续睡觉"<<endl;
  cout<<endl;
  return;
 }
 cout<<"一个客户来到理发椅"<<endl;
 //如果理发师在休息
 if(Barber == SHEEP){
  cout<<"^^叫醒在睡眠的理发师"<<endl;
  Barber = BUSY;
 }
 num--;
 cout<<"^^完成一个客户理发工作"<<endl;
 if(num==0){
  cout<<"^^没有客户在等待，理发师去睡觉了"<<endl;
 }
 cout<<endl;
}
void HaircutShop::InputCustomer(){
 cout<<"一个客户来到理发店"<<endl;
 if(num==MAXnum){
  cout<<"^^理发店人太多了，离开"<<endl;
 }
 else{
  num++;
  cout<<"^^进入理发店椅子等待"<<endl;
 }
 cout<<endl;
}
//编写一个测试函数,测试可能出现的情况
int main(){
HaircutShop hs(6);
 hs.InputCustomer();
 hs.InputCustomer();
 hs.ServiceCustomer();
 hs.ServiceCustomer();
 hs.ServiceCustomer();
 hs.InputCustomer();
 hs.InputCustomer();
 hs.InputCustomer();
 hs.InputCustomer();
 hs.ServiceCustomer();
 hs.InputCustomer();
 hs.InputCustomer();
 hs.InputCustomer();
 hs.InputCustomer();
 return 0;
}


?	参考文献:  <网上另一种解法>
理发师问题：一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席 
区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等 
待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理 
发、收银和休息三种活动。理发店的活动满足下列条件： 
1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发； 
2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发； 
3）理发时间长短由理发师决定； 
4）在站席区等待时间最长的顾客可坐到空闲的理发上； 
5）任何时刻最多只能有一个理发师在收银。 
试用信号量机制或管程机制实现理发师进程和顾客进程。 
原理： 
(1)customer 进程： 
首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入 
理发店。在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列， 
直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。坐到沙 
发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现 
空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。坐到理发椅上，释放 
准备好的信号（customer_ready），获得该理发师的编号（0~1 的数字）。等待理发师理 
发结束（finished[barber_number]）。在离开理发椅之前付款（payment），等待收据 
(receipt)，离开理发椅（leave_barberchair）。最后离开理发店。 
这里需要注意几点： 
a) 首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅 
和付款几个地方。 
b) 通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭 
baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上， 
因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该信号，而理发 
师接收到该信号后才释放barber_chair 等待下一位顾客。 
c) 在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活 
动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的，这样，当 
该编号的理发师释放对应的finished[i]信号的时候，该顾客才理发完毕。 
d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项操作（理发或者收款）。 
e) 为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理 
发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。在伪码中由以下机制实 
现：即顾客在释放离开理发椅的信号前，发出付款的信号。这样该理发师得不到顾客的 
离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款 
操作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该 
理发椅的信号，让下一位等待的顾客坐到理发椅上。 
(2)barber 进程 
首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量 
customer_ready)，开始理发，理发结束后释放结束信号（finished[i]）。等待顾客 
离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信 
号(barber_chair)，等待下一位顾客坐上来。 
(3)cash（收银台）进程 
等待顾客付款(payment),执行收款操作，收款操作结束，给付收据（receipt）。 
信号量总表： 
信号量 wait signal 
stand_capacity 顾客等待进入理发店 顾客离开站席区 
sofa 顾客等待坐到沙发 顾客离开沙发 
barber_chair 顾客等待空理发椅 理发师释放空理发椅 
customer_ready 理发师等待，直到一个顾客坐 
到理发椅 
顾客坐到理发椅上，给理发师 
发出信号 
mutex 等待理发师空闲，执行理发或 
收款操作 
理发师执行理发或收款结束， 
进入空闲状态 
mutex1 执行入队或出队等待 入队或出队结束，释放信号 
finished[i] 顾客等待对应编号理发师理 
发结束 
理发师理发结束，释放信号 
leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据，离开 
理发椅释放信号 
payment 收银员等待顾客付款 顾客付款，发出信号 
receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据， 
释放信号 
伪码： 
semaphore stand_capacity=5; 
semaphore sofa=4; 
semaphore barber_chair=3; 
semaphore customer_ready=0; 
semaphore mutex=3; 
semaphore mutex1=1; 
semaphore finished[3]={0,0,0}; 
semaphore leave_barberchair=0; 
semaphore payment=0; 
semaphore receipt=0; 
void customer() 
{ 
int barber_number; 
wait(stand_capacity); //等待进入理发店 
enter_room(); //进入理发店 
wait(sofa); //等待沙发 
leave_stand_section(); //离开站席区 
signal(stand_capacity); 
sit_on_sofa(); //坐在沙发上 
wait(barber_chair); //等待理发椅 
get_up_sofa(); //离开沙发 
signal(sofa); 
wait(mutex1); 
sit_on_barberchair(); //坐到理发椅上 
signal(customer_ready); 
barber_number=dequeue(); //得到理发师编号 
signal(mutex1); 
wait(finished[barber_number]); //等待理发结束 
pay(); //付款 
signal(payment); //付款 
wait(receipt); //等待收据 
get_up_barberchair(); //离开理发椅 
signal(leave_barberchair); //发出离开理发椅信号 
exit_shop(); //了离开理发店 
} 
void barber(int i) 
{ 
while(true) 
{ 
wait(mutex1); 
enqueue(i); //将该理发师的编号加入队列 
signal(mutex1); 
wait(customer_ready); //等待顾客准备好 
wait(mutex); 
cut_hair(); //理发 
signal(mutex); 
signal(finished[i]); //理发结束 
wait(leave_barberchair); //等待顾客离开理发椅信号 
signal(barber_chair); //释放barber_chair 信号 
} } 
void cash() //收银 
{ 
while(true) 
{ 
wait(payment); //等待顾客付款 
wait(mutex); //原子操作 
get_pay(); //接受付款 
give_receipt(); //给顾客收据 
signal(mutex); 
signal(receipt); //收银完毕，释放信号 
} } 
分析： 
在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重 
性的,主要包括： 
（1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动作的话，很 
容易造成没有收银员为其收款的情形， 原因是： 为该顾客理发的理发师收到 
leave_barberchair 信号后，释放barber_chair 信号，另外一名顾客坐到理发椅上， 
该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题， 
就是采取在释放leave_barberchair 信号之前，完成付款操作。这样该理发师无法进入 
下一轮循环为另外顾客服务，只能到收银台收款。 
（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号， 
如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号 
才会进行付款等操作。这样实现，是为避免这样的错误，即：如果仅用一个finished 信 
号量的话，很容易出现别的理发师理发完毕释放了finished 信号，把正在理发的这位顾 
客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编 
号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为finished[] 
数组不能是无限的。而为理发师编号，则只需要三个元素即可。