分布式系統(tǒng)-時(shí)間和全局狀態(tài)

1、時(shí)間和全局狀態(tài)時(shí)間和全局狀態(tài)時(shí)間和全局狀態(tài)n簡(jiǎn)介簡(jiǎn)介 n時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n同步物理時(shí)鐘同步物理時(shí)鐘n邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n全局狀態(tài)全局狀態(tài)n分布式調(diào)試分布式調(diào)試n小結(jié)小結(jié)簡(jiǎn)介簡(jiǎn)介n如何計(jì)時(shí)？n如何同步時(shí)鐘？n沒(méi)有物理時(shí)鐘能否確定事件的順序？簡(jiǎn)介簡(jiǎn)介n時(shí)間的重要性時(shí)間的重要性n需要精確度量審計(jì)電子商務(wù)n某些算法依賴(lài)于時(shí)鐘同步數(shù)據(jù)一致性維護(hù)、maken計(jì)算全局狀態(tài)事件排序n時(shí)間的復(fù)雜性時(shí)間的復(fù)雜性n節(jié)點(diǎn)具有獨(dú)立的物理時(shí)鐘n精確同步物理時(shí)鐘非常困難n全局狀態(tài)的捕獲全局狀態(tài)的捕獲n依賴(lài)于邏輯時(shí)鐘n邏輯時(shí)鐘與物理時(shí)鐘無(wú)必然聯(lián)系第第3 3章章 時(shí)間和全局狀態(tài)時(shí)間和全

