分布式程序設(shè)計語言-資料下載頁
2025-01-07 04:00本頁面
【正文】 j:=1。 *[i≤m∧x≠b[i,j]→ [j:=j+1。 [j≤n→skip □ jn→i :=i+1。j:=1] ] ] 第三章 分布式程序設(shè)計語言 分布式控制描述語言 DCDL ?重復(fù)語句 ： 例 2：確定一個 m n的矩陣 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→p :=i□ j≠n→i :=i+1] ] ] found:=(i≠m+1) 第三章 分布式程序設(shè)計語言 分布式控制描述語言 DCDL ?語句并發(fā) (或并行 )的條件 當(dāng)兩個語句并發(fā)執(zhí)行時 ， 可能產(chǎn)生與順序執(zhí)行不同的結(jié)果 。 讓我們先定義兩個符號： (1) R(Si)， Si的讀集 ， 即在 Si中被引用的所有變量的集合 。 (2) W(Si)， Si的寫集 ， 即在 Si中被修改的所有變量的集合 。 Bernstein提出了以下三個條件 ， 對于兩個并發(fā)執(zhí)行的語句 S1和 S2，必須滿足這三個條件才能使它們并發(fā)執(zhí)行的結(jié)果與它們以任意次序順序執(zhí)行的結(jié)果相同 。 (1) R(S1)∩W(S 2)=Ф (2) R(S2)∩W(S 1)=Ф (3) W(S1)∩W(S 2)=Ф 第三章 分布式程序設(shè)計語言 分布式控制描述語言 DCDL ?語句并發(fā) (或并行 )的條件 我們可以用 Bernstein條件來尋找語句中可以并行執(zhí)行的最大子集 。 為此我們定義了一個無向圖 ， 節(jié)點集由給定語句集組成 ，如果 Si||Sj， 則節(jié)點 Si和 Sj相連 ， 可以并行執(zhí)行的最大的語句子集對應(yīng)于最大的完全子圖 。 例如： S1: a:=x＋ y, S2: b:=x z, S3: x:=y＋ z, S4: c:=y1。顯然， S1， S2， S4形成最大的完全子圖，也就是說， S1||S2||S4。 S 1 S 2 S 3 S 4 第三章 分布式程序設(shè)計語言 分布式控制描述語言 DCDL ? DCDL中的通信 1) 輸出命令的形式為： send message_list to destination 其中 destination是一個進程名 (一對一通信 )或代表所有其他進程 (一對所有通信 )的關(guān)鍵字 all。 2) 輸入命令的形式為： receive message_list from source 其中 source是一個進程名 ， 這個輸入命令支持顯式和隱式的報文接收 。 隱式的報文接收表示為： receive message_list 第三章 分布式程序設(shè)計語言 分布式控制描述語言 DCDL ? DCDL中的通信 例 1：用如下遞歸的方法計算 f(n)=f(n1) n2， n＞ 1并且 f(1)=1。 p(i:1..n)::=*[receive m from p(i1)→ [[m=0→ send 1 to p(i1)□ m0→ send m1 to p(i+1)]。 receive r from p(i+1)。 send m m r to p(i1) ] ] p(0)::=send n to p(1)。 receive result from p(1) 第三章 分布式程序設(shè)計語言 分布式控制描述語言 DCDL ? DCDL中的通信 例 2： Fibonacci數(shù)列是由遞推公式 F(i)=F(i1)+F(i2)(i1)定義的一個整數(shù)數(shù)列 ， 其初始值 F(0)=0， F(1)=2。 這里有兩種算法 。 算法一：定義一系列進程： f(i)用于計算 F(ni+1)， 如果 (ni+1)大于 1， f(i)從 f(i1)接收 (ni+1)并把 (ni)傳遞給 f(i+1)。 然后 f(i)等待 f(i+1)和 f(i+2)的結(jié)果 ， 把它們相加 ， 并把相加的結(jié)果傳遞給 f(i1)和 f(i2)。 f(0)::=send n to f(1)。 receive p from f(2)。 receive q from f(1)。 ans:=q f(i)::=receive n from f(i1)。 [n1→[send n1 to f(i1)。 receive p from f(i+2)。 receive q from f(i+1)。 send p+q to f(i1)。 send p+q to f(i2)] □ n=1→[send 1 to f(i1)。 send 1 to f(i2)] □ n=0→[send 0 to f(i1)。 send 0 to f(i2)] ] f(1)::=receive p from f(1) 在上述算法中 ， f(0)是用戶進程 ， f(1)是虛進程 。 算法二 。 這個算法使通信只限于鄰居之間 ， 即 f(i) 只能和f(i1)和 f(i+1)通信 。 f(0)::=[n1→ [send n to f(1)。 receive p from f(1)。 receive q from f(1)。 ans:=p] □ n=1→ ans:=1 □ n=0→ ans:=0 ] f(i)::=receive n from f(i1)。 [n1→ [send n1 to f(i+1)。 receive p from f(i+1)。 receive q from f(i+1)。 send p+q to f(i1)。 send p to f(i1)] □ n=1→ [send 1 to f(i1)。 send 0 to f(i1)] ] 第三章 分布式程序設(shè)計語言 分布式控制描述語言 DCDL ? DCDL中的通信容錯 容錯是通過檢測故障并隨之對系統(tǒng)進行重新配置而實現(xiàn)的 。 以下是用 DCDL描述的故障檢測過程 。 sender::=[setup time(t)。 send diagnostic_signal to receiver。 [receive ack from receiver?status:=normal □ timeout(t)?status:=abnormal ] ] 個有故障的處理機將被發(fā)送方節(jié)點通過檢查狀態(tài)變量的值發(fā)現(xiàn) 。
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1