-時間和全局狀態(tài)(編輯修改稿)
2025-03-27 01:29 本頁面
【文章內容簡介】 0,0,0 (1,0,0,0) 1,0,0,0 1,1,0,0 2,0,0,0 2,0,1,0 (2,0,0,0) 2,0,2,0 2,0,2,1 (2,0,2,0) 1,2,0,0 2,2,3,0 (1,2,0,0) 4,0,2,2 4,2,4,2 (4,0,2,2) 2,0,2,2 3,0,2,2 (2,0,2,2) 2,0,2,3 4,2,5,3 (2,0,2,3) n,m,p,q 向量時鐘 第 3章 時間和全局狀態(tài) ? 簡介 ? 時鐘、事件和進程狀態(tài) ? 同步物理時鐘 ? 邏輯時間和邏輯時鐘 ? 全局狀態(tài) ? 分布式調試 ? 小結 全局狀態(tài) ? 觀察全局狀態(tài)的必要性 ? 分布式無用單元的收集 基于對象的引用計數 必須考慮信道和進程的狀態(tài) ? 分布式死鎖檢測 觀察系統(tǒng)中的“等待”關系圖中是否存在循環(huán) p1 消息 無用 對象 對象 引用 p2 等待 等待 p1 p2 ? 分布式終止檢測 與進程的狀態(tài)有關 ——“主動 ” 或 “ 被動 ” ? 分布式調試 需要收集同一時刻系統(tǒng)中分布式變量的數值 全局狀態(tài) 激活 被動的 p1 p2 被動的 全局狀態(tài) ? 全局狀態(tài)和一致割集 ? 觀察進程集的狀態(tài) —— 全局狀態(tài)非常困難 根源：缺乏全局時間 ? 進程的歷史 hi = ei0, ei1, ei2 … ? 進程歷史的有限前綴 hi k= ei0, ei1, … , eik ? 全局歷史 —— 單個進程歷史的并集 H = h1 ? h2 ?… ? hN 全局狀態(tài) ? 進程狀態(tài) sik : 進程 pi在第 k個事件發(fā)生之前的狀態(tài) ? 全局狀態(tài) —— 單個進程狀態(tài)的集合 S = (s1, s2, … sN) ? 割集 —— 系統(tǒng)全局歷史的子集 C = h1c1, h2c2… h3c3 ? 割集的一致性 割集 C是一致的 : 對于所有事件 e?C, f ? e ? f ? C 全局狀態(tài) ? 割集示例 m 1 m 2 p 1 p 2 物理時間 e 1 0 一致的割集 不一致的割集 e 1 1 e 1 2 e 1 3 e 2 0 e 2 1 e 2 2 全局狀態(tài) ? 一致的全局狀態(tài) —— 對應于一致割集的狀態(tài) S0 ? S1 ? S2 ? … ? 走向 (run) 全局歷史中所有事件的全序 與每個本地歷史順序一致 不是所有的走向都經歷一致的全局狀態(tài) ? 線性化走向 所有的線性化走向只經歷一致的全局狀態(tài) 若存在一個經過 S和 S’的線性化走向，則狀態(tài) S’是從 S可達 全局狀態(tài) ? Chandy和 Lamport的“快照”算法 ? 目的 捕獲一致的全局狀態(tài) ? 假設 進程和通道均不會出現故障 單向通道，提供 FIFO順序的消息傳遞 進程之間存在全連通關系 任一進程可在任一時間開始全局拍照 拍照時，進程可繼續(xù)執(zhí)行，并發(fā)送和接收消息 全局狀態(tài) ? 算法基本思想 接入通道 +外出通道 進程狀態(tài) +通道狀態(tài) 標記消息 標記接收規(guī)則 ：強制進程在記錄下自己的狀態(tài)之后但在它們發(fā)送其他消息前發(fā)送一個標記。 標記發(fā)送規(guī)則 ：強制沒有記錄狀態(tài)的進程去記錄狀態(tài) 全局狀態(tài) ? 算法偽碼 (一 ) 進程 pi的標記接收規(guī)則 pi接收通道 c上的標記消息： if (pi還沒有記錄它的狀態(tài) ) pi記錄它的進程狀態(tài)； 將 c的狀態(tài)記成空集； 開始記錄從其他接入通道上到達的消息 else pi把 c的狀態(tài)記錄到從保留它的狀態(tài)以來它 在 c上接收到的消息集合中 end if 全局狀態(tài) ? 算法偽碼 (二 ) 進程 pi的標記發(fā)送規(guī)則 在 pi記錄了它的狀態(tài)之后，對每個外出通道 c: (在 pi從 c上發(fā)送任何其他消息前 ) pi在 c上發(fā)送一個消息標記 全局狀態(tài) ? 算法示例 兩個進程 p p2進行交易，每件 10$ 初始狀態(tài) 進程 p2已經收到 5件商品的定單，它將馬上分發(fā)給 p1 p 1 p 2 c 2 c 1 帳戶 窗口 部件 $1000 (none) 帳戶 窗口 部件 $50 2023 全局狀態(tài) 最后狀態(tài)： P1:$1000, 0。 p2:$50,1995。 c1:(five widgets)。 c2: p1 (空 ) $1000, 0 1. 全局狀態(tài) S0 p1 p1 p1 c2 c1 (空 ) 2. 全局狀態(tài) S1 $900, 0 $900, 0 $9
環(huán)評公示相關推薦
鄂ICP備17016276號-1