2、局狀態(tài)n簡(jiǎn)介簡(jiǎn)介 n時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n同步物理時(shí)鐘同步物理時(shí)鐘n邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n全局狀態(tài)全局狀態(tài)n分布式調(diào)試分布式調(diào)試n小結(jié)小結(jié)時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n假設(shè)假設(shè)n每個(gè)進(jìn)程在單處理器上執(zhí)行n處理器之間不共享內(nèi)存n進(jìn)程之間通過(guò)消息進(jìn)行通信n進(jìn)程狀態(tài)進(jìn)程狀態(tài)n所有變量的值n相關(guān)的本地操作系統(tǒng)環(huán)境中的對(duì)象的值n事件事件n定義：一個(gè)通信動(dòng)作或進(jìn)程狀態(tài)轉(zhuǎn)換動(dòng)作n進(jìn)程歷史：,.,)(210iiiieeephistory時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n計(jì)算機(jī)時(shí)鐘計(jì)算機(jī)時(shí)鐘n晶體具有固定震蕩頻率n硬件時(shí)鐘：n軟件時(shí)鐘：n時(shí)鐘漂移時(shí)鐘漂移n

3、頻率不同n時(shí)鐘頻率隨溫度變化而有所差別n時(shí)鐘偏移不可避免時(shí)鐘偏移不可避免)(thi)()(thtCiiNetwork時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n時(shí)間分類(lèi)時(shí)間分類(lèi)n天文學(xué)時(shí)間天文學(xué)時(shí)間 -太陽(yáng)日：兩次連續(xù)的太陽(yáng)中天之間的時(shí)間間隔 -太陽(yáng)秒：1/86400個(gè)太陽(yáng)日n國(guó)際原子時(shí)間國(guó)際原子時(shí)間(TAI) -基于銫原子跳躍周期 -秒：9 192 631 770次跳躍周期n通用協(xié)調(diào)時(shí)間通用協(xié)調(diào)時(shí)間(UTC) -基于原子時(shí)間 -采用潤(rùn)秒，與天文時(shí)間保持一致第第3 3章章 時(shí)間和全局狀態(tài)時(shí)間和全局狀態(tài)n簡(jiǎn)介簡(jiǎn)介 n時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n同步物理時(shí)鐘同步物理時(shí)鐘n邏輯時(shí)間和邏輯

4、時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n全局狀態(tài)全局狀態(tài)n分布式調(diào)試分布式調(diào)試n小結(jié)小結(jié)同步物理時(shí)鐘同步物理時(shí)鐘n外部同步外部同步n采用權(quán)威的外部時(shí)間源n時(shí)鐘Ci在范圍D內(nèi)是準(zhǔn)確的n內(nèi)部同步內(nèi)部同步n無(wú)外部權(quán)威時(shí)間源,系統(tǒng)內(nèi)時(shí)鐘同步n時(shí)鐘Ci在范圍D內(nèi)是準(zhǔn)確的n關(guān)系關(guān)系 若P在范圍D內(nèi)外部同步,則P在范圍2D內(nèi)內(nèi)部同步NiDtCtSi,.,2 , 1,| )()(|NjiDtCtCji,.,2 , 1,| )()(|同步物理時(shí)鐘同步物理時(shí)鐘n時(shí)鐘正確性時(shí)鐘正確性n基于漂移率n基于單調(diào)性n基于混合條件 單調(diào)性+漂移率有界+同步點(diǎn)跳躍前進(jìn)n時(shí)鐘故障時(shí)鐘故障n崩潰故障: 時(shí)鐘完全停止滴答n隨機(jī)故障: 其它故障，如“

5、千年蟲(chóng)”問(wèn)題)(1 ()() ()(1 (tttHtHtt)() (tCtCtt同步物理時(shí)鐘同步物理時(shí)鐘n同步系統(tǒng)中的同步同步系統(tǒng)中的同步n假設(shè)條件 -已知時(shí)鐘漂移率范圍 -存在最大的消息傳輸延遲 -進(jìn)程每一步的執(zhí)行時(shí)間已知n方法 若一個(gè)進(jìn)程將時(shí)間t發(fā)送至另一個(gè)進(jìn)程，且消息傳輸時(shí)間的不確定性為u=maxmin，則接收進(jìn)程：t+min，則時(shí)鐘偏移至多為u t+max，則時(shí)鐘偏移可能為u t+(max+min)/2，則時(shí)鐘偏移至多為u/2同步物理時(shí)鐘同步物理時(shí)鐘nCristian方法方法n應(yīng)用條件應(yīng)用條件-存在時(shí)間服務(wù)器，可與外部時(shí)間源同步 -消息往返時(shí)間與系統(tǒng)所要求的精度相比足夠短n協(xié)議協(xié)議-進(jìn)

6、程p根據(jù)消息mr，mt計(jì)算消息往返時(shí)間Tround -根據(jù)服務(wù)器在mt中放置的時(shí)間t設(shè)置時(shí)鐘為：t+Tround/2mtp時(shí)間服務(wù)器Smr同步物理時(shí)鐘同步物理時(shí)鐘n精度分析精度分析若消息的最小傳輸時(shí)間為min，則精度為： (Tround/2 min)tt +Tround-mint +Tround/2t + mint +Tround同步物理時(shí)鐘同步物理時(shí)鐘nBerkeley算法算法n主機(jī)主機(jī)周期輪詢(xún)周期輪詢(xún)從屬機(jī)時(shí)間從屬機(jī)時(shí)間n主機(jī)通過(guò)消息往返時(shí)間估算從屬機(jī)的時(shí)間主機(jī)通過(guò)消息往返時(shí)間估算從屬機(jī)的時(shí)間與Cristian方法類(lèi)似n主機(jī)計(jì)算主機(jī)計(jì)算容錯(cuò)平均值容錯(cuò)平均值n主機(jī)發(fā)送每個(gè)從屬機(jī)的主機(jī)發(fā)送每個(gè)

7、從屬機(jī)的調(diào)整量調(diào)整量同步物理時(shí)鐘同步物理時(shí)鐘n網(wǎng)絡(luò)時(shí)間協(xié)議網(wǎng)絡(luò)時(shí)間協(xié)議(NTP)n設(shè)計(jì)目標(biāo)設(shè)計(jì)目標(biāo) -可外部同步 使得跨Internet的用戶(hù)能精確地與UTC同步 -高可靠性 可處理連接丟失，采用冗余服務(wù)器、路徑等 -擴(kuò)展性好 大量用戶(hù)可經(jīng)常同步，以抵消漂移率的影響 -安全性強(qiáng) 防止惡意或偶然的干擾同步物理時(shí)鐘同步物理時(shí)鐘n協(xié)議結(jié)構(gòu)協(xié)議結(jié)構(gòu) -層次結(jié)構(gòu) -主服務(wù)器直接與外部UTC同步 -同步子網(wǎng)可重新配置123233 同步子網(wǎng)結(jié)構(gòu)示例同步物理時(shí)鐘同步物理時(shí)鐘n同步模式同步模式 -組播 適用于高速LAN 準(zhǔn)確度較低，但效率高 -過(guò)程調(diào)用 與Cristian算法類(lèi)似 準(zhǔn)確度較低 -對(duì)稱(chēng)模式 保留時(shí)

8、序信息 準(zhǔn)確度最高同步物理時(shí)鐘同步物理時(shí)鐘n消息交換消息交換若消息m、m的實(shí)際傳輸時(shí)間分別為t、t；o為B時(shí)鐘相對(duì)于A時(shí)鐘的真正偏移， o為偏移估計(jì)，則 Ti-2 = Ti-3 + t + o , Ti = Ti-1 + t o 定義 oi=(Ti-2 Ti-3 + Ti-1 Ti)/2TiTi-1Ti-2Ti-3服務(wù)器 B服務(wù)器 A時(shí)間mm時(shí)間di=t+t=Ti-2 Ti-3+Ti Ti-1o=oi+(t-t)/2同步物理時(shí)鐘同步物理時(shí)鐘nNTP采用過(guò)濾離中趨勢(shì)算法，保留采用過(guò)濾離中趨勢(shì)算法，保留8個(gè)最近的個(gè)最近的，用以估算偏移用以估算偏移onNTP采用對(duì)等方選擇算法，可改變用于同步的對(duì)等方

9、采用對(duì)等方選擇算法，可改變用于同步的對(duì)等方 -優(yōu)先選擇層次較低的對(duì)等方 -優(yōu)先選擇過(guò)濾離中趨勢(shì)數(shù)值較低的對(duì)等方第第3 3章章 時(shí)間和全局狀態(tài)時(shí)間和全局狀態(tài)n簡(jiǎn)介簡(jiǎn)介 n時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n物理時(shí)鐘同步物理時(shí)鐘同步n邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n全局狀態(tài)全局狀態(tài)n分布式調(diào)試分布式調(diào)試n小結(jié)小結(jié)邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n邏輯時(shí)間的引入邏輯時(shí)間的引入n分布式系統(tǒng)中的物理時(shí)鐘無(wú)法完美同步分布式系統(tǒng)中的物理時(shí)鐘無(wú)法完美同步 -消息傳輸延時(shí)的不確定性n事件排序是眾多分布式算法的基石事件排序是眾多分布式算法的基石 -互斥算法 -死鎖檢測(cè)算法n缺乏全局時(shí)鐘缺乏全局時(shí)鐘

10、 -后發(fā)生的事件有可能賦予較早的時(shí)間標(biāo)記邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n邏輯時(shí)鐘邏輯時(shí)鐘n眾多應(yīng)用只要求所有節(jié)點(diǎn)具有眾多應(yīng)用只要求所有節(jié)點(diǎn)具有相同時(shí)間相同時(shí)間，該時(shí)間，該時(shí)間不一不一定與實(shí)際時(shí)間相同定與實(shí)際時(shí)間相同nLamport(1978)指出：不進(jìn)行交互的兩個(gè)進(jìn)程之間不需指出：不進(jìn)行交互的兩個(gè)進(jìn)程之間不需要時(shí)鐘同步要時(shí)鐘同步對(duì)于不需要交互的兩個(gè)進(jìn)程而言，即使沒(méi)有時(shí)鐘同步，也無(wú)法察覺(jué)，更不會(huì)產(chǎn)生問(wèn)題。n所有的進(jìn)程需要在時(shí)間的所有的進(jìn)程需要在時(shí)間的發(fā)生順序發(fā)生順序上上達(dá)成一致達(dá)成一致 如make程序邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n事件排序事件排序n“系統(tǒng)系統(tǒng)i中的事件中的事件a發(fā)生

11、在系統(tǒng)發(fā)生在系統(tǒng)j中的事件中的事件b之前之前”是不是不準(zhǔn)確的準(zhǔn)確的 -事件發(fā)生和觀察之間存在時(shí)延 -不同系統(tǒng)中的時(shí)鐘存在偏差n時(shí)間戳?xí)r間戳(Lamport 1978) -用于分布式系統(tǒng)中的事件排序 -與物理時(shí)鐘無(wú)關(guān) -實(shí)用高效，應(yīng)用廣泛邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n兩個(gè)基本事實(shí)兩個(gè)基本事實(shí) -同一進(jìn)程中的兩個(gè)事件存在關(guān)系“i” -任一消息的發(fā)送事件發(fā)生在該消息的接收事件之前n“發(fā)生在先發(fā)生在先(happens-before)” 關(guān)系定義關(guān)系定義 -若存在進(jìn)程pi滿(mǎn)足eie，則ee -對(duì)于任一消息m，存在send(m) recv(m) -若事件滿(mǎn)足ee 和ee ，則een并發(fā)關(guān)系定義并發(fā)

12、關(guān)系定義 XY 與 YX均不成立，則稱(chēng)事件X、Y是并發(fā)的，表示為X |Y邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n事件排序示例事件排序示例 - bc，cd和d f成立 - bf與ef均成立 -事件b和e無(wú)法比較，即b|ep1p2p3abcdefm1m2物理物理時(shí)間時(shí)間邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘nLamport時(shí)鐘時(shí)鐘n機(jī)制機(jī)制 -進(jìn)程維護(hù)一個(gè)單調(diào)遞增的軟件計(jì)數(shù)器，充當(dāng)邏輯時(shí)鐘 -用邏輯時(shí)鐘為事件添加時(shí)間戳 -按事件的時(shí)間戳大小為時(shí)間排序n邏輯時(shí)鐘修改規(guī)則邏輯時(shí)鐘修改規(guī)則 -進(jìn)程pi發(fā)出事件前，邏輯時(shí)鐘Li:=Li+1 -進(jìn)程pi發(fā)送消息m時(shí)，在m中添加時(shí)間戳t=Li -進(jìn)程pj在接收(m

13、,t)時(shí)，更新Li:=max(Lj,t)+1，給s事件recv(m)添加時(shí)間戳后發(fā)送給應(yīng)用程序abcdefm1m2213451p1p2p3物理時(shí)間邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘nLamport時(shí)鐘示例時(shí)鐘示例(一一) ab L(a)L(b) L(e)L(b) b e邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘 (a) 三個(gè)不同速率的時(shí)鐘三個(gè)不同速率的時(shí)鐘 (b) Lamport算法校正時(shí)鐘算法校正時(shí)鐘n Lamport時(shí)鐘示例時(shí)鐘示例(二二)邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘nLamport時(shí)鐘練習(xí)時(shí)鐘練習(xí)假設(shè)系統(tǒng)中只存在消息發(fā)送和接收事件，如下圖所示，請(qǐng)給出事件a-g的邏輯時(shí)鐘。邏輯時(shí)鐘 0

14、邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘nLamport時(shí)鐘練習(xí)時(shí)鐘練習(xí)答案答案邏輯時(shí)鐘：0144328657579邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n不同不同進(jìn)程產(chǎn)生的消息可能具有進(jìn)程產(chǎn)生的消息可能具有相同數(shù)值相同數(shù)值的的Lamport時(shí)間戳?xí)r間戳物理物理時(shí)間時(shí)間邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n基于基于Lamport時(shí)間戳的事件排序時(shí)間戳的事件排序-總結(jié)總結(jié)n算法不依賴(lài)于事件發(fā)生的真實(shí)時(shí)間算法不依賴(lài)于事件發(fā)生的真實(shí)時(shí)間n與真實(shí)物理時(shí)間中事件的發(fā)生順序可能不一致與真實(shí)物理時(shí)間中事件的發(fā)生順序可能不一致基于基于Lamport時(shí)間戳的排序中，在時(shí)刻時(shí)間戳的排序中，在時(shí)刻(2,1)發(fā)生的事件發(fā)生

15、比在時(shí)發(fā)生的事件發(fā)生比在時(shí)刻刻（2，2）發(fā)生的事件要早，然而在真實(shí)物理時(shí)間中可能恰好相反。發(fā)生的事件要早，然而在真實(shí)物理時(shí)間中可能恰好相反。邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘nLamport時(shí)鐘不具備性質(zhì)：若時(shí)鐘不具備性質(zhì)：若L(A) L(B)則則ABn沒(méi)有捕獲事件的因果關(guān)系沒(méi)有捕獲事件的因果關(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我們無(wú)法準(zhǔn)確確定我們無(wú)法準(zhǔn)確確定r的先后關(guān)系：的先后關(guān)系： C(a) C(r) a ra 是節(jié)點(diǎn)是節(jié)點(diǎn)A發(fā)布的文章發(fā)布的文章r 是節(jié)點(diǎn)是節(jié)點(diǎn)B對(duì)文章對(duì)文章a的評(píng)論的評(píng)論 全序邏輯時(shí)鐘全序邏輯時(shí)鐘n引入進(jìn)程標(biāo)示符創(chuàng)

16、建事件的全序關(guān)系引入進(jìn)程標(biāo)示符創(chuàng)建事件的全序關(guān)系n若若e、e分別為進(jìn)程分別為進(jìn)程pi、pj中發(fā)生的事件，則其全局中發(fā)生的事件，則其全局邏輯時(shí)間戳分別為邏輯時(shí)間戳分別為(Ti,i)、(Tj,j)。nee TiTj | Ti=Tj & ijn系統(tǒng)中各個(gè)事件系統(tǒng)中各個(gè)事件Lamport時(shí)間戳均不相同時(shí)間戳均不相同向量時(shí)鐘向量時(shí)鐘n克服Lamport時(shí)鐘的缺點(diǎn)：若L(e) L(e)不能推出則ee。n每個(gè)進(jìn)程維護(hù)它自己的向量時(shí)鐘VinVC1:初始情況下，Vij=0,i,j=1,2,.N.nVC2:在pi給事件加時(shí)間戳之前，設(shè)置Vii= Vii+1。nVC3:pi在它發(fā)送的每個(gè)消息中包括tVi。n

17、VC4：當(dāng)pi接收到消息中的時(shí)間戳t時(shí)，設(shè)置Vij=max(Vij,tj),j=1,2,.,N。向量時(shí)鐘向量時(shí)鐘abcdefm1m2(2,0,0)(1,0,0)(2,1,0)(2,2,0)(2,2,2)(0,0,1)p1p2p3Physical time 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

18、,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í)鐘向量時(shí)鐘向量時(shí)鐘向量時(shí)鐘n V1 = V2, iff V1i = V2i, i = 1, , nn V1 V2, iff V1i V2i, i = 1, , nn V1 V2, iff V1 V2 & j (1 j n & V1j V2j)n V1 is concurrent with V2iff not (V1 V2 OR V2 V1)第第3 3章章 時(shí)間和全

19、局狀態(tài)時(shí)間和全局狀態(tài)n簡(jiǎn)介簡(jiǎn)介 n時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n同步物理時(shí)鐘同步物理時(shí)鐘n邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n全局狀態(tài)全局狀態(tài)n分布式調(diào)試分布式調(diào)試n小結(jié)小結(jié)全局狀態(tài)全局狀態(tài)n觀察全局狀態(tài)的必要性觀察全局狀態(tài)的必要性n分布式無(wú)用單元的收集分布式無(wú)用單元的收集 -基于對(duì)象的引用計(jì)數(shù) -必須考慮信道和進(jìn)程的狀態(tài)n分布式死鎖檢測(cè)分布式死鎖檢測(cè) 觀察系統(tǒng)中的“等待”關(guān)系圖中是否存在循環(huán)p1消息無(wú)用對(duì)象對(duì)象引用p2等待等待p1p2n分布式終止檢測(cè)分布式終止檢測(cè) 與進(jìn)程的狀態(tài)有關(guān)“主動(dòng)”或“被動(dòng)”n分布式調(diào)試分布式調(diào)試 需要收集同一時(shí)刻系統(tǒng)中分布式變量的數(shù)值全局狀態(tài)全局狀態(tài)激

20、活被動(dòng)的p1p2被動(dòng)的全局狀態(tài)全局狀態(tài)n全局狀態(tài)和一致割集全局狀態(tài)和一致割集n觀察進(jìn)程集的狀態(tài)觀察進(jìn)程集的狀態(tài)全局狀態(tài)非常困難全局狀態(tài)非常困難根源：缺乏全局時(shí)間n進(jìn)程的歷史進(jìn)程的歷史hi = n進(jìn)程歷史的有限前綴進(jìn)程歷史的有限前綴hi k= n全局歷史全局歷史單個(gè)進(jìn)程歷史的并集單個(gè)進(jìn)程歷史的并集H = h1 h2 hN全局狀態(tài)全局狀態(tài)n進(jìn)程狀態(tài)進(jìn)程狀態(tài) sik : 進(jìn)程pi在第k個(gè)事件發(fā)生之前的狀態(tài)n全局狀態(tài)全局狀態(tài)單個(gè)進(jìn)程狀態(tài)的集合單個(gè)進(jìn)程狀態(tài)的集合S = (s1, s2, sN)n割集割集系統(tǒng)全局歷史的子集系統(tǒng)全局歷史的子集C = n割集的一致性割集的一致性割集C是一致的: 對(duì)于所有事件e

21、C, f e f C全局狀態(tài)全局狀態(tài)n割集示例割集示例m1m2p1p2物理時(shí)間物理時(shí)間e10一致的割集不一致的割集e11e12e13e20e21e22全局狀態(tài)全局狀態(tài)n一致的全局狀態(tài)一致的全局狀態(tài)對(duì)應(yīng)于一致割集的狀態(tài)對(duì)應(yīng)于一致割集的狀態(tài)S0 S1 S2 n走向走向(run) -全局歷史中所有事件的全序 -與每個(gè)本地歷史順序一致 -不是所有的走向都經(jīng)歷一致的全局狀態(tài)不是所有的走向都經(jīng)歷一致的全局狀態(tài)n線性化走向線性化走向 -所有的線性化走向只經(jīng)歷一致的全局狀態(tài)所有的線性化走向只經(jīng)歷一致的全局狀態(tài) -若存在一個(gè)經(jīng)過(guò)S和S的線性化走向，則狀態(tài)S是從S可達(dá)全局狀態(tài)全局狀態(tài)nChandy和和Lampor

22、t的的“快照快照”算法算法n目的目的捕獲一致的全局狀態(tài)n假設(shè)假設(shè) - 進(jìn)程和通道均不會(huì)出現(xiàn)故障 - 單向通道，提供FIFO順序的消息傳遞 - 進(jìn)程之間存在全連通關(guān)系 - 任一進(jìn)程可在任一時(shí)間開(kāi)始全局拍照 - 拍照時(shí)，進(jìn)程可繼續(xù)執(zhí)行，并發(fā)送和接收消息全局狀態(tài)全局狀態(tài)n算法基本思想算法基本思想 - 接入通道+外出通道 - 進(jìn)程狀態(tài)+通道狀態(tài) - 標(biāo)記消息 標(biāo)記接收規(guī)則：強(qiáng)制進(jìn)程在記錄下自己的狀態(tài)之后但在它們發(fā)送其他消息前發(fā)送一個(gè)標(biāo)記。 標(biāo)記發(fā)送規(guī)則：強(qiáng)制沒(méi)有記錄狀態(tài)的進(jìn)程去記錄狀態(tài)全局狀態(tài)全局狀態(tài)n算法偽碼算法偽碼(一一) 進(jìn)程pi的標(biāo)記接收規(guī)則 pi接收通道c上的標(biāo)記消息： if (pi還沒(méi)有記

23、錄它的狀態(tài)) pi記錄它的進(jìn)程狀態(tài)； 將c的狀態(tài)記成空集； 開(kāi)始記錄從其他接入通道上到達(dá)的消息 else pi把c的狀態(tài)記錄到從保留它的狀態(tài)以來(lái)它 在c上接收到的消息集合中 end if全局狀態(tài)全局狀態(tài)n算法偽碼算法偽碼(二二) 進(jìn)程pi的標(biāo)記發(fā)送規(guī)則 在pi記錄了它的狀態(tài)之后，對(duì)每個(gè)外出通道c: (在pi從c上發(fā)送任何其他消息前) pi在c上發(fā)送一個(gè)消息標(biāo)記全局狀態(tài)全局狀態(tài)n算法示例算法示例 - 兩個(gè)進(jìn)程p1、p2進(jìn)行交易，每件10$ - 初始狀態(tài) 進(jìn)程p2已經(jīng)收到5件商品的定單，它將馬上分發(fā)給p1 p1p2c2c1帳戶(hù)窗口部件$1000(none)帳戶(hù)窗口部件$502000全局狀態(tài)全局狀態(tài)

24、最后狀態(tài)：最后狀態(tài)： P1:; p2:; c1:; c2:p1(空)1. 全局狀態(tài) S0p1p1p1c2c1(空)2. 全局狀態(tài) S13. 全局狀態(tài) S24. 全局狀態(tài) S3p2p2p2p2c2c2c2c1c1c1(定單10，$100)，M(空)(空)(定單10，$100)，M(五個(gè)窗口部件)M=標(biāo)記信息)(定單10，$100)全局狀態(tài)全局狀態(tài)n算法終止算法終止 - 假設(shè)：一個(gè)進(jìn)程已經(jīng)收到了一個(gè)標(biāo)記信息，在有限的時(shí)間內(nèi)記錄了它的狀態(tài)，并在有限的時(shí)間里通過(guò)每個(gè)外出通道發(fā)送了標(biāo)記信息 - 若存在一條從進(jìn)程pi到進(jìn)程pj的信道和進(jìn)程的路徑，那么pi記錄它的狀態(tài)之后的有限時(shí)間內(nèi)pj將記錄它的狀態(tài) -

