第五章分布式系統(tǒng)

1、第五章 同步時鐘同步邏輯時鐘全局狀態(tài)選舉算法互斥分布式事務(wù)時鐘同步p物理時鐘p時鐘同步算法p使用同步時鐘分布式系統(tǒng)中進(jìn)行時鐘同步是個簡單的事情么?32022-7-5時鐘同步Clock Synchronization Example of UNIX make UNIX的make只是重新編譯已經(jīng)出現(xiàn)變化的文件 在分布式系統(tǒng)中，有些困難 解決方案：同步分布式系統(tǒng)中的所有時鐘42022-7-5物理時鐘Physical Clocks 計算機計時器的工作原理 通常是一個精確的石英晶體，有兩個寄存器：一個計數(shù)器和一個保持寄存器（holding register） 每個石英震蕩將計數(shù)器中的數(shù)字減1，當(dāng)計數(shù)器的

2、值變成0，發(fā)出一個中斷，再將保持寄存器中的值放入計數(shù)器 每個中斷被稱為一個時鐘嘀嗒 (clock tick)52022-7-5時鐘偏移 (Clock Skew) 在分布式系統(tǒng)中，不可能保證不同的計算機系統(tǒng)中的石英晶體有同樣的頻率 時間值之間的不同被稱為時鐘偏移（clock skew） 解決方案: 一些系統(tǒng)需要外部的物理時鐘62022-7-5國際原子時間 (TAI) 原子時鐘 (Atomic clock) 元素銫133 的原子9,192,631,770次躍遷被定義為1秒 國際原子時間International Atomic Time (TAI) 全世界有約50家實驗室擁有銫133 時鐘 BIH(

3、巴黎的原子時鐘機構(gòu))將這些時間平均，作為TAI 問題 現(xiàn)在每 86,400 TAI 秒小于一個平均的solar day，誤差是3毫秒72022-7-5UTC(統(tǒng)一協(xié)調(diào)時間) Universal Coordinated Time (UTC) BIH當(dāng)TAI和solar time的時間相差 800 毫秒之后引入一個閏秒(leap seconds ) 當(dāng)BIH引入一個閏秒的是歐，電力公司需要調(diào)整UTC時間 計算機操作系統(tǒng)必須有特別的軟件才能產(chǎn)生閏秒82022-7-5UTC Service 國際標(biāo)準(zhǔn)時間研究所National Institute of Standard Time (NIST) 擁有一個

4、名為WWV的短波電臺用于在每個UTC秒結(jié)束的時候產(chǎn)生一個脈沖 在英國，Rugby擁有一個名為MSF的同樣的電臺 有一些地球衛(wèi)星也提供UTC服務(wù)92022-7-5Cristians Algorithm 如果一個系統(tǒng)中有一臺機器擁有WWV接收器，并且希望系統(tǒng)中其它機器能夠與這臺機器同步 稱擁有WWV接收器的機器為時間服務(wù)器(time server) 每臺機器向時間服務(wù)器發(fā)送消息詢問當(dāng)前時間，時間服務(wù)器將當(dāng)前的時間CUTC發(fā)送回去102022-7-5Problems 當(dāng)發(fā)送方得到回應(yīng)，將自己的時間調(diào)整到CUTC 主要問題：時間不能回頭time must never run backward 只能一點

5、一點地引入變化 小問題: 回應(yīng)的消息需要時間發(fā)送給發(fā)送方 Cristian算法嘗試估計這個時間 為了提高精確度，Cristian建議不只用一次測量結(jié)果，而是用多次測量結(jié)果時間一定要與UTC時間一致嗎？112022-7-5Berkeley Algorithm 時間服務(wù)器是主動的,不斷輪詢每個機器的時間 基于結(jié)果,計算所有的平均值,并將計算結(jié)果告知其它機器,讓其它機器根據(jù)結(jié)果調(diào)整時鐘122022-7-5Averaging Algorithms 將時間分成定長的同步時間間隔，在每個間隔開始的時候，每個機器把自己的時鐘時間廣播給其它的機器 廣播之后，機器啟動本地的一個計時器來保證在一個S的時間間隔內(nèi)收

