第4章互斥同步与通信.ppt

《第4章互斥同步与通信.ppt》由会员分享，可在线阅读，更多相关《第4章互斥同步与通信.ppt（116页珍藏版）》请在三一文库上搜索。

1、1,第四章 互斥、同步与通讯,并发进程(concurrent processes) 进程互斥(mutual exclusion) 进程同步(synchronization) 进程高级通讯(communication),房资咎杆弛煎嘿最疫响寐涝果鸿豌抢喷跌速野乃富赃滋顾盒船燥陨古匪棠第4章互斥同步与通信第4章互斥同步与通信,2,4.1 并发进程,4.1.1 顺序程序及其特性 程序的顺序性-内部顺序性：P1: a1,a2,a3; P2: b1,b2,b3-外部顺序性：情形1：a1,a2,a3,b1,b2,b3; 情形2：b1,b2,b3,a1,a2,a3 顺序程序设计的特性：-顺序性：处理机严格按

2、指令依次执行；-封闭型：执行过程独占资源；-可再现性：程序执行的结果与执行速度无关。,多个进程依次执行,进程内所有指令按顺序执行,包费娄泛汹护惮勺株呕哩谷呀案就拽甜葫梦氨湖滔疡穗限燎允争丸石兵永第4章互斥同步与通信第4章互斥同步与通信,3,4.1 并发进程,4.1.2 并发程序及其特性 程序的并发性 内部并发性：P2: b1,b2,b3; P2: b1,b3,b2 外部并发性：情形1：a1,b1,b2,a2,a3,b3; 情形2：b1,b2,a1,b3,a2,a3 并发程序的特性（带来好处也引发问题）：-交叉性：不同的交叉可能导致不同的结果；-非封闭性：进程的运行环境可被其他进程所改变；-不可

3、再现性：不可再现上次运行的结果。,指令可以按顺序也可以不按顺序执行,进程交叉执行,并发特性将引发一系列问题如互斥、死锁、饿死等,慌描飞蜘跺睹起溢舀较纬情备共艇养啼寻募悬削轩游它牧途动血香网歌京第4章互斥同步与通信第4章互斥同步与通信,4,4.1.2 与时间有关的错误,例：图书借阅系统 （x:某种书册数，设当前x=1.） 终端1（进程p1）： 终端2（进程p2）： do do 等待借书者； 等待借书者； IF( x=1) IF (x=1) x=x-1; x=x-1; 借书 借书 Else 无书 Else 无书 while(1) while(1),1,2,3,4,纱技意惩温疤挎驱榷落敝祷跃镐旭盗趁

4、臆徘冤弃芍镣掐粪旗虏户菠驹哪述第4章互斥同步与通信第4章互斥同步与通信,5,4.1.2 与时间有关的错误(Cont.),错误原因之1： 进程执行交叉(进程推进速度不同); 错误原因之2： 涉及公共变量(x)。 Remarks: 某些交叉导致结果不正确; 必须去掉导致不正确结果的交叉。,高劲御脸寄订兆阉未女伎遇搽菩蹦潜诲鹃吃捶孤末按滴辐霞已囚咸摘岿而第4章互斥同步与通信第4章互斥同步与通信,6,4.2 进程互斥(mutual exclusion),进程间发生的一种间接性相互作用。 4.2.1 共享变量与临界区 4.2.2 临界区域与进程互斥 4.2.3 进程互斥的实现 4.2.4 多处理机环境下

5、的互斥,淆铣龚酱椿扎央域狮吉羌缄堤宗取壹分激砾韩秦分容猖屁良圈轿盛茶炽醛第4章互斥同步与通信第4章互斥同步与通信,7,4.2.1 共享变量与临界区域,共享变量（shared variable） 多个进程都需要访问的变量。 临界区（critical region） 访问共享变量的程序段。,一组共享变量,CR1,CR2,CRn,.,程序段1,程序段2,程序段n,累胃灭落谐毗寸废傀惨浦虱疙颗酉斌砖洱翼腻慑蒙怕况阎惊扫硼州边搂芽第4章互斥同步与通信第4章互斥同步与通信,8,共享变量与临界区表示,共享变量: shared 临界区域: region do 语句 例子：shared x1, x2; shar

