-時(shí)間和全局狀態(tài)-文庫吧在線文庫
【正文】 rrent 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. ? 靜夜四無鄰，荒居舊業(yè)貧。 Reachable:={S’: H中從一些 S∈ States可到達(dá)的狀態(tài) ∧ level(S’)=L}。 全局狀態(tài) ? 算法一致性 ei、 ej分別為進(jìn)程 pi、 pj中的事件，且 ei ? ej則我們有 : 若 ej ? C? ei ? C，其中 C為一個(gè)割集。 ? 每個(gè)進(jìn)程維護(hù)它自己的向量時(shí)鐘 Vi ? VC1:初始情況下， Vi[j]=0,i,j=1,2,...N. ? VC2:在 pi給事件加時(shí)間戳之前，設(shè)置 Vi[i]= Vi[i]+1。第 3章 時(shí)間和全局狀態(tài) 第 3章 時(shí)間和全局狀態(tài) ? 簡(jiǎn)介 ? 時(shí)鐘、事件和進(jìn)程狀態(tài) ? 同步物理時(shí)鐘 ? 邏輯時(shí)間和邏輯時(shí)鐘 ? 全局狀態(tài) ? 分布式調(diào)試 ? 小結(jié) 簡(jiǎn)介 ? 如何計(jì)時(shí)？ ? 如何同步時(shí)鐘？ ? 沒有物理時(shí)鐘能否確定事件的順序？ 簡(jiǎn)介 ? 時(shí)間的重要性 ? 需要精確度量 ——審計(jì)電子商務(wù) ? 某些算法依賴于時(shí)鐘同步 ——數(shù)據(jù)一致性維護(hù)、 make ? 計(jì)算全局狀態(tài) ——事件排序 ? 時(shí)間的復(fù)雜性 ? 節(jié)點(diǎn)具有獨(dú)立的物理時(shí)鐘 ? 精確同步物理時(shí)鐘非常困難 ? 全局狀態(tài)的捕獲 ? 依賴于邏輯時(shí)鐘 ? 邏輯時(shí)鐘與物理時(shí)鐘無必然聯(lián)系 時(shí)鐘、事件和進(jìn)程狀態(tài) ? 時(shí)間分類 ? 天文學(xué)時(shí)間 太陽日：兩次連續(xù)的太陽中天之間的時(shí)間間隔 太陽秒： 1/86400個(gè)太陽日 ? 國(guó)際原子時(shí)間 (TAI) 基于銫原子跳躍周期 秒： 9 192 631 770次跳躍周期 ? 通用協(xié)調(diào)時(shí)間 (UTC) 基于原子時(shí)間 采用潤(rùn)秒，與天文時(shí)間保持一致 第 3章 時(shí)間和全局狀態(tài) ? 簡(jiǎn)介 ? 時(shí)鐘、事件和進(jìn)程狀態(tài) ? 同步物理時(shí)鐘 ? 邏輯時(shí)間和邏輯時(shí)鐘 ? 全局狀態(tài) ? 分布式調(diào)試 ? 小結(jié) 時(shí)鐘、事件和進(jìn)程狀態(tài) ? 假設(shè) ? 每個(gè)進(jìn)程在單處理器上執(zhí)行 ? 處理器之間不共享內(nèi)存 ? 進(jìn)程之間通過消息進(jìn)行通信 ? 進(jìn)程狀態(tài) ? 所有變量的值 ? 相關(guān)的本地操作系統(tǒng)環(huán)境中的對(duì)象的值 ? 事件 ? 定義：一個(gè)通信動(dòng)作或進(jìn)程狀態(tài)轉(zhuǎn)換動(dòng)作 ? 進(jìn)程歷史： ??? , ...,)( 210 iiii eeephistory時(shí)鐘、事件和進(jìn)程狀態(tài) ? 計(jì)算機(jī)時(shí)鐘 ? 晶體具有固定震蕩頻率 ? 硬件時(shí)鐘： ? 軟件時(shí)鐘： ? 時(shí)鐘漂移 ? 頻率不同 ? 時(shí)鐘頻率隨溫度變化而有所差別 ? 時(shí)鐘偏移不可避免 ? In fact,the effect of clock skew is the main reason why clock offsets keep drifting away. Novel clock phase offset……IEEE Transactions on Commnunications,Vol55, )(thi ?? ?? )()( thtC iiN e t w o rk第 3章 時(shí)間和全局狀態(tài) ? 簡(jiǎn)介 ? 時(shí)鐘、事件和進(jìn)程狀態(tài) ? 同步物理時(shí)鐘 ? 邏輯時(shí)間和邏輯時(shí)鐘 ? 全局狀態(tài) ? 分布式調(diào)試 ? 小結(jié) 同步物理時(shí)鐘 ? 外部同步 ? 采用權(quán)威的外部時(shí)間源 ? 時(shí)鐘 Ci在范圍 D內(nèi)是準(zhǔn)確的 ? 內(nèi)部同步 ? 無外部權(quán)威時(shí)間源 ,系統(tǒng)內(nèi)時(shí)鐘同步 ? 時(shí)鐘 Ci在范圍 D內(nèi)是準(zhǔn)確的 ? 關(guān)系 若 P在范圍 D內(nèi)外部同步 ,則 P在范圍 2D內(nèi)內(nèi)部同步 NiDtCtS i ,...,2,1,|)()(| ??? NjiDtCtC ji ,.. .,2,1,|)()(| ???同步物理時(shí)鐘 ? Cristian方法 (適用于只有一臺(tái)機(jī)器有 WWV接收器 ) ? 應(yīng)用條件 存在時(shí)間服務(wù)器，可與外部時(shí)間源同步 消息往返時(shí)間與系統(tǒng)所要求的精度相比足夠短 ? 協(xié)議 進(jìn)程 p根據(jù)消息 mr， mt計(jì)算消息往返時(shí)間 Tround 根據(jù)服務(wù)器在 mt中放置的時(shí)間 t設(shè)置時(shí)鐘為： t+Tround/2 mt p 時(shí)間服務(wù)器 S mr 同步物理時(shí)鐘 ? Berkeley算法（沒有 WWV接收器） ? 主機(jī) 周期輪詢 從屬機(jī)時(shí)間 ? 主機(jī)通過消息往返時(shí)間估算從屬機(jī)的時(shí)間 與 Cristian方法類似 ? 主機(jī)計(jì)算 容錯(cuò)平均值 ? 主機(jī)發(fā)送每個(gè)從屬機(jī)的 調(diào)整量 同步物理時(shí)鐘 ? 網(wǎng)絡(luò)時(shí)間協(xié)議 (NTP) ? 設(shè)計(jì)目標(biāo) 可外部同步 使得跨 Inter的用戶能精確地與 UTC同步 高可靠性 可處理連接丟失，采用冗余服務(wù)器、路徑等 擴(kuò)展性好 大量用戶可經(jīng)常同步，以抵消漂移率的影響 安全性強(qiáng) 防止惡意或偶然的干擾 同步物理時(shí)鐘 ? 協(xié)議結(jié)構(gòu) 層次結(jié)構(gòu) 主服務(wù)器直接與外部 UTC同步 同步子網(wǎng)可重新配置 1 2 3 2 3 3 同步子網(wǎng)結(jié)構(gòu)示例 第 3章 時(shí)間和全局狀態(tài) ? 簡(jiǎn)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1