6、集從其它機器到來的時間 計算其它機器時間的平均值 放棄m個最高的和m個最低的 嘗試對每個消息加上一個估計的傳播時間來修正收到的時間 Example: Network Time Protocol (NTP)132022-7-5使用同步時鐘Use of Synchronized Clocks 現(xiàn)在，軟件和硬件的同步時鐘都已經(jīng)有了廣泛應(yīng)用 已經(jīng)可以將上百萬的時鐘在一個UTC的微秒內(nèi)進(jìn)行同步 Application 保證對服務(wù)器的至多一次（at-most-once）的消息發(fā)送 保證Cache的一致性邏輯時鐘pLamport時間戳為什么要設(shè)計邏輯時鐘?152022-7-5邏輯時鐘Logical Cloc

7、ks 最重要的是時鐘的內(nèi)部一致性，并不關(guān)心時鐘是否特別接近于真正的時間 如果兩個進(jìn)程不交互，沒有必要讓他們的時鐘同步因為缺少同步不會導(dǎo)致任何問題 所有進(jìn)程是否都同意當(dāng)前的時間并不重要，關(guān)鍵是大家都同意事件發(fā)生的先后順序162022-7-5Lamport時間戳- Happens-before(先發(fā)生) 表達(dá)式 ab 讀成 a happen before b 在以下兩種情況 但如果a和b是同一個進(jìn)程中的兩個事件，a在b之前發(fā)生，則 ab 為true 如果a是一個進(jìn)程發(fā)送消息的事件，b是另一個進(jìn)程接收這個消息的事件，則ab為 true Happens-before是一個傳遞關(guān)系 如果C(a)是事件a

8、的時鐘，則如果 ab, 則C(a)C(b) C的值可以增加，但不可以減少172022-7-5Lamport timestamps- Example182022-7-5Lamport timestamps- Total Ordering of All Events 沒有兩個事件發(fā)生在同一個時刻 保證兩個事件的發(fā)生時間之間至少有一個tick 可以將進(jìn)程號添加在時間的后面，用于區(qū)分兩個事件的發(fā)生時間 Example: 40.1, 40.2192022-7-5Lamport timestamps- The rules of time in DS The rules of time in DS 如果在同

9、一個進(jìn)程中a happens before b，則 C(a)C(b) 如果a和b分別表示一個消息的發(fā)送和接收，則C(a) JFK; reserve JFK - Nairobi; reserve Nairobi - Malindi full =ABORT_TRANSACTIONn (b)nBEGIN_TRANSACTION reserve WP - JFK; reserve JFK - Nairobi; reserve Nairobi - Malindi;END_TRANSACTIONn (a)492022-7-5事務(wù)的特點 ACID Atomic（原子性） 對于外部世界，事務(wù)是不可分的 Con

10、sistent 事務(wù)不能破壞系統(tǒng)的不變量 Isolated(獨立性) 并發(fā)事務(wù)不能相互影響 Durable(持久性) 一旦一個事務(wù)提交，其產(chǎn)生的改變將是永久的502022-7-5Flat Transaction(單層事務(wù)) 事務(wù)的最簡單類型 不允許部分結(jié)果被提交或者放棄nBEGIN_TRANSACTION reserve WP - JFK; reserve JFK - Nairobi; reserve Nairobi - Malindi full =ABORT_TRANSACTIONn (b)nBEGIN_TRANSACTION reserve WP - JFK; reserve JFK -

11、Nairobi; reserve Nairobi - Malindi;END_TRANSACTIONn (a)512022-7-5Nested Transaction(嵌套事務(wù)) 由很多的子事務(wù)組成 最頂層的事務(wù)可以產(chǎn)生可以并發(fā)在不同機器上執(zhí)行的孩子，以獲取性能上的提升或者簡化程序設(shè)計 當(dāng)雙親失敗時，將整個系統(tǒng)恢復(fù)到頂層事務(wù)開始之前的狀態(tài)。因此，提交過的所有子事務(wù)都需要回滾。 持久性只是頂層事務(wù)才有的特性 需要做大量的管理工作以保證正確性522022-7-5Distributed Transaction(分布式事務(wù)) 是由扁平的子事務(wù)組成，操作的數(shù)據(jù)分散地放在多個機器上 嵌入式事務(wù)和分布式事務(wù)

