操作系统--PV操作习题补.ppt

《操作系统--PV操作习题补.ppt》由会员分享，可在线阅读，更多相关《操作系统--PV操作习题补.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.1/25December221 1、用、用P.VP.V操作解决下面的同步问题操作解决下面的同步问题getcopyputfstg要解决的同步问题：要解决的同步问题：GetGet不能向不能向“满满”的的S S中放；中放；CopyCopy不能从不能从“空空”的的S S中取；不能向中取；不能向“满满”的的T T中放；中放；PutPut不能从不能从“空空”的的T T中取中取有有3 3个进程：个进程：get,copyget,copy和和putput，它们对它们对4 4个存储区域个存储区域f f、s s、t t和和g g进行操作：进行操作：其中：其中：f f有取之不尽的数据可以有取之不尽的数据可以get

2、get；g g有用之不完的空间可以有用之不完的空间可以putputs s和和t t则只有一个存储空间。则只有一个存储空间。3,4,.,m22(1,2 )2,3,4,.,m11(1 )1,2,3,4,.,m()练习：练习：操作系统6.2/25December22（同步）信号量：（同步）信号量：实际上也起到互斥作用实际上也起到互斥作用 S_Empty,T_EmptyS_Empty,T_Empty，初值为初值为11S_FullS_Full,T_FullT_Full;初值为初值为00Get进程进程:Begin Repeat P(S_Empty)T_get_S();V(S_Full);Until fal

3、se;EndCopy进程进程:Begin Repeat P(S_Full);P(T_Empty);S_copy_T();V(T_Full);V(S_Empty);Until false;EndPut进程进程:Begin Repeat P(T_Full);T_put_G();V(T_Empty);Until false;End操作系统6.3/25December22正常行车到站停车开车售票开车门关车门司机售票员2 2、重新研究司机和售票员问题，分别写出司机和售票员、重新研究司机和售票员问题，分别写出司机和售票员进程，从而实现该问题的同步进程，从而实现该问题的同步操作系统6.4/25Decembe

4、r22司机进程：司机进程：BeginBegin Repeat Repeat P(S_Door);P(S_Door);行驶；行驶；停车；停车；V(S_Stop);V(S_Stop);Until false;Until false;EndEnd乘务员进程乘务员进程:Begin Begin Repeat Repeat 关门；关门；V(S_Door);V(S_Door);售票；售票；P(S_Stop);P(S_Stop);开门；开门；Until false;Until false;EndEndVar S_Door,S_Stop:Semaphore:=0,0操作系统6.5/25December22司机进

5、程：司机进程：Begin Repeat P(door);行驶；停车;V(stop);Until false;End乘务员进程乘务员进程:Begin RepeatP(stopP(stop););开门；关门；V（door）；售票;Until false;EndVar door，stop:semaphore：1，0操作系统6.6/25December223 3、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能

6、放一只水果供吃者取用，请用的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P P、V V原语实现爸爸、儿子、女儿三个并发进程的同步。原语实现爸爸、儿子、女儿三个并发进程的同步。分析：分析：本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。若放入果盘中的是苹果，则允许女儿吃，儿子必须等待

7、。本题实际上是生产者本题实际上是生产者-消费者问题的一种变形：消费者问题的一种变形：这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品只消费其中固定的一类产品 操作系统6.7/25December22S S：表示盘子是否为空，其初值为：表示盘子是否为空，其初值为l l；SoSo：表示盘中是否有桔子，其初值为：表示盘中是否有桔子，其初值为0 0；SaSa：表示盘中是否有苹果，其初值为：表示盘中是否有苹果，其初值为0 0。设置三个信号量设置三个信号量:S:S、SoSo、SaSa，DaughterDau

8、ghter进程：进程：while(1)while(1)P(SaP(Sa););从盘中取出苹果从盘中取出苹果;V(S);V(S);吃苹果吃苹果;FatherFather进程：进程：while(1)while(1)P(S);P(S);将水果放入盘中将水果放入盘中;if if（放入的是桔子）（放入的是桔子）V(SoV(So););else else V(SaV(Sa););SonSon进程：进程：while(1)while(1)P(SoP(So););从盘中取出桔子从盘中取出桔子;V(S);V(S);吃桔子吃桔子;操作系统6.8/25December22分析问题中涉及的进程；分析问题中涉及的进程；分

