嗜睡的理发师问题

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

2、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<CHAIRS)/唐看有没有空椅子waiting=waiting+1;/等候顾客数加1signal(customers);必要的话唤醒理发师signal(mutex);

3、/开放临界区wait(barbers);无理发师，顾客等待get_haircut();/一个顾客坐下等理发elsesignal(mutex);人满了，走吧1、嗜睡的理发师问题：一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已经占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店，试用信号量实现这一同步问题。分析：本题中，顾客进程和理发师进程之间

4、存在着多种同步关系：只有在理发椅空闲时，顾客才能做到理发椅上等待理发师理发，否则顾客便必须等待；只有当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待；这种同步关系类似于单缓冲的生产者-消费者问题中的同步关系，故可通过信号量empty和full来控制；理发师为顾客理发时，顾客必须等待理发的完成，并在理发完成后理发师唤醒他，这可单独使用一个信号量cut来控制；顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开；而理发师则需等待顾客付费，并在收费后唤醒顾客以允许他离开，这可分别通过两个信号量payment和receipt来控制。等候室中的N帐沙发是顾客竞争的资源，故还需为它们设置了

5、一个资源信号量sofa为了控制顾客的人数，使顾客能自所有的沙发都被占用时离开理发店，还必须设置一个整型变量count来对理发店重的顾客进行计数，该变量将被多个顾客进程互斥地访问并修改，这可通过一个互斥信号量mutext来实现。答：为解决上述问题，需设置一个整型变量count用来对理发店重的顾客进行计数，并需设置7个信号量，其中：mutex用来实现顾客进程对count变量的恶互斥访问，其初值为1;sofa是对应于等候室中N张沙发的资源信号量，其初值为N;empty表示是否有空闲的理发椅，其初值为1;full表示理发椅上是否有等待理发的顾客，其初值为0;cut用来等待理发的完成，其初值为0;pay

6、ment表示用来等待付费，其初值为0;receipt用来等待收费，其初值0。具体算法描述如下:Intcout=0;Semaphoremutex=1,sofa=N,empty=1,full=0,cut=0,payment=0,receipt=0;processguesti()顾客iwait(mutex);/count既用于判断，也要修改，所以为临界资源，用mutex管理互斥，但由于是分支结构，所以要在每个分支结构中注意离开count的临界区时使用signal释放临界资源if(count>N)沙发中已经坐满客人N个和正在理发的1位，没有沙发，客人离开理发店signal(mutex);exit

7、shop;elsecount=count+1;if(count>1)/count>1,意味着原来理发店里有客人，所以不能坐理发椅，需要坐到沙发上等待signal(mutex);wait(sofa);/申请沙发，肯定能得到sitonsofa;wait(empty);申请理发椅，等不到阻塞，得到，则从沙发上站起，准备坐到理发椅上getupformsofa;signal(sofa);/归还沙发elsesignal(mutex);wait(empty);/count=1,意味着这个店里只有这一个顾客，他不必要申请沙发，直接申请理发椅即可sitonthebaber_chair;signal(

8、full);若理发师阻塞，则唤醒理发师，若未阻塞，则将full由0增1,理发师申请理发时即可通过wait(cut);测试理发是否完成，没有则阻塞pay；signal(payment);若理发师阻塞，则唤醒理发师告知其已经付费，若未阻塞，则将paymentl由0增1,理发师申请理要求付费时即可通过wait(receipt);/测试理发师收费是否完成，没有则阻塞getupformthebaber_chair;/理发师收费完成，顾客离开理发椅signal(empty);/释放理发椅wait(mutex);/对count临界资源操作，用mutex完成互斥count=count-1;signal(mut

9、ex);exitshop;processbarber()while(1)wait(full);测试理发椅上是否有顾客，无则阻塞cuthair;signal(cut);/告知顾客理发完成wait(payment);/测试顾客是否付费acceptpament;signal(receipt);/告知顾客收费完毕main()cobeginguesti()；Barber();5、设有两个生产者进程A、B和一个销售者进程C,他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库；而且要求生产和消费A产品和B

10、产品的件数都满足一下关系：-nWA的件数一B的件数Wm,其中n、m是正整数。分析：本题中存在着以下的同步和互斥关系：生产者A、B和消费者之间不能同时将产品入库和出库，故仓库是一个临界资源；两个生产者之间必须进行同步，当生产的A、B产品的件数之差大于等于m时，生产者A必须等待；小于等于-n时，生产者B必须等待；生产者和销售者之间也必须进行同步，只有当生产者生产出产品并入库后，销售者才能进行销售；而且由于销售的产品件数必须满足关系-nWA的件数一B的件数Wm,因此当销售的A、B产品件数之差大于等于m而仓库中已无B产品时，或者销售的A、B产品的件数之差小于等于-n而仓库中已无A产品时，销售者C必须等

