第2章-分布式程序设计语言课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,分布式系统(二)08-03,*,第2章 分布式程序设计语言,2008.3,分布式程序设计语言,为什么需要分布式程序设计语言？,传统顺序程序设计语言（如：Fortran、Pascal或C等）不能解决诸如并发、通信、同步和可靠性等分布式环境下需要解决的问题，因此不适合于分布式系统。,并行程序设计语言不一定能在分布式系统中使用，因为它没有考虑通信开销。,分布式程序设计语言较传统顺序程序设计语言更注重（显式）表达如下3个方面的需求：,多个PE的使用；（并发）,PE之间的合作；（通信和同步）,对局部故障的生存能力。（故障弱化）,分布式系统(二)08-03,2,分布式程序设计语言,分布式控制描述语言（DCDL）,本章主要介绍一种称为分布式控制描述语言的DCDL，它是一种框架控制驱动的描述语言。,DCDL可用于描述一些控制结构，如：并行的表示、进程间通信和同步、容错设计等。,DCDL表示的控制算法是在抽象层上提出的，可以应用于操作系统层、语言运行时（run-time）系统层或用户层。,DCDL有形式定义,（书中附录给出了DCDL常用的语法符号列表）,，我们主要通过一些实例来阐述它的语义结构。,分布式系统(二)08-03,3,分布式程序设计语言,优先图,（precedence graph）,优先图是一个有向无环图（DAG,Directed Acyclic Graph），即不带环路的有向图。,节点代表语句（可以为空），有向边代表优先关系。如：,S,1,S,2,S,4,S,3,S,5,分布式系统(二)08-03,5,分布式程序设计语言,优先顺序是可传递的（transitive）。即：,若 ，则 。,但优先图中不允许存在冗余的连接，如上页图中，若有 ，就是冗余连接。,（冗余连接的优先顺序可以从其它优先顺序导出）,不存在冗余连接的优先图是保持所有优先关系的最简化的优先图！,即：一个优先顺序集合R是非冗余的当且仅当不存在R的子集使得它们有相同的传递闭包。,S,1,S,2,S,3,S,1,S,3,S,1,S,3,分布式系统(二)08-03,6,分布式程序设计语言,顺序语句,（Sequence Statement）,顺序执行的语句：S,1,、S,2,、S,n,优先图：,DCDL表示：S,1,;S,2,;S,n,S,1,S,2,S,n,.,.,分布式系统(二)08-03,7,分布式程序设计语言,并行语句,（Parallel Statement）,并行执行的语句：S,1,、S,2,、S,n,优先图：,DCDL表示：S,1,|S,2,|S,n,S,1,S,n,.,S,2,分布式系统(二)08-03,8,分布式程序设计语言,以DCDL的复合语句（由顺序或/和并行语句组成）描述的语句一定可以用一个优先图来表示，但并不是所有优先图都可以用DCDL来表示。如优先图：,就不能用DCDL复合语句来表示。,解决的办法可以通过下面三种。,S,2,S,1,S,4,S,5,S,3,S,6,分布式系统(二)08-03,10,分布式程序设计语言,解决办法二：使用fork/join语句,用fork/join语句这样一个更有效的结构来描述：,S,2,S,1,S,4,S,5,S,3,S,6,S,1,;或,c1:=2;,fork L1;,S,2,;,c2:=2;,fork L2;,S,4,;,goto L3;,L1:S,3,;,L2:join c1;,S,5,;,L3:join c2;,S,6,;,c1、c2：分支计数器（fork的线程数）,S,1,;,c1:=2;,fork L1;,S,3,;,goto L2;,L1:S,2,;,c2:=2;,fork L3;,L2:join c1,S,5,;,goto L4;,L3:S,4,;,L4:join c2,S,6,;,分布式系统(二)08-03,12,分布式程序设计语言,再使用parbegin/parend（或cobegin/coend）使所有的复合语句或进程并发执行，其程序如下：,所有信号量s,ij,初始化为0；,parbegin,S(1);,S(2);,S(3);,S(4);,S(5);,S(6);,parend,其中parbegin到parend间的语句也可DCDL表示成：,|S(i:16);也称为并发(concurrent)语句,或,S(1)|S(2)|S(3)|S(4)|S(5)|S(6),分布式系统(二)08-03,14,分布式程序设计语言,进程（或复合语句）若由若干顺序执行的语句构成，则并发时只要每个进程中的语句执行顺序不变即可。,(例),P,1,：p,1,(1);p,1,(2),P,2,：p,2,(1);p,2,(2);p,2,(3),则P,1,|,P,2,在各语句执行时，时间上可以是：,p,1,(1);p,1,(2);p,2,(1);p,2,(2);p,2,(3),p,1,(1);p,2,(1);p,1,(2);p,2,(2);p,2,(3),p,1,(1);p,2,(1);p,2,(2);p,1,(2);p,2,(3),p,1,(1);p,2,(1);p,2,(2);p,2,(3);p,1,(2),p,2,(1);p,1,(1);p,1,(2);p,2,(2);p,2,(3),p,2,(1);p,1,(1);p,2,(2);p,1,(2);p,2,(3),p,2,(1);p,1,(1);p,2,(2);p,2,(3);p,1,(2),p,2,(1);p,2,(2);p,1,(1);p,1,(2);p,2,(3),p,2,(1);p,2,(2);p,1,(1);p,2,(3);p,1,(2),p,2,(1);p,2,(2);p,2,(3);p,1,(1);p,1,(2),分布式系统(二)08-03,15,分布式程序设计语言,判别两个语句S,1,和S,2,是否可并行执行的条件（Bernstein条件）,R(S,1,),W(S,2,)=,W(S,1,),R(S,2,)=,W(S,1,),W(S,2,)=,这三个条件同时满足，则,S,1,和,S,2,可并行执行。其中：,R(S,i,),：,S,i,的读集（所有被引用变量的集合）,W(S,i,),：,S,i,的写集（所有被改变变量的集合）,分布式系统(二)08-03,16,分布式程序设计语言,(例)假设,S,1,：a:=x+y,S,2,：b:=x,z,S,3,：,c:=y-1,S,4,：,z:=y+c,则S,1,|S,2,，S,1,|S,3,，S,1,|S,4,，S,2,|,S,3,。,一个语句集S,i,，1,i n，如果两两满足,Bernstein条件，那么可以并行执行，即：,S,1,|S,2,|,S,n,i,j,S,i,|S,j,可以通过求最大的完全子图来得到语句可并行执行的最大子集：,S,2,S,1,S,4,S,3,其中，节点是语句，边表示两个语句可并行执行。,则：S,1,|S,2,|S,3,（书上错误，下同）,分布式系统(二)08-03,17,分布式程序设计语言,选择语句,（Alternative Statement）,优先图：,DCDL表示：,G,1,C,1,G,2,C,2,G,n,C,n,其中,G,i,C,i,是,Dijkstra保护命令。若多个条件（保护）G,i,可满足，则结果不确定（选择任意一个）。,x xy,(例)m=,y x,y,则DCDL表示为：,xym:=x,x,ym:=y,C,1,C,n,.,C,2,G,1,G,2,G,n,分布式系统(二)08-03,18,分布式程序设计语言,第1种重复语句的例子：,从一个二维数组b1:m1:n中找到一个确定的值x。,（重复语句与选择语句结合）,程序：,i:=1;,j:=1;,*i m x bi,j,j:=j+1;,j n skip,jn,i:=i+1;j:=1,分布式系统(二)08-03,20,分布式程序设计语言,另一个例子：,Rubin问题：判别矩阵a1:m1:n中某一行是否为全0。,程序：,i:=1;p:=m+1;,*i p,j:=1;q:=n+1;,*j q,ai,j=0,j:=j+1,ai,j,0,q:=j,;,j=n,+1,p:=i,j,n,+1,i:=i+1,found:=(i,m+1),分布式系统(二)08-03,21,分布式程序设计语言,多进程间的同步有两种方式,a.非对称同步：一个协调者，若干工作者，当协调者收到每个工作者的消息时给所有的工作者发一个特别的信号。,worker(i):=*,true,code to implement process,P,i,;,send,signal,to,coordinator;,receive,ack,from,coordinator,coordinator:=*,true,counter,:=0,;,*,counter,n,receive,signal;,counter,:=,counter,+1,;,send,ack,to,all;,分布式系统(二)08-03,23,分布式程序设计语言,b.对称同步：没有协调者，由工作者（进程）之间通过多次两两同步来实现全部同步。,例：8个进程间的同步。,阶段1：,barrier(P,1,P,2,)|barrier(P,3,P,4,)|barrier(P,5,P,6,)|barrier(P,7,P,8,),阶段2：,barrier(P,1,P,3,),|barrier(P,2,P,4,),|barrier(P,5,P,7,),|barrier(P,6,P,8,),阶段3：,barrier(P,1,P,5,),|barrier(P,2,P,6,)|barrier(P,3,P,7,)|barrier(P,4,P,8,),图示如下：,P,2,P,1,P,4,P,3,P,6,P,5,P,8,P,7,（可以简化！）,分布式系统(二)08-03,24,分布式程序设计语言,说明：,a.,P,(0)是用户输入输出进程，它把n输入给进程,P,(1)，从进程,P,(1)处接收输出结果f(n)；,b.每个进程,P,(i)计算f(n-i+1)，1,in；,c.活动的,P,(i)数取决于n。,图示：,f(n),f(m),f(1),m,m*m*r,m-1,r,1,1,n-1,(n-1)*(n-1)*r,n,result,P(0)=USER P(1)P(i)P(n),计算数值逐步减小，直到1,计算结果逐步返回,分布式系统(二)08-03,26,分布式程序设计语言,2.Fibonacci数列，即计算F(i)=F(i-1)+F(i-2)(i1)，F(0)=0,F(1)=,1,。,（兔子生育问题:每个兔子每年生一个兔子,兔子生下一年后就可生育,永不死）,解一：,使用多进程通信、递归方法，定义一系列进程f(i)用于计算F(n-i+1)。,如果(n-i+1)1，f(i)从f(i-1)接收(n-i+1)并把(n-i)传递给f(i+1)，然后f(i)等待f(i+1)和f(i+2)的结果，把它们相加，并把相加的结果传递给f(i-1)和f(i-2)。,如下图示：,F(n-i+2),F(n-i+1),m-1(=n-,i,),m(=n,-i+1,),q+p,q,F(n-i),p,q+p,f(i-2)f(i-1)f(i)f(i+1)f(i+2),F(n),F(0),分布式系统(二)08-03,27,分布式程序设计语言,DCDL程序：,f,(0):=,n,1 ,send,n,to,f,(,1,);,receive,p,from,f,(,2,);,receive,q,from,f,(,1,);,ans:=q,n,=1 ans:=1,n,=0 ans:=0,f,(,i,):=,receive,m,from,f,(,i-1,);,m,1 ,send,m,-,1,to,f,(,i+1,);,receive,p,from,f,(,i+2,);,receive,q,from,f,(,i+1,);,s