DCDL分布式程序设计语言.ppt

分布式程序设计语言 判别两个语句S1和S2是否可并行执行的条件（Bernstein条件） R(S1)?W(S2)=? W(S1)?R(S2)=? W(S1)?W(S2)=? 这三个条件同时满足，则S1和S2可并行执行。记为： S1||S2 其中： R(Si)：Si的读集（所有被引用变量的集合） W(Si)：Si的写集（所有被改变变量的集合） * 分布式程序设计语言 (例) 假设 S1：a:=x+y S2：b:=x?z S3：c:=y-1 S4：z:=y+c 则S1||S2，S1||S3，S1||S4，S2||S3。 一个语句集Si，1 ? i ? n，如果两两满足Bernstein条件，那么可以并行执行，即： S1||S2||…||Sn=?i?j Si||Sj * 可以通过求最大的完全子图来得到语句可并行执行的最大子集： * S2 S1 S4 S3 其中，节点是语句，边表示两个语句可并行执行。 则： S1||S2||S3 分布式程序设计语言 选择语句（Alternative Statement） [S1 □ S2 □ …… □ Sn] 在S1…..到Sn中选择一个语句执行。 其中Si要么全部是保护语句，要么全部不是保护语句 优先图： * DCDL表示：[G1?C1?G2?C2? … ?Gn?Cn] 其中Gi?Ci是Dijkstra保护命令。若多个条件（保护）Gi可满足，则结果不确定（选择任意一个）。 例：如果x≥y，将x赋予m，如果y≥x，将y赋予m。 DCDL表示为：[x?y?m:=x ? x?y?m:=y] * 分布式程序设计语言 重复语句（Repetitive Statement） *[语句] 三种重复语句，其DCDL表示为： *[G1?C1?G2?C2? … ?Gn?Cn] 所有保护都经过（都不满足）时终止。 *[S1?S2? … ?Sn] 至某个状态不再改变，达到一个状态固定点（Fixed point）时终止。 n[S1?S2? … ?Sn] 选择做n次后终止（若有保护，则所有保护都经过时会提前终止）。 * 分布式程序设计语言 第1种重复语句的例子： 从一个二维数组b[1:m][1:n]中找到一个确定的值x。（重复语句与选择语句结合） 程序： i:=1; j:=1; *[ i ? m ? x ? b[i,j] ? [ j:=j+1; [ j ? n ? skip ? jn ? i:=i+1; j:=1] ] ] * 第2种重复语句例： 约会时间调度::= t:=0; “：：=”代表一个函数（或过程）的定义 *[t:=a(t)?t:=b(t)?t:=c(t)] （由于没有保护，选择是不确定的，但由于无限重复，选择是公平的） * 分布式程序设计语言 另一个例子： Rubin问题：判别矩阵a[1:m][1:n]中某一行是否为全0。 程序： i:=1; p:=m+1; *[ i ? p ? [ j:=1; q:=n+1; *[ j ? q ? [ a[i,j] = 0 ? j:=j+1 ? a[i,j] ? 0 ? q:=j ] ]; [ j = n+1 ? p:=i ? j ? n+1 ? i:=i+1 ] ] ] found:=(i ? m+1) * 分布式程序设计语言 进程间通信与同步 数据共享 在没有共享存储器的分布式系统中为通信提供共享数据。 关键问题在于防止多个进程同时修改数据。 消息传递 由发送和接收两个基本操作构成 有同步、异步、一对多、会合和远程过程调用等模式 在DCDL中采用了异步点到点消息传递。 * 分布式程序设计语言 DCDL通信采用异步点到点的消息传递。消息通过两个进程间的一个异步静态通道（或称链路，是一个FIFO队列）来传递，且一般假设任意两个进程间只有一个通道。 输出命令：send message_list to destination/all 输入命令：receive message_list from source/sender （显式） 或 receive message_list （隐式） 可以用异步通