研究生课程_程序语言设计原理教程_第14章.ppt

第14章进程交互机制和并发程序设计语言,如果说忙等待是人们设计、实现并发程序的最初尝试。信号灯理论则为进程交互的同步与互斥的研究打下了基础。70年代结构化程序设计已经比较成熟，人们利用结构程序的概念为并发机制提供较高层的机制，并设计了一系列并发程序设计语言。基于变量共享的并发机制提出了条件临界区、监控器、路径表达式等技术。70年代末把结构化与通信相结合提出了远程过程调用和会合机制。80年代又有多原语范型的机制出现。,14.1基于变量共享的高层并发机制条件临界区条件临界区(ConditionCritiealRegion简称CCR)将共享变量显式地置于叫做资源的区域内每个进程在自己的进程体内指明要访问的条件临界区，而同一临界区可出现在不同进程之中(谁进谁用)首先在资源中声明共享变量:resourcer(共享变量声明)例：resourcesema(s:int:=n)regionrwhenBdoSendregionsemawhens0dos:=s-1end/P操作regionsemados:=s+1end/V操作,例:用CCR实现例12-4的生产者与消费者pragramPRODUCER_CONSUMER_CCRvarbuf:TYPE;varempty:sema,full:sema;resourcesema:(empty:=1,full:=0);processPRODUCERi:1.M:loopPRODUCERi产生一条消息m;deposit:regionsemawhenempty0doempty:=empty-1end；buf:=m;regionsemadofull:=full+1end;endloop;end;processCONSUMERj:1.N:loopfetch:regionsemawhenfull0dofull:=full-1end;m=buf；regionsemadoempty:=empty+1end;CONSUMERj消费者取出的这条消息m;endloop;end;endPRODUCER_CONSUMER_CCR.,条件临界区评价条件临界区最主要的优点是概念清晰。此外:无需辅助标志和变量即可描述共享变量的任何进程交互程序编译时即可保证互斥一个进程创建一个条件不需顾及其它条件是否与此条件有关易于程序正确性证明体现了共享数据传递的方便它的致命缺点是低效(和信号灯相比)。此外：进程和共享变量耦合太紧临界区利写不利读，一多了就太散，因而也难修改,监控器Dijkstra建议是把分散在整个程序中的region语句进一步集中成为一个模块叫做监控器(monitor)。programmonitormonitorMname:共享数据声明并初始化;procop1()isend;.procopn()isend;end;processPnamei:1.N:局部数据声明并初始化begin:callMname.opi(实参表);:endbegin初始化，激活进程endmonitor.,例:有界缓冲区的监控器实现算法monitorBOUNDED_BUFFER:varbuf1.q：TYPE;varfrout:=1，rear:=1，count:=0;varnot_fall:cond；/当count0示信为真procdeposit(data:TYPE)iswhilecount=qdowait(not_full)end;bufrear:=data;rear:=(rearmodq)+1;count:=count+1;signal(not_empty);end;procfetch(varresult:TYPE)iswhilecount=0dowait(not_empty)end;result:=buffront;front:=(frontmodq)+1;count:=count-1;signal(not_full);end;endBOUNDED_BUFFER.,以监控器实现条件同步的技术(1)复盖条件变量(2)传递条件(3)有无占先对竞争的并发进程影响是很大的,由于不占先在被唤醒进程执行之前,监控器不能拒绝另一进程进入它.(见下例*)(4)为了防止条件信号被偷，发信号的进程直接将条件传入被唤醒的进程。(见下例*)(5)会合同步进程交互是客户/服务器(C/S)关系时,为此两交互进程必须会合(rendezvou)才能得到服务。如不能到达会合的同步点则要相互等待。（见下例*）,例*以监控器作信号灯monitorSEMAPHORE:vars:=0;varpos:cond;/当s0，pos示信为真procP()iswhiles=0dowait(pos)end;s:=s-1;end;procV()iss:=s+1；signal(pos);end;endSEMAPHORE.,例*：以监控器实现的FIFO信号灯monitorSEMAPHORE:vars=0;varpos:cond；/当V中pos队列非空示真procP()isifs0thens:=s-1endif;ifs=0thenwait(pos)endif;end;procV()isifempty(pos)thens:=s+1endif;ifnotempty(pos)thensignal(pos)endif;end;endSEMAPHORE.注:本例中“”号表示和前一个语句并行执行的语句,以下同.,例*贪睡的理发师的模拟解monitorBARBER_SHOP:varbarber:=0,chair:=0,open=0;varbarber_available:cond/当barber0示真varchair_occupied:cond/当chair0示真varchoor_open:cond/当open=0示真procget_haircut()is/顾客调用whilebarber=0dowait(barber_available)end;barber:=barber-1;chair:=chair+1；signal(chair_occupied);whileopen=0dowait(door_open)end;open:=open-1；signal(customer_left);end;procget_next_customer()isprocfinished_cut()isendBARBER_SHOP.,见下一页,procget_next_customer()is/理发师调用barber:=barber+1；signal(barber_available);whilechair=0dowait(chair_occupied)end;chair:=chair-1;end;procfinished_cut()is/理发师调用open:=open+1；signal(door_open);whileopen0dowait(customer_left)end;end;,各种语言实现监控器时的原语语义差异监控器有三个特征：第一，监控器封装了共享变量，共享变量仅能由监控器内的过程访问。第二，监控器内的过程都是互斥地执行的。因而共享变量不能并发访问。第三，条件同步由wait和signal操作实现程序设计语言Mesa包括以上三个特征。UNIX采用上述条件同步。监控器有时不一定必须互斥。也可以采用其它办法实现条件同步,(1)实现条件同步的各种信号机制自动信号AS:只要wait加上条件就可以不用signal原语了.即省去检查signal是否执行的开销,程序员也不必操心是否用错信号和继续SC:当无占先时发信号的进程继续执行.直至它进入等待或返回之前,其它进程是不许进入监控器的信号和出口SX:既然被占了先,发信号的进程也就不等了.立即从监控器出口或从过程返回信号和等待SW:发信号的进程被人占先之后处于监控器内等待，直到它能再次获得互斥访问，恢复执行信号和急等SU:发信号进程被人占先之后也要等待，但保证在监控器有新的进程进入之前先使它得到恢复,(2)嵌套监控器中的互斥在磁盘调度器之类的应用中，一个进程首先要争取进入磁盘去寻址，找到地址后读/写，这样就要设计两个监控器一个管理粗的磁盘资源，进程进入或释放。另一个管理读/写区，进程互斥地读写。这两个监控器是嵌套的每一时刻只有一个进程进入监控器，调用某个过程，我们称它是闭式调用.在嵌套监控器之中，这种方式容易引起死锁。开式调用是若有嵌套调用发生时上层互斥自动解开，待调用返回后上层监控器又重新闭合(获得)互斥,路径表达式1974年Campbell和Habermann提出以路径表达式直接控制进程顺序的建议路径表达式是就每一资源在其开始声明时,就在其上定义操作的约束。pathdeposit,fetchend/deposit和fetch并发执行pathdeposit;fetchend/deposit必须先于fetch执行path1:（deposit；fetch)end/只能有一条路径(但可多次执行此路径),两操作交替互斥执行.pathN:(1:(deposit)；1:(fetch)end/deposit和fetch是一一对应地互斥激活,先执行deposit,完成的deposit个数不超过N次,且可多于fetch完成的个数.由路径表达式指明的同步约束,编译时即可保证.优点是程序员可直接控制过程的执行,正文清晰。但当同步化依赖过程参数或监控器的状态时，表达能力差。,14.2基于消息传递的高层并发机制,14.2.1异步消息传递chan(:，,：)其中:为传到信道上的数据域名(可缺省)和类型。例如:chaninput(char);chandisk_access(cylinder，block，count：int,buffer：char*);charoutput1.N(1.M：char);,异步通信的过滤器chaninput(char)，output(1.MAXLINE:char);char_to_Line:varline1.MAXLINE:char，i:int:=1;loopreceiveinput(linei);whilelinei=CRandiifavail0then/正常分配avail:=avail-1;unitid:=remove(units);sendreplyindex(unitid)；endif;ifavail=0then/记住index号客户未分insert(pending，index)/插入阻塞队pendingendif;接下一张,casekind=RELEASE=ifempty(pending)thenavail:=avail+1;insert(units，unitid);endif;ifnotempty(pending)then/分配unitid号资源index:=remove(pending);sendreplyindex(unitid);endif;endcase;endloop;clienti:1.N:varunitid:int;sendrequest(i，ACQUIRE，0);receivereplyi(unitid);/使用unitid号资源然后释放它，发以下消息:sendrelease(i，RELEASE，unitid);客户/服务器进程的特点是send，receive是对等的，服务器要应答消息。本算法有N个客户一个服务器。用其它主控程序创建clienti，当它发送request后，接着执行replyi，如发现未分配(未应答)则在本处等待，直至确已分配unitid/=0再使用它。,14.2.2同步消息传递通信着的顺序进程CSP(1)通信语句,A:.B!e./B!e是输出语句，目标是BB:.A?x./A?x是输入语句，源自A进程!信道名()?信道名(),我们把求最大公约数做成一服务器进程GCD。客户进程client每向它发送一对整数，它求出结果发回客户。GCD:varx，y:int;loopclient?args(x，y)whilex/=ydoifxythenx:=x-yendififyxtheny:=y-xendif;end;client!result(x);endloop;client进程在准备好数据v1,v2和结果存储空间r之后，应有以下语句:.GCD!args(v1，v2);GCD?result(r).其中args，result是信道端口名。,(2)选择通信Dijkstra1975年提出的(警)卫式命令。即设一布尔条件B，仅当B为真才执行消息传递语句。所以，也叫卫式通信。卫式通信语句的一般形式是:B；CS;选择通信语句一般形式是:ifG1S1G2S2.GnSnendif,GCD:varx，y：int;while(i:1.N)clienti?args(x，y)dowhilex/=ydoifxythenx:=x-yendififxytheny:=y-xendif;end;client!result(x);end;,过滤器的同步实现sreve1:varp:=2，i:int;print(p)；sieve2!p;fori:=3toNby2do/发送候选奇数sieve2!iend.srevej：2.L:varp:int，next:int;sievej-1?p；print(p)；/只打印“第一个”收到的loopsievej-1?next;ifnextmodp/=0thensievei+1!nextendif;endloop;,客户/服务器的同步通信实现文件服务器的同步实现算法File_Serveri:1.N:varfname:string，args:TYPE;varmore:bool;var局部缓冲区，快速缓存，磁盘地址等;while(c:1.M)clientc?open(fname)do/如名为fname的文件已打开:client!open_reply();more:=true;whilemore=truedoifclientc?read(args)then调处理读入数据的过程;clientc!read_reply(results);ifclientc?write(args)then调处理写的过程;clientc!write_reply(results);ifclientc?close()then调关闭文件操作;more:=falseendif;end;end.,clientj:1.M:varserverid：int;while(i:1.N)File_Serveri!open(“foo”)doserverid:=i;File_serveri?open_reply(serverid);end./以下写使用该进程的代码。例如，读可写:File_Serverserverid!read(访问参数);File_Serverserverid?read_reply(results);./最后要有关闭文件的消息,同步通信的底层实现,应用程序,分布式并发核示意图,应用程序,原语例程,描述子缓冲区,网络接口,本地核,描述子缓冲区,原语例程,网络接口,本地核,同步通信在最基本的操作上和异步是一样的。当前实现同步有两种策略:(1)集中式的同步实现,CH,Pi,Pj,集中管理，它易于检查进程匹配情况。然而，在分布式系统中，这样多次来回通信增加了系统通信开销，往往成为并行核的瓶颈。,分散式同步实现,用异步通信原语实现分散式同步通信，为每个要求通信的进程设立一个匹配信道(输出语句为一端，输入语句为另一端)和一个应答信道。并于有输入语句的进程设阻塞等候队列.如果输出/入语句不出现在警卫子句内处理程序要简单得多，输出语句出现在警卫子句中情况会变得更复杂。因此CSP和Occam的最初版本均不允许在警卫子句中有输出语句,14.3远程过程调用和会合,调用进调,服服务进程从创建到完成,callRPC,调用进程,调用进调,进入同步点in,等待,数据通信完成,call,会合,(等待）,RPC,会合,14.3.1远程过程调用RPC,callMname.opname(AP_list);,每个模块在各自的地址空间。每当有远程调用时，服务模块创建一服务进程，调用进程一直延迟到整个服务完成。如果同一时间只允许一个远程调用进入本模块，就实现了对共享数据的互斥访问。多个调用者们就要排队等待。,现在的问题是块内各操作进程在有了远程调用之后如何同步与互斥。一个办法最简单；块内同一时间只能有一个进程执行(不管是局部调用还是远程的一起排队)。这样最安全，隐含地实现了互斥，共享变量无需保护。但不可取，丧失了大量潜在的并发性。现在多数RPC实现是支持模块内并发执行的。其实现模块可以如前所述的异步、同步、卫式同步模式。远程调用只是其并发成分之一。我们举例说明。,14.3.2会合,callMname.Pname.Opi(ARG_list),RPC是进程级的(一个过程一个进程)，且允许有多个并发进程进入封装这些操作的模块。会合是操作级的(一个进程有若干个操作)，调用的是进程输出的操作，因而，操作不能是并行的，只能同时有一个操作在执行。而每个操作都有自己的等候队列。正是由于定义输出操作，带来了卫式通信的方便性。会合的一般形式是:,inOp1andB1bye1s1.OpnandBnbyensnendin,callOp1andB1bye1.OpnandBnbyenendcall,会合实现过滤器,Baffer:opdeposit(data:TYPE)，fetch(varresult:TYPE);varbuf1.q:TYPEvarfront:=1，rear:=1，count!=0;loopindeposit(data)andcount0doresult:=buffront;front:=frontmodn+1;count:=count-1end;endloop.,有界缓冲区buf1.q是本地机上的共享变量。front，rear，count为控制和警卫变量,14.3.3Ada的任务,Ada的任务结构,taskTNAMEisentryENAME(FP_list)；/可以多个endTNAME；taskbodyTNAMEis局部声明；beginacceptENAME(FP_list)is/对应多个语句序列;endENAME;endTNAME;任务激活后就是一个进程。其它进程通过callTNAME.ENAME(AP_list);,Ada的通信与同步,（1）简单选择(2)否则选择(3)卫式选择（4）延时选择,14.4多原语的并发机制,进程交互主要技术的回顾,忙等待,信号灯,条件临界区,监控器,同步消息传递,异步消息传递,远程过程调用/会合,路径表达式,多原语交互,面向过程,面向消息,面向操作,多原语并发程序表示法moduleMname可见Op(操作)声明;/输出操作b