25、進(jìn)程和通道圖是強(qiáng)連接的，因此在一些進(jìn)程記錄它的狀態(tài)之后的有限時(shí)間內(nèi)，所有進(jìn)程將記錄它們的狀態(tài)和節(jié)入通道的狀態(tài)。全局狀態(tài)全局狀態(tài)n算法一致性算法一致性 ei、ej分別為進(jìn)程pi、pj中的事件，且ei ej則我們有: 若ej C ei C，其中C為一個(gè)割集。即如果ej在pj記錄它的狀態(tài)之前發(fā)生，那么ei必須在pi記錄它的狀態(tài)之前發(fā)生.證明思路如下： - i=j時(shí)，顯然成立 - ij時(shí)，反證法第第3 3章章 時(shí)間和全局狀態(tài)時(shí)間和全局狀態(tài)n簡(jiǎn)介簡(jiǎn)介 n時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n物理時(shí)鐘同步物理時(shí)鐘同步n邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n全局狀態(tài)全局狀態(tài)n分布式調(diào)試分布式調(diào)試n小結(jié)小

26、結(jié)分布式調(diào)試分布式調(diào)試n目的目的對(duì)系統(tǒng)實(shí)際執(zhí)行中的暫態(tài)作出判斷n例子例子n安全條件檢查 xi為進(jìn)程pi的變量(i=1,2,)，安全條件為|xi-xj| n控制系統(tǒng)所有閥門(mén)在某些時(shí)間是否全部處于開(kāi)啟狀態(tài)分布式調(diào)試分布式調(diào)試n方法方法n監(jiān)控器進(jìn)程收集進(jìn)程狀態(tài)信息n全局狀態(tài)謂詞的判斷 -可能的：存在一個(gè)一致的全局狀態(tài)S，H的一個(gè)線性化走向經(jīng)歷了這個(gè)全局狀態(tài)S，而且該S使得(s) 為T(mén)rue。 -明確的：對(duì)于H的所有線性化走向L，存在L經(jīng)歷的一個(gè)一致的全局狀態(tài)S，而且該S使得(s) 為T(mén)rue。分布式調(diào)試分布式調(diào)試n觀察一致的全局狀態(tài)觀察一致的全局狀態(tài)n進(jìn)程的狀態(tài)信息附有向量時(shí)鐘值n全局狀態(tài)的一致性判

