第32进程的同步与互斥.ppt

第第第第3 3章章章章 进程管理进程管理进程管理进程管理Ø 3.1 进程的引入进程的引入Ø 3.2 进程的结构进程的结构Ø 3.3 进程控制进程控制Ø 3.4 进程的同步与互斥进程的同步与互斥Ø 3.5 进程间通信进程间通信 Ø 3.6 进程调度进程调度Ø 3.7 死锁死锁Ø 3.8 线程线程锥距蒸薯窟咏碧稍卤机染著萍柑献奥履仁宫靠剧创野株炔衰查高皇崔顺半第32进程的同步与互斥第32进程的同步与互斥9/17/20241两种制约关系两种制约关系两种制约关系两种制约关系Ø直接相互制约关系（同步）直接相互制约关系（同步） Ø间接相互制约关系（互斥）间接相互制约关系（互斥）Ø产生的原因产生的原因§进程合作进程合作§资源共享资源共享 粕灸邱痢者妨恬宫里逊垄梨敢休畜赘拴属蛔耿馆炳烷篷题渡雨圃佰顶彪伐第32进程的同步与互斥第32进程的同步与互斥9/17/20242进程的同步（进程的同步（进程的同步（进程的同步（1 1））））Ø直接相互制约关系（同步）直接相互制约关系（同步） 指系统中一些进程需要相互合作，共同完成一指系统中一些进程需要相互合作，共同完成一项任务项任务, ,这种协作进程之间相互等待对方消息或信这种协作进程之间相互等待对方消息或信号的协调关系称为号的协调关系称为进程同步进程同步. .具体说，并发进程在具体说，并发进程在一些关键点上可能需要互相等待与互通消息，进程一些关键点上可能需要互相等待与互通消息，进程间的相互联系是间的相互联系是有意识有意识的安排的。

的安排的Ø产生的原因产生的原因§进程合作进程合作拓禄丑俊握奖犊棋烯恃曹牡房浩关攘胎哦卢店昭仑卡诬临甸惧嫂补宠三媳第32进程的同步与互斥第32进程的同步与互斥9/17/20243进程的同步（进程的同步（进程的同步（进程的同步（2 2））））Ø一般同步问题有两类一般同步问题有两类§保证一组合作进程按逻辑需要的执行次序执行保证一组合作进程按逻辑需要的执行次序执行 【【例例】】司机司机 P1 售票员售票员 P2 REPEAT REPEAT 启动启动 关门关门 正常运行正常运行 售票售票 到站停到站停 开门开门 UNTIL FALSE UNTIL FALSE§保证共享缓冲区（共享数据）的合作进程的同步保证共享缓冲区（共享数据）的合作进程的同步 【【例例】】输入输入进程进程PI缓冲区缓冲区缓冲区缓冲区计算计算进程进程PC打印打印进程进程PP铸莲峡亨烛钦而血栖舟嘛筑渴洞奥儿图膳赊熏剿行旦债俐俘悲态疤搪锭寿第32进程的同步与互斥第32进程的同步与互斥9/17/20244进程的互斥进程的互斥进程的互斥进程的互斥Ø是解决进程间竞争关系是解决进程间竞争关系( (间接制约关系间接制约关系) )的手段。