12、的區(qū)別 嵌入式事務(wù)邏輯上由多個有層次的子事務(wù)組成 分布式事務(wù)邏輯上是一個扁平的、不可分的事務(wù)，其處理的數(shù)據(jù)處于分布式系統(tǒng)中的多個機器上532022-7-5Private Workspace 當(dāng)一個事務(wù)開始，就給這個事務(wù)一個Private Workspace 用于包含所有訪問的文件的副本 直到事務(wù)提交或者失敗，所有對數(shù)據(jù)的讀和寫都在Private Workspace中解決，而不是寫到文件系統(tǒng)中 Optimization 當(dāng)一個進(jìn)程讀文件但是不需要修改文件數(shù)據(jù)，就不需要保存這個文件的副本 當(dāng)一個文件打開用于寫，除非是第一次復(fù)制到Private Workspace，不要再復(fù)制 當(dāng)復(fù)制的時候，只復(fù)制文

13、件的索引542022-7-5Example In UNIX, the index is inode552022-7-5寫前日志W(wǎng)riteahead Log Writeahead log (寫前日志) 當(dāng)文件被修改的時候，一個記錄被寫在日志中用于記錄 哪個事務(wù)提交了改變 哪個文件哪一塊被修改了 修改之前的值和修改之后的值 只有在日志被成功地寫之后才能夠?qū)⑿薷奶峤唤o文件 Rollback(回退，回滾) 使用日志來回滾到原來的狀態(tài)562022-7-5ExamplenLognx = 0 / 1ny = 0/2nx = 1/4n (d)nLognx = 0 / 1ny = 0/2n (c) nLognx

14、 = 0 / 1n (b)nx = 0;ny = 0;nBEGIN_TRANSACTION;n x = x + 1;n y = y + 2n x = y * y;nEND_TRANSACTION;n (a) 572022-7-5為防止事務(wù)并發(fā)執(zhí)行出錯事務(wù)在共享數(shù)據(jù)上的執(zhí)行要小心582022-7-5Concurrency Control(并發(fā)控制) 目標(biāo) 允許幾個事務(wù)能夠同時執(zhí)行，但是所有被操作的數(shù)據(jù)項集合能夠保持一致性狀態(tài) 通過讓各個事務(wù)以一個特定的順序訪問數(shù)據(jù)項來實現(xiàn) 組織形式 Data manager(數(shù)據(jù)管理器) 讀寫操作 Scheduler (調(diào)度器) 控制并發(fā)性 Transactio

15、n manager(事務(wù)管理器) 保證原子屬性592022-7-5Example 每個位置有自己的調(diào)度器和數(shù)據(jù)管理器，一起負(fù)責(zé)保證本地數(shù)據(jù)保持一致性 每個事務(wù)被一個單獨的事務(wù)管理器控制602022-7-5Serializability(串行性) 目標(biāo) 多個事務(wù)可以同時執(zhí)行 但是最終的結(jié)果與這些事務(wù)一個一個按照某種特定順序執(zhí)行是一樣的 ExampleBEGIN_TRANSACTION x = 0; x = x + 3;END_TRANSACTION (c)BEGIN_TRANSACTION x = 0; x = x + 2;END_TRANSACTION (b)BEGIN_TRANSACTION

16、 x = 0; x = x + 1;END_TRANSACTION (a)Illegalx = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3;Schedule 3Legalx = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3;Schedule 2Legalx = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3Schedule 1(d)This is serializedThis is NOT serialized612022-7-5Confl

