時間和全局狀態(tài)ppt課件(完整版)
【正文】 n 時鐘、事件和進程狀態(tài)n 同步物理時鐘n 邏輯時間和邏輯時鐘n 全局狀態(tài)n 分布式調(diào)試n 小結(jié)41全局狀態(tài)n 觀察全局狀態(tài)的必要性n 分布式無用單元的收集 基于對象的引用計數(shù) 必須考慮信道和進程的狀態(tài)n 分布式死鎖檢測 觀察系統(tǒng)中的 “等待 ”關(guān)系圖中是否存在循環(huán)p1消息無用對象對象引用p2等待等待p1 p242n 分布式終止檢測 與進程的狀態(tài)有關(guān) ——“ 主動 ”或 “被動 ”n 分布式調(diào)試 需要收集同一時刻系統(tǒng)中分布式變量的數(shù)值全局狀態(tài)激活被動的p1 p2被動的43全局狀態(tài)n 全局狀態(tài)和一致割集n 觀察進程集的狀態(tài) —— 全局狀態(tài)非常困難 根源：缺乏全局時間n 進程的歷史 hi = ei0, ei1, ei2 … n 進程歷史的 有限前綴 hi k= ei0, ei1, … , eikn 全局歷史 —— 單個進程歷史 的并集 H = h1 ? h2 ?… ? hN44全局狀態(tài)n 進程狀態(tài) sik : 進程 pi在第 k個事件發(fā)生之前的狀態(tài)n 全局狀態(tài) —— 單個進程狀態(tài)的集合 S = (s1, s2, … sN)n 割集 —— 系統(tǒng)全局歷史的子集 C = h1c1, h2c2… h3c3 n 割集的 一致性割集 C是一致的 : 對于所有事件 e?C , f ? e ? f ? C45全局狀態(tài)n 割集示例m1 m2p1p2 物理時間e10一致的割集不一致的割集e11 e12 e13e20 e21 e2246全局狀態(tài)n 一致的全局狀態(tài) —— 對應(yīng)于一致割集的狀態(tài) S0 ? S1 ? S2 ? …47全局狀態(tài)n 走向 (run) 全局歷史中所有事件的全序 與每個本地歷史順序一致 不是所有的走向都經(jīng)歷一致的全局狀態(tài)48全局狀態(tài)n 線性化走向 所有的線性化走向只經(jīng)歷一致的全局狀態(tài) 若存在一個經(jīng)過 S和 S’的線性化走向，則狀態(tài) S’是從 S可達49全局狀態(tài)n Chandy和 Lamport的 “快照 ”算法n 目的 捕獲一致的全局狀態(tài)n 假設(shè) 進程和通道均不會出現(xiàn)故障 單向通道，提供 FIFO順序的消息傳遞 進程之間存在全連通關(guān)系 任一進程可在任一時間開始全局拍照 拍照時，進程可繼續(xù)執(zhí)行，并發(fā)送和接收消息50全局狀態(tài)n 算法基本思想 接入通道 +外出通道 進程狀態(tài) +通道狀態(tài) 標(biāo)記消息 標(biāo)記接收規(guī)則 ：強制進程在記錄下自己的狀態(tài)之后但在它們發(fā)送其他消息前發(fā)送一個標(biāo)記。amp。第 3章 時間和全局狀態(tài)2第 3章 時間和全局狀態(tài)n 簡介 n 時鐘、事件和進程狀態(tài)n 同步物理時鐘n 邏輯時間和邏輯時鐘n 全局狀態(tài)n 分布式調(diào)試n 小結(jié)3簡介n 如何計時？n 如何同步時鐘？n 沒有物理時鐘能否確定事件的順序？4簡介n 時間的重要性n 需要精確度量 —— 審計電子商務(wù)n 某些算法依賴于時鐘同步 —— 數(shù)據(jù)一致性維護n 計算全局狀態(tài) —— 事件排序n 時間的復(fù)雜性n 節(jié)點具有獨立的物理時鐘n 精確同步物理時鐘非常困難n 全局狀態(tài)的捕獲n 依賴于邏輯時鐘n 邏輯時鐘與物理時鐘無必然聯(lián)系5第 3章 時間和全局狀態(tài)n 簡介 n 時鐘、事件和進程狀態(tài)n 同步物理時鐘n 邏輯時間和邏輯時鐘n 全局狀態(tài)n 分布式調(diào)試n 小結(jié)6時鐘、事件和進程狀態(tài)n 假設(shè)n 每個進程在單處理器上執(zhí)行n 處理器之間不共享內(nèi)存n 進程之間通過消息進行通信n 進程狀態(tài)n 所有變量的值n 相關(guān)的本地操作系統(tǒng)環(huán)境中的對象的值n 事件n 定義：一個通信動作或進程狀態(tài)轉(zhuǎn)換動作n 進程歷史：7時鐘、事件和進程狀態(tài)n 計算機時鐘n 晶體具有固定震蕩頻率n 硬件時鐘：n 軟件時鐘：n 時鐘漂移n 頻率不同n 時鐘頻率隨溫度變化而有所差別n 時鐘偏移不可避免8時鐘、事件和進程狀態(tài)n 時間分類n 天文學(xué)時間 太陽日：兩次連續(xù)的太陽中天之間的時間間隔 太陽秒： 1/86400個太陽日n 國際原子時間 (TAI) 基于銫原子跳躍周期 秒： 9 192 631 770次跳躍周期n 通用協(xié)調(diào)時間 (UTC) 基于原子時間 采用潤秒，與天文時間保持一致9第 3章 時間和全局狀態(tài)n 簡介 n 時鐘、事件和進程狀態(tài)n 同步物理時鐘n 邏輯時間和邏輯時鐘n 全局狀態(tài)n 分布式調(diào)試n 小結(jié)10同步物理時鐘n 外部同步n 采用權(quán)威的外部時間源n 時鐘 Ci在范圍 D內(nèi)是準(zhǔn)確的n 內(nèi)部同步n 無外部權(quán)威時間源 ,系統(tǒng)內(nèi)時鐘同步n 時鐘 Ci在范圍
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1