時(shí)間和全局狀態(tài)ppt課件(編輯修改稿)
2025-05-27 18:21 本頁面
【文章內(nèi)容簡(jiǎn)介】 輯時(shí)鐘n Lamport時(shí)鐘不具備性質(zhì)：若 L(A) L(B)則 A?Bn 沒有捕獲事件的因果關(guān)系 節(jié)點(diǎn) B發(fā)布一篇文章并傳送給節(jié)點(diǎn) A和 C。節(jié)點(diǎn) A就此發(fā)表評(píng)論并傳送給節(jié)點(diǎn) B和 C。araarr我們無法準(zhǔn)確確定 r的先后關(guān)系： C(a) C(r) a ?ra 是節(jié)點(diǎn) A發(fā)布的文章r 是節(jié)點(diǎn) B對(duì)文章 a的評(píng)論 35全序邏輯時(shí)鐘n 引入進(jìn)程標(biāo)示符創(chuàng)建事件的全序關(guān)系n 若 e、 e’分別為進(jìn)程 pi、 pj中發(fā)生的事件，則其全局邏輯時(shí)間戳分別為 (Ti,i)、 (Tj,j)。n e?e’ TiTj || Ti=Tj amp。amp。 ijn 系統(tǒng)中各個(gè)事件 Lamport時(shí)間戳均不相同36向量時(shí)鐘n 克服 Lamport時(shí)鐘的缺點(diǎn)： 若 L(e) L(e’)不能推出則e?e’。n 每個(gè)進(jìn)程維護(hù)它自己的向量時(shí)鐘 Vin VC1:初始情況下， Vi[j]=0,i,j=1,2,...N.n VC2:在 pi給事件加時(shí)間戳之前，設(shè)置 Vi[i]= Vi[i]+1。n VC3:pi在它發(fā)送的每個(gè)消息中包括 t＝ Vi。n VC4：當(dāng) pi接收到消息中的時(shí)間戳 t時(shí)，設(shè)置Vi[j]=max(Vi[j],t[j]),j=1,2,...,N。取兩個(gè)向量時(shí)間戳的最大值稱為 合并操作 。 37向量時(shí)鐘38 Host 1Host 2Host 3Host 40,0,0,0Vector logical clockMessage(vector timestamp)Physical Time0,0,0,00,0,0,00,0,0,0(1,0,0,0)1,0,0,01,1,0,02,0,0,02,0,1,0(2,0,0,0)2,0,2,02,0,2,1(2,0,2,0)1,2,0,02,2,3,0(1,2,0,0)4,0,2,24,2,4,2(4,0,2,2)2,0,2,23,0,2,2(2,0,2,2)2,0,2,34,2,5,3(2,0,2,3)n,m,p,q向量時(shí)鐘39向量時(shí)鐘n V1 = V2, iff V1[i] = V2[i], i = 1, … , nn V1 V2, iff V1[i] V2[i], i = 1, … , nn V1 V2, iff V1 V2 amp。 ? j (1 j n amp。 V1[j] V2[j])n V1 is concurrent with V2iff not (V1 V2 OR V2 V1)40第 3章 時(shí)間和全局狀態(tài)n 簡(jiǎn)介 n 時(shí)鐘、事件和進(jìn)程狀態(tài)n 同步物理時(shí)鐘n 邏輯時(shí)間和邏輯時(shí)鐘n 全局狀態(tài)n 分布式調(diào)試n 小結(jié)41全局狀態(tài)n 觀察全局狀態(tài)的必要性n 分布式無用單元的收集 基于對(duì)象的引用計(jì)數(shù) 必須考慮信道和進(jìn)程的狀態(tài)n 分布式死鎖檢測(cè) 觀察系統(tǒng)中的 “等待 ”關(guān)系圖中是否存在循環(huán)p1消息無用對(duì)象對(duì)象引用p2等待等待p1 p242n 分布式終止檢測(cè) 與進(jìn)程的狀態(tài)有關(guān) ——“ 主動(dòng) ”或 “被動(dòng) ”n 分布式調(diào)試 需要收集同一時(shí)刻系統(tǒng)中分布式變量的數(shù)值全局狀態(tài)激活被動(dòng)的p1 p2被動(dòng)的43全局狀態(tài)n 全局狀態(tài)和一致割集n 觀察進(jìn)程集的狀態(tài) —— 全局狀態(tài)非常困難 根源：缺乏全局時(shí)間n 進(jìn)程的歷史 hi = ei0, ei1, ei2 … n 進(jìn)程歷史的 有限前綴 hi k= ei0, ei1, … , eikn 全局歷史 —— 單個(gè)進(jìn)程歷史 的并集 H = h1 ? h2 ?… ? hN44全局狀態(tài)n 進(jìn)程狀態(tài) sik : 進(jìn)程 pi在第 k個(gè)事件發(fā)生之前的狀態(tài)n 全局狀態(tài) —— 單個(gè)進(jìn)程狀態(tài)的集合 S = (s1, s2, … sN)n 割集 —— 系統(tǒng)全局歷史的子集 C = h1c1, h2c2… h3c3 n 割集的 一致性割集 C是一致的 : 對(duì)于所有事件 e?C , f ? e ? f ? C45全局狀態(tài)n 割集示例m1 m2p1p2 物理時(shí)間e10一致的割集不一致的割集e11 e12 e13e20 e21 e2246全局狀態(tài)n 一致的全局狀態(tài) —— 對(duì)應(yīng)于一致割集的狀態(tài) S0 ? S1 ? S2 ? …47全局狀態(tài)n 走向 (run) 全局歷史中所有事件的全序 與每個(gè)本地歷史順序一致 不是所有的走向都經(jīng)歷一致的全局狀態(tài)48全局狀態(tài)n 線性化走向 所有的線性化走向只經(jīng)歷一致的全局狀態(tài) 若存在一個(gè)經(jīng)過 S和 S’的線性化走向，則狀態(tài) S’是從 S可達(dá)49全局狀態(tài)n Chandy和 Lamport的 “快照 ”算法n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1