分布式操作系統(tǒng)課件

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

中國(guó)科技大學(xué)軟件學(xué)院丁箐1第3章分布式系統(tǒng)的同步中國(guó)科技大學(xué)軟件學(xué)院1主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖2主要內(nèi)容3.1時(shí)鐘同步2主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖3主要內(nèi)容3.1時(shí)鐘同步33.1時(shí)鐘同步分布式算法的特點(diǎn)相關(guān)信息散布在多個(gè)場(chǎng)地上每個(gè)進(jìn)程只能基于本地信息做決定應(yīng)避免因單點(diǎn)故障造成整個(gè)系統(tǒng)的失敗不存在公共時(shí)鐘或精確的全局時(shí)間43.1時(shí)鐘同步分布式算法的特點(diǎn)4時(shí)鐘同步問(wèn)題例：makefile誤差時(shí)間output.o：cc–Coutput.c5時(shí)鐘同步問(wèn)題例：makefile誤差時(shí)間output.o：邏輯時(shí)鐘計(jì)時(shí)器：石英晶體+計(jì)數(shù)器時(shí)鐘偏差（clockskew）邏輯時(shí)鐘：相對(duì)時(shí)間物理時(shí)鐘：真實(shí)時(shí)間“之前”關(guān)系:事件a在b之前出現(xiàn)，則aba為發(fā)送消息m，b為接收m，則ab具有傳遞性：ab,bc,則ac并發(fā)事件（concurrent）6邏輯時(shí)鐘計(jì)時(shí)器：石英晶體+計(jì)數(shù)器6Lamport算法對(duì)每一事件a，在所有進(jìn)程中都認(rèn)可給它分配一個(gè)時(shí)間值C(a）ifab;則C(a)<C(b)a,bC(a)C(b)C是遞增的校正算法ab，ifC(b)<C(a),則C(b)=C(a)+17Lamport算法對(duì)每一事件a，在所有進(jìn)程中都認(rèn)可給它分配一Lamport算法時(shí)間慢快慢快8Lamport算法時(shí)間慢快慢快8物理時(shí)鐘與現(xiàn)實(shí)時(shí)鐘（1）如何用現(xiàn)實(shí)世界的時(shí)鐘將它們同步起來(lái)；（2）如何使各時(shí)鐘之間保持同步。

太陽(yáng)日：連續(xù)的兩次日中天的時(shí)間太陽(yáng)秒：solar-day/86400平均太陽(yáng)秒：如，格林威治時(shí)間9物理時(shí)鐘與現(xiàn)實(shí)時(shí)鐘（1）如何用現(xiàn)實(shí)世界的時(shí)鐘將它們同步起來(lái)；現(xiàn)實(shí)時(shí)鐘銫原子鐘：9192631770次躍遷=1秒TAI秒：國(guó)際原子時(shí)間UTC秒：世界時(shí)間（在TAI秒中加入閏秒）時(shí)間服務(wù)：WWV電臺(tái)、GEOS衛(wèi)星102010現(xiàn)實(shí)時(shí)鐘銫原子鐘：9192631770次躍遷=1秒10201時(shí)鐘同步算法如何與現(xiàn)實(shí)時(shí)鐘同步如何使不同機(jī)器之間相互同步設(shè)機(jī)器時(shí)鐘值Cp(t),t為UTC時(shí)間最大偏移率精確時(shí)鐘：dC/dt=1快時(shí)鐘：dC/dt〉1慢時(shí)鐘：dC/dt<111時(shí)鐘同步算法如何與現(xiàn)實(shí)時(shí)鐘同步11Christian’s算法--逐步調(diào)整法時(shí)間服務(wù)器，可接受WWV的UTC時(shí)間每隔δ/2ρ校準(zhǔn)時(shí)間（允許誤差δ，存在誤差ρ）兩個(gè)問(wèn)題：時(shí)間決不能倒退,延遲假設(shè)：每秒產(chǎn)生100次中斷，每次中斷將時(shí)間加10毫秒若調(diào)慢時(shí)鐘，中斷服務(wù)程序每次只加9毫秒；若加快時(shí)鐘，則加11毫秒。傳播時(shí)間12Christian’s算法--逐步調(diào)整法時(shí)間服務(wù)器，Berkeley算法–主動(dòng)式方法時(shí)間監(jiān)控器定期查詢其他機(jī)器時(shí)間計(jì)算出平均值通知其他機(jī)器調(diào)整時(shí)間13Berkeley算法–主動(dòng)式方法時(shí)間監(jiān)控器定期查詢其他平均值算法–非集中式方法將時(shí)間劃分成固定長(zhǎng)度的再同步間隔，第i次間隔開(kāi)始于T0+iR，而結(jié)束于T0+(i+1)R所有機(jī)器廣播自己的時(shí)鐘時(shí)間啟動(dòng)本地計(jì)時(shí)器收集在S時(shí)間間隔中到達(dá)的其他機(jī)器廣播的時(shí)間執(zhí)行平均時(shí)間計(jì)算算法，得到新的時(shí)間值（取平均值，去掉兩端值）14平均值算法–非集中式方法將時(shí)間劃分成固定長(zhǎng)度的再同步間隔多個(gè)外部時(shí)間源法例：OSFDCE方法接受所有時(shí)間源的當(dāng)前UTC區(qū)間去掉與其他區(qū)間不相交的區(qū)間將相交部分的中點(diǎn)作為校準(zhǔn)時(shí)間時(shí)間15多個(gè)外部時(shí)間源法例：OSFDCE方法時(shí)間15使用同步時(shí)鐘最多一次消息提交每個(gè)消息攜帶一個(gè)ID和一個(gè)時(shí)間印ts（timestamp）服務(wù)器的表T中，記錄每個(gè)連接C最近的時(shí)間印t如果到達(dá)的消息m，ts(m)<t,則拒絕m

服務(wù)器要一直保存一個(gè)全局變量G=CurrentTime–MaxLifetime–MaxClockSkew所有<G的時(shí)間印從表T中清除對(duì)于具有新的ID的到達(dá)消息m,如果ts(m)<G則拒絕m,否則，接受m按照一定時(shí)間間隔T，定期地將G寫(xiě)入磁盤。當(dāng)系統(tǒng)重啟后，G’=G+T16使用同步時(shí)鐘最多一次消息提交服務(wù)器要一直保存一個(gè)全使用同步時(shí)鐘基于時(shí)鐘的緩存一致性當(dāng)客戶讀取一個(gè)副本到緩存時(shí)，設(shè)置一個(gè)租期（lease）在租期過(guò)期之前，客戶可更新副本，重續(xù)租期如果已經(jīng)過(guò)期，緩存中的副本失效改進(jìn)的一致性協(xié)議當(dāng)客戶修改文件時(shí)，只需將所有沒(méi)有到期的緩存副本設(shè)為無(wú)效如果某個(gè)客戶崩潰，則等待直到該客戶的租期過(guò)期17使用同步時(shí)鐘基于時(shí)鐘的緩存一致性改進(jìn)的一致性協(xié)議1主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖18主要內(nèi)容3.1時(shí)鐘同步183.2互斥基本概念當(dāng)一個(gè)進(jìn)程使用某個(gè)共享資源，其他進(jìn)程不允許對(duì)這個(gè)資源操作臨界區(qū)（CriticalSection）：對(duì)共享資源進(jìn)行操作的程序段基本方法：信號(hào)量、管程問(wèn)題：死鎖活鎖饑餓193.2互斥基本概念19集中式算法（仿照單處理機(jī)系統(tǒng)的方法）協(xié)調(diào)者：確定那個(gè)進(jìn)程可進(jìn)入臨界區(qū)通信量：3個(gè)消息：請(qǐng)求-許可-釋放缺點(diǎn)：?jiǎn)吸c(diǎn)失敗單協(xié)調(diào)者會(huì)成為執(zhí)行的瓶頸