27、斷CGS條件 設(shè)S=(s1,s2,sN)是從監(jiān)控器進(jìn)程接收到的狀態(tài)信息中得出的全局狀態(tài)，V(si)是從pi接收到的狀態(tài)si的向量時(shí)間戳，則S是一致的全局狀態(tài)當(dāng)且僅當(dāng)： V(si)i=V(sj)i (i,j = 1,2, N)即若一個(gè)進(jìn)程的狀態(tài)依賴(lài)于另一個(gè)進(jìn)程的狀態(tài)，則全局狀態(tài)也包含了它所以來(lái)的狀態(tài)。分布式調(diào)試分布式調(diào)試n全局狀態(tài)示例m1m2p1p2物理時(shí)間 Cut C1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1= 1x1= 100 x1= 105x2= 100 x2= 95x2= 90 x1= 90Cut C2Sij=在進(jìn)程發(fā)生事件i以及在進(jìn)程發(fā)生事件j之后的全

28、局狀態(tài)S00S10S20S21S30S31S32S22S23S33S43層次 01234567分布式調(diào)試分布式調(diào)試n一致全局狀態(tài)網(wǎng)格分布式調(diào)試分布式調(diào)試n判定可能的判定可能的 從初始狀態(tài)考試，遍歷可達(dá)狀態(tài)的網(wǎng)格。L:=0;States:=(s01, s02, , s0N);while (對(duì)所有可能的SStates，(s)=False) L:=L+1; Reachable:=S: H中從一些SStates可到達(dá)的狀態(tài)level(S)=L; States:=Reachable;end while輸出“可能的”; ? 層次 012345FFFFTFF= (s)=False); T=(s)=True)

