【正文】 第三章 分布式系統(tǒng)中的通信 ● PCAP的基本算法 目的：根據(jù)語法規(guī)則的要求組織可傳送集 D 令： m 代表任意一個消息 V 代表 Q的要求，是一個消息序列 Sm代表發(fā)送序列 Sv表示由 V組成的消息序列 e表示空集 send（ m,Q）表示將消息 m發(fā)送至 Q的信箱 first（ S）表示消息序列 S的第一個元素 若 S = S’’ m S’，則： before（ m， S） = S’ after（ m， S） = S’’ 第三章 分布式系統(tǒng)中的通信 ★ Cpq的基本算法 ⑴ Cpq收到來自 P的消息 m， Sm = mSm ⑵ C收到來自 Q的要求 v， Sv=vSv ⑶ 若 Sm、 Sv非空，則： ① x = first（ Sv） ② 若滿足 ?m=x 且 m是 Sm的可傳送元素，則 { 將 m移到 Sm的首部； Sm= after（ m， Sm）； Sv= after（ x， Sv）； send（ m， Q）；轉(zhuǎn) ⑶ } 否則轉(zhuǎn)⑷ ⑷ 轉(zhuǎn)⑴ 第三章 分布式系統(tǒng)中的通信 ★ 討論與分析 判斷“ ?m=x 且 m是 Sm的可傳送元素”是算法的關(guān)鍵，耗時最長。同樣，它與 PCAP的層次通道規(guī)則 Gh關(guān)系密切。這樣可以改寫為 ?m=x 且 m?Dh（這里 Dh為層次通道 Gh的可傳送集） ∵ Gh=Rh∪∪ Gi ， ∴ Dh = L∩D 這里， L = { m|Sm= S’mS’’； ?m’ ?S’’且m’ .level} （實際上， L表示了那些在它前面的元素層次都較低的元素集合） D=∪ Di， Di={m|(=I)且 ExtractSame(m,Sm) Sm’ m} 這里 ExtractSame(m,Sm)表示在 Sm中取出與 m層次相同的消息后形成的消息序列。 i≥0 i≥0 * Gi 第三章 分布式系統(tǒng)中的通信 這樣， m=v且 m?Dh就變成了 m=v且 m?(L∩D) 引入記號，用以判斷 m是否可以在 Sm中超越（即 m?L）： NonLowerAhead(m, Sm)=true iff (Sm=S’ mS’’ )∧ (?m’ ?S’’：m’ .level≥)； 這樣再引入 LevelDeliverable(m, Sm) = true iff ExtractSame(m, Sm) S’ mm （即 m在同一通道中可傳送） * Gi 第三章 分布式系統(tǒng)中的通信 ★ 改進后的 Cpq算法 ⑴ 收到來自 P的消息 m，則 ⅰ ） Sm = mSm； ⅱ ） 若 NonLowerAhead(m,Sm)=true 則 L=L∪ m； ⅲ ） 若 LevelDeliverable(m,Sm)=true 則 D=D∪ m； ⑵ 收到來自 Q的要求 v，則 Sv=vSv； ⑶ 若 Sv≠e∧ L∩D ≠e 則 ⅰ ） x=first(Sv) ⅱ ） 若 ?m∧ m?(L∩D) 則 { 將 m移至 Sm的首部， Sm= after(m, Sm ) ； L={m’ ∣ NonLowerAhead(m’ , Sm)}； 第三章 分布式系統(tǒng)中的通信 D={m’ |LevelDeliverable(m’, Sm)}； send（ m,Q）； Sv= after（ m,Sv）； 轉(zhuǎn) ⑶ } 否則轉(zhuǎn)⑷ ⑷ 轉(zhuǎn)⑴ 顯然，目前 PCAP的算法只是定性描述，只有在確定了各子通道的類型， LevelDeliverable(m’, Sm)才是確定的和可計算的。 第三章 分布式系統(tǒng)中的通信 167。 5 RPC的結(jié)構(gòu)模型 1. 一對多模型 2. 在這種情況，系統(tǒng)中存在多個 Server，對一個 client，其 RPC發(fā)往何處并不明確。 3. ● 分散式 4. RPC以廣播方式發(fā)出，每個 server收到后自行判斷?；驋仐墸?server無此服務(wù)），或執(zhí)行 RPC。 5. 優(yōu)點：邏輯簡單， client處理方便。 6. 缺點：網(wǎng)絡(luò)開銷大，計算開銷大（ server需要判斷，甚至重復(fù)計算） 第三章 分布式系統(tǒng)中的通信 改進型： client上配置全局服務(wù)目錄，由 client自行選取提供服務(wù)的 server，定向發(fā)送 RPC。適用于專業(yè)系統(tǒng)。 ● 集中式 配置服務(wù)目錄 agent。 改進型： Client agent RPC 執(zhí)行結(jié)果 Server 1 Server n agent Server 1 Server n Client 服務(wù)地址 詢問地址 WEB Service 第三章 分布式系統(tǒng)中的通信 優(yōu)點：減少了網(wǎng)絡(luò)負載 缺點： agent的負擔(dān)過大，將成為系統(tǒng)的瓶頸，一旦故障，系統(tǒng)陷于崩潰。 改進型（ WEB Service）雖然部分減輕了 agent的負載，但是增加了網(wǎng)絡(luò)的開銷。集中式的弊病依然存在。 第三章 分布式系統(tǒng)中的通信 2. 多對多模型 在這種情形，一個 client可以同時發(fā)出多個 RPC，指向多個 server。 mtom（ agentid， n， service1， arg1,… ， argt1， … servicen， arg1， … ， argtn） 實現(xiàn)模型 mtom Agent leader 服務(wù)結(jié)果 返回結(jié)果 隊列管理 Agent線程 （服務(wù)隊列）） 輸向 server的服務(wù)請求 第三章 分布式系統(tǒng)中的通信 工作示意 client agent server mtom 接收 mtom請求，分配線程，將分服務(wù)要求插入線程，進行線程調(diào)度。 各線程分別向 server發(fā)送服務(wù)請求 接收服務(wù)請求，執(zhí)行服務(wù)例程。發(fā)送服務(wù)結(jié)果。 接收服務(wù)結(jié)果，根據(jù)服務(wù)存根分類存放，收齊所有結(jié)過后向client發(fā)送。 發(fā)送服務(wù)請求 回送服務(wù)結(jié)果 接收結(jié)果 向 agent發(fā)送 RPC請求 第三章 分布式系統(tǒng)中的通信 討論： 如果只有一個 agent，將引起超載 若有多個 agent副本，之間如何協(xié)調(diào)以避免重復(fù) agent公布負載情況，供用戶選擇？ 用戶規(guī)定 agent次序，超載 agent自動轉(zhuǎn)移負載？ 劃分 agent的功能范圍，劃分原則 靜態(tài)劃分，增加用戶負擔(dān)，不方便 動態(tài)劃分，管理困難 劃分原則的確定 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAIT