第3章分布式系統(tǒng)的同步

1、第3章 分布式系統(tǒng)的同步分布式系統(tǒng)的同步 中國科技大學軟件學院丁箐2主要內容主要內容3.1 時鐘同步3.2 互斥3.3 選舉算法3.4 原子性事務3.5 分布式系統(tǒng)中的死鎖3主要內容主要內容3.1 時時鐘鐘同步同步3.2 互斥3.3 選舉算法3.4 原子性事務3.5 分布式系統(tǒng)中的死鎖43.1 時鐘同步時鐘同步l分布式算法的特點相關信息散布在多個場地上每個進程只能基于本地信息做決定應避免因單點故障造成整個系統(tǒng)的失敗不存在公共時鐘或精確的全局時間5時鐘同步問題時鐘同步問題l例：makefile誤差時間時間output.o ： cc C output.c6邏輯時鐘邏輯時鐘l計時器：石英晶體+計數器

2、l時鐘偏差（clock skew）l邏輯時鐘：相對時間l物理時鐘：真實時間l“之前”關系: 事件a在b之前出現，則aba為發(fā)送消息m，b為接收m，則ab具有傳遞性：ab, bc,則acl并發(fā)事件（concurrent）7Lamport算法算法l對每一事件a，在所有進程中都認可給它分配一個時間值C(a） if ab;則C(a)C(b)a,b C(a) C(b)C是遞增的l校正算法ab，if C(b)C(a), 則C(b) = C(a) +18Lamport算法算法時時間間慢慢快快慢慢快快9物理時鐘與現實時鐘物理時鐘與現實時鐘（1）如何用現實世界的時鐘將它們同步起來；（2）如何使各時鐘之間保持同步

3、。 l太陽日：連續(xù)的兩次日中天的時間l太陽秒：solar-day/86400l平均太陽秒：如，格林威治時間10現實時鐘現實時鐘l銫原子鐘：9192631770次躍遷=1秒lTAI秒：國際原子時間lUTC秒：世界時間（在TAI秒中加入閏秒）l時間服務：WWV電臺、GEOS衛(wèi)星102011時鐘同步算法時鐘同步算法如何與現實時鐘同步如何使不同機器之間相互同步l設機器時鐘值Cp(t), t 為UTC時間最大偏移率精確時鐘： dC/dt =1快時鐘： dC/dt 1慢時鐘： dC/dt 112Christians 算法算法 - 逐步調整法逐步調整法l時間服務器，可接受WWV的UTC時間l每隔/2校準時間

4、（ 允許誤差 ，存在誤差 ）o兩個問題：時間決不能倒退,延遲o假設：每秒產生100次中斷，每次中斷將時間加10毫秒 若調慢時鐘，中斷服務程序每次只加9毫秒； 若加快時鐘，則加11毫秒。 傳播時間13Berkeley 算法算法 主動式方法主動式方法1.時間監(jiān)控器定期查詢其他機器時間2.計算出平均值3.通知其他機器調整時間14平均值算法平均值算法 非集中式方法非集中式方法1.將時間劃分成固定長度的再同步間隔，第i次間隔開始于T0+iR，而結束于 T0+(i+1)R 2.所有機器廣播自己的時鐘時間3.啟動本地計時器收集在S時間間隔中到達的其他機器廣播的時間4.執(zhí)行平均時間計算算法，得到新的時間值（取

5、平均值，去掉兩端值 ）15多個外部時間源法多個外部時間源法q 例：OSF DCE方法1.接受所有時間源的當前UTC區(qū)間2.去掉與其他區(qū)間不相交的區(qū)間3.將相交部分的中點作為校準時間時間16使用同步時鐘使用同步時鐘l最多一次消息提交1.每個消息攜帶一個ID和一個時間印ts（timestamp）2.服務器的表T中，記錄每個連接C最近的時間印t3.如果到達的消息m，ts(m)t, 則拒絕m 服務器要一直保存一個全局變量 G = CurrentTime MaxLifetime MaxClockSkew所有G的時間印從表T中清除對于具有新的ID的到達消息m,如果ts(m)G則拒絕m,否則，接受m按照一定

6、時間間隔T，定期地將G寫入磁盤。當系統(tǒng)重啟后，G=G+T17使用同步時鐘使用同步時鐘l基于時鐘的緩存一致性1.當客戶讀取一個副本到緩存時，設置一個租期（lease）2.在租期過期之前，客戶可更新副本，重續(xù)租期3.如果已經過期，緩存中的副本失效 改進的一致性協(xié)議當客戶修改文件時，只需將所有沒有到期的緩存副本設為無效如果某個客戶崩潰，則等待直到該客戶的租期過期18主要內容主要內容3.1 時鐘同步3.2 互斥互斥3.3 選舉算法3.4 原子性事務3.5 分布式系統(tǒng)中的死鎖193.2 互互 斥斥l基本概念當一個進程使用某個共享資源，其他進程不允許對這個資源操作l臨界區(qū)（Critical Section

7、）：對共享資源進行操作的程序段l基本方法：信號量、管程l問題：死鎖活鎖饑餓20集中式算法集中式算法（仿照單處理機系統(tǒng)的方法 ）l協(xié)調者：確定那個進程可進入臨界區(qū)l通信量：3個消息：請求-許可-釋放l缺點：單點失敗l單協(xié)調者會成為執(zhí)行的瓶頸 CCC21Win Thread 臨界區(qū)臨界區(qū)lCreateMutex()lWaitForSingleObject()lReleaseMutex()lInitializeCriticalSection()lEnterCriticalSection()lLeaveCriticalSection()22分布式算法（分布式算法（Ricart-Agrawala算法算法

8、）要求系統(tǒng)中所有事件都是全序的1. 在一個進程P打算進入臨界區(qū)R之前，向所有其他進程廣播消息 2. 當一個進程P收到消息后，做如下決定：若P不在臨界區(qū)R中，也不想進入R，它就向P發(fā)送OK消息；若P已經在臨界區(qū)R中，則不回答，并將P放入請求隊列；若P也同時要進入臨界區(qū)R，但是還沒有進入時，則將發(fā)來的消息和它發(fā)送給其余進程的時間戳對比。如果P時間印小，則P發(fā)送OK消息;否則，不回答，并將P放入請求隊列；3. 當P收到所有的OK消息后，進入R。否則，等待。4. 當P退出R時，如果存在等待隊列，則取出請求者，向其發(fā)送OK消息。23分布式算法舉例分布式算法舉例舉例： 共有0，1，2三個進程。進程0，2申

9、請進入臨界區(qū)02002224分布式算法評價分布式算法評價l缺點：n點失敗n點瓶頸2（n-1)個消息l改進方案：超時重發(fā)組通信簡單多數同意比原來集中式算法慢，復雜，昂貴，而且不健壯。 25令牌環(huán)算法令牌環(huán)算法構造一個邏輯環(huán)，得到令牌才可進入臨界區(qū)326三種互斥算法的比較三種互斥算法的比較算法每次進出需要的消息進入前的延遲（按消息次數）存在問題集中式32協(xié)調者崩潰分布式2（n-1）2（n-1）任何一個進程崩潰令牌環(huán)1到0到n-1丟失令牌，進程崩潰27主要內容主要內容3.1 時鐘同步3.2 互斥3.3 選舉算法選舉算法3.4 原子性事務3.5 分布式系統(tǒng)中的死鎖283.3 選舉算法選舉算法l許多分布