9、析问题中的同步关系（竞争，合作）；分析问题中的同步关系（竞争，合作）；（其中，合作关系的解决也是通过转化为对资源的竞争完成的。）（其中，合作关系的解决也是通过转化为对资源的竞争完成的。）参照所竞争的资源设置信号量，并赋予初值；参照所竞争的资源设置信号量，并赋予初值；写出各个进程的描述；写出各个进程的描述；检查每个进程的描述，看是否会出现死锁现象并改正之。检查每个进程的描述，看是否会出现死锁现象并改正之。小结：同步问题解法小结：同步问题解法操作系统6.9/25December22具体的规范格式如下（以苹果桔子题目为例：）具体的规范格式如下（以苹果桔子题目为例：）intint S S1;1;int

10、int Sa Sa0;0;intint So So0;0;main()main()cobegincobegin father();/*father();/*父亲进程父亲进程*/son();/*son();/*儿子进程儿子进程*/daughter();/*daughter();/*女儿进程女儿进程*/coendcoend 解：设置三个信号量解：设置三个信号量S S、SoSo、SaSa，信号量，信号量S S表示盘子是否为空，其初值为表示盘子是否为空，其初值为l l；信号；信号量量SoSo表示盘中是否有桔子，其初值为表示盘中是否有桔子，其初值为0 0；信号量；信号量SaSa表示盘中是否有苹果，其初值

11、表示盘中是否有苹果，其初值为为0 0。同步描述如下：。同步描述如下：father()father()while(1)while(1)P(S);P(S);将水果放入盘中将水果放入盘中;if if（放入的是桔子）（放入的是桔子）V(SoV(So););else else V(SaV(Sa););son()son()while(1)while(1)P(SoP(So););从盘中取出桔子从盘中取出桔子;V(S);V(S);吃桔子吃桔子;daughter()daughter()while(1)while(1)P(SaP(Sa););从盘中取出苹果从盘中取出苹果;V(S);V(S);吃苹果吃苹果;操作系统

12、6.10/25December22作业：睡眠理发师问题操作系统6.11/25December22作业：睡眠理发师问题问题描述问题描述（经典理发师问题）假设后街有家理发店，店里有一个理发师、一把理发椅和n把等候理发的顾客椅子。（1）.如果没有顾客则理发师便在理发椅上睡觉（看报纸）；（2）.当有一个顾客到达时，首先查看理发师在干什么，如果在睡觉（看报纸）则告诉理发师理发，然后坐到理发椅上开始理发；如果理发师正在理发，则查看是否有空的椅子可坐，如果有，他就坐下等待，如果没有，则离开；（3）.理发师为一位顾客理完发后，查看是否有人等待，如有则唤醒一位为其理发，如没有则在理发椅上睡觉（看报纸）；（4）.

13、顾客不分优先级操作系统6.12/25December22作业：睡眠理发师问题问题分析 题目中要求描述理发师和顾客的行为，因此需要两类进程Barber()和Customer()分别描述理发师和顾客的行为。当理发师看报时顾客近来需要唤醒理发师为其理发，当有顾客时理发师为其理发，没有的时候理发师看报，因此理发师和顾客之间是同步的关系，由于每次理发师只能为一个人理发，且可供等侯的椅子有限只有n个，即理发师和椅子是临界资源，所以顾客之间是互斥的关系。故引入3个信号量和一个控制变量：1)控制变量waiting用来记录等候理发的顾客数，初值均为0；2)信号量customers用来记录等候理发的顾客数，并用作

14、阻塞理发师进程，初值为0；3)信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；4)信号量mutex用于互斥，初值为1 操作系统6.13/25December22作业：睡眠理发师问题问题实现 PV操作代码如下:int waiting=0；/等候理发的顾客数 int chairs=n；/为顾客准备的椅子数 semaphore customers=0,barbers=0,mutex=1;barber()while(TRUE);/理完一人,还有顾客吗?P(cutomers);/若无顾客,理发师睡眠 P(mutex);/进程互斥 waiting:=waiting 1;/

15、等候顾客数少一个 V(barbers);/理发师去为一个顾客理发 V(mutex);/开放临界区 cut-hair();/正在理发操作系统6.14/25December22作业：睡眠理发师问题问题实现（接上页）customer()P(mutex);/进程互斥 if(waiting)waiting:=waiting+1;/等候顾客数加1 V(customers);/必要的话唤醒理发师 V(mutex);/开放临界区 P(barbers);/无理发师,顾客坐着养神 get-haircut();/一个顾客坐下等理/else V(mutex);/人满了,走吧!操作系统6.15/25December22

16、理发师问题：理发师问题：一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理发、收银和休息三种活动。理发店的活动满足下列条件：1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；3）理发时间长短由理发师决定；4）在站席区等待时间最长的顾客可坐到空闲的理发上；5）任何时刻最多只能有一个理发师在收银。试用信号量机制或管程机制实现理发师进程和顾客进程。操作系