CCC20集中式算法（仿照單處理機(jī)系統(tǒng)的方法）協(xié)調(diào)者：確定那個(gè)進(jìn)程可WinThread臨界區(qū)CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeCriticalSection()EnterCriticalSection()LeaveCriticalSection()21WinThread臨界區(qū)CreateMutex()21分布式算法（Ricart-Agrawala算法）要求系統(tǒng)中所有事件都是全序的1.在一個(gè)進(jìn)程P打算進(jìn)入臨界區(qū)R之前，向所有其他進(jìn)程廣播消息<臨界區(qū)R名、進(jìn)程號(hào)、時(shí)間印>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，但是還沒(méi)有進(jìn)入時(shí)，則將發(fā)來(lái)的消息和它發(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消息。22分布式算法（Ricart-Agrawala算法）要求系統(tǒng)中所分布式算法舉例舉例：

共有0，1，2三個(gè)進(jìn)程。進(jìn)程0，2申請(qǐng)進(jìn)入臨界區(qū)02002223分布式算法舉例舉例：共有0，1，2三個(gè)進(jìn)程。0200222分布式算法評(píng)價(jià)缺點(diǎn)：n點(diǎn)失敗n點(diǎn)瓶頸2（n-1)個(gè)消息改進(jìn)方案：超時(shí)重發(fā)組通信簡(jiǎn)單多數(shù)同意比原來(lái)集中式算法慢，復(fù)雜，昂貴，而且不健壯。24分布式算法評(píng)價(jià)缺點(diǎn)：24令牌環(huán)算法構(gòu)造一個(gè)邏輯環(huán)，得到令牌才可進(jìn)入臨界區(qū)325令牌環(huán)算法構(gòu)造一個(gè)邏輯環(huán)，得到令牌才可進(jìn)入臨界區(qū)325三種互斥算法的比較算法每次進(jìn)出需要的消息進(jìn)入前的延遲（按消息次數(shù)）存在問(wèn)題集中式32協(xié)調(diào)者崩潰分布式2（n-1）2（n-1）任何一個(gè)進(jìn)程崩潰令牌環(huán)1到∞0到n-1丟失令牌，進(jìn)程崩潰26三種互斥算法的比較算法每次進(jìn)出進(jìn)入前的延遲（按消息次數(shù)）存在主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖27主要內(nèi)容3.1時(shí)鐘同步273.3選舉算法許多分布式算法需要一個(gè)進(jìn)程充當(dāng)協(xié)調(diào)者，發(fā)起者，排序者或其他特定的角色。作用：做出統(tǒng)一的的決定例如：確定協(xié)調(diào)者283.3選舉算法許多分布式算法需要一個(gè)進(jìn)程充當(dāng)協(xié)調(diào)者，發(fā)起欺負(fù)（Bully）算法將進(jìn)程進(jìn)行排序P向高的進(jìn)程發(fā)E消息如果沒(méi)有響應(yīng)，P選舉獲勝如果有進(jìn)程Q響應(yīng),則P結(jié)束，Q接管選舉并繼續(xù)下去。45656465629欺負(fù)（Bully）算法將進(jìn)程進(jìn)行排序45656465629環(huán)算法所有進(jìn)程按邏輯或物理次序排序，形成一個(gè)環(huán)當(dāng)一個(gè)進(jìn)程P發(fā)現(xiàn)協(xié)調(diào)者C失效后，向后續(xù)進(jìn)程發(fā)送E消息每個(gè)進(jìn)程繼續(xù)向后傳遞E消息，直到返回PP在將新確定的協(xié)調(diào)者C’傳給所有進(jìn)程5230環(huán)算法所有進(jìn)程按邏輯或物理次序排序，形成一個(gè)環(huán)5230主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖31主要內(nèi)容3.1時(shí)鐘同步313.4原子性（Atomic）事務(wù)原子性：組成原子事務(wù)的一組操作要么全部執(zhí)行，要么一個(gè)也不執(zhí)行，并且事務(wù)失敗后能返回到最初狀態(tài)例1：老式磁帶系統(tǒng)（備份）例2：匯款（提款存款）323.4原子性（Atomic）事務(wù)原子性：組成原子事務(wù)的事務(wù)模型穩(wěn)定存儲(chǔ)器（StableStorage）：通過(guò)一對(duì)雙工磁盤實(shí)現(xiàn)33事務(wù)模型穩(wěn)定存儲(chǔ)器（StableStorage）：33事務(wù)原語(yǔ)（1）BEGIN_TRANSACTION：標(biāo)記一個(gè)事務(wù)的開(kāi)始；（2）END_TRANSACTION：結(jié)束事務(wù)并設(shè)法提交；（3）ABORT_TRANSACTION：取消事務(wù)并恢復(fù)舊值；（4）READ：從一個(gè)文件（或其他類型的對(duì)象，如數(shù)據(jù)庫(kù)）讀取數(shù)據(jù)；（5）WRITE：將數(shù)據(jù)寫(xiě)入一個(gè)文件（或其他類型的對(duì)象，如數(shù)據(jù)庫(kù)）34事務(wù)原語(yǔ)（1）BEGIN_TRANSACTION：標(biāo)記一個(gè)事務(wù)舉例BEGINTRANSACTIONreserveWP－JFKreserveJFK－NairobireserveNairobi－MalindiENDTRANSACTION

