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

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

2、l時(shí)鐘偏差（clock skew）l邏輯時(shí)鐘：相對(duì)時(shí)間l物理時(shí)鐘：真實(shí)時(shí)間l“之前”關(guān)系: 事件a在b之前出現(xiàn)，則aba為發(fā)送消息m，b為接收m，則ab具有傳遞性：ab, bc,則acl并發(fā)事件（concurrent）7Lamport算法算法l對(duì)每一事件a，在所有進(jìn)程中都認(rèn)可給它分配一個(gè)時(shí)間值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算法算法時(shí)時(shí)間間慢慢快快慢慢快快9物理時(shí)鐘與現(xiàn)實(shí)時(shí)鐘物理時(shí)鐘與現(xiàn)實(shí)時(shí)鐘（1）如何用現(xiàn)實(shí)世界的時(shí)鐘將它們同步起來；（2）如何使各時(shí)鐘之間保持同步

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

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

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

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

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

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

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

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

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

12、類型的對(duì)象，如數(shù)據(jù)庫）35事務(wù)舉例事務(wù)舉例BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi reserve NairobiMalindi END TRANSACTION BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi NairobiMalindi fullABORT TRASACTION 當(dāng)?shù)谌齻€(gè)航班的機(jī)票預(yù)定失敗后事務(wù)中止預(yù)定三個(gè)航班機(jī)票：中轉(zhuǎn)站是JFK、Nairobi36事務(wù)的特性事務(wù)的特性 1. 原子性（Atomic）：對(duì)外部世界來說，事務(wù)的發(fā)生是不可分割的；2. 一致性（Consi

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

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

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

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

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

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