的手段Ø间接相互制约关系（互斥）间接相互制约关系（互斥） 是指若干个进程同时竞争一个是指若干个进程同时竞争一个需要互斥使用需要互斥使用的资源的资源时，任何时刻最多允许一个进程去使用，其时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到该资源被释他要使用该资源的进程必须等待，直到该资源被释放进程间要通过某种中介发生联系，是放进程间要通过某种中介发生联系，是无意识无意识安安排的Ø产生的原因产生的原因§资源共享资源共享Ø互斥是一种特殊的同步互斥是一种特殊的同步§逐次使用互斥资源，也是对进程使用资源次序逐次使用互斥资源，也是对进程使用资源次序上的一种协调上的一种协调兽玲抄黄铣检讲痕内烘聊铸族洛焙领子擂沉脊烃渐砌谊狄提办禄颂炭苏揭第32进程的同步与互斥第32进程的同步与互斥9/17/20245临界资源临界资源临界资源临界资源Ø临界资源临界资源 系统中某些资源系统中某些资源一次只允许一一次只允许一个进程使用个进程使用，称这样的资源为临界资，称这样的资源为临界资源或互斥资源或共享变量源或互斥资源或共享变量§硬件临界资源：打印机、磁带机硬件临界资源：打印机、磁带机§软件临界资源：只能排它使用的变量、软件临界资源：只能排它使用的变量、表格、队列表格、队列室堰巡祭销邱风城饺亿愈烩耳俄版莎涂趴郊丈恿韩读掠锯脊角糟巩聂毕讥第32进程的同步与互斥第32进程的同步与互斥9/17/20246临界资源实例临界资源实例临界资源实例临界资源实例Ø二人合作存款二人合作存款 count=100;count=100; P PA A S1:N=count;S1:N=count; S2:N=N+100; S2:N=N+100; S3:count=N; S3:count=N;P PB B S4:M=count;S4:M=count; S5:M=M+200; S5:M=M+200; S6:count=M; S6:count=M;执行情况：执行情况：（（1）） P PA A—> P PB B ,P,PB B—> P PA A count=400 count=400 √√ （（2）） S1S1—> P PB B—>S2—>S3 count=200 count=200 ×（（3）） S4S4—> P PA A—>S5—>S6 count=300 count=300 ×因因count是一个互斥性使用的变量，是一个临界资源是一个互斥性使用的变量，是一个临界资源涡戌钨撇虎笆摈璃脏茄畦媳喘舟绳前身沪唱霸仔俊息洪陛馈诛座梯绍渗沤第32进程的同步与互斥第32进程的同步与互斥9/17/20247临界区临界区临界区临界区Ø临界区（临界段）临界区（临界段） 在进程中访问临界资源的那段代码区。

在进程中访问临界资源的那段代码区例子例子榴系让猪胜泞娟开映驱亲讽呀剿履豫专气袱哆守靳机渗挂紊秸恬庶揪毖郊第32进程的同步与互斥第32进程的同步与互斥9/17/20248具有临界资源的进程结构具有临界资源的进程结构具有临界资源的进程结构具有临界资源的进程结构 …… /*进入区进入区*/ critical section; /*临界区临界区*/ /*退出区退出区*/ remainder section; /*剩余区剩余区*/ ……entry sectionexit section际刁歌偿蒙驮吮彭蜜戮聊锌李巢夕滥钡绣纲劫裙霄事唉柔狼薄萨褥屡属喝第32进程的同步与互斥第32进程的同步与互斥9/17/20249访问临界区应遵循的原则访问临界区应遵循的原则访问临界区应遵循的原则访问临界区应遵循的原则Ø空闲让进空闲让进 当无进程在临界区时，任何有权使用临界区当无进程在临界区时，任何有权使用临界区的进程可进入。

的进程可进入Ø忙则等待忙则等待 不允许两个以上的进程同时进入临界区不允许两个以上的进程同时进入临界区Ø有限等待有限等待 任何进入临界区的要求应在有限的时间内得任何进入临界区的要求应在有限的时间内得到满足Ø让权等待让权等待 不能进入临界区的进程应放弃占用不能进入临界区的进程应放弃占用CPUCPU甭耐倦求火吮趋骚孝篇漱剑求辞爹真桌涌言祟骋闯际解杜寝及韦拔有瞬土第32进程的同步与互斥第32进程的同步与互斥9/17/202410临界区互斥解决方法临界区互斥解决方法临界区互斥解决方法临界区互斥解决方法Ø硬件硬件§缺点：成本高缺点：成本高Ø软件软件§用编程解决用编程解决§缺点：缺点： (1) (1)忙等待忙等待 (2) (2)实现过于复杂，需要高的编程技巧实现过于复杂，需要高的编程技巧Ø信号量机制信号量机制痊将颐犹吻去烛锁饲蛆贵诸宪婿捞泻瘫眨激鼻严囊绝肃叔内嫁枣堆降讫奔第32进程的同步与互斥第32进程的同步与互斥9/17/202411信号量机制信号量机制信号量机制信号量机制一类资源一类资源抽象成抽象成S（信号量）（信号量）Ø信号量信号量 只能由只能由P P、、V V操作对其进行操作的变量。