BEGINTRANSACTIONreserveWP－JFKreserveJFK－Nairobi

Nairobi－MalindifullABORTTRASACTION

當(dāng)?shù)谌齻€(gè)航班的機(jī)票預(yù)定失敗后事務(wù)中止預(yù)定三個(gè)航班機(jī)票：中轉(zhuǎn)站是JFK、Nairobi35事務(wù)舉例BEGINTRANSACTION預(yù)定三個(gè)航班機(jī)票：事務(wù)的特性

原子性（Atomic）：對(duì)外部世界來(lái)說(shuō)，事務(wù)的發(fā)生是不可分割的；一致性（Consistent）：事務(wù)不會(huì)破壞系統(tǒng)的恒定；隔離性（Isolated）：并發(fā)的事務(wù)之間不會(huì)互相干擾；可串行性（Serializable）:多個(gè)事務(wù)并發(fā)執(zhí)行的結(jié)果，與它們順序地執(zhí)行效果相同。持久性（Durable）：一旦一個(gè)事務(wù)提交，它的更新結(jié)果不會(huì)因故障而丟失。36事務(wù)的特性原子性（Atomic）：對(duì)外部世界來(lái)說(shuō)，事務(wù)的發(fā)隔離性（Isolated）37隔離性（Isolated）37事務(wù)的實(shí)現(xiàn)

私有工作空間與影子更新：當(dāng)進(jìn)程啟動(dòng)事務(wù)T時(shí)，分配一個(gè)私有工作空間W，在提交或中止T前所有的讀寫(xiě)操作都是在W中進(jìn)行0‘3‘影子塊38事務(wù)的實(shí)現(xiàn)私有工作空間與影子更新：0‘3‘影子塊38先寫(xiě)日志（WAL）就地更新（in-place）日志紀(jì)錄〈事務(wù)標(biāo)識(shí)，文件標(biāo)識(shí)，塊號(hào)，前像，后像〉例：39先寫(xiě)日志（WAL）就地更新（in-place）39先寫(xiě)日志協(xié)議回滾（Rollback）:反做（undo）廢棄事務(wù)的更新結(jié)果只有當(dāng)日志成功地寫(xiě)入穩(wěn)存之后，才可以修改文件。如果事務(wù)執(zhí)行成功并被提交，則它的提交記錄將被寫(xiě)入日志。如果事務(wù)異常中止，則用日志來(lái)備份初始狀態(tài)。從日志的未尾開(kāi)始，向回逐個(gè)讀取日志記錄，反做記錄中描述的修改，即回滾處理。在系統(tǒng)崩潰后,日志也可用來(lái)進(jìn)行的恢復(fù)。40先寫(xiě)日志協(xié)議回滾（Rollback）:40示例(a)一個(gè)事務(wù)(b)-(d)每條語(yǔ)句執(zhí)行前的日志41示例(a)一個(gè)事務(wù)(b)-(d)每條語(yǔ)句執(zhí)行前的兩階段提交協(xié)議（two-phasecommitprotocol）

