【正文】 01:29:1901:29:1901:293/28/2023 1:29:19 AM ? 1越是沒有本領的就越加自命不凡。 2023年 3月 28日星期二 上午 1時 29分 19秒 01:29: ? 1比不了得就不比，得不到的就不要。 States:={(s01, s02, …, s 0N)}。 a r a a r r 我們無法準確確定 r的先后關系： C(a) C(r) a ?r ??a 是節(jié)點 A發(fā)布的文章 r 是節(jié)點 B對文章 a的評論 全序邏輯時鐘 ? 引入進程標示符創(chuàng)建事件的全序關系 ? 若 e、 e’分別為進程 pi、 pj中發(fā)生的事件，則其全局邏輯時間戳分別為 (Ti,i)、 (Tj,j)。 向量時鐘 a bc de fm1m2( 2 , 0 , 0 )( 1 , 0 , 0 )( 2 , 1 , 0 ) ( 2 , 2 , 0 )( 2 , 2 , 2 )( 0 , 0 , 1 )p1p2p3P h y s ic a l t im e Host 1 Host 2 Host 3 Host 4 0,0,0,0 Vector logical clock Message (vector timestamp) Physical Time 0,0,0,0 0,0,0,0 0,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) ? 分布式調(diào)試 ? 小結 全局狀態(tài) ? 觀察全局狀態(tài)的必要性 ? 分布式無用單元的收集 基于對象的引用計數(shù) 必須考慮信道和進程的狀態(tài) ? 分布式死鎖檢測 觀察系統(tǒng)中的“等待”關系圖中是否存在循環(huán) p1 消息 無用 對象 對象 引用 p2 等待 等待 p1 p2 ? 分布式終止檢測 與進程的狀態(tài)有關 ——“主動 ” 或 “ 被動 ” ? 分布式調(diào)試 需要收集同一時刻系統(tǒng)中分布式變量的數(shù)值 全局狀態(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) 全局歷史中所有事件的全序 與每個本地歷史順序一致 不是所有的走向都經(jīng)歷一致的全局狀態(tài) ? 線性化走向 所有的線性化走向只經(jīng)歷一致的全局狀態(tài) 若存在一個經(jīng)過 S和 S’的線性化走向，則狀態(tài) S’是從 S可達 全局狀態(tài) ? Chandy和 Lamport的“快照”算法 ? 目的 捕獲一致的全局狀態(tài) ? 假設 進程和通道均不會出現(xiàn)故障 單向通道，提供 FIFO順序的消息傳遞 進程之間存在全連通關系 任一進程可在任一時間開始全局拍照 拍照時，進程可繼續(xù)執(zhí)行，并發(fā)送和接收消息 全局狀態(tài) ? 算法基本思想 接入通道 +外出通道 進程狀態(tài) +通道狀態(tài) 標記消息 標記接收規(guī)則 ：強制進程在記錄下自己的狀態(tài)之后但在它們發(fā)送其他消息前發(fā)送一個標記。 ? – 層次 0 1 2 3 4 5 F F F F T F F= (?(s)=False)。 , March 28, 2023 ? 很多事情努力了未必有結果，但是不努力卻什么改變也沒有。 2023年 3月 28日星期二 上午 1時 29分 19秒 01:29: ? 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。 。 , March 28, 2023 ? 雨中黃葉樹，燈下白頭人。即如果 ej在 pj記錄它的狀態(tài)之