17、icting Operations(沖突操作) 兩個操作如果要處理同一個數(shù)據(jù)項，并且至少一個是一個寫操作，則稱兩個操作沖突 read-write 沖突 write-write 沖突 并發(fā)控制算法可以通常通過他們?nèi)绾螌ψx寫操作進(jìn)行同步而進(jìn)行分類622022-7-5Two-Phase Locking(兩階段鎖定) 兩階段鎖定Two phase locking(2PL) 最古老并且最廣泛使用的同步算法 Growing(增長階段) phase: 獲取所有需要的鎖 Shrinking (收縮階段) phase: 釋放所有的鎖632022-7-5規(guī)則 當(dāng)調(diào)度器從事務(wù)管理器接收了一個操作，它檢測這個操作是否

18、與已經(jīng)獲取了鎖的任何其它操作沖突。 如果有沖突存在，延遲操作； 如果沒有沖突，給這個操作一個鎖并將操作交給數(shù)據(jù)管理執(zhí)行 當(dāng)數(shù)據(jù)管理器聲明它已經(jīng)執(zhí)行了某個鎖所設(shè)定的操作，調(diào)度器可以釋放鎖。 一旦調(diào)度器已經(jīng)釋放了一個事務(wù)的鎖，它將不會再給這個事務(wù)另一個鎖642022-7-5嚴(yán)格的兩階段鎖定 收縮階段在所有事務(wù)已經(jīng)結(jié)束運行的時候發(fā)生 不論這個事務(wù)是提交了還是失敗了 Advantages 消除了Eliminates瀑布型終止 (cascaded aborts) 不得不取消一個已經(jīng)提交的事務(wù)，因為它看到了不應(yīng)該看到的數(shù)據(jù)項652022-7-5死鎖Deadlock 如果兩個進(jìn)程每個都試圖用相反的順序獲取同

19、樣的一對鎖，可能會導(dǎo)致死鎖 用規(guī)范的順序獲取所有的鎖以防止擁有并等待環(huán) 通過維護(hù)一個明晰的圖，圖中表明哪個進(jìn)程擁有哪個鎖，這樣就可以事先知道相關(guān)信息并保證沒有環(huán)存在 Timeout機制 如果鎖被同一個事務(wù)持續(xù)擁有超過 t 秒，一定就存在死鎖662022-7-5可否不用鎖？672022-7-5兩種并發(fā)控制方法 Pessimistic approaches(悲觀方法) 如果壞事會發(fā)生，那就一定會發(fā)生 在操作執(zhí)行之前就把這些操作進(jìn)行同步 Optimistic approaches (樂觀方法) 一切都會正常 因此所有操作都會簡單地執(zhí)行，而同步在事務(wù)完成之后發(fā)生 如果在同步時發(fā)現(xiàn)沖突發(fā)生，一個或者多個

20、事務(wù)將被迫失敗回滾時間戳排序 時間戳排序 每個事務(wù)T開始時給它分配一個時間戳ts(T) 使用Lamport算法，可以保證時間戳唯一 事務(wù)T的每個操作都被蓋上時間戳ts(T) 系統(tǒng)中的每個數(shù)據(jù)項x都有一個相關(guān)的讀時間戳tsRD(x) 和寫時間戳tsWR(x) 讀時間戳被設(shè)置為最近讀x的事務(wù)的時間戳 寫時間戳是最近修改x的事務(wù)的時間戳。 使用時間戳排序，如果兩個操作沖突，則數(shù)據(jù)管理器先處理時間戳最早的操作。悲觀的時間戳排序基本原則：基于Murphy定律：如果某事務(wù)可以出錯，那么它就會出錯。悲觀方法意味著沖突在允許發(fā)生之前就解決了。思想：每個事務(wù)指定一個時間戳，文件都有相關(guān)的讀時間戳和寫時間戳如果事