準(zhǔn)備階段：取得一致決定執(zhí)行階段：執(zhí)行命令（提交或廢棄）42兩階段提交協(xié)議（two-phasecommitproto并發(fā)控制(ConcurrencyControl)加鎖法正確性標(biāo)準(zhǔn)：可串行性（serializable）封鎖加鎖：獲得資源上的封鎖解鎖：釋放已擁有的鎖封鎖的類型和相容性讀鎖(R)寫(xiě)鎖(W)鎖的粒度細(xì)粒度：如字段粗粒度：如文件RWR√?W??43并發(fā)控制(ConcurrencyControl)加鎖法RW兩階段封鎖協(xié)議(2PL)恰好在需要或不再需要鎖時(shí)去請(qǐng)求或釋放鎖可能會(huì)導(dǎo)致不一致和死鎖？

加鎖階段開(kāi)鎖階段嚴(yán)格的2PL與2PC結(jié)合避免級(jí)聯(lián)廢棄（cascadedabort)死鎖：等待圖（WFG）

檢查是否有環(huán)路

超時(shí)檢測(cè)（timeout)44兩階段封鎖協(xié)議(2PL)恰好在需要或不再需要鎖時(shí)去請(qǐng)求或釋放樂(lè)觀法(Optimistic)最適合于基于私有工空間的情況讀階段：將文件讀入私有工作區(qū)確認(rèn)階段：提交前，檢查是否有沖突有，則廢棄事務(wù)，重啟。無(wú)，則提交事務(wù)寫(xiě)階段：如可以提交，則將修改內(nèi)容從私有工作區(qū)，寫(xiě)入文件。45樂(lè)觀法(Optimistic)最適合于基于私有工空間的情況時(shí)間戳(Timestamp)每個(gè)事務(wù)的操作帶有該事務(wù)的時(shí)間戳每個(gè)文件帶有對(duì)它操作的最后一個(gè)提交事務(wù)的讀時(shí)間戳、寫(xiě)時(shí)間戳算法：如果當(dāng)前事務(wù)T的時(shí)間戳〉文件的時(shí)間戳，則執(zhí)行；否則，廢棄T;46時(shí)間戳(Timestamp)每個(gè)事務(wù)的操作帶有該事務(wù)的時(shí)間戳?xí)r間戳法示例設(shè)有三個(gè)事務(wù)α，β，γ。T(α)<T(β)<T(γ)TT(φ)47時(shí)間戳法示例設(shè)有三個(gè)事務(wù)α，β，γ。T(α)<T(β)<T(三種方法比較并發(fā)度死鎖性能2PL低有中樂(lè)觀法高無(wú)高（廢棄度低時(shí)）時(shí)間印法較高無(wú)較高48三種方法比較并發(fā)度死鎖性能2PL低有中樂(lè)觀法高無(wú)高（廢棄度低主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖49主要內(nèi)容3.1時(shí)鐘同步493.5分布式系統(tǒng)的死鎖處理通信死鎖和資源死鎖死鎖解決策略鴕鳥(niǎo)法：（忽略問(wèn)題，留給用戶考慮）檢測(cè)法：（允許死鎖發(fā)生，在檢測(cè)到后想辦法恢復(fù)）預(yù)防法：（靜態(tài)的使死鎖在結(jié)構(gòu)上是不可能發(fā)生的）避免法：（在運(yùn)行中，通過(guò)仔細(xì)的分配資源以避免死鎖）實(shí)際在分布式系統(tǒng)中從來(lái)都不采用

銀行家算法[Dijkstra,1965]P<has,max>,free503.5分布式系統(tǒng)的死鎖處理通信死鎖和資源死鎖50檢測(cè)方法：集中式一臺(tái)中心機(jī)器擁有整個(gè)系統(tǒng)（所有資源圖的集合）的資源圖

進(jìn)程-資源等待圖節(jié)點(diǎn)：進(jìn)程P、資源R有向邊:(1)PR請(qǐng)求關(guān)系;(2)RP擁有關(guān)系;死鎖檢測(cè)協(xié)調(diào)者負(fù)責(zé)檢測(cè)死鎖資源圖的維護(hù)策略：當(dāng)資源圖中，有一條邊加入/刪除時(shí)，通知協(xié)調(diào)者每個(gè)進(jìn)程周期性地向協(xié)調(diào)者發(fā)送圖的更新消息協(xié)調(diào)者在需要時(shí)，向參入者請(qǐng)求51檢測(cè)方法：集中式一臺(tái)中心機(jī)器擁有整個(gè)系統(tǒng)（所有資源圖的集合）檢測(cè)方法：集中式舉例假死鎖問(wèn)題：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)情況