29、分布式調(diào)試分布式調(diào)試n值判定示例 在第層的狀態(tài)為T(mén)rue明確的在第層的狀態(tài)為False可能的分布式調(diào)試分布式調(diào)試n異步系統(tǒng)異步系統(tǒng)開(kāi)銷(xiāo)很大，需要作O(k)次比較。n同步系統(tǒng)同步系統(tǒng)物理時(shí)鐘：|Ci(t) Cj(t) |D，即在范圍D內(nèi)同步。n同步系統(tǒng)中的算法改進(jìn)同步系統(tǒng)中的算法改進(jìn)n消息中同時(shí)攜帶物理時(shí)間戳和向量時(shí)間戳n測(cè)試條件 V(si)i V(si)i ，且si和sj能在同一時(shí)間發(fā)生第第3 3章章 時(shí)間和全局狀態(tài)時(shí)間和全局狀態(tài)n簡(jiǎn)介簡(jiǎn)介 n時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)鐘、事件和進(jìn)程狀態(tài)n物理時(shí)鐘同步物理時(shí)鐘同步n邏輯時(shí)間和邏輯時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘n全局狀態(tài)全局狀態(tài)n分布式調(diào)試分布式調(diào)試n小結(jié)小結(jié)小結(jié)小結(jié)n時(shí)鐘偏移和時(shí)鐘