21、務(wù)的進(jìn)程試圖訪問文件時，文件的讀時間戳和寫時間戳都比此事務(wù)的時間戳更早（?。?，這種關(guān)系是正常的反之，說明當(dāng)前事務(wù)提交太晚，應(yīng)該終止。悲觀的時間戳排序 規(guī)則： 老事務(wù)Tj不可以修改年輕事務(wù)Ti已經(jīng)讀過或者提交的數(shù)據(jù)； 老事務(wù)Tj不可以讀年輕事務(wù)Ti已經(jīng)寫過的數(shù)據(jù)； 年輕事務(wù)可以讀老事務(wù)提交的數(shù)據(jù)； 年輕事務(wù)可以寫未被更年輕的事務(wù)讀過、且未被更年輕的事務(wù)提交的數(shù)據(jù)；示例 假設(shè) 有三個事務(wù)T1、 T2和T3，共享文件 T1運行得早，已經(jīng)讀寫過文件 文件的時間戳已經(jīng)設(shè)置為T1的時間戳 T2和T3同時開始并發(fā)執(zhí)行，但T2的時間戳小于T3，即ts(T2)ts(T3) 若T3還未提交 tsRD(x)和tsW

22、R(x) 是T1的時間戳 ts(T2)比tsRD(x)和tsWR(x)都大，故寫入可行 T2提交后，其結(jié)果是持久的。T2的時間戳記錄在文件中以當(dāng)作數(shù)據(jù)寫的時間戳。T2寫文件T2寫文件 若T3已經(jīng)提交 tsRD(x)和tsWR(x) 是T3的時間戳 T2事務(wù)就將被中止 采用一個新的時間戳全部重新開始比 較 同加鎖法相比 當(dāng)一個事務(wù)碰到了更大（晚）的時間戳?xí)r，就要中止 而如果使用加鎖法，在相同的情況下要么等待，要么立即執(zhí)行。 時間戳方法不會出現(xiàn)死鎖樂觀的時間戳排序(Optimistic) 樂觀并發(fā)控制法 （Kung and Robinson，1981） 盡管放心去做你想做的，不用在意其他人正在做什

23、么。如果有問題出現(xiàn)，那么以后再考慮吧（許多政治家也采用這個策略）。 樂觀方法是基于錯誤一般不會發(fā)生的觀點，所以操作被簡單地執(zhí)行，在事務(wù)結(jié)束的時候再進(jìn)行同步，如果那時確實發(fā)生了沖突，一個或者更多的事務(wù)將被迫中止。 在實際情況中，沖突相對來說非常少，所以這個策略大部分時間都可以正常工作。沖突的處理 盡管沖突會非常少，但存在的可能性還是有的，因此還需要一些處理沖突的方法。 樂觀并發(fā)控制算法所做的只是 記錄下有哪些文件曾經(jīng)被讀寫過。 在提交時刻，檢測其他的事務(wù)以判斷在本事務(wù)開始后它的文件是否被其他事務(wù)修改過。 如果被修改過，那么本事務(wù)將被中止。 如果沒有修改過，那么本事務(wù)就可以提交了。沖突的處理 樂觀

24、并發(fā)控制算法最適合于基于私有工作空間 每個事務(wù)都獨立地修改各自的文件，不會涉及其他的事務(wù)。 在結(jié)束的時候，新文件要么被提交要么被釋放。 樂觀并發(fā)控制算法的最大優(yōu)點 避免了死鎖，而且允許最大的并行度（進(jìn)程不需要去等待一個鎖） 缺點 有時可能會失效，這時所有事務(wù)都必須退回,重新運行 在重負(fù)載的情況下，算法失效的可能性將會直線上升。死鎖問題p死鎖的預(yù)防p死鎖的檢測和恢復(fù)分布式系統(tǒng)中如何解決死鎖問題?分布式系統(tǒng)中的死鎖 分布式系統(tǒng)中的死鎖類似單處理機系統(tǒng)中的死鎖，只是情況更糟 它們更難于避免、預(yù)防或者檢測 即使在檢測到以后也很難處理，因為所有的相關(guān)信息都分散在多臺機器上。分布式系統(tǒng)中死鎖的問題相當(dāng)嚴(yán)重

