os之分布式系統(tǒng)中的同步問題-資料下載頁
2025-08-04 09:52本頁面
【正文】 用時(shí)間戳進(jìn)行并發(fā)控制 時(shí)間戳 (3) ? 事務(wù)碰到時(shí)間戳較大的文件時(shí) ， 必須終止 ? 時(shí)間戳方法不會(huì)發(fā)生死鎖 ? 大大提升了它的優(yōu)勢(shì) 十、分布式系統(tǒng)中的死鎖 ? 兩種死鎖：通信死鎖和資源死鎖 ? 一個(gè)例子：進(jìn)程 A試著向進(jìn)程 B發(fā)送消息 ? 而進(jìn)程 B試圖向進(jìn)程 C發(fā)送消息 ? 同時(shí)進(jìn)程 C又試圖向進(jìn)程 A發(fā)送消息 ? 這種情況下導(dǎo)致死鎖的原因很多 ? 比如 ， 沒有可用的緩沖區(qū)時(shí)就會(huì)發(fā)生死鎖 資源死鎖 ? 發(fā)生在多個(gè)進(jìn)程搶占需要互斥訪問的 I/O設(shè)備 ， 文件 ， 鎖或其它資源的情況下 ? 通信信道 ， 緩沖區(qū)等也是資源 ? 因此通信死鎖也可以認(rèn)為是資源死鎖 處理死鎖的通用策略： ? 無視死鎖 (忽略問題 ) ? 檢測(cè) (允許發(fā)生死鎖 ， 檢測(cè)死鎖 , 并試圖從死鎖中恢復(fù) ) ? 預(yù)防 (靜態(tài)的結(jié)構(gòu)處理使死鎖不可能發(fā)生 ) ? 避免 (通過仔細(xì)分配資源避免發(fā)生死鎖 ) ? 在分布式系統(tǒng)中 ， 第一種方法應(yīng)用普遍 ，效果好 1. 分布式死鎖的檢測(cè) ? 只檢測(cè)死鎖 ， 而不是禁止死鎖的發(fā)生 ? 在基于原子事務(wù)的系統(tǒng)中檢測(cè)到死鎖時(shí) ? 可以通過終止一個(gè)或多個(gè)事務(wù)解除死鎖 ? 由于導(dǎo)致死鎖而中止某事務(wù)時(shí) ? 系統(tǒng)首先恢復(fù)到事務(wù)啟動(dòng)前的狀態(tài) ? 這時(shí)事務(wù)可以再次被啟動(dòng) 第二次啟動(dòng)成功也是可能有的 集中式死鎖檢測(cè)方法 (1) ? 模擬非分布式的算法 ? 每臺(tái)機(jī)器維護(hù)它上面運(yùn)行的進(jìn)程和資源構(gòu)成的資源圖 ? 用中心協(xié)調(diào)者維護(hù)整個(gè)系統(tǒng)的資源圖 (所有單個(gè)圖的并集 ) ? 在協(xié)調(diào)者檢測(cè)到系統(tǒng)資源圖中存在回路時(shí) ? 殺死某個(gè)進(jìn)程結(jié)束死鎖 集中式死鎖檢測(cè)方法 (2) ? 分布式系統(tǒng)中 ， 信息必須明確發(fā)送給某臺(tái)機(jī)器 ? 每臺(tái)機(jī)器維護(hù)自己的進(jìn)程和資源圖 ? 不論資源圖中增加 /減少弧線 ， 消息都可送給協(xié)調(diào)器更新 ? 周期性地 ， 送出相對(duì)先前所更新的弧線增加或刪除的清單 ? 方法需要比較少的消息 ? 協(xié)調(diào)器在需要可以詢問信息 虛假死鎖 (1) ? 在分布式系統(tǒng)中 ， 由于不完整或延遲的消息 ? 會(huì)產(chǎn)生虛假死鎖 ? 解決問題的方法是用 Lamport算法提供全局時(shí)間 虛假死鎖 (2) ? 當(dāng)協(xié)調(diào)者接收到機(jī)器的消息懷疑發(fā)生了死鎖時(shí) ? 它就向系統(tǒng)中的所有機(jī)器發(fā)送消息： ? “ 我剛接收到時(shí)間戳為 T的消息 ， 它導(dǎo)致死鎖 ? 如果誰有時(shí)間戳在此之前的消息 ， 請(qǐng)立即發(fā)送給我 ” ? 方法排除了虛假死鎖 ， 但需要全局時(shí)間 ，代價(jià)昂貴 2. 分布式死鎖檢測(cè)方法 ? Chandy – Misra Haas算法 (1) ? 允許進(jìn)程一次請(qǐng)求多個(gè)資源 (比如 ， 鎖 )而不是一次一個(gè) ? 事務(wù)的成長(zhǎng)階段的速度大大加快 ? 結(jié)果 ， 進(jìn)程就可能同時(shí)等待兩個(gè)或更多資源 分布式死鎖檢測(cè)方法 ? Chandy – Misra Haas算法 (2) ? 進(jìn)程 0被進(jìn)程 1阻塞時(shí) ? 這時(shí)生成一條特殊的檢測(cè)消息 ? 這條消息發(fā)送給占用所需資源的那個(gè)或那些進(jìn)程 分布式死鎖檢測(cè)方法 ? Chandy – Misra Haas算法 (3) ? 檢測(cè)消息由三個(gè)數(shù)字構(gòu)成： ? 正被阻塞的進(jìn)程號(hào) ? 發(fā)送消息的進(jìn)程號(hào) ? 接收消息的進(jìn)程號(hào) 分布式死鎖檢測(cè)方法 ? Chandy – Misra Haas算法 (4) ? 從進(jìn)程 0發(fā)送到進(jìn)程 1的起始消息為三個(gè)值（ 0， 0， 1） ? 消息到達(dá)時(shí) ， 接收者檢查它自身是否正在等待進(jìn)程 ? 如果是 ， 修改接收到的消息 ， 第一個(gè)數(shù)不變 ， ? 用它自己進(jìn)程號(hào)代替第二個(gè)數(shù) ? 用它正在等待的進(jìn)程號(hào)代替第三個(gè)數(shù) 分布式死鎖檢測(cè)方法 ? Chandy – Misra Haas算法 (5) ? 消息然后被送到被阻塞的進(jìn)程 ? 如果它被多個(gè)進(jìn)程阻塞 ， 它們都被送上（ 不同 ） 的消息 ? 如果某條消息經(jīng)過多次發(fā)送又回到了原發(fā)送進(jìn)程 ? 說明圖中存在回路 ， 系統(tǒng)被死鎖 解決死鎖辦法 (1) ? 一種算法讓激活死鎖檢測(cè)的進(jìn)程將自己殺死 ? 但是 ， 同時(shí)有多個(gè)進(jìn)程卷入該算法時(shí)就會(huì)出問題 ? 其實(shí)只要?dú)⑺榔渲幸粋€(gè)就可以解決死鎖問題 解決死鎖辦法 (1) ? 另一種算法讓每個(gè)接到檢測(cè)消息的進(jìn)程 ? 將其進(jìn)程號(hào)加到檢測(cè)消息的尾部 ? 這樣當(dāng)消息回到原始發(fā)送者 ， 整個(gè)循環(huán)都被列了出來 ? 觀察最大號(hào)碼的進(jìn)程 ， 將其殺死 ? 或發(fā)送消息讓該進(jìn)程將自己殺死 ? 無論哪種方法 ， 一旦發(fā)現(xiàn)相同的回路 ，選擇犧牲一個(gè)進(jìn)程 3. 分布式死鎖的預(yù)防 (1) 死鎖預(yù)防的技術(shù)有： ? 只允許進(jìn)程一次占用一個(gè)資源 ? 要求進(jìn)程在初始時(shí)申請(qǐng)其所需的全部資源 ? 要求進(jìn)程在申請(qǐng)新資源時(shí)釋放其占有的所有資源 ? 實(shí)踐中這些方法都很笨拙 分布式死鎖的預(yù)防 (2) ? 將所有的資源排序 ? 然后要求進(jìn)程嚴(yán)格按照升序獲取資源 ? 不允許進(jìn)程在占有一個(gè)序號(hào)大的資源時(shí) ? 申請(qǐng)序號(hào)比它小的資源 ? 因此不會(huì)產(chǎn)生回路 分布式死鎖的預(yù)防 (3) ? 基本思想 在事務(wù)啟動(dòng)時(shí)為它指定一個(gè)全局時(shí)間戳 任何兩個(gè)事務(wù)不能指定相同的時(shí)間戳 分布式死鎖的預(yù)防 (4) ? 進(jìn)程要阻塞等待另一個(gè)進(jìn)程正在使用的資源時(shí) ? 先檢查它們的時(shí)間戳哪個(gè)大 (即更年輕 ） ? 如果等待進(jìn)程的時(shí)間戳比被等待進(jìn)程的時(shí)間戳小 (即更老 ） ? 就允許進(jìn)程阻塞等待 ? 沿著任何等待鏈 ， 時(shí)間戳都是增加的 ，因此不可能出現(xiàn)回路 另外一種預(yù)防 ? 讓等待進(jìn)程的時(shí)間戳比被等待進(jìn)程的時(shí)間戳大 ? （ 即更年輕 ） 時(shí)允許進(jìn)程等待 ? 這時(shí)等待鏈上的時(shí)間戳是不斷減小的 分布式死鎖的預(yù)防 (5) ? 等待 死亡算法 ? 為啟動(dòng)早的進(jìn)程指定高的優(yōu)先級(jí)更明智 ? 這些進(jìn)程的執(zhí)行時(shí)間較長(zhǎng) ? 占用的系統(tǒng)時(shí)間較多 ? 而且可能占有較多的資源 等待 死亡的死鎖預(yù)防算法 老進(jìn)程 10 年輕進(jìn)程 20 需要資源 保持資源 等待 (a) 老進(jìn)程 10 年輕進(jìn)程 20 需要資源 保持資源 死亡 (b) 負(fù)傷 等待算法 ? 假定一個(gè)事務(wù)負(fù)傷 （ 實(shí)際上是被殺死 ） ? 而另一個(gè)事務(wù)等待而得名 ? 如果一個(gè)老進(jìn)程申請(qǐng)的資源被年輕的進(jìn)程占用 ? 老進(jìn)程就可以搶占年輕的進(jìn)程的資源 ? 對(duì)應(yīng)的事務(wù)也就被殺死了 ? 年輕的進(jìn)程可能會(huì)立即再次啟動(dòng) ， 并試圖獲得資源 ， 結(jié)果被迫等待 負(fù)傷 等待死鎖預(yù)防算法 老進(jìn)程 10 年輕進(jìn)程 20 申請(qǐng)資源 保持資源 優(yōu)先 (a) 老進(jìn)程 10 年輕進(jìn)程 20 保持資源 (b) 申請(qǐng)資源 等待
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1