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