习题课（一）+PV操作的应用.ppt

习题课 一 PV操作的应用 PV原语的含义 P passerenpassV verhoogincrementP操作和V操作是不可中断的程序段 称为原语 PV操作对于每一个进程来说 都只能进行一次 而且必须成对使用 在PV原语执行期间不允许有中断的发生 PV原语的含义 信号量S是一整数P S 原语操作的动作是 1 S减1 2 若S减1后仍大于或等于零 则进程继续执行 3 若S减1后小于零 则该进程被阻塞后进入与该信号相对应的队列中 然后转进程调度 V S 原语操作的动作是 1 S加1 2 若相加结果大于零 则进程继续执行 3 若相加结果小于或等于零 则从该信号的等待队列中唤醒一等待进程 然后再返回原进程继续执行或转进程调度 用PV操作实现进程的互斥与同步 解决此类问题的一般方式 根据问题给出的条件 确定进程有几个或几类 确定进程间的制约关系 是互斥 还是同步 各相关进程间通过什么信号量实现彼此的制约 标明信号量的含义和初值 用PV操作写出相应的代码段验证代码的正确性 设以不同的次序运行各进程 是否能保证问题的圆满解决 切忌按固定顺序执行各进程 苹果桔子问题 桌上有一只盘子 每次只能放入一只水果 爸爸专向盘子中放苹果 apple 妈妈专向盘子中放桔子 orange 一个儿子专等吃盘子中的桔子 一个女儿专等吃盘子里的苹果 请用 操作实现爸爸 妈妈 儿子 女儿四个并发进程的同步与互斥 苹果桔子问题 解 sp semaphore 盘子里可以放几个水果 sg1 semaphore 盘子里有桔子 sg2 semaphore 盘子里有苹果 sp 1 盘子里允许放一个水果 Sg1 0 盘子里没有桔子 sg2 0 盘子里没有苹果 cobegin 苹果桔子问题 processfatherbeginL1 削一个苹果 盘子为空吗 把苹果放入plate 女儿可以拿苹果 gotoL1 end processdaughterbeginL4 盘子里有苹果吗 从plate中取苹果 盘子又为空 吃苹果 gotoL4 end V sg2 P sp P sg2 V sp 苹果桔子问题 processmotherbeginL2 剥一个桔子 盘子为空吗 把桔子放入plate 儿子可以拿桔子 gotoL2 end processsonbeginL3 盘子里有桔子吗 从plate中取桔子 盘子又为空 吃桔子 gotoL3 end V sg1 P sp P sg1 V sp 苹果桔子问题 processfatherbeginL1 削一个苹果 P sp 把苹果放入plate V sg2 gotoL1 end processmotherbeginL2 剥一个桔子 P sp 把桔子放入plate V sg1 gotoL2 end 苹果桔子问题 processsonbeginL3 P sg1 从plate中取桔子 V sp 吃桔子 gotoL3 end processdaughterbeginL4 P sg2 从plate中取苹果 V sp 吃苹果 gotoL4 end coend 缓冲问题 一 有三个并发进程R M和P 它们共享一个缓冲区B 进程R负责从输入设备读入一条记录 每读一条记录后把它存放在缓冲区B中 进程M在缓冲区B中加工进程R存入的记录 进程P把加工后的记录打印输出 缓冲区B每次只能存放一条记录 当记录被加工输出后 缓冲区B中才可存放另一条新记录 请用P V操作作为同步机制来描述它们并发执行时能正确工作的程序 缓冲问题 一 解 beginR M P semaphore R 1 M P 0 cobegin 进程RL1 从输入设备中读取一条记录 P R 将读入记录存入缓冲区 V M gotoL1进程ML2 P M 对缓冲区中的数据信息进行加工 并将其存入缓冲区中 V P gotoL2进程PL3 P P 输出缓冲区的信息 V R gotoL3coend end 缓冲问题 一 缓冲问题 二 若有三个进程A B和C协作解决文件打印问题 A将文件记录从磁盘读入主存的缓冲区buffer1 每执行一次读一个记录 B将缓冲区buffer1的内容复制到缓冲区buffer2 每执行一次复制一个记录 C打印缓冲区buffer2的内容 每执行一次打印一个记录 缓冲区的大小和一个记录大小一样 请用P V操作来保证文件的正确打印 缓冲问题 二 注意 B既是生产者 也是消费者解 设置信号量初值 mutex1 mutex2 1 empty1 empty2 1 full1 full2 0begincobegin 缓冲问题 二 进程AL1 readfromdisk P empty1 申请空缓冲区buffer1 P mutex1 进程A和B要互斥的访问buffer1 puttobuffer1 向buffer1输入数据 V full1 释放满缓冲区buffer1 V mutex1 进程A对buffer1的访问结束 GotoL1 缓冲问题 二 进程BL2 P full1 P mutex1 Getfrombuffer1 V empty1 V mutex1 P emmty2 P mutex2 Puttobuffer2 V full2 V mutex2 GotoL2 缓冲问题 二 进程CL3 P full2 P mutex2 Getfrombuffer2 V empty2 V mutex2 Printrecord GotoL3 CoendEnd 总结 以上三个题目均为生产者 消费者问题的变型 在处理这类问题时 应注意生产者 消费者问题里的两个条件 对缓冲区的读 写要互斥进行不能从空的缓冲区中读数据 不能向满缓冲区中写数据 通过以上三个题目 加深对PV操作的理解 掌握用PV操作解决进程同步和互斥问题的方法 重点 找出进程间的制约关系 嗜睡的理发师问题 一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成 没有顾客要理发时 理发室便去睡觉 当一个顾客走进理发店时 如果所有的沙发都已被占用 他便离开理发店 否则 如果理发师正在为其他顾客理发 则该顾客就找一张空沙发坐下等待 如果理发师因无顾客正在睡觉 则由新到的顾客唤醒理发师为其理发 在理发完成后 顾客必须付费 知道理发师收费后才能离开理发店 试用信号量实现这一同步问题 嗜睡的理发师问题 解 Varcount integer 0 Mutex sofa empty full semaphore 1 n 1 0 Cut payment receipt semaphore 0 0 0 BeginParbegin 嗜睡的理发师问题 Guest beginWait mutex If count N thenbeginSignal mutex Exitshop endelse begincount count 1 if count 1 thenbeginwait sofa sitonsofa wait empty getupfromsofa signal sofa end 嗜睡的理发师问题 else count 1 wait empty sitonthebaber chair signal full wait cut pay signal payment wait receipt getupfromthebaber chair signal empty wait mutex count count 1 signal mutex exitshop endend 嗜睡的理发师问题 barber beginrepeatwait full cuthair signal cut wait payment acceptpayment signal receipt untilfalse endparendend 仓库问题 设有两个生产者进程A B和一个销售者进程C 他们共享一个无限大的仓库 生产者每次循环生产一个产品 然后入库供销售者销售 销售者每次循环从仓库中取出一个产品进行销售 如果不允许同时入库 也不允许边入库边出库 而且要求生产和销售A产品和B产品的件数都满足以下关系 n A的件数 B的件数 m 其中n m是正整数 请用信号量机制写出A B C三个进程的工作流程 仓库问题 解 vardifference integer 0 SAB SBA S SA SB mutex semaphore m n 0 0 0 1 BeginParbegin 仓库问题 ProcessA beginRepeatWait SAB ProcedureaproductA Signal SBA Wait mutex AddtheproductAtothestorehouse Signal mutex Signal SA Signal S untilfalse end 仓库问题 processB beginrepeatwait SBA produceaproductB signal SAB wait mutex addtheproductBtothestorehouse signal mutex signal SB signal S untilfalse end 仓库问题 processC beginrepeatwait S ifdifference nthenbeginwait SA wait mutex takeaproductAfromstorehouse signal mutex difference difference 1 end elseifdifference mthenbeginwait SB wait mutex takeaproductBfromstorehouse signal mutex difference difference 1 end 仓库问题 elsebeginwai