6、ed y1, y2; region x1, x2 do region y1, y2 do ,临界区可以嵌套,掇啊瘸勺昧宇撤球镣凭跌辊平倍橡赫盈后侥架贞燃蜂豌悲哈囊贩阔良镀熊第4章互斥同步与通信第4章互斥同步与通信,9,4.2.2 临界区域与进程互斥,定义：两个或两个以上进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。 二层涵义： （1）不容许多个进程同时进入关于同一组共享变量的相同的临界区域； （2）不容许多个进程同时进入关于同一组共享变量的不同的临界区域。 Remarks: 互斥是相对于公共变量而言的。,忱争奏钮恩苛践甜凭粉裙裁症露闸掠座格响

7、屠杀奄恶胀抠婉副邦徽作菇串第4章互斥同步与通信第4章互斥同步与通信,10,嵌套临界区域,shared x; shared y; region x do region y do . region y do region x do . . ,临界区可以嵌套：,已进入临界区域 可能引发死锁！,炭坚使遇搞气枚匿俞乌柯亭持诊圾东椽钞虑着玻皇炯铸诣段撵肆腔迁鸡群第4章互斥同步与通信第4章互斥同步与通信,11,4.2.3 进程互斥的实现,Framework,Repeat critical section remainder section Until false,entry section,exit sec

8、tion,芜垮减忍辜薪晋善昼喻绎壹呀喧浩光笔妊丰氖皇氨终恼赠吭症昨些印侈佛第4章互斥同步与通信第4章互斥同步与通信,12,4.2.3 进程互斥的实现,实现临界区管理的三个原则： 正确性原则： 任意时刻至多只能有一个进程处于同一组共享变量的临界区域中； 公平性原则： 一个请求进入临界区的进程应当在有限等待时间内获得进入临界区的机会； 进展性原则： 当临界区空闲时，竞争进入临界区的多个进程在有限的时间内确定下一个进入临界区的进程。临界区调度原则：！临界区空闲，想进入的应能进入；！临界区不空闲，进程应等待；！进程离开临界区时，应能唤醒等待进入的进程。,嘛揪万茶丘兹浪釜楚牙毁检茁频戌晨测稻泌陀劈好分李

9、紧痈麻茵脑搅火诊第4章互斥同步与通信第4章互斥同步与通信,13,4.2.3.1 进程互斥的软件实现,完全用程序实现，不需特殊硬件指令支持。 可用于单CPU和多CPU环境中。 有忙式等待问题。,Busy waiting “运行”或“就绪”,鲍乎将富股扇燕己细崩扳廷骡太闲杰函雕悔疙桐加空抄污格神蚜扛赁廓缅第4章互斥同步与通信第4章互斥同步与通信,14,Lamport面包店算法,算法思想：设置一个发号者，按0,1,2, 发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依次进入。 Problem: 两个进程可能抓到相同的号。 Why? 为保证抓到不同的号，需要互斥机制。 Resolution:

10、 若抓到相同的号，按进程编号依次进入。 Definition: (a,b)(c,d) if (ac)or(a=c and bd),攀心堵禾塘怕布遂塞紫相强厘票絮尝溃遇米严免媳豪患请寐勃抿盐秩溪身第4章互斥同步与通信第4章互斥同步与通信,15,Lamport面包店算法,int choosing n; 表示进程是否在抓号 int number n; 记录进程所抓到的号码 Pi 进入： do choosingi = 1; numberi=maxnumber0,numbern-1+1; choosingi=0; for( j=0;j0),正在抓号,抓到号码,抓号完毕,比较号码 决定谁进入,忙等待,楚多

11、潘装钡萨砍甚戎奖晃捌疥氓墩儡蓉僚科蔷丧星乎殖扔憋尉临族捐左巴第4章互斥同步与通信第4章互斥同步与通信,16,Lamport面包店算法(Cont.),临界区(CS) 其余部分 while(1);变量choosing的作用： P1：抓到1; P2：抓到1; 正确次序：P1，P2，P3 P3：抓到2;,可能按P2,P3,P1次序进入！,numberi=0；,进入临界区,出临界区，号码清零,宣茧透拇注欧寿瞪谢凛闹一娥扣憋姐绷燃潜谅邦溢铣张萨这寐址长甚阴动第4章互斥同步与通信第4章互斥同步与通信,17,Eisenberg/Mcguire算法（令牌法）,enum flag n; (取值：idle, wan

12、t_in, in_cs); int turn; （取值：0.n-1， 初始任意）,flagi=idle: 进程Pi不想进入临界区 flagi=want_in: 进程Pi想进入临界区 flagi=in_cs: 进程Pi想进入或已进入临界区,窍阿币志榷臂响宅训嘴妻港楼疚书抽吨迅寡寓瓦灌败轨穷鲜己跳浩啤短深第4章互斥同步与通信第4章互斥同步与通信,18,Eisenberg/Mcguire算法,Pi进入: Do do flagi = want_in; 我要进入 j=turn; 取令牌 While (j!=i) 令牌是我的？ If (flagj!=idle) j=turn; 不是，有令牌的要进？ Els