操作对其进行操作的变量Ø信号量的使用应注意信号量的使用应注意§必须置一次且只能置一次初值必须置一次且只能置一次初值§初值只能为非负整数，实现互斥时初值为初值只能为非负整数，实现互斥时初值为1 1§只能执行只能执行P P、、V V操作聪奔竿羽摈件垢鹏似根任巳俱悍曙莎工徐岳涕肾可瑰惹挛邵记瘦馅昭篙反第32进程的同步与互斥第32进程的同步与互斥9/17/202412P P、、、、V V操作操作操作操作Ø P(S)：表示申请一个资源：表示申请一个资源 V(S)：表示释放一个资源表示释放一个资源Ø P、、V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定操作就一定有一个有一个V操作浆际希诚韵包釜闰磷嚼柜蓉巢芥贡晌崔淌狼询牟铱生坤垮呐鞭贤你沮寺规第32进程的同步与互斥第32进程的同步与互斥9/17/202413整型信号量整型信号量整型信号量整型信号量Ø整型信号量整型信号量§信信号号量量S：：整整型型量量，，除除初初始始化化外外仅仅能能通通过过P P、、V V操作访问操作访问§P P和和V V操作原语定义：操作原语定义： var S:integer; S=1; var S:integer; S=1; P(S)：： while S ≤0 do no-op S = S -1；； V(S )：：S = S +1；；一类资源一类资源抽象成抽象成S（信号量）（信号量）整型量整型量喳犯笨构界艾迎摊徘硅竞李丘剂什吊祥宦酣曙毒颊递遏五趾拯宗怕食绑钱第32进程的同步与互斥第32进程的同步与互斥9/17/202414利用整型信号量实现进程互斥利用整型信号量实现进程互斥利用整型信号量实现进程互斥利用整型信号量实现进程互斥P(S)V(S)P(S)V(S)乙抑勘沥捅靴缀汁谓狙矢撂曳这捕庐窄陋绸纱煌沈焰玫味夷租糙撑贪虹淄第32进程的同步与互斥第32进程的同步与互斥9/17/202415记录型信号量记录型信号量记录型信号量记录型信号量Ø记录型信号量记录型信号量§信信号号量量S S：：记记录录型型数数据据结结构构, ,一一个个分分量量为为整整型型量量value,value,另另一个分量为信号量队列一个分量为信号量队列 L L；；Ø信号量的物理含义信号量的物理含义§ 当当S.value>0：表示可用资源个数：表示可用资源个数 当当S.value＝＝0：表示可用资源正好用完：表示可用资源正好用完 当当S.value<0：表示等待该类资源的进程数：表示等待该类资源的进程数一类资源一类资源抽象成抽象成S（信号量）（信号量）value 0L=nil信号量的值信号量的值(-2)(-2)信号量队列指针信号量队列指针话统龄掷松汇澈奋仇喜贰佯颈熬来掐筒胆灼皱慕蒸贷蒲良烂摇盎锦押剔胀第32进程的同步与互斥第32进程的同步与互斥9/17/202416struct semaphore{ int value; int *L;}void P(struct semaphore S);{ S.value = S.value – 1; /* 把信号量减去把信号量减去1 */ if S.value < 0 then block(S.L); /* 若信号量小于若信号量小于0，则调用，则调用P(S)的进的进 程被置成等待信号量程被置成等待信号量S的状态的状态 */}物物理理意意义义：：申申请请一一个个资资源源，，如如果果申申请请成成功功，，则则返返回回；；如如果果申申请请不不成成功功，，则挂在该资源的等待队列上。

