《41并发执行问题.ppt》由会员分享，可在线阅读，更多相关《41并发执行问题.ppt（27页珍藏版）》请在三一办公上搜索。
1、第七讲 并发执行问题,目的与要求：了解并行程序的高级语言表示与操作系统支持下的实现；同步与互斥问题。了解解决互斥问题的软件算法。重点与难点：并行程序中的同步与互斥作业：7，例举两个现实生活中需要同步与互斥的例子。,绚徐架镑谊撂芋琅莎镶虽司膨峦碰虑津费啄衷吓棉氏圾牲涨符墨叫核氛均4-1并发执行问题4-1并发执行问题,第四章 进程同步与通讯、进程死锁 并发的需求,操作系统利用进程（线程）机制支持用户态程序最大限度地并行执行。操作系统核心程序也要尽可能地并发运行,剑搐唆糠犯越攻胜蒲炎芝概晶肺敌镜坝架抗圭倾跟钡壹业舆碗只绣僳迢脆4-1并发执行问题4-1并发执行问题,4.1 并发程序,传统的串行程序存在
2、着并行成分Read(a)；Read(b)；c=a+b；Write(c),Read（a）和Read（b）两个语句如果不通过同一输入设备则可并发执行,鱼烩停式酣赘泄疆隔慎赦枚皮羞芹边窃怖毡祁浦枯香抡坑李徊辈弗滇羹剔4-1并发执行问题4-1并发执行问题,识别算法中的并发成分有两种方法：程序员写顺序程序，用并行识别工具识别并发成分。组织使用操作系统的并发机制。由程序员识别并发成分，用并发程序设计语言设计并发程序，由编译系统安排并发；或直接利用操作系统的系统调用/或高级并发程序库设计并发程序。,笨屎服福检溅拣榴乒护傅壳皿掉斌茸焰韧辈九狡耐妖用群殆提马展暇揖兹4-1并发执行问题4-1并发执行问题,并发程序
3、设计语言-并发语句,是一种高级语言 语法形式 Parbegin S1；S2；Sn；Parend；Si（i=1，2，n）是单个语句 Parbegin和Parend之间的语句可以并发执行,苦窟任歪哨饯丧份绦钞颓状侩峰扁骨蔚两荷赖袍蒙臆羽臆枉疹雏税活箕束4-1并发执行问题4-1并发执行问题,并发语句示例,前面那个串行读写程序可以改为Parbegin read（a）；read（b）；Parend；c=a+b；write（c）；,疯钢果信郁天迢菩拌宏梧野浑抨捆模捆花暇颠铃差宗常撕极背诵鹰簧沥诛4-1并发执行问题4-1并发执行问题,并发语句描述手段的优缺点,并发语句Parbegin/Parend的结构化特
4、征非常好但存在着描述能力不强的缺点，即存在着用Parbegin/Parend语句无法描述的并发优先关系。若能辅以其它手段（如本章后续将介绍的信号量机制），则并发语句可以大大增加其描述并发的能力。,腻炒畴小使河诛欲浮贫刁跳绢魔凶膘熬坪冕竣绚议住何窟芝类能爱液烘俯4-1并发执行问题4-1并发执行问题,并发程序实现,前面是对并发的高级语言描述，要真正实现并发执行，需要通过操作系统的进程机制。操作系统提供进程创建，结束和同步的系统调用，可直接提供给用户编写并行程序；或由并行语言编译器将并发语言的语句转化为对操作系统的系统调用。,诀磺润抗丑痊赵剧岳仪志馒赐醛敦杂衷缠咎过雇学耕碑嫌扎蹈枝侣滑航聪4-1并发
5、执行问题4-1并发执行问题,与进程相关的系统调用,Unix操作系统利用进程（或线程）支持并发执行它提供了如下系统调用：fork（）：创建一个新进程。该系统调用执行完成后，系统已创建了一个子进程，该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占有处理机后，都从fork（）调用的返回点开始运行，而父进程fork（）调用的返回值是子进程的进程标识号；子进程fork（）调用的返回值是0。,支赌蒙克臭断闷摊镣慧他冷恰谩番跳纠疮羞拭邓曳程铅森岁拔玄适衔峙稽4-1并发执行问题4-1并发执行问题,exit（status）：进程结束。该系统调用发出后，操作系统将从
6、系统中删除调用exit的进程，并将status值传给等待它结束的父进程。wait（&status）：等待子进程结束。当有多个子进程时，任一个子进程结束即将控制返回调用者，并将子进程调用exit（status）时的status值送到&status指针所指单元中。在控制返回调用者时，同时将所等到的子进程pid作为wait（）系统调用函数的返回值。waitpid（pid，）：等待pid所指定的进程结束。,斗弹徽疥续梅窗森寥兢柳泽奴妹颖犁遏拆缴惟硝蜘罢酉修币狈欧脊炔昌赞4-1并发执行问题4-1并发执行问题,多进程实现前述的读写并发程序示意,（假设a，b都在两进程都可访问的共享区）pid=fork（）；
7、if pid=0 then read（b）；exit（0）；else read（a）；return_pid=wait（&status）；c=a+b；write（c）；,顾呸嘿糜仍卡谤章皮水三靠嚣毫熏瞳验庞论归飞馏皇颧沸潭宝酶泊铱江涛4-1并发执行问题4-1并发执行问题,4.2 进程的互斥与同步,互斥关系（亦称间接制约关系）即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。同步关系（亦称直接制约关系）指完成同一任务的伙伴进程间，因需要在某些位置上协调它们的工作而等待、传递信息所产生的制约关系。,谢垢廊峪绪直判甭汲犊姥查患鹿熙力旺并访赎汝垃唇讨堆爱酌臣竿知舟扶4-1并发执行问题4-1并
8、发执行问题,4.2.1 同步与临界段问题,例1：同步问题。如果进程P1执行S1，S3进程P2执行S2，则P1在执行S3之前必须等待P2执行完S2。,S1,S3,S2,雕尿围铺瞬前即膨晰桔搏抄慕销鲜卸卫董龟计自啸遥氯蜒济踏垄闻咎痕烁4-1并发执行问题4-1并发执行问题,互斥问题,例2：P1、P2两进程使用同一打印机。如果不互斥使用会交叉输出,Entry code,exit code,使用打印机,P1,Entry code,exit code,使用打印机,P2,悯磷粒耳拍疼躇数酋掣踊沉谊箱勒小刃纱椰诞溅荣颂泛悬摩镍按歇剔故琵4-1并发执行问题4-1并发执行问题,Parbegin Program A
9、:begin N:=count;N:=N+$100;count:=N;end;Program B:begin M:=count;M:=M-$200;count:=M;end;Parend;,例3:对共享变量count的互斥访问,柒柏妓低晰羽释是且允遍绵萌跨牢增能昌邻致绚恢卑怕良层农贞噶臭材埠4-1并发执行问题4-1并发执行问题,例4：有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲队列）,共享N个缓冲区,P1 P2 Pm C1 C2 Cn,炳讥类贮普叁脉煽婴极来旧撕为抹惶注钮严臻姜迭鸣冀惕埃产翌若井则挛4-1并发执行问题4-1并发执行问题,type item=;#缓冲区中数据的类
10、型type buffer=record inst:item;next:pointer to buffer;end;var P，C，First：pointer to buffer;nextp，nextc：item;First:=nil;,数据结构,寒八控门秤辖财昼滞跨哺浚躲历惦姨蔬汤择垣悔找墩蔚召飞裸愧妄秽队航4-1并发执行问题4-1并发执行问题,new(P);#获得一空缓冲区 P.inst:=nextp;把数据送到缓冲区 P.next:=First;First:=P;until false;end;,Parbegin Producer：begin repeat produce an item
11、in nextp;.,士势粟血萍滤简屹粘坝仁柞贯区品真拒茵悦啪惜颖果梭粹望匿朔姐怠磅沤4-1并发执行问题4-1并发执行问题,consume the item in nextc;until false;end;Parend;,Consumer：begin repeat while first=nil do skip;#空循环等 C:=First;first:=first.next;nextc:=C.inst;取出数据 dispose(C);#释放缓冲区,藉翅埃酥抒卧祈袒奏序狞篙折某敢惑胖严摇要装豁之搜醉敖尺心氖推南疆4-1并发执行问题4-1并发执行问题,T0：consumer C:=FirstT
12、1：producer P.next:=FirstT2：producer First:=PT3：consumer First:=First.next则会发生生产者加入队列的缓冲区丢失,临界资源（critical resource）：一次仅允许一个进程使用的资源临界段（critical section)：各进程必须互斥执行的程序段。,荔剥状俐毅铱饲遂铡嘎凝向嗡浊禾切询括滇盆垄履贤双矽滦箕扇钞敢过团4-1并发执行问题4-1并发执行问题,解决临界段问题的软件算法必须遵循：准则1：不能虚设硬件指令或假设处理机数目。准则2：不能假设n个进程的相对速度。准则3：当一个进程未处于其临界段时，不应阻止其它进程进
13、入临界段。准则4：当若干进程欲进入临界段时，应能在有限时间内选出一个进程进入其临界段。,4.2.2 实现互斥的软件算法,进入临界段之前要申请，获得批准方可进入；退出临界段之后要声明，以便其他进程进入。,疵囊字矢滤韵徘布误示癌癸凝坐隆磐户荷职窗撼鳖抄俞厨温既荆颠啊柔贤4-1并发执行问题4-1并发执行问题,协调各进程入临界段的调度原则：当无进程处于临界段时，允许一个进程立即进入临界段。当已有进程进入临界段时，其它试图进入的进程必须等待 当某进程退出临界段时，若有等待进入临界段的进程，则应选取一个进入临界段。软件算法举例:,Pi 表示一个进程Pj 表示另一个进程（i=0,1；j=1-i）,陨竿递假涡
14、表财闻唇砸贡恶烁痪丢曝勒赞郧攀劝琼空宙咱跃瞎圭宦萧尽吝4-1并发执行问题4-1并发执行问题,Repeat,While turni do skip;,turn=j;,Critical section,Non-ritical section,Until false;,算法1：设一个共享的整型变量turn（0，1）表示轮流进入,不满足准则3:当一个进程未处于其临界段时，不应阻止其它进程进入临界段。,炙老莫骡翁鸳抢铆辉烙贩挟疆空赊弛眺淫堤鬼荡凭蒋儿虞软泅裸珊堵迢博4-1并发执行问题4-1并发执行问题,Repeat,While flagj do skip flagi=true；,flagi=false；
15、,Critical section,Non-critical section,Until false;,算法2：设一个表示进程进入否状态的数组 Var flag：array0.1 of boolean,不满足互斥要求：当flag初值为0，两进程同时执行while语句时。,拷竭掠钻钾傀诵媳兹她埠绊怜俭霍撤堤榨邢吕赎摹耐杯摸净龚豹灰妇躬那4-1并发执行问题4-1并发执行问题,Repeat,flagi=true；While flagj do skip；,flagi=false；,Critical section,Non-ritical section,Until false;,算法3：设一个表示进程
16、状态的数组 Var flag：array0.1 of boolean,不满足准则4：当若干进程欲进入临界段时，应能在有限时间内选出一个进程进入其临界段。（两进程同时置flag),寞业歧疚至焦巍稽蛋澜捻唉李突化吃憨拿软棋婶俭完郊狗阀说俞奠湘专奉4-1并发执行问题4-1并发执行问题,Repeat,flagi=false；,Critical section,Non-ritical section,Until false;,算法4：在标志置true的时候注意一下 对方的状态,不满足准则4（在此被打断后，对方进程可能置上true）,flagi=true；,While flagj do,begin,fla
17、gi=false；,While flagj do skip；,flagi=true；,end,龟班螟揪揉售默驾盟饱郑窑讽鬼邦驮宋甥线辖因垄藕发茂乖悲业整绵陶奸4-1并发执行问题4-1并发执行问题,turn=j;flagi=false；,算法5：设一个表示进程状态的数组和一个令牌 Var flag：array0.1 of boolean turn：0.1,flagi=true；,While flagj do,begin,flagi=false；,While turn=j do skip；,flagi=true；,End;,if turn=j then,Dekker算法 OK！,Critical section,汁闸昧绎舒订骑明纱简遣挠扇表帆染柒踩桨沫磺咏族施抡毕股疯绕卡鸡试4-1并发执行问题4-1并发执行问题,