25、分布式系統(tǒng)中的死鎖與一般的死鎖不同它們應(yīng)該如何處理?策略的分類 1. 鴕鳥算法:忽略問題2. 預(yù)防:靜態(tài)的，使死鎖在機制上不可能發(fā)生3. 避免:通過仔細(xì)的分配資源以避免死鎖，需要（事先）知道每個進(jìn)程最終到底需要多少資源。而這樣的信息即使有也非常的少4. 檢測與恢復(fù):允許死鎖發(fā)生，在檢測到后想辦法恢復(fù)分布式死鎖預(yù)防 死鎖預(yù)防是由細(xì)致的系統(tǒng)設(shè)計構(gòu)成的，因此死鎖從機制上來說是不可能的。 一些已有的辦法在實踐中都不太方便，例如 在某一時刻只允許進(jìn)程占有一個資源 要求進(jìn)程在初始階段請求所有的資源 當(dāng)進(jìn)程請求新資源時必須釋放所有資源。 或者要求進(jìn)程必須預(yù)定資源，并以嚴(yán)格增序請求資源。 即一個進(jìn)程不可能既占

26、有了一個高序資源又去請求一個低序資源，這就使得環(huán)路不可能出現(xiàn)了。分布式死鎖避免 基于時間戳的算法 在擁有全局時間和原子事務(wù)的分布式系統(tǒng)中，另外兩種實用的算法也是可能的。 這兩種算法都是基于在一個事務(wù)開始時給它分配一個全局時間戳的思想。 同許多基于時間戳的算法一樣，在這兩種算法中保證不會有兩個事務(wù)分配了完全一致的時間戳。 Lamport的算法有效的保證了時間戳是唯一的?；舅枷?當(dāng)一個進(jìn)程因等待一個正被其他進(jìn)程占用的資源而要阻塞時，進(jìn)行檢查以判斷哪個進(jìn)程的時間戳更大（即更晚）。 只有當(dāng)?shù)却M(jìn)程的時間戳小于（早于）被等待進(jìn)程的時間戳，才允許等待發(fā)生，否則中止 沿著等待進(jìn)程鏈，時間戳遞增，不可能發(fā)生

27、環(huán)路 或只有當(dāng)?shù)却M(jìn)程擁有大于（晚于）被等待進(jìn)程的時間戳?xí)r，才允許等待發(fā)生，否則中止沿著等待進(jìn)程鏈，時間戳遞減老進(jìn)程？新進(jìn)程？ 盡管兩種方法都能預(yù)防死鎖，但是給予老的進(jìn)程以優(yōu)先權(quán)更明智些。 它們已經(jīng)運行了較長時間，系統(tǒng)對它們的投入會更大一些 它們占有的資源也就更多一些等-死算法（wait-die） 由于使用了時間戳，當(dāng)請求被占用的資源時只可能有兩種情況： 老進(jìn)程請求被新進(jìn)程占用的資源， 新進(jìn)程請求被老進(jìn)程占用的資源 前一種情況等待 后一種情況中止進(jìn)程資源不可剝奪？ 假設(shè)有事務(wù)存在，一個事務(wù)可以在不成功的情況下重新提交。 當(dāng)沖突發(fā)生的時候，我們不需要中止提出請求的進(jìn)程，我們可以中止資源擁有者 若

28、沒有事務(wù)，中止一個進(jìn)程可能會有嚴(yán)重的后果 例如進(jìn)程可能已經(jīng)修改了文件 而若有事務(wù)，當(dāng)事務(wù)提交失敗時這些效果會消失所以有了新算法傷-等算法（wound-wait） 在傷-等算法中： 當(dāng)較老的進(jìn)程想得到一個被新進(jìn)程占用的資源時，老進(jìn)程將搶占新進(jìn)程的資源，使得新進(jìn)程終止執(zhí)行，等待時機重啟 而當(dāng)較新的進(jìn)程想得到一個被老進(jìn)程占用的資源時，新進(jìn)程將等待。 等-死算法與傷-等算法比較 等-死算法: 若一個老事務(wù)想得到一個正被新事務(wù)占用的資源，那么它會很禮貌的等待 反之，若一個新事務(wù)想得到一個被老事務(wù)占用的資源，它將被中止 盡管它還會重新開始，但很可能又會立即被中止。 在老事務(wù)釋放資源之前，這個循環(huán)可能要重復(fù)