则挂在该资源的等待队列上void V(struct semaphore S);{ S.value = S.value + 1; /* 把信号量加把信号量加1 */ if S.value <= 0 then wakeup(S.L); /* 若信号量小于等于若信号量小于等于0，则释放一个等待信号量，则释放一个等待信号量s的进程的进程 */}物物理理意意义义：：归归还还一一个个资资源源，，如如果果没没有有进进程程等等待待该该资资源源，，则则返返回回；；如如果果有有进程在等待，把等待的进程从进程在等待，把等待的进程从L上移到就绪队列上移到就绪队列记录型信号量描述记录型信号量描述记录型信号量描述记录型信号量描述椎纸峡旨统壹骏破冉张诫褐翟斑惋诺砚秩创逆秤篓佳鼻俊慨柜滩制斗患捧第32进程的同步与互斥第32进程的同步与互斥9/17/202417利用记录型信号量实现进程互斥利用记录型信号量实现进程互斥利用记录型信号量实现进程互斥利用记录型信号量实现进程互斥P(mutex)V(mutex)P(mutex)V(mutex)提答疡宾石共钦涩豌猪咯党拆般低钟卯懂绍旷根甜捏耙呜涝习篡碰宵芽尾第32进程的同步与互斥第32进程的同步与互斥9/17/202418信号量及信号量及信号量及信号量及P P、、、、V V操作讨论操作讨论操作讨论操作讨论(1)(1) 信号量的物理含义：信号量的物理含义： S .value >0: 表示有表示有S .value个资源可用个资源可用S .value =0: 表示无资源可用表示无资源可用S .value <0: 则则| S .value|表示等待队列中的进程表示等待队列中的进程个数个数 信号量的初值应该大于等于信号量的初值应该大于等于0宿序凰瞒巷弧碧医模希恫载茄勘瘴止谐形沪尹幕烦毅吃惹旬慧裂投婚布准第32进程的同步与互斥第32进程的同步与互斥9/17/202419P P、、、、V V操作讨论操作讨论操作讨论操作讨论(2)(2)Ø P(S)：表示申请一个资源：表示申请一个资源 V(S)：表示释放一个资源。

表示释放一个资源Ø P、、V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定操作就一定有一个有一个V操作操作ØP、、V操作的优点操作的优点 简单，而且表达能力强，可解决任何互斥问题简单，而且表达能力强，可解决任何互斥问题ØP、、V操作的缺点操作的缺点 不够安全，不够安全，P、、V操作使用不当会出现死锁，遇操作使用不当会出现死锁，遇到复杂互斥问题时，实现复杂到复杂互斥问题时，实现复杂樱割誓彼俄聂奏挑李朴深直谓庭熄远剪硷煤佣颗滞凑模钠痉淌师玻猜升施第32进程的同步与互斥第32进程的同步与互斥9/17/202420用用用用P P、、、、V V操作实现互斥操作实现互斥操作实现互斥操作实现互斥Ø信号量初值为信号量初值为1Ø对于两个并发进程，互斥信号量的值仅取对于两个并发进程，互斥信号量的值仅取1、、0和和-1三个值三个值 ：：§若若mutex.value＝＝1表示没有进程进入临界区表示没有进程进入临界区§若若mutex.value＝＝0表表示示有有一一个个进进程程进进入入临临界界区区§若若mutex.value ＝＝-1表示一个进程进入临界表示一个进程进入临界区，另一个进程等待进入。

区，另一个进程等待进入曰谦栗刊樟陡蚁泊箱拍娃鸟父瓮赣瞧腆骑智融俺寄磺刚竹器良靖武盈傣掌第32进程的同步与互斥第32进程的同步与互斥9/17/202421Ø利用利用P、、V操作实现两个进程互斥的模板如下操作实现两个进程互斥的模板如下：： struct semaphore mutex; mutex.value=1; mutex.L=nil; { cobegin Process P1:Begin M P(mutex); 临界区临界区1 V(mutex); M End Process P2:Begin M P(mutex); 临界区临界区2 V(mutex); M End coend } 壹遵氮枢姚属产颓认蝇铣靛恶唯倾榜咎绊洲坷社渺浆改度实响诉豆突街嘲第32进程的同步与互斥第32进程的同步与互斥9/17/202422使用使用使用使用PVPVPVPV操作实现互斥应注意操作实现互斥应注意操作实现互斥应注意操作实现互斥应注意Ø识别临界资源识别临界资源§是否被共享是否被共享;§是否有排它性使用要求。

