第五章分布式系統(tǒng)_第1頁(yè)
第五章分布式系統(tǒng)_第2頁(yè)
第五章分布式系統(tǒng)_第3頁(yè)
第五章分布式系統(tǒng)_第4頁(yè)
第五章分布式系統(tǒng)_第5頁(yè)
已閱讀5頁(yè),還剩99頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

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

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

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

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

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

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

9、一個(gè)進(jìn)程中a happens before b,則 C(a)C(b) 如果a和b分別表示一個(gè)消息的發(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ù)的特點(diǎn) ACID Atomic(原子性) 對(duì)于外部世界,事務(wù)是不可分的 Con

10、sistent 事務(wù)不能破壞系統(tǒng)的不變量 Isolated(獨(dú)立性) 并發(fā)事務(wù)不能相互影響 Durable(持久性) 一旦一個(gè)事務(wù)提交,其產(chǎn)生的改變將是永久的502022-7-5Flat Transaction(單層事務(wù)) 事務(wù)的最簡(jiǎn)單類型 不允許部分結(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ā)在不同機(jī)器上執(zhí)行的孩子,以獲取性能上的提升或者簡(jiǎn)化程序設(shè)計(jì) 當(dāng)雙親失敗時(shí),將整個(gè)系統(tǒng)恢復(fù)到頂層事務(wù)開始之前的狀態(tài)。因此,提交過的所有子事務(wù)都需要回滾。 持久性只是頂層事務(wù)才有的特性 需要做大量的管理工作以保證正確性522022-7-5Distributed Transaction(分布式事務(wù)) 是由扁平的子事務(wù)組成,操作的數(shù)據(jù)分散地放在多個(gè)機(jī)器上 嵌入式事務(wù)和分布式事務(wù)

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

13、件的索引542022-7-5Example In UNIX, the index is inode552022-7-5寫前日志W(wǎng)riteahead Log Writeahead log (寫前日志) 當(dāng)文件被修改的時(shí)候,一個(gè)記錄被寫在日志中用于記錄 哪個(gè)事務(wù)提交了改變 哪個(gè)文件哪一塊被修改了 修改之前的值和修改之后的值 只有在日志被成功地寫之后才能夠?qū)⑿薷奶峤唤o文件 Rollback(回退,回滾) 使用日志來(lái)回滾到原來(lái)的狀態(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í)行出錯(cuò)事務(wù)在共享數(shù)據(jù)上的執(zhí)行要小心582022-7-5Concurrency Control(并發(fā)控制) 目標(biāo) 允許幾個(gè)事務(wù)能夠同時(shí)執(zhí)行,但是所有被操作的數(shù)據(jù)項(xiàng)集合能夠保持一致性狀態(tài) 通過讓各個(gè)事務(wù)以一個(gè)特定的順序訪問數(shù)據(jù)項(xiàng)來(lái)實(shí)現(xiàn) 組織形式 Data manager(數(shù)據(jù)管理器) 讀寫操作 Scheduler (調(diào)度器) 控制并發(fā)性 Transactio

15、n manager(事務(wù)管理器) 保證原子屬性592022-7-5Example 每個(gè)位置有自己的調(diào)度器和數(shù)據(jù)管理器,一起負(fù)責(zé)保證本地?cái)?shù)據(jù)保持一致性 每個(gè)事務(wù)被一個(gè)單獨(dú)的事務(wù)管理器控制602022-7-5Serializability(串行性) 目標(biāo) 多個(gè)事務(wù)可以同時(shí)執(zhí)行 但是最終的結(jié)果與這些事務(wù)一個(gè)一個(gè)按照某種特定順序執(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(沖突操作) 兩個(gè)操作如果要處理同一個(gè)數(shù)據(jù)項(xiàng),并且至少一個(gè)是一個(gè)寫操作,則稱兩個(gè)操作沖突 read-write 沖突 write-write 沖突 并發(fā)控制算法可以通常通過他們?nèi)绾螌?duì)讀寫操作進(jìn)行同步而進(jìn)行分類622022-7-5Two-Phase Locking(兩階段鎖定) 兩階段鎖定Two phase locking(2PL) 最古老并且最廣泛使用的同步算法 Growing(增長(zhǎng)階段) phase: 獲取所有需要的鎖 Shrinking (收縮階段) phase: 釋放所有的鎖632022-7-5規(guī)則 當(dāng)調(diào)度器從事務(wù)管理器接收了一個(gè)操作,它檢測(cè)這個(gè)操作是否

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

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

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

21、務(wù)的進(jìn)程試圖訪問文件時(shí),文件的讀時(shí)間戳和寫時(shí)間戳都比此事務(wù)的時(shí)間戳更早(小),這種關(guān)系是正常的反之,說明當(dāng)前事務(wù)提交太晚,應(yīng)該終止。悲觀的時(shí)間戳排序 規(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è) 有三個(gè)事務(wù)T1、 T2和T3,共享文件 T1運(yùn)行得早,已經(jīng)讀寫過文件 文件的時(shí)間戳已經(jīng)設(shè)置為T1的時(shí)間戳 T2和T3同時(shí)開始并發(fā)執(zhí)行,但T2的時(shí)間戳小于T3,即ts(T2)ts(T3) 若T3還未提交 tsRD(x)和tsW

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

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

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

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論