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