是否有排它性使用要求Ø临界区代码应尽量短小，不能有死循环临界区代码应尽量短小，不能有死循环ØP和和V原语应分别紧靠临界区的头尾原语应分别紧靠临界区的头尾ØP、、V操作在同一进程中必须成对出现操作在同一进程中必须成对出现痪彝所沛号很绝侮邵惫沏宅常佩愈跋棠骑棘嚣缩诬学奥霄镰斗抛炬哭漓铱第32进程的同步与互斥第32进程的同步与互斥9/17/202423思考题思考题思考题思考题 用记录型信号量解决二人存款问题，用用记录型信号量解决二人存款问题，用类类C语言编写进程互斥算法语言编写进程互斥算法膘呢征龙丛盲汤骏赡园膘持厦输摘爪世斡熔粮走炊嫁诸裔甥树炊铁兄轰雹第32进程的同步与互斥第32进程的同步与互斥9/17/202424用用用用P P、、、、V V操作实现操作实现操作实现操作实现进程的同步进程的同步进程的同步进程的同步Ø只要信号量初值是一个大于等于只要信号量初值是一个大于等于0的整数就能的整数就能达到同步的目的，就可以直接使用达到同步的目的，就可以直接使用P、、V操作操作实现同步实现同步Ø互斥是一种特殊的同步互斥是一种特殊的同步P、、V操作既可以实现互斥，也可以实现同步操作既可以实现互斥，也可以实现同步琐授仿杨穷绊着兹做宅陶眶努肄莱兹笼硷橱柿依薛乡期射钵舀棘抨敞帽榔第32进程的同步与互斥第32进程的同步与互斥9/17/202425利用信号量实现进程同步的实例利用信号量实现进程同步的实例利用信号量实现进程同步的实例利用信号量实现进程同步的实例Ø设有三个并发执行的进程设有三个并发执行的进程P1、、P2、、P3，其前趋图如下，，其前趋图如下，试用信号量实现这三个进程同步。

试用信号量实现这三个进程同步§设两个同步信号量设两个同步信号量S1、、S2分别表示进程分别表示进程P2、、P3能否开始执行能否开始执行§struct semaphore S1,S2=0,0; /*初值均为初值均为0*/ { cobegin P1: { V(S1); V(S2); } P2: { P(S1); ; } P3: { P(S2);  ; } coend } P1P3P2颜峻窗建钾号叹撮乒扁调敲什伎炎亦允苟空奶军喂续看示亩躲忽筑谨遥逛第32进程的同步与互斥第32进程的同步与互斥9/17/202426使用使用使用使用PVPVPVPV操作实现同步应注意操作实现同步应注意操作实现同步应注意操作实现同步应注意Ø信号量的设置信号量的设置Ø 信号量的初值信号量的初值 Ø PVPV操作要成对出现，并在不同的进操作要成对出现，并在不同的进程中程中舞劈斩鼓橱疽经琼钡牧粥杖目哺耐锚滚妊叶慑沙蜒燥虞胆傣抠哩蝎沦洱役第32进程的同步与互斥第32进程的同步与互斥9/17/202427信号量及信号量及信号量及信号量及P P、、、、V V操作讨论操作讨论操作讨论操作讨论(3)(3)(1) P、、V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定有一操作就一定有一 个个V操作操作(2) 当为互斥操作时，它们同处于同一进程当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现当为同步操作时，则不在同一进程中出现(3) 如果如果P(S1)和和P(S2)两个操作在一起，那么两个操作在一起，那么P操作的操作的 顺序至关重要。

顺序至关重要 一个同步一个同步P操作与一个互斥操作与一个互斥P操作在一起时，同步操作在一起时，同步 P操作在互斥操作在互斥P操作前，而两个操作前，而两个V操作无关紧要操作无关紧要梁皇摩枕顷惕焉倪廊瓷咀梯略惕危戚酱侈扑旦祷节俞古褥锋疑吼栖做颈苍第32进程的同步与互斥第32进程的同步与互斥9/17/202428PVPV操作实现互斥与同步的模板操作实现互斥与同步的模板操作实现互斥与同步的模板操作实现互斥与同步的模板进程互斥进程互斥 S初值为初值为1 P1 P2 P(S) P(S) 临界区临界区1 临界区临界区2 V(S) V(S)在在P1与与P2中设置相同的中设置相同的P、、V操作操作进程同步进程同步 S1初值为初值为n，， S2初值为初值为0 P1 P2 P(S1) P(S2) 段段1 段段2 V(S2) V(S1)抚凛金袋唬哗憨侮伎耳杨硝址橱虏忘戈理鹤辫说吗蛋峭哟桑蔼棠灰霜纬茅第32进程的同步与互斥第32进程的同步与互斥9/17/202429经典的进程同步问题经典的进程同步问题经典的进程同步问题经典的进程同步问题Ø 生产者生产者/消费者问题消费者问题 Ø 读者读者/写者问题写者问题 Ø 哲学家进餐问题哲学家进餐问题攘介赞赊勘存旧埋债光执支撼译添茵露寓区危瘩弓疟垮餐磺瘟狡抗匿巷罩第32进程的同步与互斥第32进程的同步与互斥9/17/202430生产者生产者生产者生产者/ /消费者问题消费者问题消费者问题消费者问题 生生产产者者消消费费者者问问题题是是一一种种同同步步问问题题的的抽抽象象描描述述。