29、多次。 傷-等算法 雖然老進(jìn)程會搶新進(jìn)程的資源導(dǎo)致新進(jìn)程終止 但新進(jìn)程事務(wù)重啟之后若老進(jìn)程還未釋放此資源，新進(jìn)程會等，而不是多次重啟分布式死鎖檢測 在分布式系統(tǒng)中找出一般的死鎖預(yù)防和避免的解決方法是相當(dāng)困難的 嘗試死鎖檢測 集中式死鎖檢測 分布式死鎖檢測集中式的死鎖檢測 集中式的死鎖檢測算法 每臺機器都有一幅資源圖以描述自己所擁有的進(jìn)程和資源 有一臺中心機器擁有整個系統(tǒng)（所有資源圖的集合）的資源圖。 當(dāng)協(xié)調(diào)者檢測到了環(huán)路時它就中止一個進(jìn)程以解決死鎖。全局資源圖信息的維護(hù) 在分布式系統(tǒng)中需要精確維護(hù)全局資源圖。 每臺機器的資源圖中只包含它自己的進(jìn)程和資源。 需要適當(dāng)?shù)姆椒ňS護(hù)全局資源圖信息。 方

30、法1：每當(dāng)資源圖中加入或刪除一條弧時，相應(yīng)的消息就發(fā)送給協(xié)調(diào)者以提供更新。 方法2：每個進(jìn)程周期性的把從上次更新后新添加的和刪除的弧的列表發(fā)送給協(xié)調(diào)者。 比方法1發(fā)送的消息要少。 方法3：協(xié)調(diào)者在需要的時候主動去請求信息。反 例 上述方法的效果都不太好。例如有這樣一種系統(tǒng)： PA和PB運行在機器0上，C運行在機器1上。 共有三種資源S，R和T。 如圖，一開始A擁有S并想請求R，但B正在使用R；C擁有T并想請求S。反例（contd） 協(xié)調(diào)者看到的情況如圖c所示。 這種配置是安全的。一旦B結(jié)束運行，A就可以得到R然后結(jié)束，并釋放C所等待的S。反例（contd） 過一會兒，B釋放R并請求T，這是一個

31、完全合法的安全操作。 機器0向協(xié)調(diào)者發(fā)送一條消息聲明它釋放R 機器1向協(xié)調(diào)者發(fā)送了一條消息聲明進(jìn)程B正在等待它的資源T。 不幸的是，機器1的消息首先到達(dá)，于是 出現(xiàn)環(huán)。 根據(jù)上圖中的信息，協(xié)調(diào)者將錯誤的得出死鎖存在的結(jié)論，并中止某個進(jìn)程。 這種情況稱為假死鎖。 由于信息的不完整和延遲，使得分布式系統(tǒng)中的許多死鎖算法產(chǎn)生了類似的假死鎖問題。假死鎖解決假死鎖問題 解決方法：使用Lamport算法提供全局時間 每個消息加全局時間戳 當(dāng)協(xié)調(diào)者收到了從機器1發(fā)來的有導(dǎo)致死鎖嫌疑的消息后，給每臺機器發(fā)送一條消息 “我剛收到一條會導(dǎo)致死鎖的消息，時間戳為T，若有任何小于T的消息要發(fā)給我，請立即發(fā)送” 當(dāng)每臺機器給出肯定或否定的響應(yīng)之后，協(xié)調(diào)者就會看到環(huán)并不存在，死鎖沒有發(fā)生。 此方法需要全局時間戳，且開銷大。 其他的一些消除假死鎖的方法也很困難。分布式的死鎖檢測 Chandy-Misra-Haas算法（Chandy等，1983）允許進(jìn)程一次請求多個資源而