嗜睡的理发师问题

《嗜睡的理发师问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、嗜睡的理发师问题：一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已经占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店，试用信号量实现这一同步问题。intwaiting;//等候理发的顾客数intCHAIRSr;//为顾客准备的椅子数semaphoreCustomers,babers,mutex;Customers=0

2、;barbers=0;waiting=0;mutex=1;barber()//理发师进程{while(TRUE){wait(customers);//若无顾客，理发师睡眠wait(mutex);//进程互斥waiting=waiting-1;//等待顾客数少一signal(barbers)；//理发师去为一个顾客服务signal(mutex);//离开临界区Cut_hair();}}Customer（inti）{wait(mutex);//进程互斥if(waiting

3、ustomers);//必要的话唤醒理发师signal(mutex);//开放临界区wait(barbers);//无理发师，顾客等待get_haircut();//一个顾客坐下等理发}elsesignal(mutex);//人满了，走吧}1、嗜睡的理发师问题：一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已经占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必

4、须付费，直到理发师收费后才能离开理发店，试用信号量实现这一同步问题。分析：本题中，顾客进程和理发师进程之间存在着多种同步关系：1．只有在理发椅空闲时，顾客才能做到理发椅上等待理发师理发，否则顾客便必须等待；只有当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待；这种同步关系类似于单缓冲的生产者-消费者问题中的同步关系，故可通过信号量empty和full来控制；1．理发师为顾客理发时，顾客必须等待理发的完成，并在理发完成后理发师唤醒他，这可单独使用一个信号量cut来控制；2．顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开；而理发师则需等待顾客付费，并在收费

5、后唤醒顾客以允许他离开，这可分别通过两个信号量payment和receipt来控制。3．等候室中的N帐沙发是顾客竟争的资源，故还需为它们设置了一个资源信号量sofa4．为了控制顾客的人数，使顾客能自所有的沙发都被占用时离开理发店，还必须设置一个整型变量count来对理发店重的顾客进行计数，该变量将被多个顾客进程互斥地访问并修改，这可通过一个互斥信号量mutext来实现。答：为解决上述问题，需设置一个整型变量count用来对理发店重的顾客进行计数，并需设置7个信号量，其中：mutex用来实现顾客进程对count变量的恶互斥访问，其初值为1；sofa是对应于等候室中N张沙发的资

6、源信号量，其初值为N；empty表示是否有空闲的理发椅，其初值为1；full表示理发椅上是否有等待理发的顾客，其初值为0；cut用来等待理发的完成，其初值为0；payment表示用来等待付费，其初值为0；receipt用来等待收费，其初值为0。具体算法描述如下：Intcout=0；Semaphoremutex=1,sofa=N,empty=1,full=0,cut=0,payment=0,receipt=0;processguesti()顾客i{wait(mutex);//count既用于判断，也要修改，所以为临界资源，用mutex管理互斥，但由于是分支结构，所以要在每个分

7、支结构中注意离开count的临界区时使用signal释放临界资源if(count>N)//沙发中已经坐满客人N个和正在理发的1位，没有沙发，客人离开理发店{signal(mutex);exitshop;}else{count=count+1;if(count>1)//count>1，意味着原来理发店里有客人，所以不能坐理发椅，需要坐到沙发上等待{signal（mutex）；wait(sofa);//申请沙发，肯定能得到sitonsofa;wait(empty);//申请理发椅，等不到阻塞，得到，则从沙发上站起，准备