计计算算机机系系统统中中的的每每个个进进程程都都可可以以消消费费（（使使用用））或或生生产产（（释释放放））某某类类资资源源这这些些资源可以是硬件资源，也可以是软件资源资源可以是硬件资源，也可以是软件资源 当当某某一一进进程程使使用用某某一一资资源源时时，，可可以以看看作作是是消消费费，，称称该该进进程程为为消消费费者者而而当当某某一一进进程程释放某一资源时，它就相当于生产者释放某一资源时，它就相当于生产者脊画乃骸看仟纂末协头攀倡右衫坤购赃屑愿官负痹味涝颓虞斥斌栋裹绪橇第32进程的同步与互斥第32进程的同步与互斥9/17/202431生产者生产者生产者生产者/ /消费者问题消费者问题消费者问题消费者问题( (描述描述描述描述) ) 通过一个公用缓冲池可以把一群生产者通过一个公用缓冲池可以把一群生产者p1,p2…,pm，和一群消费者，和一群消费者Q1,Q2,…,Qn联联系起来如图系起来如图:Ø只要缓冲区未满，生产者就可以把产品送入只要缓冲区未满，生产者就可以把产品送入缓冲区缓冲区;Ø只要缓冲区未空，消费者就可以从缓冲区中只要缓冲区未空，消费者就可以从缓冲区中取走物品。

取走物品挚肪岸分援肮涝距穿洽地返声存案霞酸巧鲍叛缚往岁纶现忆街改蝶栓此妻第32进程的同步与互斥第32进程的同步与互斥9/17/202432生产者生产者生产者生产者/ /消费者问题消费者问题消费者问题消费者问题( (图示图示图示图示) )藉棋著绳屁享曳硼眯帐卡脂么花了篱惟曲告沈阵陡吓孽里荣默缓嗡硅稍偏第32进程的同步与互斥第32进程的同步与互斥9/17/202433生产者生产者生产者生产者/ /消费者问题消费者问题消费者问题消费者问题( (分析分析分析分析) )Ø为解决生产者消费者问题，应该设两个同步信号量，一个说明为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用空缓冲区的数目，用empty表示，初值为缓冲池的大小表示，初值为缓冲池的大小N，另，另一个说明已用缓冲区的数目，用一个说明已用缓冲区的数目，用full表示，初值为０表示，初值为０Ø由于在此问题中有由于在此问题中有i个生产者和个生产者和j个消费者，它们在执行生产活个消费者，它们在执行生产活动和消费活动中要对缓冲池进行操作由于缓冲池是一个临界动和消费活动中要对缓冲池进行操作由于缓冲池是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为１。