解決方案一：協(xié)調(diào)者確認(rèn)（消息的全局時(shí)序）52檢測(cè)方法：集中式舉例假死鎖問(wèn)題：B釋放R,請(qǐng)求T。若請(qǐng)求T消檢測(cè)方法：分布式Chandy－Misra－Haas分布式死鎖檢測(cè)算法，探測(cè)消息：〈阻塞Pid，請(qǐng)求Pid，接收Pid〉e.g.（0,2,3）,（0,4,6）,（0,5,7）,（0,8,0）構(gòu)成死鎖53檢測(cè)方法：分布式Chandy－Misra－Haas分布式死鎖分布式深度限制算法（DWDL）90%的死鎖發(fā)生在兩個(gè)進(jìn)程之間算法：//p1為請(qǐng)求者;L(p1)為p1的壽命1)if(waitQueue=p2->p1->p0)thenif(L(p1)<L(p2)orL(p1))<L(p0)thenrestartp1;elserestartp0;2)if(waitQueue=p1->p1'->p0)thenif(L(p'1)<L(p1)orL(p'1)<L(p0))thenrestartp'1;elserestartp0;3)if(waitQueue=p2->p1->p'1->p0)thenif(L(p1)<L(p2)orL(p1)<L(p0))thenrestartp1;elserestartp'1;54分布式深度限制算法（DWDL）90%的死鎖發(fā)生在兩個(gè)進(jìn)程之間等-死算法(wait-die)設(shè)請(qǐng)求進(jìn)程0的時(shí)間印t0,擁有資源的進(jìn)程1的時(shí)間印t1如果t0<t1,0等待;否則，撤銷0分布式死鎖預(yù)防55等-死算法(wait-die)分布式死鎖預(yù)防55分布式死鎖的預(yù)防傷-等算法（wound-wait)設(shè)請(qǐng)求進(jìn)程0的時(shí)間印t0,擁有資源的進(jìn)程1的時(shí)間印t1如果t0<t1，撤銷1;否則，0等待56分布式死鎖的預(yù)防傷-等算法（wound-wait)56第3章分布式系統(tǒng)的同步

