分散式演算法续.PPT

分散式系統簡介 第十九章 分散式協調 第十九章 分散式協調 事件順序 先發生於 全域排序 互斥 推選演算法 不可分割交易 並行控制 死結處理 摘要 事件順序 單處理器系統中可以輕易地解決同步問題 號誌 監督程式 分散式環境下，每個電腦擁有各自的時脈，所以沒辦法根據時脈來決定事件發生的先後順序 分散式系統只能利用事件彼此的相依性來決定事件發生的先後順序 先發生於 分散式的環境下不容易定出統一的時脈，所以利用事件彼此的相依性，也就是所謂「先發生於」的關係 此方法依據以下三種狀況來定義事件發生的先後關係 如果 a 和 b 是同一個行程的事件，而且 a 在 b 之前執行，則 a→b 如果 a 是某個行程傳送訊息的事件，而 b 是另一個行程接收此訊息的事件，則 a→b 如果 a→b 且 b→c，則a→c 事件關係圖 決定各事件的關係如下 P1→Q2 Q1→S1 Q1→P3 R2→S3 Q1→S3（因為Q1→S1且S1→S3） R1→S3（因為R1→R2且R2→S3） 全域排序 分散式系統中達成全域排序，可以將系統中每個事件都附上一個時間戳記 系統所有事件的時間戳記定義完後，即可以依此排列出全域的排序 遇到不同行程的事件擁有相同的時間戳記，則可以利用行程識別代號決定順序 整體排序示意圖 第十九章 分散式協調 事件順序 互斥 集中式演算法 分散式演算法 令牌環演算法 推選演算法 不可分割交易 並行控制 死結處理 摘要 互斥 互斥就是多個行程同時想要使用同一個資源時，但這個資源一次只允許一個行程使用 分散式系統或集中式系統常使用臨界區的作法來避免多個行程同時使用同一個資源或資料 數種演算法可處理分散式系統中解決互斥的問題 集中式演算法 分散式演算法 令牌環演算法 集中式演算法 在分散式系統中要達到互斥的功能，最直接的方法就是模擬成單處理器系統，將互斥的資源集中管理，也就是選擇其中一個行程當協調者來管制臨界區的進出 集中式演算法可以保證互斥的條件，讓同一時間之內只有一個行程進入臨界區，並保證不會有行程發生飢餓現象 集中式演算法也有缺點，當協調者不能運行時，其他行程會因此無法進入臨界區 集中式演算法(續) 集中式演算法範例 行程 P1 送一個REQUEST 的訊息給協調者 Pc 協調者 Pc 回覆 OK 訊息給行程 P1 行程 P2 發 REQUEST 的訊息給協調者 Pc Pc 會回覆 NO 的訊息給行程 P2 行程 P1 離開臨界區並傳送 RELEASE 的訊息給協調者 Pc 協調者 Pc 便會送 OK 訊息給行程 P2 集中式演算法(續) 分散式演算法 分散式演算法是將決定權分散到整個系統，整個演算法的基本想法是建立在已知事件的全域排序基礎上 當行程要進入某個臨界區時，互相傳遞的訊息至少要 2 (n-1) 個，所以演算法執行起來相當複雜且緩慢 此演算法適用在小型且穩定的分散式系統上 分散式演算法(續) 令牌環演算法 令牌環演算法是利用令牌的概念來達到互斥的功能，在分散式系統中有一個令牌在行程間互相傳遞，拿到令牌的行程才能進入臨界區 這個演算法有兩個問題必須解決 如果令牌在傳送的途中遺失或是毀損了，必須要建立另一個新的令牌 如果系統中某一個行程出了問題無法運作，令牌勢必無法順利傳遞，必須馬上重建一個新的令牌傳遞環狀結構 令牌環演算法(續) 第十九章 分散式協調 事件順序 互斥 推選演算法 強勢演算法 環狀演算法 不可分割交易 並行控制 死結處理 摘要 推選演算法 二種選出一個行程擔任協調者的演算法 強勢演算法 環狀演算法 強勢演算法 強勢演算法的步驟如下 行程 P 送推選訊息給所有行程編號比行程 P 高的行程 如果在一定時間內沒有任何行程送反對訊息回來，則行程 P 就當選協調者，並送當選訊息通知所有的行程 如果有任何行程編號較高的行程回應反對訊息，則行程 P 放棄當協調者 強勢演算法(續) 環狀演算法 環狀演算法的步驟如下 當任何的行程發現協調者不再運作，就送出推選訊息，訊息內會包含一個行程編號的列表，並將自己的行程編號加入這個列表 當任何的行程收到這個推選訊息，也會將自己的行程編號加入列表，然後將此訊息傳給下一個行程 如果遇到傳送給下一個行程卻沒有回應的情況，則傳送給再下一個行程。 如果行程發現自己的行程編號已經在推選訊息的列表上，則此行程從列表上找出編號最大的行程當協調者，並把這個當選訊息傳送出去 環狀演算法(續) 第十九章 分散式協調 事件順序 互斥 推選演算法 不可分割交易 兩段式交付協定 兩段式交付協定的錯誤處理 並行控制 死結處理 摘要 不可分割交易 不可分割交易的觀念是