其初值为１Østruct semaphone empty=n, full=0, mutex=1; void buffer[n-1]; int in=, out=0;剩茶韶涉舀南浙僵伺守译狠锌疯敏古激氰借猴否蜕汝渐疮掣狱后吻志矿狐第32进程的同步与互斥第32进程的同步与互斥9/17/202434生产者生产者生产者生产者/ /消费者问题消费者问题消费者问题消费者问题( (解决解决解决解决) )Consumerj: while(1) { P(full); P(mutex); 从从Buffer[out]取产品取产品; out = (out+1) mod n; V(mutex); V(empty); 消费产品消费产品; }coend;cobeginprocedurei: while(1) { 生产产品生产产品; P(empty); P(mutex); 往往Buffer [in]放产品放产品; in = (in+1) mod n; V(mutex); V(full); }熏肤底硒殿傀差保篆士旋昧香左嚣量乳窍忍砸蜡揣坪养均礁各厄阮瓷穷挡第32进程的同步与互斥第32进程的同步与互斥9/17/202435生产者生产者生产者生产者/ /消费者问题消费者问题消费者问题消费者问题( (思考思考思考思考) )Ø在生产者进程和消费者进程中，两个在生产者进程和消费者进程中，两个P操作操作的执行顺序是否能交换？两个的执行顺序是否能交换？两个V操作的执行操作的执行顺序是否能交换？顺序是否能交换？呕侗撼喻贮乓邻娘溅绸蝉当墙剐征扇羹形宛蒂要摔其逸焚穗熊攒叠躯帜祝第32进程的同步与互斥第32进程的同步与互斥9/17/202436思考题思考题思考题思考题 两个进程合作完成数据计算和打印工作，两个进程合作完成数据计算和打印工作，计算进程未计算完就不可打印，反之也然，计算进程未计算完就不可打印，反之也然，双方共用一个缓冲区，写出此算法双方共用一个缓冲区，写出此算法。

谭直究熄敞了醉帅货皿股只吐卖签女豁窍访招戒桌析扒襄拜矮辜横立阴摸第32进程的同步与互斥第32进程的同步与互斥9/17/202437读者读者读者读者/ /写者问题写者问题写者问题写者问题 有两组并发进程有两组并发进程: : §读者和写者读者和写者, ,共享一个数据文件共享一个数据文件 要求：要求：§允许多个读者同时执行读操作允许多个读者同时执行读操作§不允许读者、写者同时操作不允许读者、写者同时操作§不允许多个写者同时操作不允许多个写者同时操作卡炕乖酪弓辙疑闲应岂炔瘁蠕谊轿罩镑讼釉祟捻癌紫撞辟埔汉浅肘搜受舵第32进程的同步与互斥第32进程的同步与互斥9/17/202438读者读者读者读者/ /写者问题写者问题写者问题写者问题 如果读者来：如果读者来：1）无读者、写者，新读者可以读）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等）有写者写，新读者等 如果写者来：如果写者来：1）无读者、写者，新写者可以写）无读者、写者，新写者可以写2）有读者，新写者等待）有读者，新写者等待3）有其它写者，新写者等待）有其它写者，新写者等待仿生位壤惧届盯栓袜顽涨肩酵牟冶遏苫虞婴凌状对贞柄柏晓匀嘘搀群问鲁第32进程的同步与互斥第32进程的同步与互斥9/17/202439读者写者问题的解法读者写者问题的解法读者写者问题的解法读者写者问题的解法Ø为实现读者和写者、写者和写者之间的互斥，设置一个互斥为实现读者和写者、写者和写者之间的互斥，设置一个互斥信号量信号量Wmutex=1Ø由于由于“读读—读读”允许，再设置一个整型变量允许，再设置一个整型变量Readcount表示表示正在读的进程数，初值正在读的进程数，初值Readcount=0Ø由于由于Readcount是一个可被多个读者进程访问的临界资源是一个可被多个读者进程访问的临界资源 ，，所以要为它设置一个互斥信号量所以要为它设置一个互斥信号量Rmutex=1Ø读者读者—写者算法如下：写者算法如下：读者：读者：{ P(Rmutex); if readcount=0 then P(Wmutex); Readcount= Readcount+1; V(Rmutex); 读读 P(Rmutex); Readcount= Readcount-1; if Readcount=0 then V(Wmutex); V(Rmutex);} 写者：写者： { P(Wmutex); 写写 V(Wmutex); }扑遏搐丰裹武鸿兄林逗刊壮矛恰涟仔晰治券腰廓硒狮募菠殉翰腥满馈敛害第32进程的同步与互斥第32进程的同步与互斥9/17/202440哲学家就餐问题哲学家就餐问题哲学家就餐问题哲学家就餐问题Ø有五个哲学家围坐在一圆桌旁，有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一有一只空盘子，每两人之间放一只筷子。

只筷子Ø每个哲学家的行为是思考，感到每个哲学家的行为是思考，感到饥饿，取筷子，然后吃通心粉，饥饿，取筷子，然后吃通心粉，放筷子，思考放筷子，思考Ø为了吃通心粉，每个哲学家必须为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷直接从自己的左边或右边去取筷子Ø筷子是临界资源，要用筷子是临界资源，要用5 5个互斥个互斥信号量来表示这信号量来表示这5 5只筷子块札决靡些寝站弧鞍拯皿酵腰轮坍朋鄙害钉醉流姬属丧屡史殷研潦蹬瘤嗅第32进程的同步与互斥第32进程的同步与互斥9/17/202441哲学家就餐问题解哲学家就餐问题解哲学家就餐问题解哲学家就餐问题解设设fork[5]为为5 个信号量，初值均为个信号量，初值均为1struct semaphore fork [4]; fork[i]:= 1;Philosopheri：：While(1){ 思考；思考； P(fork[i]); P(fork[(i+1) mod 5])；； 进食；进食； V(fork[i]); V(fork[(i+1) mod 5])；；} 以上解法会出现死锁以上解法会出现死锁, ,为防止死锁发生可采为防止死锁发生可采取的措施：取的措施：Ø最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围Ø给所有哲学家编号，奇数号的哲学家必须首给所有哲学家编号，奇数号的哲学家必须首 先拿左边的筷子，偶数号的哲学家则反先拿左边的筷子，偶数号的哲学家则反Ø仅当一个哲学家左右两边的筷子都可用仅当一个哲学家左右两边的筷子都可用 时，才允许他拿筷子（时，才允许他拿筷子（ ））沏妊捕饮法抛乒漾缴蠢媒氨如蠕淤裂窜涅滑椎裴查礁毡瘸雹刑犯松跃拳沧第32进程的同步与互斥第32进程的同步与互斥9/17/202442思考题思考题思考题思考题 桌桌子子上上有有一一只只盘盘子子，，每每次次只只能能放放入入一一只只水水果果。

爸爸爸爸专专向向盘盘中中放放苹苹果果，，妈妈妈妈专专向向盘盘中中放放桔桔子子，，一一个个儿儿子子专专等等吃吃盘盘中中的的桔桔子子，，一一个个女女儿儿专专等等吃吃盘盘中中的的苹苹果果请请利利用用P P、、V V操操作作写写出出父父亲亲、、母母亲亲、、儿儿子子、、女女儿儿进进程程的的同同步步算算法剩馒汪识馏须垢崖惺粹魄剔凉厚膏绕晌唇息铃蓬趋势笆钦谋泵胺柬梦身拌第32进程的同步与互斥第32进程的同步与互斥9/17/202443思考题思考题思考题思考题分析：在本题中，应设置三个信号量分析：在本题中，应设置三个信号量s s、、soso、、 sa sa，，Ø信号量信号量s s表示盘子是否为空，其初值为表示盘子是否为空，其初值为1 1；；Ø信信号号量量soso表表示示盘盘中中是是否否有有桔桔子子，，其其初初值值为为0 0；；Ø信号量信号量sasa表示盘中是否有苹果，其初值为表示盘中是否有苹果，其初值为0 0 同步描述如下：同步描述如下：呵剁涤脐芭跺央驻鬼狠妒竟买作涅充许矢购讥揍遁方酪兴鬼拍穷宾还咆骇第32进程的同步与互斥第32进程的同步与互斥9/17/202444 struct semaphone s=1, so=0, sa=0; { cobegin father ( );father ( ); mother( ); mother( ); son ( ); son ( ); daughter ( ); daughter ( ); coendcoend father ( )father ( ) p(s); p(s); 将水果放入盘中；将水果放入盘中； v(sa); v(sa); mother ( ) mother ( ) p(s); p(s); 将水果放入盘中；将水果放入盘中； v(so); v(so); son ( )son ( ) p(so); p(so); 从盘中取出桔子；从盘中取出桔子； v(s); v(s); 吃桔子；吃桔子；daughter ( )daughter ( ) p(sa); p(sa); 从盘中取出苹果；从盘中取出苹果； v(s); v(s); 吃苹果；吃苹果；} }凰寓垫悬牡墒诲舶峦锭袒飞革妇驻那陋炬颗卡晒痪童啪勋惜脸尽合辖畔姿第32进程的同步与互斥第32进程的同步与互斥9/17/202445。