中國(guó)科技大學(xué)軟件學(xué)院丁箐57第3章分布式系統(tǒng)的同步中國(guó)科技大學(xué)軟件學(xué)院1主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖58主要內(nèi)容3.1時(shí)鐘同步2主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖59主要內(nèi)容3.1時(shí)鐘同步33.1時(shí)鐘同步分布式算法的特點(diǎn)相關(guān)信息散布在多個(gè)場(chǎng)地上每個(gè)進(jìn)程只能基于本地信息做決定應(yīng)避免因單點(diǎn)故障造成整個(gè)系統(tǒng)的失敗不存在公共時(shí)鐘或精確的全局時(shí)間603.1時(shí)鐘同步分布式算法的特點(diǎn)4時(shí)鐘同步問(wèn)題例：makefile誤差時(shí)間output.o：cc–Coutput.c61時(shí)鐘同步問(wèn)題例：makefile誤差時(shí)間output.o：邏輯時(shí)鐘計(jì)時(shí)器：石英晶體+計(jì)數(shù)器時(shí)鐘偏差（clockskew）邏輯時(shí)鐘：相對(duì)時(shí)間物理時(shí)鐘：真實(shí)時(shí)間“之前”關(guān)系:事件a在b之前出現(xiàn)，則aba為發(fā)送消息m，b為接收m，則ab具有傳遞性：ab,bc,則ac并發(fā)事件（concurrent）62邏輯時(shí)鐘計(jì)時(shí)器：石英晶體+計(jì)數(shù)器6Lamport算法對(duì)每一事件a，在所有進(jìn)程中都認(rèn)可給它分配一個(gè)時(shí)間值C(a）ifab;則C(a)<C(b)a,bC(a)C(b)C是遞增的校正算法ab，ifC(b)<C(a),則C(b)=C(a)+163Lamport算法對(duì)每一事件a，在所有進(jìn)程中都認(rèn)可給它分配一Lamport算法時(shí)間慢快慢快64Lamport算法時(shí)間慢快慢快8物理時(shí)鐘與現(xiàn)實(shí)時(shí)鐘（1）如何用現(xiàn)實(shí)世界的時(shí)鐘將它們同步起來(lái)；（2）如何使各時(shí)鐘之間保持同步。

太陽(yáng)日：連續(xù)的兩次日中天的時(shí)間太陽(yáng)秒：solar-day/86400平均太陽(yáng)秒：如，格林威治時(shí)間65物理時(shí)鐘與現(xiàn)實(shí)時(shí)鐘（1）如何用現(xiàn)實(shí)世界的時(shí)鐘將它們同步起來(lái)；現(xiàn)實(shí)時(shí)鐘銫原子鐘：9192631770次躍遷=1秒TAI秒：國(guó)際原子時(shí)間UTC秒：世界時(shí)間（在TAI秒中加入閏秒）時(shí)間服務(wù)：WWV電臺(tái)、GEOS衛(wèi)星102066現(xiàn)實(shí)時(shí)鐘銫原子鐘：9192631770次躍遷=1秒10201時(shí)鐘同步算法如何與現(xiàn)實(shí)時(shí)鐘同步如何使不同機(jī)器之間相互同步設(shè)機(jī)器時(shí)鐘值Cp(t),t為UTC時(shí)間最大偏移率精確時(shí)鐘：dC/dt=1快時(shí)鐘：dC/dt〉1慢時(shí)鐘：dC/dt<167時(shí)鐘同步算法如何與現(xiàn)實(shí)時(shí)鐘同步11Christian’s算法--逐步調(diào)整法時(shí)間服務(wù)器，可接受WWV的UTC時(shí)間每隔δ/2ρ校準(zhǔn)時(shí)間（允許誤差δ，存在誤差ρ）兩個(gè)問(wèn)題：時(shí)間決不能倒退,延遲假設(shè)：每秒產(chǎn)生100次中斷，每次中斷將時(shí)間加10毫秒若調(diào)慢時(shí)鐘，中斷服務(wù)程序每次只加9毫秒；若加快時(shí)鐘，則加11毫秒。傳播時(shí)間68Christian’s算法--逐步調(diào)整法時(shí)間服務(wù)器，Berkeley算法–主動(dòng)式方法時(shí)間監(jiān)控器定期查詢其他機(jī)器時(shí)間計(jì)算出平均值通知其他機(jī)器調(diào)整時(shí)間69Berkeley算法–主動(dòng)式方法時(shí)間監(jiān)控器定期查詢其他平均值算法–非集中式方法將時(shí)間劃分成固定長(zhǎng)度的再同步間隔，第i次間隔開(kāi)始于T0+iR，而結(jié)束于T0+(i+1)R所有機(jī)器廣播自己的時(shí)鐘時(shí)間啟動(dòng)本地計(jì)時(shí)器收集在S時(shí)間間隔中到達(dá)的其他機(jī)器廣播的時(shí)間執(zhí)行平均時(shí)間計(jì)算算法，得到新的時(shí)間值（取平均值，去掉兩端值）70平均值算法–非集中式方法將時(shí)間劃分成固定長(zhǎng)度的再同步間隔多個(gè)外部時(shí)間源法例：OSFDCE方法接受所有時(shí)間源的當(dāng)前UTC區(qū)間去掉與其他區(qū)間不相交的區(qū)間將相交部分的中點(diǎn)作為校準(zhǔn)時(shí)間時(shí)間71多個(gè)外部時(shí)間源法例：OSFDCE方法時(shí)間15使用同步時(shí)鐘最多一次消息提交每個(gè)消息攜帶一個(gè)ID和一個(gè)時(shí)間印ts（timestamp）服務(wù)器的表T中，記錄每個(gè)連接C最近的時(shí)間印t如果到達(dá)的消息m，ts(m)<t,則拒絕m

服務(wù)器要一直保存一個(gè)全局變量G=CurrentTime–MaxLifetime–MaxClockSkew所有<G的時(shí)間印從表T中清除對(duì)于具有新的ID的到達(dá)消息m,如果ts(m)<G則拒絕m,否則，接受m按照一定時(shí)間間隔T，定期地將G寫(xiě)入磁盤。當(dāng)系統(tǒng)重啟后，G’=G+T72使用同步時(shí)鐘最多一次消息提交服務(wù)器要一直保存一個(gè)全使用同步時(shí)鐘基于時(shí)鐘的緩存一致性當(dāng)客戶讀取一個(gè)副本到緩存時(shí)，設(shè)置一個(gè)租期（lease）在租期過(guò)期之前，客戶可更新副本，重續(xù)租期如果已經(jīng)過(guò)期，緩存中的副本失效改進(jìn)的一致性協(xié)議當(dāng)客戶修改文件時(shí)，只需將所有沒(méi)有到期的緩存副本設(shè)為無(wú)效如果某個(gè)客戶崩潰，則等待直到該客戶的租期過(guò)期73使用同步時(shí)鐘基于時(shí)鐘的緩存一致性改進(jìn)的一致性協(xié)議1主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖74主要內(nèi)容3.1時(shí)鐘同步183.2互斥基本概念當(dāng)一個(gè)進(jìn)程使用某個(gè)共享資源，其他進(jìn)程不允許對(duì)這個(gè)資源操作臨界區(qū)（CriticalSection）：對(duì)共享資源進(jìn)行操作的程序段基本方法：信號(hào)量、管程問(wèn)題：死鎖活鎖饑餓753.2互斥基本概念19集中式算法（仿照單處理機(jī)系統(tǒng)的方法）協(xié)調(diào)者：確定那個(gè)進(jìn)程可進(jìn)入臨界區(qū)通信量：3個(gè)消息：請(qǐng)求-許可-釋放缺點(diǎn)：?jiǎn)吸c(diǎn)失敗單協(xié)調(diào)者會(huì)成為執(zhí)行的瓶頸

