時間和全局狀態(tài)ppt課件-資料下載頁
2025-04-30 18:21本頁面
【正文】 有 線 性化走向 L，存在 L經(jīng)歷的一個一致的全局狀 態(tài) S，而且 該 S使得 ?(s) 為 True。61分布式調(diào)試n 觀察一致的全局狀態(tài)n 進程的狀態(tài)信息附有向量時鐘值n 全局狀 態(tài) 的一致性判斷 —— CGS條件 設 S=(s1,s2,… ,sN)是從監(jiān)控器進程接收到的狀態(tài)信息中得出的全局狀態(tài)， V(si)是從 pi接收到的狀態(tài) si的向量時間戳，則 S是一致的全局狀態(tài)當且僅當： V(si)[i]=V(sj)[i] (i,j = 1,2,…, N) 即若一個 進 程的狀 態(tài) 依 賴 于另一個 進 程的狀 態(tài) ，則 全局狀 態(tài) 也包含了它所依 賴 的狀 態(tài) 。62分布式調(diào)試n 全局狀態(tài)示例m1 m2p1p2 物理時間 Cut C1(1,0) (2,0) (4,3)(2,1) (2,2) (2,3)(3,0)x1= 1 x1= 100 x1= 105x2= 100 x2= 95 x2= 90x1= 90Cut C263Sij=在進程１發(fā)生事件 i以及在進程２發(fā)生事件 j之后的全局狀態(tài)S00S10S20S21S30S31S32S22S23S33S43層次 01234567分布式調(diào)試n 一致全局狀態(tài)網(wǎng)格64分布式調(diào)試n 判定可能的 ? 從初始狀 態(tài) 開始，遍 歷 可達狀 態(tài) 的網(wǎng)格。L:=0。States:={(s01, s02, …, s 0N)}。while (對 所有可能的 S∈ States， ?(s)=False) L:=L+1。 Reachable:={S’: H中從一些 S∈ States可到達的狀 態(tài) ∧ level(S’)=L}。 States:=Reachable。end while輸 出 “可能的 ?”。65 ? –層次 012345FFFF TFF= (?(s)=False)。 T=(?(s)=True)分布式調(diào)試n ?值判定示例 ?在第 4層的狀態(tài)為 True＝ 》 明確的 ??在第５層的狀態(tài)為 False＝ 》 可能的 ?66分布式調(diào)試n 異步系統(tǒng) 開銷很大，需要作 O(kＮ )次比較。 n 同步系統(tǒng) 物理時鐘： |Ci(t) － Cj(t) |D，即在范圍 D內(nèi)同步。n 同步系統(tǒng)中的算法改進n 消息中同時攜帶物理時間戳和向量時間戳n 測試條件 V(si)[i] ≧ V(sj)[i] ，且 si和 sj能在同一時間發(fā)生67第 3章 時間和全局狀態(tài)n 簡介 n 時鐘、事件和進程狀態(tài)n 物理時鐘同步n 邏輯時間和邏輯時鐘n 全局狀態(tài)n 分布式調(diào)試n 小結68小結n 時鐘偏移和時鐘漂移n 物理時鐘同步n Cristian方法n Berkeley方法n 網(wǎng)絡時間協(xié)議n 邏輯時間n 發(fā)生在先關系n Lamport時間戳n 向量時鐘69小結n 全局狀態(tài)n 一致割集，一致全局狀態(tài)n “快照 ”算法n 分布式調(diào)試n 狀態(tài)收集n 判定可能的 ?和 明確的 ?70作業(yè)1. DatabasesRUs runs a cluster of three servers A, B, and C, which municate with one another. You are told that the current clock skews between server pairs are as follows: AB: 3 ms。 BC: 1 ms。 CA: 4 ms. Further, you are told that correctness in the database requires that no two server clocks be more than 30ms apart. If each of the servers has an absolute clock drift of 2 ms per minute, how many minimum (., worstcase) minutes can the cluster go without running a synchronization algorithm among its servers?71作業(yè)4. a, b, and c are events and no two events belong to the same process. Prove or disprove (give counterexample) the following:(a)a is concurrent with b and b is before c implies that a is before c.(b)a is concurrent with b and b is concurrent with c implies that a is concurrent with c.
教學課件相關推薦
鄂ICP備17016276號-1