10、式算法需要一個進程充當協(xié)調者，發(fā)起者，排序者或其他特定的角色。 l作用：做出統(tǒng)一的的決定例如：確定協(xié)調者29欺負（欺負（Bully）算法）算法v將進程進行排序1.P向高的進程發(fā)E消息2.如果沒有響應，P選舉獲勝3.如果有進程Q響應,則P結束，Q接管選舉并繼續(xù)下去。45656465630環(huán)算法環(huán)算法l所有進程按邏輯或物理次序排序，形成一個環(huán)1.當一個進程P發(fā)現協(xié)調者C失效后，向后續(xù)進程發(fā)送E消息2.每個進程繼續(xù)向后傳遞E消息，直到返回P3.P在將新確定的協(xié)調者C傳給所有進程5231主要內容主要內容3.1 時鐘同步3.2 互斥3.3 選舉算法3.4 原子性事務原子性事務3.5 分布式系統(tǒng)中的死鎖3

11、23.4 原子性（原子性（Atomic）事務）事務l原子性： 組成原子事務的一組操作要么全部執(zhí)行，要么一個也不執(zhí)行，并且事務失敗后能返回到最初狀態(tài)l例1： 老式磁帶系統(tǒng)（備份）l例2：匯款（提款存款）33事務模型事務模型l穩(wěn)定存儲器（Stable Storage）：通過一對雙工磁盤實現34事務原語事務原語（1）BEGIN_TRA NSACTION：標記一個事務的開始；（2）END_TRANSACTION：結束事務并設法提交；（3）ABORT_TRANSACTION：取消事務并恢復舊值；（4）READ：從一個文件（或其他類型的對象，如數據庫）讀取數據；（5）WRITE：將數據寫入一個文件（或其他

12、類型的對象，如數據庫）35事務舉例事務舉例BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi reserve NairobiMalindi END TRANSACTION BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi NairobiMalindi fullABORT TRASACTION 當第三個航班的機票預定失敗后事務中止預定三個航班機票：中轉站是JFK、Nairobi36事務的特性事務的特性 1. 原子性（Atomic）：對外部世界來說，事務的發(fā)生是不可分割的；2. 一致性（Consi

13、stent）：事務不會破壞系統(tǒng)的恒定；3. 隔離性（Isolated）：并發(fā)的事務之間不會互相干擾；可串行性（Serializable）:多個事務并發(fā)執(zhí)行的結果，與它們順序地執(zhí)行效果相同。4. 持久性（Durable）：一旦一個事務提交，它的更新結果不會因故障而丟失。37隔離性（隔離性（Isolated）38事務的實現事務的實現 q 私有工作空間與影子更新：-當進程啟動事務T時，分配一個私有工作空間W，在提交或中止T前所有的讀寫操作都是在W中進行03影子塊39先先寫日志寫日志（WAL）l就地更新（in-place）l日志紀錄事務標識，文件標識，塊號，前像，后像l例：40先先寫日志寫日志協(xié)議協(xié)議