CCC76集中式算法（仿照單處理機(jī)系統(tǒng)的方法）協(xié)調(diào)者：確定那個(gè)進(jìn)程可WinThread臨界區(qū)CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeCriticalSection()EnterCriticalSection()LeaveCriticalSection()77WinThread臨界區(qū)CreateMutex()21分布式算法（Ricart-Agrawala算法）要求系統(tǒng)中所有事件都是全序的1.在一個(gè)進(jìn)程P打算進(jìn)入臨界區(qū)R之前，向所有其他進(jìn)程廣播消息<臨界區(qū)R名、進(jìn)程號(hào)、時(shí)間印>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，但是還沒(méi)有進(jìn)入時(shí)，則將發(fā)來(lái)的消息和它發(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消息。78分布式算法（Ricart-Agrawala算法）要求系統(tǒng)中所分布式算法舉例舉例：

共有0，1，2三個(gè)進(jìn)程。進(jìn)程0，2申請(qǐng)進(jìn)入臨界區(qū)02002279分布式算法舉例舉例：共有0，1，2三個(gè)進(jìn)程。0200222分布式算法評(píng)價(jià)缺點(diǎn)：n點(diǎn)失敗n點(diǎn)瓶頸2（n-1)個(gè)消息改進(jìn)方案：超時(shí)重發(fā)組通信簡(jiǎn)單多數(shù)同意比原來(lái)集中式算法慢，復(fù)雜，昂貴，而且不健壯。80分布式算法評(píng)價(jià)缺點(diǎn)：24令牌環(huán)算法構(gòu)造一個(gè)邏輯環(huán)，得到令牌才可進(jìn)入臨界區(qū)381令牌環(huán)算法構(gòu)造一個(gè)邏輯環(huán)，得到令牌才可進(jìn)入臨界區(qū)325三種互斥算法的比較算法每次進(jìn)出需要的消息進(jìn)入前的延遲（按消息次數(shù)）存在問(wèn)題集中式32協(xié)調(diào)者崩潰分布式2（n-1）2（n-1）任何一個(gè)進(jìn)程崩潰令牌環(huán)1到∞0到n-1丟失令牌，進(jìn)程崩潰82三種互斥算法的比較算法每次進(jìn)出進(jìn)入前的延遲（按消息次數(shù)）存在主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖83主要內(nèi)容3.1時(shí)鐘同步273.3選舉算法許多分布式算法需要一個(gè)進(jìn)程充當(dāng)協(xié)調(diào)者，發(fā)起者，排序者或其他特定的角色。作用：做出統(tǒng)一的的決定例如：確定協(xié)調(diào)者843.3選舉算法許多分布式算法需要一個(gè)進(jìn)程充當(dāng)協(xié)調(diào)者，發(fā)起欺負(fù)（Bully）算法將進(jìn)程進(jìn)行排序P向高的進(jìn)程發(fā)E消息如果沒(méi)有響應(yīng)，P選舉獲勝如果有進(jìn)程Q響應(yīng),則P結(jié)束，Q接管選舉并繼續(xù)下去。45656465685欺負(fù)（Bully）算法將進(jìn)程進(jìn)行排序45656465629環(huán)算法所有進(jìn)程按邏輯或物理次序排序，形成一個(gè)環(huán)當(dāng)一個(gè)進(jìn)程P發(fā)現(xiàn)協(xié)調(diào)者C失效后，向后續(xù)進(jìn)程發(fā)送E消息每個(gè)進(jìn)程繼續(xù)向后傳遞E消息，直到返回PP在將新確定的協(xié)調(diào)者C’傳給所有進(jìn)程5286環(huán)算法所有進(jìn)程按邏輯或物理次序排序，形成一個(gè)環(huán)5230主要內(nèi)容3.1時(shí)鐘同步3.2互斥3.3選舉算法3.4原子性事務(wù)3.5分布式系統(tǒng)中的死鎖87主要內(nèi)容3.1時(shí)鐘同步313.4原子性（Atomic）事務(wù)原子性：組成原子事務(wù)的一組操作要么全部執(zhí)行，要么一個(gè)也不執(zhí)行，并且事務(wù)失敗后能返回到最初狀態(tài)例1：老式磁帶系統(tǒng)（備份）例2：匯款（提款存款）883.4原子性（Atomic）事務(wù)原子性：組成原子事務(wù)的事務(wù)模型穩(wěn)定存儲(chǔ)器（StableStorage）：通過(guò)一對(duì)雙工磁盤實(shí)現(xiàn)89事務(wù)模型穩(wěn)定存儲(chǔ)器（StableStorage）：33事務(wù)原語(yǔ)（1）BEGIN_TRANSACTION：標(biāo)記一個(gè)事務(wù)的開(kāi)始；（2）END_TRANSACTION：結(jié)束事務(wù)并設(shè)法提交；（3）ABORT_TRANSACTION：取消事務(wù)并恢復(fù)舊值；（4）READ：從一個(gè)文件（或其他類型的對(duì)象，如數(shù)據(jù)庫(kù)）讀取數(shù)據(jù)；（5）WRITE：將數(shù)據(jù)寫(xiě)入一個(gè)文件（或其他類型的對(duì)象，如數(shù)據(jù)庫(kù)）90事務(wù)原語(yǔ)（1）BEGIN_TRANSACTION：標(biāo)記一個(gè)事務(wù)舉例BEGINTRANSACTIONreserveWP－JFKreserveJFK－NairobireserveNairobi－MalindiENDTRANSACTION

BEGINTRANSACTIONreserveWP－JFKreserveJFK－Nairobi

Nairobi－MalindifullABORTTRASACTION

當(dāng)?shù)谌齻€(gè)航班的機(jī)票預(yù)定失敗后事務(wù)中止預(yù)定三個(gè)航班機(jī)票：中轉(zhuǎn)站是JFK、Nairobi91事務(wù)舉例BEGINTRANSACTION預(yù)定三個(gè)航班機(jī)票：事務(wù)的特性

