《DCDL描述语言》PPT课件.ppt

本章主要内容,DCDL语言常用符号DCDL语言描述与执行优先图描述基本知识DCDL与执行优先图之间的转换DCDL描述顺序语句，选择语句和重复语句DCDL编程实例,分布式程序设计的特点,多个PE的使用对并行性的支持PE之间的合作对通信与同步的支持单播/组播同步（直接通信）/异步（间接通信）对称（双向通信）/非对称（单向通信）对局部故障的生存能力对容错的支持,DCDL：分布式控制描述语言,处理的基本元素是语句能以语言的方式完成对并发、进程间通信与同步和容错这3个基本功能的无二义的表达能力,DCDL基本符号,DCDL的顺序和并行语句,顺序语句语法：S1；S2；Sn语义：顺序执行S1；S2；Sn这n个语句并行语句语法：S1|S2|Sn语义：并发执行S1、S2、Sn这n个语句复合语句：S1；S2；Sn,执行优先图,用途：支持对并发的设计定义：用于描述语句间执行优先关系的不带环路的有向图，图中的点代表语句，边代表语句间的优先关系。优先关系直接优先关系：语句A、B间存在直接优先关系当且仅当执行图中存在边（A，B）间接优先关系：经直接优先关系传递的语句间的优先关系,执行优先图（续）,起点：执行优先图中入度为零的结点终点：执行优先图中出度为零的结点如果一个执行优先图由几个不连通的子图构成，则这些子图可以并行的且每张子图均是执行优先图连通的执行优先图中的每一点均是从起点可达的由一个单个结点构成的图也是执行优先图,执行优先图及其DCDL表示DCDL中的并行单元是语句。并行语句可以用优先图表示，节点代表语句，有向边代表优先关系。优先图是有向无环图。一组并行语句表示为：S1|S2|Sn一组顺序语句表示为：S1；S2；Sn如图所示的优先图表示为:S1；S2；S3|S4；S5|S7;S6,S,1,S,2,S,2,S,4,S,7,S,5,S,6,DCDL并行语句的局限,DCDL的基本结构是并行的串行表示，因此它不能表示一个并发依赖于另一个并发的情形，如图所示：,三种解决方法,方法一：对原来的优先图进行修改，转换为更具限制性的优先图，再用DCDL来描述方法二：使用fork和join语句方法三：使用P/V操作语句,方法一,牺牲一个并发，这样优先图可表述为：S1;S3;S2;S4|S5;S6或S1;S3|S2;S4|S5;S6后者损失了S4的开始时间（强行增加了S3和S4间的优先关系）,方法二：使用fork和join语句,Fork语句：语法：forkL1,L2Lnn0语义：产生n个新线程，分别从标号开始执行Join语句：语法：joinCC是整型常数或变量语义：合并C个线程，除主线程外其他线程在到达该语句时退出。,S1；C1:=2;ForkL1;S2;C2:=2;ForkL2;S4;GotoL3;,L1:S3;L2:joinc1;S5;L3:joinc2;S6;,进程的并发,过程调用产生进程，过程调用也是语句，所以，DCDL处理进程的并发等同语句的并发：P1|P2|Pn,进程的并发,当并发的进程分别由多个串型子进程构成时（可分成多个串型子进程）分属于不同进程的子进程相互独立，可以调换执行的顺序，对最终的结果不会产生影响。属于同一进程的子进程，必须按原有的顺序执行,进程的并发,实例：若P1：p11p12,P2:p21p22p23则：P1|P2可以按以下任一顺序执行（对最终结果没有影响）p11p12p21p22p23p11p21p12p22p23p11p21p22p12p23p11p21p22p23p12只要不改变p11与p12以及p21与p22和p24间的偏序关系即可,保护语句和选择语句,保护语句（guardedcommand条件语句）语法：GS语义：当布尔表达式G为真时执行语句S选择语句语法：S1S2Sn，其中Si要么全部是保护语句，要么全部不是保护语句语义：在S1Sn中选择一个语句执行,实例,带保护的选择语句xym:=xy1m:=0执行结果：如果xy和y1同时成立，则m可能等于x，也可能等于0，如果前者成立，则m=x,若后者成立，则m=0,若2个条件均不成立，则m的值没有变化。非保护选择语句r:=ar:=br:=c执行结果：r的取值为a,b,c中的一个,重复语句,语法：*语句语义：将语句重复执行如果被重复的语句是保护语句，则在条件均不满足时选择语句结束如果被重复的语句是带保护的选择语句，则在条件均不满足时选择语句结束如果被重复的语句不是保护语句，则该语句不能自动中止,重复语句的实例,*r:=a(t)r:=b(t)r:=c(t)结果：随机地在选择一个函数执行并将结果赋给变量r，因此r的值随时间的推进而不断变化意义：在每一时刻，r均有一个有意义的值，可被其它进程使用,进程的通信与同步,消息传递由发送和接收两个基本操作构成有同步、异步、一对多、会合和远程过程调用等模式数据共享底层的网络连接不在本课程的讨论范围（总假设所有需要传递的信息均能正确到达对方）,DCDL所支持的消息传递机制,最基本的异步单播方式，通过异步静态通道进行交互输出语句sendmessage_listtodestination其中destination可以是一个进程（单播）或是all（广播）输入（接收）语句receivemessage_listfromsource其中source是一个进程名（可选），即输入命令支持显式和隐式的消息接收。,用DCDL支持消息的同步传递,同步传递可以通过命令的组合来实现在发送方Sendmessage_listtodestinationReceiveempty_signalfromdestination在接收方Receivemessage_listfromsenderSendempty_signaltosender,用DCDL支持多个进程的会合,第i个工作者（1in）进程的代码：CodeofprocessPi;Sendsignaltocoordinator协同者进程代码：Counter=0;*counternreceivesignal;counter:=counter+1;Sendacktoall,DCDL对通信故障检测的描述,Sender:=setup_time(t);senddiagnostic_signaltoreceiver;receiveackfromreceiverstatus:=normaltimeout(t)tatus:=abnormal其中setup_time和timeout是DCDL的外部函数对通信故障的检测和恢复是非常复杂的，但也是分布式系统的基本问题,对局部故障的生存能力容错技术,程序设计容错向前恢复：根据已有的知识试图去改正错误向后恢复：恢复到出错前的一个状态通信错误：没有能在规定的时间内正确收到应该收到的消息。造成通信错误的原因非常复杂,例2.1给出一个确定的数组b1:m1:n，其中1ni:=i+1;j:=1,DCDL编程实例,例2.2Rubin问题：确定一个mn的矩阵a1:m1:n中某一行的所有元素是否全部为0，这是一个二维的查找问题。i:=1;p:=m+1;*ipj:=1;q:=n+1;*jqai,j=0j:=j+1ai,j0q:=j;j=np:=ijni:=i+1found:=(im+1)布尔变量foundT，则存在这样的全0行，否则，不存在。,语句并发(并行)的条件:Bernstein条件当两个语句并发执行时，可能产生与顺序执行不同的结果。让我们先定义两个符号：R(Si)：Si的读集，即在Si中被引用的所有变量的集合。W(Si)：Si的写集，即在Si中被修改的所有变量的集合。Bernstein提出了以下三个条件，对于两个并发执行的语句S1和S2，必须满足这三个条件才能使它们并发执行的结果与它们以任意次序顺序执行的结果相同。R(S1)W(S2)=R(S2)W(S1)=W(S1)W(S2)=使用S1|S2表示语句S1和S2满足这三个条件，可以并行或并发执行。,例2.3假设S1为a:=x+y，S2为b:=x+z，用bernstein条件证明这两个语句可以并发执行。解：按照bernstein判定条件，因为R(S1)=x，y，R(S2)=x，z，W(S1)=a，W(S2)=b它们满足以下三个条件，即：R(S1)W(S2)=R(S2)W(S1)=W(S1)W(S2)=所以这两个语句可以并发执行,例2.4假设S1:a:=xy,S2:b:=xz,S2:x:=yz,S4:c:=y-1。利用Bernstein条件，有S1|S2，S1|S4，S2|S4，S2|S4，相应的表示在下图中，显然，S1，S2，S4形成最大的完全子图，也就是说S1|S2|S4。,DCDL中的通信采用异步点对点报文传递，报文通过异步静态通道传递给指定的接收方进程。输出命令的形式为：sendmessage_listtodestination其中destination是一个进程名(一对一通信)或代表所有其他进程(一对所有通信)的关键字all。输入命令的形式为：receivemessage_listfromsource其中source是一个进程名，这个输入命令支持显式和隐式的报文接收。隐式的报文接收表示为：receivemessage_list,