17、统6.16/25December22原理：(1)customer 进程：首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入理发店。在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列，直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。坐到沙发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。坐到理发椅上，释放准备好的信号（customer_ready），获得该理发师的编号（01 的数字）。等待理

18、发师理发结束（finishedbarber_number）。在离开理发椅之前付款（payment），等待收据(receipt)，离开理发椅（leave_barberchair）。最后离开理发店。操作系统6.17/25December22这里需要注意几点：a)首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅和付款几个地方。b)通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上，因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该

19、信号，而理发师接收到该信号后才释放barber_chair 等待下一位顾客。c)在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的，这样，当该编号的理发师释放对应的finishedi信号的时候，该顾客才理发完毕。d)理发师是通过mutex 信号量保证他们每个人同时只进行一项操作（理发或者收款）。e)为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。在伪码中由以下机制实现：即顾客在释放离开理发椅的信号前，发出付款的信号

20、。这样该理发师得不到顾客的离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款操作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该理发椅的信号，让下一位等待的顾客坐到理发椅上。操作系统6.18/25December22(2)barber 进程首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量customer_ready)，开始理发，理发结束后释放结束信号（finishedi）。等待顾客离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信号(barber_chair)，等待下一位顾客坐

21、上来。(3)cash（收银台）进程等待顾客付款(payment),执行收款操作，收款操作结束，给付收据（receipt）。操作系统6.19/25December22信号量总表：信号量 wait signalstand_capacity 顾客等待进入理发店 顾客离开站席区sofa 顾客等待坐到沙发 顾客离开沙发barber_chair 顾客等待空理发椅 理发师释放空理发椅customer_ready 理发师等待，直到一个顾客坐到理发椅顾客坐到理发椅上，给理发师发出信号mutex 等待理发师空闲，执行理发或收款操作理发师执行理发或收款结束，进入空闲状态mutex1 执行入队或出队等待 入队或出队结

22、束，释放信号finishedi 顾客等待对应编号理发师理发结束；理发师理发结束，释放信号leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据，离开理发椅释放信号payment 收银员等待顾客付款 顾客付款，发出信号receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据，释放信号 操作系统6.20/25December22伪码：semaphore stand_capacity=5;semaphore sofa=4;semaphore barber_chair=3;semaphore customer_ready=0;semaphore mutex=3;s

23、emaphore mutex1=1;semaphore finished3=0,0,0;semaphore leave_barberchair=0;semaphore payment=0;semaphore receipt=0;操作系统6.21/25December22void customer()int barber_number;wait(stand_capacity);/等待进入理发店enter_room();/进入理发店wait(sofa);/等待沙发leave_stand_section();/离开站席区signal(stand_capacity);sit_on_sofa();/坐在

24、沙发上wait(barber_chair);/等待理发椅get_up_sofa();/离开沙发signal(sofa);操作系统6.22/25December22wait(mutex1);sit_on_barberchair();/坐到理发椅上signal(customer_ready);barber_number=dequeue();/得到理发师编号signal(mutex1);wait(finishedbarber_number);/等待理发结束pay();/付款signal(payment);/付款wait(receipt);/等待收据get_up_barberchair();/离开理发

25、椅signal(leave_barberchair);/发出离开理发椅信号exit_shop();/了离开理发店操作系统6.23/25December22void barber(int i)while(true)wait(mutex1);enqueue(i);/将该理发师的编号加入队列signal(mutex1);wait(customer_ready);/等待顾客准备好wait(mutex);cut_hair();/理发signal(mutex);signal(finishedi);/理发结束wait(leave_barberchair);/等待顾客离开理发椅信号signal(barber_

26、chair);/释放barber_chair 信号操作系统6.24/25December22void cash()/收银while(true)wait(payment);/等待顾客付款wait(mutex);/原子操作get_pay();/接受付款give_receipt();/给顾客收据signal(mutex);signal(receipt);/收银完毕，释放信号 操作系统6.25/25December22分析：在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重性的,主要包括：（1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动

27、作的话，很容易造成没有收银员为其收款的情形，原因是：为该顾客理发的理发师收到leave_barberchair 信号后，释放barber_chair 信号，另外一名顾客坐到理发椅上，该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题，就是采取在释放leave_barberchair 信号之前，完成付款操作。这样该理发师无法进入下一轮循环为另外顾客服务，只能到收银台收款。（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号，如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号才会进行付款等操作。这样实现，是为避免这样的错误，即：如果仅用一个finished 信号量的话，很容易出现别的理发师理发完毕释放了finished 信号，把正在理发的这位顾客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为finished数组不能是无限的。而为理发师编号，则只需要三个元素即可操作系统