原子性（Atomic）：對(duì)外部世界來(lái)說(shuō)，事務(wù)的發(fā)生是不可分割的；一致性（Consistent）：事務(wù)不會(huì)破壞系統(tǒng)的恒定；隔離性（Isolated）：并發(fā)的事務(wù)之間不會(huì)互相干擾；可串行性（Serializable）:多個(gè)事務(wù)并發(fā)執(zhí)行的結(jié)果，與它們順序地執(zhí)行效果相同。持久性（Durable）：一旦一個(gè)事務(wù)提交，它的更新結(jié)果不會(huì)因故障而丟失。92事務(wù)的特性原子性（Atomic）：對(duì)外部世界來(lái)說(shuō)，事務(wù)的發(fā)隔離性（Isolated）93隔離性（Isolated）37事務(wù)的實(shí)現(xiàn)

私有工作空間與影子更新：當(dāng)進(jìn)程啟動(dòng)事務(wù)T時(shí)，分配一個(gè)私有工作空間W，在提交或中止T前所有的讀寫(xiě)操作都是在W中進(jìn)行0‘3‘影子塊94事務(wù)的實(shí)現(xiàn)私有工作空間與影子更新：0‘3‘影子塊38先寫(xiě)日志（WAL）就地更新（in-place）日志紀(jì)錄〈事務(wù)標(biāo)識(shí)，文件標(biāo)識(shí)，塊號(hào)，前像，后像〉例：95先寫(xiě)日志（WAL）就地更新（in-place）39先寫(xiě)日志協(xié)議回滾（Rollback）:反做（undo）廢棄事務(wù)的更新結(jié)果只有當(dāng)日志成功地寫(xiě)入穩(wěn)存之后，才可以修改文件。如果事務(wù)執(zhí)行成功并被提交，則它的提交記錄將被寫(xiě)入日志。如果事務(wù)異常中止，則用日志來(lái)備份初始狀態(tài)。從日志的未尾開(kāi)始，向回逐個(gè)讀取日志記錄，反做記錄中描述的修改，即回滾處理。在系統(tǒng)崩潰后,日志也可用來(lái)進(jìn)行的恢復(fù)。96先寫(xiě)日志協(xié)議回滾（Rollback）:40示例(a)一個(gè)事務(wù)(b)-(d)每條語(yǔ)句執(zhí)行前的日志97示例(a)一個(gè)事務(wù)(b)-(d)每條語(yǔ)句執(zhí)行前的兩階段提交協(xié)議（two-phasecommitprotocol）

準(zhǔn)備階段：取得一致決定執(zhí)行階段：執(zhí)行命令（提交或廢棄）98兩階段提交協(xié)議（two-phasecommitproto并發(fā)控制(ConcurrencyControl)加鎖法正確性標(biāo)準(zhǔn)：可串行性（serializable）封鎖加鎖：獲得資源上的封鎖解鎖：釋放已擁有的鎖封鎖的類型和相容性讀鎖(R)寫(xiě)鎖(W)鎖的粒度細(xì)粒度：如字段粗粒度：如文件RWR√?W??99并發(fā)控制(ConcurrencyControl)加鎖法RW兩階段封鎖協(xié)議(2PL)恰好在需要或不再需要鎖時(shí)去請(qǐng)求或釋放鎖可能會(huì)導(dǎo)致不一致和死鎖？

加鎖階段開(kāi)鎖階段嚴(yán)格的2PL與2PC結(jié)合避免級(jí)聯(lián)廢棄（cascadedabort)死鎖：等待圖（WFG）

檢查是否有環(huán)路

超時(shí)檢測(cè)（timeout)100兩階段封鎖協(xié)議(2PL)恰好在需要或不再需要鎖時(shí)去請(qǐng)求或釋放樂(lè)觀法(Optimistic)最適合于基于私有工空間的情況讀階段：將文件讀入私有工作區(qū)確認(rèn)階段：提交前，檢查是否有沖突有，則廢棄事務(wù)，重啟。無(wú)，則提交事務(wù)寫(xiě)階段：如可以提交，則將修改內(nèi)容從私有工作區(qū)，寫(xiě)入文件。101樂(lè)觀法(Optimistic)最適合于基于私有工空間的情況時(shí)間戳(Timestamp)每個(gè)事務(wù)的操作帶有該事務(wù)的時(shí)間戳每個(gè)文件帶有對(duì)它操作的最后一個(gè)提交事務(wù)的讀時(shí)間戳、寫(xiě)時(shí)間戳算法：如果當(dāng)前事務(wù)T的時(shí)間戳〉文件的時(shí)間戳，則執(zhí)行；否則，廢棄T;102時(shí)間戳(Timestamp)每個(gè)事務(wù)的操作帶有該事務(wù)的時(shí)間戳?xí)r間戳法示例設(shè)有三個(gè)事務(wù)α，β，γ。T(α)<T(β)<T(γ)TT(φ)103時(shí)間戳法示例設(shè)有三個(gè)事務(wù)α，β，γ。T(α)<T(β)<T(三種方法比較并發(fā)度死鎖性能2PL低有中