os之分布式系統(tǒng)中的同步問題(已修改)
2025-08-16 09:52 本頁面
【正文】 分布式系統(tǒng)中同步問題 一 、 時鐘同步 分布式系統(tǒng)特點： ? 相關(guān)的信息分布在多臺機器上 ? 沒有共享內(nèi)存進程只根據(jù)本地可用的信息做出決策 ? 系統(tǒng)中不存在公共時鐘或其它精確的全局時間源 ? 在集中式系統(tǒng)中 ， 時間是很明確的 時鐘同步 例子 UNIX的 Make， 檢查文件最后修改時間 ? 創(chuàng)建 ， 源 ， 要重新編譯 ? 設(shè) 的 修 改 時 間 是 2022 。 創(chuàng)建 ? 但編輯 ， 修改后 1999 ? make不會重新編譯 ， 程序的運行會出現(xiàn)問題 二、邏輯時鐘 (1) ? 只關(guān)心時鐘內(nèi)部一致性 ， 不關(guān)心時鐘是否與實際時間一致 ? 1978年 Lamport指出 ， 系統(tǒng)中的時鐘并不需要絕對的同步 ? 重要的不是進程有完全一致的時間 ， 而是事件發(fā)生的先后次序要一致 二、邏輯時鐘 (2) 發(fā)生之前 （ happensbefore） 關(guān)系定義 ? 表達式 a b讀作 “ a發(fā)生在 b前 ” ? 即所有進程都認為事件 a先發(fā)生 ， 然后才發(fā)生事件 b 事件 a， 有一個時間值 C（ a） ? 如果 a和 b是同一進程中的事件 ， 而且 a發(fā)生在 b前 ? 那么 a b為 true, C（ a） C（ b） 二、邏輯時鐘 (3) ? 傳遞性 Happensbefore關(guān)系具有傳遞性 如果 a b和 b c都成立 ， a c也成立 并發(fā)事件： ? 如果事件 x和 y發(fā)生在不同的進程中 ， 且這兩進程間不交換信息 那么 x y和 y x都不成立 。 這兩個事件就稱為并發(fā)事件 ? 并發(fā)意味著兩個事件發(fā)生時 ， 無法確定哪個事件先發(fā)生 ， 或者說不需要考慮此事 ? 時鐘時間 C必須向前 （ 不斷增加 ） ， 不能后退 （ 減小 ） ? 對時間的更新 ， 只能是在時鐘上加一個正數(shù) ，不能減正數(shù) Lamport算法 (1)： 例子說明 (1) ? 三個進程運行在不同的有自己時鐘的機器上 ，每個時鐘按自己的速度運行 ? 可以看到 ， 進程 0中時鐘有 6次嘀嗒時 ， 進程 1已經(jīng)有了 8次 ， 而進程 2已經(jīng)有了 10次 Lamport算法 (2)： ? 設(shè) ， 計時器每秒生成 60次中斷 ， 每次中斷稱為一個時鐘嘀嗒 ? 從進程 2發(fā)送該進程 1的消息 C， 其發(fā)送時刻為 60， 到達時刻為 56 ? 同樣 ， 從進程 1到進程 0的消息 D， 其發(fā)送時刻為 64， 到達時刻為 54 ? 這顯然是不可能的 ， 也是必須避免出現(xiàn)的情況 例子說明 (2) Lamport算法 (3)： ? 消息 c的發(fā)送時間為 60， 它的到達時間一定在時刻 61或 61之后 ? 讓每條消息都攜帶發(fā)送者時鐘的發(fā)送時刻 ? 當消息到達接收時 ， 如果接收者的時鐘指示值先于發(fā)送消息的時間 ? 接受者的時鐘值就應(yīng)快于消息發(fā)送時刻加 1之后時間值 例子說明 (3) Lamport算法 (4)： Lamport算法 (5)： ? 兩個事件之間 ， 時鐘至少應(yīng)間隔一個嘀嗒 ? 如果一個進程依次快速發(fā)送或接收兩條消息 ，就必須調(diào)整時鐘 ? 使兩個事件之間 （ 至少 ） 間隔一個時鐘嘀嗒 ? 附加條件 , 沒有兩個事件是精確地在同一時刻發(fā)生的： ， 如果 a在 b前面發(fā)生 ， 那么 C(a)C(b) a與 b分別代表消息的發(fā)送和接收 ， 那么 C(a)C(b) a與 b而言 ， C(a)≠C(b) Lamport算法 (6)： ? 算法給出系統(tǒng)中所有事件的整體定序方法 ? 該算法在學(xué)術(shù)界中得到廣泛認同 Lamport算法 (7)： 三、時鐘 (1) ? 在某些系統(tǒng)中 ， 實際的時鐘時間非常重要 ，需要物理時鐘 ? 如何使物理時鐘與世界的時鐘同步 ？ ? 物理時間之間如何保持同步 ？ ? 原子鐘可以準確度量時間 ? 世界時 （ Universal Coordinated Time）簡稱 UTC ? UTC是現(xiàn)代計時的基礎(chǔ) ? National Institute of Standard Time ? NIXT, 國家標準時間組織短波電臺 ， WWV ? 每個 UTC秒的起始時刻 ， WWV就發(fā)送一個短脈沖 ? WWV本身的誤差大約為 +1毫秒 物理時鐘 (2) 四、時鐘同步算法 ? 如果某臺機器有 WWV接收器 ? 時鐘同步的目的是使其它機器與這臺機器同步 時鐘同步算法的基本模型 (1) ? 設(shè)每臺機器都有個計時器 ， 該計時器每秒中斷 H次 ? 計時器溢出時 ， 中斷處理程序就將軟件時鐘加 1 ? 軟件時鐘是從過去某一已知時間開始所經(jīng)歷的 tick數(shù) ? 這個時鐘的值稱為 C。 當 UTC時間為 t時 ，機器 p的時鐘值為 Cp (t) ? 理想情況下 dC/dt應(yīng)為 1 ? 理論上 ， 當 H = 60時 ， 計時器應(yīng)每小時生成216,000次 ticks ? 實際上 ， 計時器芯片的相對誤差大約為 105， ? 即 每 小 時 的 tick 數(shù) 的 范 圍 為 215,998 到216,002 準確地說 ， 如果存在一個常數(shù) p 1 ρ≤ dC/dt ≤ 1 + ρ 成立 ， 就可以認為計時器是正常工作的 時鐘同步算法的基本模型 (2) ? 如果兩個時鐘偏離 UTC的方向相反 那么在同步之后的 △ t時刻時 它們的時差為 2ρ△ t ? 要保證兩個時鐘間時間差不超過 δ 必須至少每隔 δ/2ρ秒重新同步 Cristian算法 (1) ? 某臺機器擁有 WWV接收器的系統(tǒng)的算法 ? 時鐘同步的目的就是使其它機器與有 WWV接收器的機器保持同步 ? 有 WWV 接收器的機器稱為時間服務(wù)器（ time server） Cristian算法 (2) ? 系統(tǒng)中每臺機器至少每隔 δ/2ρ秒就向時間服務(wù)器發(fā)送一條消息 查詢當前時間 ? 服務(wù)器盡快將攜帶當前時間 CUTC的消息返回給請求者 ? 一種近似方法 發(fā)送者得到時間服務(wù)器的響應(yīng)后 ， 直接將其時鐘值設(shè)置為 CUTC Cristian算法 (3) ? 笫一個問題：時間決不能倒退 如果這個請求發(fā)送者的時鐘比實際時間快 這時僅將 CUTC設(shè)置為時鐘的當前值會引起嚴重問題 Cristian算法 (4) ? 對時鐘的調(diào)整必須逐步進行 ? 一種方法：假設(shè)計時器每秒中斷 100次 正常情況下 ， 每次中斷將時鐘時間增加 10毫秒 如果要使時鐘慢下來 ， 中斷程序就每次只將時間增加 9 直到將時間矯正過來為止 Cristian算法 (5) ? 同樣 ， 每次中斷時將時間加 11毫秒 ， 就會逐漸將時鐘調(diào)快 ， 而不應(yīng)直接將時鐘值設(shè)快 Cristian算法 (6) ? 第二個問題 時間服務(wù)器將當前時間發(fā)送給查詢時間的機器需要時間
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1