14、l回滾（Rollback）:反做（undo）廢棄事務的更新結果l只有當日志成功地寫入穩(wěn)存之后，才可以修改文件。如果事務執(zhí)行成功并被提交，則它的提交記錄將被寫入日志。如果事務異常中止，則用日志來備份初始狀態(tài)。從日志的未尾開始，向回逐個讀取日志記錄，反做記錄中描述的修改，即回滾處理。l在系統(tǒng)崩潰后,日志也可用來進行的恢復。41示例示例(a)一個事務 (b)-(d)每條語句執(zhí)行前的日志 42兩階段提交協(xié)議兩階段提交協(xié)議（two-phase commit protocol） l準備階段：取得一致決定l執(zhí)行階段：執(zhí)行命令（提交或廢棄）43并發(fā)控制并發(fā)控制(Concurrency Control)l加鎖法

15、l正確性標準：可串行性（serializable）l封鎖加鎖：獲得資源上的封鎖解鎖：釋放已擁有的鎖l封鎖的類型和相容性讀鎖(R)寫鎖(W)l鎖的粒度細粒度：如字段粗粒度：如文件RWRW44兩階段封鎖協(xié)議兩階段封鎖協(xié)議(2PL)恰好在需要或不再需要鎖時去請求或釋放鎖可能會導致不一致和死鎖？ q加鎖階段開鎖階段嚴格的2PL與2PC結合避免級聯廢棄（cascaded abort)v死鎖：等待圖（WFG） 檢查是否有環(huán)路 超時檢測（timeout)45樂觀法樂觀法(Optimistic)最適合于基于私有工空間的情況 q讀階段：將文件讀入私有工作區(qū)1.確認階段：提交前，檢查是否有沖突有，則廢棄事務，重啟

16、。無，則提交事務2.寫階段：如可以提交，則將修改內容從私有工作區(qū)，寫入文件。46時間戳時間戳(Timestamp)l每個事務的操作帶有該事務的時間戳l每個文件帶有對它操作的最后一個提交事務的讀時間戳、寫時間戳l算法：1.如果當前事務T的時間戳文件的時間戳，則執(zhí)行；2.否則 ，廢棄T;47時間戳法示例時間戳法示例l設有三個事務，。T()T()T()TT()48三種方法比較三種方法比較并發(fā)度死鎖性能2PL低有中樂觀法高無高（廢棄度低時）時間印法較高無較高49主要內容主要內容3.1 時鐘同步3.2 互斥3.3 選舉算法3.4 原子性事務3.5 分布式系統(tǒng)中的死鎖分布式系統(tǒng)中的死鎖503.5 分布式系

17、統(tǒng)的死鎖處理分布式系統(tǒng)的死鎖處理l通信死鎖和資源死鎖 l死鎖解決策略鴕鳥法：（忽略問題，留給用戶考慮）檢測法：（允許死鎖發(fā)生，在檢測到后想辦法恢復） 預防法：（靜態(tài)的使死鎖在結構上是不可能發(fā)生的） 避免法：（在運行中，通過仔細的分配資源以避免死鎖）實際在分布式系統(tǒng)中從來都不采用 l銀行家算法Dijkstra,1965lP, free51檢測檢測方法：方法：集中式集中式一臺中心機器擁有整個系統(tǒng)（所有資源圖的集合）的資源圖 l進程-資源等待圖節(jié)點：進程P、資源R有向邊:(1)PR請求關系; (2) R P擁有關系;l死鎖檢測協(xié)調者負責檢測死鎖l資源圖的維護策略：當資源圖中，有一條邊加入/刪除時，通

18、知協(xié)調者每個進程周期性地向協(xié)調者發(fā)送圖的更新消息協(xié)調者在需要時，向參入者請求52檢測檢測方法：方法：集中式集中式舉例舉例l假死鎖問題：B釋放R,請求T。若請求T消息先到達協(xié)調者(a)機器0初始資源圖 (b)機器1初始資源圖(c)協(xié)調者對系統(tǒng)的觀察(d)延遲信息后的系統(tǒng)情況 l解決方案一：協(xié)調者確認（消息的全局時序）53檢測方法：分布式檢測方法：分布式lChandyMisraHaas分布式死鎖檢測算法，l探測消息：阻塞Pid，請求Pid ，接收Pid le.g. （0,2,3）,（0,4,6）,（0,5,7 ）,（0,8,0）構成死鎖54分布式深度限制算法（分布式深度限制算法（DWDL）l90%的死鎖發(fā)生在兩個進程之間l算法：/ p1為請求者; L(p1)為p1的壽命 1) if ( waitQueue = p2-p1-p0 ) then if ( L(p1)L