11、待生产的A、B产品必须满足：-nWA的件数一B的件数Wm,如例题4中，同样的方法管理，分别使用了信号量SAB和SBA仓库的管理只要求出入库互斥，由于仓库无限大入库只好操作互斥就可以完成，出库要考虑有无产品，SA对应于仓库中的A产品量，SB对应于仓库中的B产品量；销售要满足：-nWA的件数一B的件数用difference表示A的件数一B的件数，即difference=A的件数B的件数;difference=-n的时候，不能取产品B,只能取A;difference=m的时候，不能取产品A,只能取B;-n<difference<m,即可以取产品A也可以取产品B;答：为了互斥地入库和出库，

12、蓄为仓库设置一初值为1的互斥信号量mutex;为了使生产的产品件数满足-nWA的件数一B的件数Wm,须设置两个同步的信号量，其中SAB表示当前允许A生产的产品数量，其初值为m,SBA表示当前允许B生产的产品数量，其初值为n;另外，还需设置一个整数difference表示所销售的A、B产品数量之差，而为了同步生产者和销售者并使销售的A、B产品的件数-nWA的件数一B的件数Wm,还需要设置三个资源信号量，其中s对应于仓库中的总的产品量，SA对应于仓库中的A产品量，SB对应于仓库中的B产品量，它们的初值都为0.SemaphoreSAB=m,SBA=n,S=0,SA=0,SB=0,mutex=1;pr

13、ocessA()while(1)生产产品，5<的件数一8的件数001,方法同第4题wait(SAB);ProduceaproductA;signal(SBA);入库操作，满足出入库操作互斥即可wait(mutex);addtheproductAtothestorehouse;signal(mutex);signal(SA);入库产品A一件，所以给SA增值signal(S);入库产品一件，所以给S增值，S是仓库中全部产品的数量processB()while(1)生产产品，5<的件数一8的件数001,方法同第4题wait(SBA);ProduceaproductB;signal(SAB

14、);入库操作，满足出入库操作互斥即可wait(mutex);addtheproductAtothestorehouse;signal(mutex);signal(SB);队库产品A一件，所以给SA增值signal(S);入库产品一彳所以给S增值，S是仓库中全部产品的数量processB()while(1)wait(S);首先检查有无产品，无产品阻塞，有产品，下面操作将会取走一件产品，所以S减1if(difference<=-n)wait(SA);/difference<=-n时只能取A产品一件，无A产品则需阻塞出库操作，满足出入库操作互斥wait(mutex);takeaprodu

15、ctAfromstorehouse;signal(mutex);difference+;取A产品一件，difference+elseif(difference>=m)wait(SB);difference>=m时只能取B产品一件，无B产品则需阻塞出库操作，满足出入库操作互斥wait(mutex);takeaproductBfromstorehouse;signal(mutex);difference-;/取B产品件，difference-else-n<difference<m,即可以取产品A也可以取产品B,随意取一件产品出来,之后再根据取得产品是A还是B进行处理出库操作

16、，满足出入库操作互斥wait(mutex);takeaproductA或Bfromstorehouse;signal(mutex);if(product_type=A)取的是产品A,则信号量SA减1,这里不可能发生没有A产品，进程C需要阻塞的情况wait(SA);difference+;/取A产品一件，difference+else取的是产品B,则信号量SB减1,这里不可能发生没有B产品，进程C需要阻塞的情况wait(SB);difference-;/取B产品一件，difference-Selltheproduct;main()cobeginA()；B()；C()；6、考虑三个吸烟者进程和一个

17、经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷，做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可以做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试设计一个同步算法来描述他们的活动。SemaphoreSA=SB=SC=0,SD=1;i:integer;processsmokerA()while(1)wait(SA);制烟；signal(SD);吸烟；processsmokerB()while(1)wait(SB);制烟；sig

18、nal(SD);吸烟；processsmokerC()while(1)wait(SC);制烟；signal(SD);吸烟；Processprovider。while(1)wait(SD);i=random(2);switch(i)case'0':signal(SA);case'1':signal(SB);case'2':signal(SC);main()cobeginsomkerA();somkerB();somkerC();provider。；5、现有四个进程1、2、1、W2,它们共享可以存放一个数的缓冲器B。进程R1每次把来自键盘的一个数存入缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数存放到缓冲器B中，供进程W2打印输出。为防止数据的丢失和重复打印，问怎样用信号量操作来协调这四个进程的并发执行。semaphoreS=1,S1=S2=0;bufferB;processR1()intx;while(1)接收来自键盘的数；乂=接收的数；wait(S);B=x;signal(S1);processR2()inty；while(1)从磁盘上读一个数；丫=接收的数；wait(S);B=y；signal(S2);processW1()intk;while(1)wait(Sl);k=B