第2章分布式程序设计语言.ppt

第2章分布式程序设计语言,2008.3,分布式系统(二)08-03,2,分布式程序设计语言,为什么需要分布式程序设计语言？传统顺序程序设计语言（如：Fortran、Pascal或C等）不能解决诸如并发、通信、同步和可靠性等分布式环境下需要解决的问题，因此不适合于分布式系统。并行程序设计语言不一定能在分布式系统中使用，因为它没有考虑通信开销。分布式程序设计语言较传统顺序程序设计语言更注重（显式）表达如下3个方面的需求：多个PE的使用；（并发）PE之间的合作；（通信和同步）对局部故障的生存能力。（故障弱化）,分布式系统(二)08-03,3,分布式程序设计语言,分布式控制描述语言（DCDL）本章主要介绍一种称为分布式控制描述语言的DCDL，它是一种框架控制驱动的描述语言。DCDL可用于描述一些控制结构，如：并行的表示、进程间通信和同步、容错设计等。DCDL表示的控制算法是在抽象层上提出的，可以应用于操作系统层、语言运行时（run-time）系统层或用户层。DCDL有形式定义（书中附录给出了DCDL常用的语法符号列表），我们主要通过一些实例来阐述它的语义结构。,分布式系统(二)08-03,4,分布式程序设计语言,DCDL语义结构中用到的一些表示方法：语句和命令语句：Si（1in）它可以是一个命令列表C或一个Dijkstra保护命令。命令列表：C由一系列命令组成。Dijkstra(被)保护命令（guardedcommand）：GC其中G是一个布尔表达式列表组成的保护(guarded)，C是一个命令列表。当保护G执行结果为true时，执行命令列表C。（即满足条件G时，执行C）,分布式系统(二)08-03,5,分布式程序设计语言,优先图（precedencegraph）优先图是一个有向无环图（DAG,DirectedAcyclicGraph），即不带环路的有向图。节点代表语句（可以为空），有向边代表优先关系。如：,S1,S2,S4,S3,S5,分布式系统(二)08-03,6,分布式程序设计语言,优先顺序是可传递的（transitive）。即：若，则。但优先图中不允许存在冗余的连接，如上页图中，若有，就是冗余连接。（冗余连接的优先顺序可以从其它优先顺序导出）不存在冗余连接的优先图是保持所有优先关系的最简化的优先图！即：一个优先顺序集合R是非冗余的当且仅当不存在R的子集使得它们有相同的传递闭包。,S1,S2,S3,S1,S3,S1,S3,分布式系统(二)08-03,7,分布式程序设计语言,顺序语句（SequenceStatement）顺序执行的语句：S1、S2、Sn优先图：DCDL表示：S1;S2;Sn,S1,S2,Sn,.,分布式系统(二)08-03,8,分布式程序设计语言,并行语句（ParallelStatement）并行执行的语句：S1、S2、Sn优先图：DCDL表示：S1|S2|Sn,S1,Sn,.,S2,分布式系统(二)08-03,9,分布式程序设计语言,例：一个优先图用顺序语句和并行语句表示优先图：其DCDL表示：S1;S2;S3|S4;S5;S6|S7;S8,S2,S7,S4,S1,S3,S5,S6,S8,分布式系统(二)08-03,10,分布式程序设计语言,以DCDL的复合语句（由顺序或/和并行语句组成）描述的语句一定可以用一个优先图来表示，但并不是所有优先图都可以用DCDL来表示。如优先图：就不能用DCDL复合语句来表示。解决的办法可以通过下面三种。,S2,S1,S4,S5,S3,S6,分布式系统(二)08-03,11,分布式程序设计语言,解决办法一：更具限制性优先图将给定的优先图G转化为更具限制性的新优先图G，G中保留了G所有的优先顺序，但可能又加上了新的优先顺序（可能会失去一定程度的并行性）。如上图中，断开S1到S2、S3到S5的连接，加入S3到S2的连接后，其更具限制性的优先图为：则可用DCDL描述，为：S1;S3;S2;S4|S5;S6,S2,S1,S4,S5,S3,S6,分布式系统(二)08-03,12,分布式程序设计语言,解决办法二：使用fork/join语句用fork/join语句这样一个更有效的结构来描述：,S2,S1,S4,S5,S3,S6,S1;或c1:=2;forkL1;S2;c2:=2;forkL2;S4;gotoL3;L1:S3;L2:joinc1;S5;L3:joinc2;S6;c1、c2：分支计数器（fork的线程数）,S1;c1:=2;forkL1;S3;gotoL2;L1:S2;c2:=2;forkL3;L2:joinc1S5;gotoL4;L3:S4;L4:joinc2S6;,分布式系统(二)08-03,13,分布式程序设计语言,解决办法三：使用信号量用parbegin/parend（或cobegin/coend）加上二元信号量s来解决。对信号量s可进行P、V操作：P(s):若s为0，则挂起;s:=s-1V(s):s:=s+1如例图，对每个有优先顺序关系的语句定义一个二元信号量sij，初始值为0；每个语句变成复合语句或进程：S(1):S1;V(s12);V(s13)S(2):P(s12);S2;V(s24);V(s25)S(3):P(s13);S3;V(s35)S(4):P(s24);S4;V(s46)S(5):P(s25);P(s35);S5;V(s56)S(6):P(s46);P(s56);S6,Si,Sj,S2,S1,S4,S5,S3,S6,s12,s13,s24,s35,s56,s46,s25,分布式系统(二)08-03,14,分布式程序设计语言,再使用parbegin/parend（或cobegin/coend）使所有的复合语句或进程并发执行，其程序如下：所有信号量sij初始化为0；parbeginS(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,15,分布式程序设计语言,进程（或复合语句）若由若干顺序执行的语句构成，则并发时只要每个进程中的语句执行顺序不变即可。(例)P1：p1(1);p1(2)P2：p2(1);p2(2);p2(3)则P1|P2在各语句执行时，时间上可以是：p1(1);p1(2);p2(1);p2(2);p2(3)p1(1);p2(1);p1(2);p2(2);p2(3)p1(1);p2(1);p2(2);p1(2);p2(3)p1(1);p2(1);p2(2);p2(3);p1(2)p2(1);p1(1);p1(2);p2(2);p2(3)p2(1);p1(1);p2(2);p1(2);p2(3)p2(1);p1(1);p2(2);p2(3);p1(2)p2(1);p2(2);p1(1);p1(2);p2(3)p2(1);p2(2);p1(1);p2(3);p1(2)p2(1);p2(2);p2(3);p1(1);p1(2),分布式系统(二)08-03,16,分布式程序设计语言,判别两个语句S1和S2是否可并行执行的条件（Bernstein条件）R(S1)W(S2)=W(S1)R(S2)=W(S1)W(S2)=这三个条件同时满足，则S1和S2可并行执行。其中：R(Si)：Si的读集（所有被引用变量的集合）W(Si)：Si的写集（所有被改变变量的集合）,分布式系统(二)08-03,17,分布式程序设计语言,(例)假设S1：a:=x+yS2：b:=xzS3：c:=y-1S4：z:=y+c则S1|S2，S1|S3，S1|S4，S2|S3。一个语句集Si，1in，如果两两满足Bernstein条件，那么可以并行执行，即：S1|S2|SnijSi|Sj可以通过求最大的完全子图来得到语句可并行执行的最大子集：,S2,S1,S4,S3,其中，节点是语句，边表示两个语句可并行执行。则：S1|S2|S3,（书上错误，下同）,分布式系统(二)08-03,18,分布式程序设计语言,选择语句（AlternativeStatement）优先图：DCDL表示：G1C1G2C2GnCn其中GiCi是Dijkstra保护命令。若多个条件（保护）Gi可满足，则结果不确定（选择任意一个）。xxy(例)m=yxy则DCDL表示为：xym:=xxym:=y,C1,Cn,.,C2,G1,G2,Gn,分布式系统(二)08-03,19,分布式程序设计语言,重复语句（RepetitiveStatement）三种重复语句，其DCDL表示为：*G1C1G2C2GnCn所有保护都经过（都不满足）时终止。*S1S2Sn至某个状态不再改变，达到一个状态固定点（Fixedpoint）时终止。nS1S2Sn选择做n次后终止（若有保护，则所有保护都经过时会提前终止）。第2种重复语句例：约会时间调度:=t:=0;*t:=a(t)t:=b(t)t:=c(t)（由于没有保护，选择是不确定的，但由于无限重复，选择是公平的）,分布式系统(二)08-03,20,分布式程序设计语言,第1种重复语句的例子：从一个二维数组b1:m1:n中找到一个确定的值x。（重复语句与选择语句结合）程序：i:=1;j:=1;*imxbi,jj:=j+1;jnskipjni:=i+1;j:=1,分布式系统(二)08-03,21,分布式程序设计语言,另一个例子：Rubin问题：判别矩阵a1:m1:n中某一行是否为全0。程序：i:=1;p:=m+1;*ipj:=1;q:=n+1;*jqai,j=0j:=j+1ai,j0q:=j;j=n+1p:=ijn+1i:=i+1found:=(im+1),分布式系统(二)08-03,22,分布式程序设计语言,进程间通信与同步DCDL通信采用异步点到点的消息传递。消息通过两个进程间的一个异步静态通道（或称链路，是一个FIFO队列）来传递，且一般假设任意两个进程间只有一个通道。输出命令：sendmessage_listtodestination/all输入命令：receivemessage_listfromsource/sender（显式）或receivemessage_list（隐式）可以用异步通信来构造barrier（阻挡/屏蔽）同步。发送方：sendmessage_listtodestinationreceiveempty_signalfromdestination接收方：receivemessage_listfromsendersendempty_signaltosender,分布式系统(二)08-03,23,分布式程序设计语言,多进程间的同步有两种方式a.非对称同步：一个协调者，若干工作者，当协调者收到每个工作者的消息时给所有的工作者发一个特别的信号。worker(i):=*truecodetoimplementprocessPi;sendsignaltocoordinator;receiveackfromcoordinatorcoordinator:=*truecounter:=0;*counternreceivesignal;counter:=counter+1;sendacktoall;,分布式系统(二)08-03,24,分布式程序设计语言,b.对称同步：没有协调者，由工作者（进程）之间通过多次两两同步来实现全部同步。例：8个进程间的同步。阶段1：barrier(P1,P2)|barrier(P3,P4)|barrier(P5,P6)|barrier(P7,P8)阶段2：barrier(P1,P3)|barrier(P2,P4)|barrier(P5,P7)|barrier(P6,P8)阶段3：barrier(P1,P5)|barrier(P2,P6)|barrier(P3,P7)|barrier(P4,P8)图示如下：,P2,P1,P4,P3,P6,P5,P8,P7,（可以简化！）,分布式系统(二)08-03,25,分布式程序设计语言,关于进程间通信与同步的另外2个例子：1.计算(n!)2，即计算f(n)=f(n-1)*n2,n1且f(1)=1。解：使用进程递归方法，递归的结果通过进程通信来传递。DCDL程序：P(i:1n):=*receivemfromP(i-1)m=1send1toP(i-1)m1sendm-1toP(i+1);receiverfromP(i+1);sendm*m*rtoP(i-1)P(0):=sendntoP(1);receiveresultfromP(1);|P(i:0n)#主控程序,分布式系统(二)08-03,26,分布式程序设计语言,说明：a.P(0)是用户输入输出进程，它把n输入给进程P(1)，从进程P(1)处接收输出结果f(n)；b.每个进程P(i)计算f(n-i+1)，1in；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)=USERP(1)P(i)P(n),计算数值逐步减小，直到1,计算结果逐步返回,分布式系统(二)08-03,27,分布式程序设计语言,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,28,分布式程序设计语言,DCDL程序：f(0):=n1sendntof(1);receivepfromf(2);receiveqfromf(1);ans:=qn=1ans:=1n=0ans:=0f(i):=receivemfromf(i-1);m1sendm-1tof(i+1);receivepfromf(i+2);receiveqfromf(i+1);sendp+qtof(i-1);sendp+qtof(i-2)m=1send0tof(i+1);send1tof(i-1);send1tof(i-2)m=0send0tof(i-2)f(-1):=receivepfromf(1);,f(0)是用户进程，解的结果在ans中。f(-1)是虚进程，目的是让f(1)在发送结果消息时有一个目的接收者，如果把f(i)中的sendp+qtof(i-2)改成i1sendp+qtof(i-2)，则可去掉f(-1)。,分布式系统(二)08-03,29,分布式程序设计语言,解二(优化)：可改写成每个进程只和邻居进程打交道：在向上传递结果时，不仅传递本进程的计算结果，同时传递下一级进程的计算结果。如下图示：,F(n-i+2),F(n-i+1),m-1(=n-i),m(=n-i+1),q+p,q,q,p,F(n-i),f(i-1)f(i)f(i+1),F(n),F(1),分布式系统(二)08-03,30,分布式程序设计语言,DCDL程序：f(0):=n1sendntof(1);receiveqfromf(1);receivepfromf(1);ans:=qn=1ans:=1n=0ans:=0f(i):=receivemfro