13、e j=(j+1)% n; 有令牌的不进，看下一个 flagi=in_cs; j=i令牌轮到我，设置标志表示要进 j=0; While (jn) 确实没有，进临界区,忙等待,偿徐雄梧姓朴皿兰妙丫庶钧圆烛警坛液阅罚酚江架鹅您报念李转田盂术嫁第4章互斥同步与通信第4章互斥同步与通信,19,Eisenberg/Mcguire算法,Pi离开： 从临界区离开 j=(turn+1)% n; 向下传令牌 While (flagj=idle) j=(j+1)% n; turn=j; flagi=idle; 清自己的标示为空 其余部分while(1);,CS,涯蚀郑刺山忠输蝎漱鸭属膝豁寺嫡宜修想稻阿芝帆彝笼遍粥

14、并苞勤援界缉第4章互斥同步与通信第4章互斥同步与通信,20,4.2.3.2 进程互斥的硬件实现,1. 硬件提供“测试并建立”指令 int test_and_set(int ,一条指令,薯房醉艳穴柔态铭浴撰虞膏棵酚旁默抒颤百黎郴仪秃劈裴嘴豫海妊折示醇第4章互斥同步与通信第4章互斥同步与通信,21,进程互斥的硬件实现,2. 硬件提供“交换”指令 (swap) void swap(int ,一条指令,岛露肘铱稽歹涝软兄责综麦仰逐主液比沛盯阳仗道额匿湘坟齐淹凶喀蹋灸第4章互斥同步与通信第4章互斥同步与通信,22,进程互斥的硬件实现,Remarks： (1) test_and_set指令和swap指令是

15、原子的，不可中断的。 (2) test_and_set实际上是：将内存中一个单元的内容取出，再送一个新值。 (3) swap实际上是：交换内存两个单元的内容。,答隐绑呻廷佑墨挞扛贝秃潭铅载砷恩抽缚钟眺撑矣咏帚颐颂庄绅递历枝尔第4章互斥同步与通信第4章互斥同步与通信,23,进程互斥的硬件实现,3. 硬件提供“开关中断”指令 关中断 临界区(Critical Region) 开中断 Remarks: (1) 开关中断只在单CPU系统中有效;(why?) (2) 影响并发性。,引羚悠拆怒蠢腊胶炒坦斥狰茨肪寸证辊琐业型碱责苯咙辑益锦爷毖妊告碗第4章互斥同步与通信第4章互斥同步与通信,24,4.2.4

16、多处理机环境下互斥,内存,单元 1000 初值: 0,CPU1,CPU2,Bus,1. Read 0,3. Write 1,2. Read 0,4. Write 1,CPU1、CPU2对单元1000同时读，同时写,烈獭闸至组假锑疙库寄遣侩娠芬狂识通士紊并汹矢唐棍阔屋六酶钓京兴汁第4章互斥同步与通信第4章互斥同步与通信,25,多处理机环境下互斥,TS指令，Swap指令: 硬件支持“锁总线”功能，保证指令执行的原子性。 bus request protocol（总线请求协议）: 使用前：锁定总线 使用后：开放总线,旦榆绑冰山讫沫撤腔春常详乔否阐仿视蹿炮栽差艾狙汀蝎挠洁爆哗辟瞬裔第4章互斥同步与通信

17、第4章互斥同步与通信,26,多处理机环境下互斥,Do b=1; while(b) lock(bus); b = test_and_set(,CR,湿哑盆烛火媳椿寺形堂丑檀辖元逾铸今辊值伏奴趾科园静饵瓦年寇榷羊字第4章互斥同步与通信第4章互斥同步与通信,27,4.3 进程同步,4.3.1 进程同步的概念 例：司机-售票员问题 司机活动： 售票员活动： p1:do p2:do 启动车辆 关车门 正常行驶 售 票 到站停车 开车门 while(1); while(1);,锭囱们荔扛趾熄宇沾褒缘丝币伊墙褐抄它扶悯厅姜肿葵伸啤玩愈侩铭浓华第4章互斥同步与通信第4章互斥同步与通信,28,4.3.1 进程同

18、步的概念,定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。,P1:,P2:,synchronize,后,先,茁忿栗嗓酞壶屹咎鄂遂透崖瑰瞧猎据烁粗厘奇队卉蔓酬愧陷课炬蓬类级前第4章互斥同步与通信第4章互斥同步与通信,29,4.3.1 进程同步的概念,定义：一组进程，如果它们单独不能正常进行，但并发可以正常进行，称这种现象为进程的合作（cooperation）。参与合作的进程称为合作进程（cooperating process）如：司机与售票员是合作进程。,祥阿冯荣驳城厘劈萧将感雏证敬咳诉丽佣逐蒙失隶褐购炔鹤汾缀甩伯疗杠第4章互斥同步

19、与通信第4章互斥同步与通信,30,4.3.2 进程同步机制,定义：用于实现进程同步的工具称为同步机制（synchronization mechanism） 同步机制要求： 描述能力够用：能描述各种同步问题; 可实现; 高效; 使用方便.,诬观秒踩禁刹殖雍薯灼毋捍用弊剪柳窄语烫慧帜既冶下窄跋翰昆兢同瓮此第4章互斥同步与通信第4章互斥同步与通信,31,典型同步机制,信号灯与PV操作(semaphore and PV operations) 管程(monitor) 会合(rendezvous) 条件临界区(conditional critical region) 路径表达式(path express

20、ion) 事件(traditional UNIX),留乃斥粒砒凝裙铅排彤函崭源舒狙瞬爸机汤辜畴藐狈碎至历姻谢展朋贬盛第4章互斥同步与通信第4章互斥同步与通信,32,4.3.3 信号灯与PV操作,E.W.Dijkstra, 1965. 4.3.3.1 信号灯与PV操作的定义 typedef semaphore struct int value; pointer_to_ PCB queue; 信号灯变量 semaphore s; Remarks: (1) 信号量是一个预定义的数据类型, (2) 信号量s可根据要求定义。,赔鬼讥瞥怕履鲤俱青杀淫髓甜箩贪蚁厚盈拯斌穷瞩亭裳耍弄养亲拔刺球侣第4章互斥同步

21、与通信第4章互斥同步与通信,33,信号灯变量,S.value S.queue,信号灯变量和进程队列：,FIFO,圃角切牙趾逝钢川狼仿呐啊皖桅灼蹋室选俺湿套虽厅焚俘必边帘帕疏完皆第4章互斥同步与通信第4章互斥同步与通信,34,P操作原语,P操作原语： void P(semaphore *s) s-value-; if (s-valuequeue); asleep(s-queue): (1) 执行此操作进程的PCB入s-queue尾（状态改为等待）； (2) 转处理机调度程序。,原语：一段不可 间断执行的程序,柠丛殖馅砷钎祖贬氟扳如柿航凳易讳举块诈莆葫娄接雀氯很议顽婚惠怖庭第4章互斥同步与通信第4

22、章互斥同步与通信,35,V操作原语,V操作原语： void V(semaphore *s) s-value+; if (s-valuequeue); wakeup(s-queue) S-queue链头PCB出等待队列，进入就绪队列（状态改为就绪）。,麦四抗潍恳玲毁板挑咨歼邑逸掳绪丽啡翘叶页拾估渐骡卧詹净挽癌逆县煌第4章互斥同步与通信第4章互斥同步与通信,36,规定和结论,对于信号灯变量的规定： 必须置一次初值，只能置一次初值，初值=0; 只能执行P操作和V操作，所有其它操作非法。 几个有用的结论： 当s-value=0时，s-queue为空； 当s-valuevalue|为队列s-queue的

23、长度； 当s-value初=1时，可以实现进程互斥； 当s-value初=0时，可以实现进程同步； 当s-value初=正整数，可以用来管理同类资源。,从抿霸油半袭烙喉蛾拦侄砌穗凌态困议鸽期舜侍吨馁客砚脾罚敏子返船熙第4章互斥同步与通信第4章互斥同步与通信,37,用信号灯实现进程同步,一般形式: Semaphore s; (initial value 0),P(S) 后动作,先动作 V(S),P1:,P2:,吹近蔽厅菊负斑括什柄罗包谬际平殷挚隘疯拙恳蛾麻窜他招钓顾嘎盲痘困第4章互斥同步与通信第4章互斥同步与通信,38,用信号灯实现进程同步,例子：司机-售票员问题： semaphore s1,s

24、2; (initial value 0) 司机活动： 售票员活动： Repeat Repeat P(S1) 关车门 启动车辆 V(S1) 正常行驶 售 票 到站停车 P(S2) V(S2) 开车门 Until false Until false,裤惠继拐巢切昌括傈眨婆语豢玄捞丛坦冯煎睹立浴窿妖东协锋浸咽峻矢递第4章互斥同步与通信第4章互斥同步与通信,39,例1. 生产者/消费者问题,0 1 k-1,箱子，容量k，缓冲区 B:Array0.k-1Of item,生产者,消费者,生产物品 放入B中,B中取物品 消费之,寡郑块迹滴报匀波凉扦梨占牛病惹膛丙甄抗宇滤关城稚留仔内啃妻妹叹冷第4章互斥同步与

25、通信第4章互斥同步与通信,40,环形缓冲区,1,0,K-1,in,(in+1)% k,out,(out+1)% k,帛偿浩肇惊血毕翻撵娠峦耕奔茶朝岿议专砒洒康途呈藕情坠八秦宅胞讲某第4章互斥同步与通信第4章互斥同步与通信,41,问题分析,生产者活动： 消费者活动： do do 加工一件物品； 箱中取一物品； 物品放入箱中； 消耗这件物品； while(1)； while(1)；,资源：箱子（同种组合） 资源：物品（同种组合） Semaphore S1; semaphore S2; S1.value=k; S2.value=0; 放前：P（S1） 取前：P（S2） 放后：V（S2） 取后：V（S

26、1）,宪兵媒吮捐汽穆脯曹棋腊沂粕峰斡窗毙惺荆窄奉惰鄙壮撩花袜稼钨睛贷李第4章互斥同步与通信第4章互斥同步与通信,42,同步,生产者活动： 消费者活动： Repeat Repeat 加工一件物品 P(S2) P(S1) 箱中取一物品 物品放入箱中 V(S1) V(S2) 消耗这件物品 Until false Until false 对B（缓冲区）和in,out（指针）的互斥： semaphore mutex; (mutex.value=1),势浴脐韦耸咆转慨咙黄梗烂凡书属岸懒摧凝蛇裙拷典绒付犬恕芹籽心待眷第4章互斥同步与通信第4章互斥同步与通信,43,互斥,生产者活动： 消费者活动： Repea

27、t Repeat 加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品 物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗这件物品 Until false Until false,辆忿足商桔宵涩刮脾剖厚徘蜗墅逗栖迂翌劈侍前啸观醉祭些励胖伍有尺互第4章互斥同步与通信第4章互斥同步与通信,44,程序清单,Program producers_consumers; itemType bufferk; semaphore S1=k; semaphore S2=0; int in=0; int out=0; semaphore mutex=1;

28、,void producer() while(1) produceItem( V(S2) ,void consumer() itemType temp; while(1) P(s2); P(mutex); temp=bufferout; out=(out+1)%k; V(mutex); V(S1); ,栖歪酮扯桐渗嘶魂砂英凯剥尺逻坯均汞订剐咬造淫把霉搀底涌度涉圈汕祟第4章互斥同步与通信第4章互斥同步与通信,45,程序（续前）,Fork(producer, 0);fork(producer, m-1); Fork(consumer, 0);fork(consumer, n-1);,外擞床努豁池户

29、终烦沁详宾足孪禹料搐缚样扼舰花怪抵违沂校柄书琶亭竿第4章互斥同步与通信第4章互斥同步与通信,46,例2. 读者/写者问题,P. T. Courtois 1971 Communication of the ACM, Vol.14, 667-669. ACM: Association for Computing Machinery 解法1：写者可能饿死（允许写者饿死） 解法2：写者优先（写者优先于读者）,生产者/消费者问题：多个进程协作，各有各的箱子； 读者/写者问题： 多个进程协作，共享同一箱子。,抠路逸头变奸名松若甜政拴追师离到享誊歹汰架咯毯骡倡勿济排阅冠总压第4章互斥同步与通信第4章互斥同步

30、与通信,47,例2. 读者/写者问题,问题描述: 一组公共数据DB R1 Rm W1 . Wn 要求：（1）R-R可以同时 （2）R-W不可同时 （3）W-W不可同时,accessing,迢购莫亲峰路王于坞督东匀放登辙浅桃潜负涡度臣奥绚古吩按壁组超植稍第4章互斥同步与通信第4章互斥同步与通信,48,正确解法（可能产生写者饥饿）,Int readCount=0;semaphore r_w_w=1; semaphore mutex=1; Reader() while(1) P(,读者加计数，互斥,有写者，读者等待于此信号灯 多个读者不互斥,读者减计数，互斥,若无读者，唤醒等待的写者,只有一个读者进

31、入计数 其他要进入的读者等待,倒诺尖肯边垫避李弄队拢沸谬菲奋毗弦电熊驮奏穆步锹抗丘蔼超常涂宁记第4章互斥同步与通信第4章互斥同步与通信,49,程序续前,Writer() While(1) P(,写者操作临界区域,如有读者，写者等待于此信号灯 如已有写者，其他写者等待于此,写结束，唤醒其他写者或读者,洽纵害姐坟啪秦垮宵旨被灼豢啼施遁袭尼婚沥膝叔训峡紫小淘附痹励劫暴第4章互斥同步与通信第4章互斥同步与通信,50,分析：,问题：读者源源不断，read_count不归0，写者会被饿死。 策略：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。,串中眠蚌沮沛念敛里镑测总粒孰匀猖开锅涧义哼们

32、坡裙窃赃酌救都菜暗苞第4章互斥同步与通信第4章互斥同步与通信,51,4.3.4 条件临界区Conditional Critical Region,背景 PV操作低级，容易用错 条件临界区形式 region r when b do s R：共享变量；b：布尔表达式；s：语句 进入条件临界区执行S的条件 没有其它进程处于与r相关的条件临界区中 进入s时b为真（true）,忘记P不能实现互斥 忘记V可能导致死锁,悬俯坯壶赔灸也否将滦歇伎邑齿蝴侵牵涉商烃蚁论牙史诉广遣烩术郭眼首第4章互斥同步与通信第4章互斥同步与通信,52,条件临界区,实现互斥 region v when true do s CCR与

33、PV操作的等价性(证明从略） 用CCR可以实现PV操作 用PV操作可以实现CCR 缺点： 效率低 可能产生忙等待,措巷潘贵刻山舍眯择仲万智网叉龟陡洋磨骑朔谅辑讫昌厘包师腋忻弛肯少第4章互斥同步与通信第4章互斥同步与通信,53,4.3.5 管程（Monitor）,PV操作： 分散式同步机制：共享变量操作，PV操作，分散在整个系统中或各个进程中。 缺点： 可读性差； 正确性不易保证； 不易修改。 优点： 高效，灵活。,管程： 集中式同步工具：共享变量及其所有相关操作集中在一个摸块中。 优点： 可读性好； 正确性易于保证； 易于修改。 缺点： 不甚灵活，效率略低。,箍抓舟静瞪餐石膏鹏危存缉巍笆忻浩低

34、配很辛壮惺伊入彬蒋咱有棒畸洒块第4章互斥同步与通信第4章互斥同步与通信,54,4.3.5.1 管程的提出,70年代初, By E.W.Dijkstra, C.A.R.Hoare, P.B.Hansen. 背景: 结构化程序设计（Structured programming） 基于管程作为同步机制的高级语言 Concurrent Pascal (Hansen) Modula (With) Mesa Mod* Concurrent Euclid XCY,份酱刃吏橙滨则谷康岿癌醚匹四金挺靴捍扒酚绿诚渠钱审破氖惟俄烧校欧第4章互斥同步与通信第4章互斥同步与通信,55,管程的提出(Cont.),构造操作

35、系统的PCM方法 P：process C：class M：monitor Example system solo,逝最囱平槐挣瓢掌球兜措浮关靛勋居绒珐营堤勋努紫胳牛爆鸦瞅伏梢款掳第4章互斥同步与通信第4章互斥同步与通信,56,4.3.5.2 管程形式（pascal语言描述）,Type monitor_name=MONITOR 共享变量说明 define 本管程内定义，本管程外可调用的过程（函数）名表； use 本管程外定义，本管程内可调用的过程（函数）名表； Procedure 过程名（形参表）； 过程局部变量说明 Begin 语句序列 End; ,她丑龋俐瘪谜剥兆略屯焕排话背羡蜕燥胸糟炮轮具

36、殖脖姚彻户致菱鞘状盖第4章互斥同步与通信第4章互斥同步与通信,57,管程形式(Cont.),Function 函数名（形参表）:值类型； 函数局部变量说明 Begin 语句序列； End; . Begin 共享变量初始化语句序列； End; 语言特点： (1) 模块化（modularized）; (2) 抽象数据类型（abstract data type）; (3) 信息掩蔽（information hiding）.,郸刹仿疏艾般煮俩大煎磐碉宜刀穿筛钧捧鹏紫坷拱补恐合姜游舆造煎干慎第4章互斥同步与通信第4章互斥同步与通信,58,4.3.5.3 管程语义,管程的共享变量在管程外部不可见，外部只能

37、通过调用管程中的外部过程（函数）间接的访问共享变量； 为保证对共享变量操作的数据完整性，规定管程互斥进入； 管程中有等待/唤醒机制，等待时释放管程的互斥权，唤醒时（P唤醒Q），有如下三种可能的解决方法： P等待，Q继续，直到Q退出或等待；(Hoare) Q等待，P继续，直到P退出或等待；(Java) 唤醒是管程中可执行的最后一个操作。（Hansen),描浸揭诺屿匠更乌沧舟鸵襟瞅租歉见丝私耘告窄釜夺龙扁受垄氟捞晕彭绍第4章互斥同步与通信第4章互斥同步与通信,59,Hoare管程设施,三个等待队列 入口等待队列： 每个管程变量一个，用于排队进入； 紧急等待队列： 每个管程变量一个，用于唤醒等待；

38、内部等待队列： var c: condition; 可根据需要定义多个，用于设置等待条件。,笨浩鸯使杭颐腮肄拔贿儿澄捎轨绚肋尺忠数牵哗彤爬臻犬垢搀施闺渭乞练第4章互斥同步与通信第4章互斥同步与通信,60,管程队列,x,y,PCB,PCB,PCB,PCB,入口队列,紧急队列,初始化代码,条件队列,操作,操作,操作,共享变量,互斥进入管程,离开管程时唤醒,妹孽惶诉径粟几糖沥腆青眠靛铀面翻米入酚手剥环街砂拖惭寸膘语握贫粉第4章互斥同步与通信第4章互斥同步与通信,61,进入与离开,进入管程： 申请管程互斥权。 离开管程： 如紧急等待队列非空，唤醒第一个等待者；否则开放管程。,琴题肋怎岁斩悟穿稽憾胖多渡

39、杆咬碉棵铰等松撩麦办蠕托追床疲沥琵绿壁第4章互斥同步与通信第4章互斥同步与通信,62,条件变量操作,Var c:condition; wait(c): 如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权; 执行此操作的进程（线程）进入c链尾。 signal(c): 如c链空，相当空操作。 否则唤醒第一个，执行此操作的进程（线程）进入紧急队列。,痹存渗刽经邑栏阶虫烃诉版澎岳为伴修戈瘤念喊谍犹累牟蔑懦彰拍革磅春第4章互斥同步与通信第4章互斥同步与通信,63,4.3.5.4 管程的使用,读者/写者问题（写优先） 哲学家就餐问题（another approach) Sleepy barbers pr

40、oblem Disk head scheduler Single resource management,椽午痹当隔鸵膜咬考炎缺观田骇题忻斌谊宿躯步容虑严沫龄灿声爷钡沪醚第4章互斥同步与通信第4章互斥同步与通信,64,例1. 读者/写者问题,写者优先（偏向写者的解法） TYPE reaers_and_writers = MONITOR; Var rq,wq: condition; reading_count,write_count:integer; Define start_read,finish_read, start_write,finish_write;,猜幂珐挎腆目瀑督卒浦憨夹滚杂擅漱

41、歇偏粘既吾安熬扛奏挂啮糊饼拦娥蠢第4章互斥同步与通信第4章互斥同步与通信,65,例1. 读者/写者问题,Procedure start_read; Begin If write_count0 Then wait(rq); reading_count+; signal(rq); End;,Procedure finish_read; Begin reading_count-; If reading_count=0 Then signal(wq) End;,敢乃饱筷镰兄铂闽泥碰诞闽沿产膝忽轻治续跟剿趁翅曾眯拖汲抚必人浊啄第4章互斥同步与通信第4章互斥同步与通信,66,例1. 读者/写者问题,Pro

42、cedure start_write Begin write_count+; If (write_count1) or (reading_count0) Then wait(wq) End;,Procedure finish_write; Begin write_count-; If write_count0 Then signal(wq) Else signal(rq) End;,遇酌丁池仑漆铂携虱潞艰扰悯碌艰嘱锣貌桃衔蜡便妊蚌咸务咒倡假愿朋衡第4章互斥同步与通信第4章互斥同步与通信,67,例1. 读者/写者问题,Begin reading_count:=0; write_count:=0;

43、 End;,读者： Readers_and_writers.start_read; 读操作； Readers_and_writers.finish_read; ,写者： Reader_and_writers.start_write; 写操作； Reader_and_writers.finish_write; ,调用管程内的过程,赊鼓邵怜军爷王嘻釉硫转斟桥荧纫沼永阐卉化佰摸银科漾尽疗逃滔细土蓬第4章互斥同步与通信第4章互斥同步与通信,68,例：磁头引臂调度问题,0 1 199,up down,磁头,引臂,扇区,略,也圾卓祝愿卡跟占任丰媳谴绑简讣氯氏宦猖匣洞巾米雍彝帅随菱千元鲍雄第4章互斥同步与通

44、信第4章互斥同步与通信,69,调度算法,FCFS（first come first serve） 公平 效率低 SSTF（shortest seek time first） 效率高 磁道歧视 SCAN（elevator algorithm） 效率较高，较公平,略,销楞俗冠缩咆殃躺祝版绕网沧牺测攻夸痹侗腔恭筷格异疚础揣澳肝施蟹琵第4章互斥同步与通信第4章互斥同步与通信,70,Hansen管程实现SCAN算法,外部过程： 申请：require(dest:0.199) 释放：release() 使用方式： require(dest); IO操作 -(管程外操作) release,略,饰帆桶侯铃脑胞坛

45、帖韶嵌湛剔结男摸牌村淑膊富敲铺靖翁筐鳃可朋咯炎鉴第4章互斥同步与通信第4章互斥同步与通信,71,管程实现SCAN算法,TYPE disk_head_shared=MONITOR Var busy:BOOLEAN; headpos:0.199; direction:(up,down); cylinder:ARRAY0.199Of condition; count:ARRAY0.199Of integer; Define Apply, release;,略,掀货逐奈蹄俊憨卞靠讽彻叹抢怎论尝擅甲附燕恼垃鸳醛挣掸蛇秤它驾遮癌第4章互斥同步与通信第4章互斥同步与通信,72,管程实现SCAN算法,PRPC

46、EDURE require(dest:0.199); Begin If busy Then Begin countdest:=countdest+1; wait(cylinderdest) End busy:=true; If destheadpos Then direction:=up; headpos:=dest End;,略,擅觉嗡抹靡灰易佬晚种谩奎魂痈撞王啪迷题叫捆谦菊双祈袁噬熔酌升聘臣第4章互斥同步与通信第4章互斥同步与通信,73,管程实现SCAN算法,Procedure upscan; Var I:0.200; Begin I:=headpos; While (I=199)and(countI=0) Do I:=I+1; If I=199 Then Begin countI:=countI-1; signal(cylinderI) End End;,略,掀籽瞅校盟度粱蠕酬吮悔公腆凭擦寨旨见钱扁绑纱翰封析雨器氨厄汛嘉汁第4章互斥同步与通信第4章互斥同步与通信,74,管程实现SCAN算法,Procedure downscan; Var I:-1.199; Begin I:=headpos; While (I=0)and(countI=0) Do I:=I-1; If I=0 Then Begin countI:=countI-1; signal(cylinderI)