【正文】 9:23:55 下午 9:23 下午 21:23:55一月 21MOMODA POWERPOINTLorem ipsum dolor sit amet, consectetur adipiscing elit. Fusce id urna blandit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis ut cursus. 感謝您的下載觀看專 家告 訴。 一月 219:23 下午 一月 2121:23January 25, 20231業(yè)余生活要有意義，不要越軌。 一月 21一月 2121:23:5521:23:55January 25, 20231意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 21:23:5521:23:5521:23Monday, January 25, 20231知人者智，自知者明。 21:23:5521:23:5521:231/25/2023 9:23:55 PM1越是沒有本領的就越加自命不凡。 9:23:55 下午 9:23 下午 21:23:55一月 21楊柳散和風，青山澹吾慮。 一月 219:23 下午 一月 2121:23January 25, 20231少年十五二十時，步行奪得胡馬騎。 25 一月 20239:23:55 下午 21:23:55一月 211楚塞三湘接，荊門九派通。 21:23:5521:23:5521:23Monday, January 25, 20231不知香積寺，數(shù)里入云峰。 21:23:5521:23:5521:231/25/2023 9:23:55 PM1成功就是日復一日那一點點小小努力的積累。 9:23:55 下午 9:23 下午 21:23:55一月 21沒有失敗，只有暫時停止成功！。 一月 219:23 下午 一月 2121:23January 25, 20231行動出成果，工作出財富。 25 一月 20239:23:55 下午 21:23:55一月 211比不了得就不比，得不到的就不要。 21:23:5521:23:5521:23Monday, January 25, 20231乍見翻疑夢，相悲各問年。 21:23:5521:23:5521:231/25/2023 9:23:55 PM1以我獨沈久，愧君相見頻。陳香蘭 88分布式系統(tǒng)同步（續(xù)）靜夜四無鄰，荒居舊業(yè)貧。在老事務釋放資源之前，這個循環(huán)可能要重復多次。反之，若一個新事務想得到一個被老事務占用的資源，它將被中止。l 這種算法稱為傷 等算法（ woundwait），因為一個事務可能會受到傷害（實際是被中止）而其他的事務等待。l 在這種情況下，箭頭總是指向事務編號增長的方向，使得環(huán)路不可能出現(xiàn)。那就會使得老進程中止，但這樣的效率較低（老進程只會變得更老）。陳香蘭 84分布式系統(tǒng)同步（續(xù)）等 死算法（ waitdie）l 由于使用了時間戳，當請求被占用的資源時只可能有兩種情況：1）老進程請求被新進程占用的資源，2）新進程請求被老進程占用的資源l 一種情況應該允許進程等待，另一種情況應該中止進程。l 它們都已經(jīng)運行了較長時間，系統(tǒng)對他們的投入會更大一些，他們占有的資源也就更多一些。陳香蘭 82分布式系統(tǒng)同步（續(xù)）時間戳算法的基本思想這兩個基于時間戳的算法的 基本思想 是：l 當一個進程因等待一個正被其他進程占用的資源而要被阻塞時，比較哪個進程的時間戳更大（即更晚）。l 和其它基于時間戳的算法一樣，在這兩個算法中保證不會有兩個事務分配了完全一致的時間戳。陳香蘭 81分布式系統(tǒng)同步（續(xù)）兩個基于時間戳的算法l 在擁有全局時間和原子事務的分布式系統(tǒng)中，有兩個算法比較實用。l 或者要求進程必須預定資源，并以嚴格增序請求資源。陳香蘭 80分布式系統(tǒng)同步（續(xù)） 分布式死鎖預防l 死鎖預防是仔細地設計使得死鎖在結(jié)構(gòu)上不可能的。于是發(fā)送者就能看出哪個 進程編號最大 ，可以將它中止或者發(fā)送一個消息給它請求其自殺。中止掉一個進程就足夠了。l 若有多個進程同時調(diào)用了此算法，就會出現(xiàn)問題：例如在上例中假設進程 0~6同時阻塞，而且都初始化了探測消息。陳香蘭 78分布式系統(tǒng)同步（續(xù)）處理死鎖的方法（ 1）l 可以多種方法來處理死鎖。l 圖中（ 0， 2， 3），（ 0， 4， 6），（ 0， 5， 7）和（ 0， 8， 0）都是遠程消息。l 若存在多個等待進程，就要發(fā)送多個不同的消息。l 若是，就更新消息，字段 1保持不變，字段 2改成當前進程號，字段 3改為自己等待資源被占有的進程號。l 由 P0到 P1的初始消息包含三元組（ 0， 0， 1）。l 等待者進程生成一個 探測消息 并發(fā)送給占用資源的進程。l 一些進程，如進程 2在等待其他機器上的資源。l 可以看到l 機器 1上的進程 3正在等待兩個資源，一個由進程 4占有，一個由進程 5占有。陳香蘭 74分布式系統(tǒng)同步（續(xù)）資源圖l 下圖是一種改進的資源圖，圖中只給出進程。l 通過允許多個請求同時進行使得事務的增長階段可以加速。l 盡管這種方法消除了假死鎖，但它需要全局時間，而且開銷很大。l 當協(xié)調(diào)者收到了從機器 1發(fā)來的有導致死鎖嫌疑的消息后，給每臺機器發(fā)送一條消息l “我剛剛收到一條會導致死鎖的消息，帶有時間戳 T，若有任何小于 T的消息要發(fā)給我，請立即發(fā)送。集中式死鎖檢測中的假死鎖問題陳香蘭 71分布式系統(tǒng)同步（續(xù)）解決假死鎖問題l 一種可能的解決方法是使用 lamport算法以提供全局時間。l 這種情況稱為假死鎖。l 不幸的是，機器 1的消息首先到達，這導致協(xié)調(diào)者生成了一幅如圖 d所示的資源圖。陳香蘭 69分布式系統(tǒng)同步（續(xù)）反例（ cont’d）l 過一段時間后， B釋放 R并請求 T，這是一個完全合法的安全操作。資源 使用 “方框 ”表示進程 使用 “圓圈 ”表示從資源到進程 的箭頭表示 “進程擁有資源 ”從進程到資源 的箭頭表示 “進程請求資源 ”陳香蘭 68分布式系統(tǒng)同步（續(xù)）反例（ cont’d）l 協(xié)調(diào)者看到的情況如圖 c所示。l 共有三種資源 S， R和 T。陳香蘭 67分布式系統(tǒng)同步（續(xù)）反例l 不幸的是上述方法的效果都不太好。l 這種方法比第一種方法發(fā)送的消息要少。l 方法 1：每當資源圖中加入或刪除一條弧時，相應的消息就發(fā)送給協(xié)調(diào)者以便更新。l 由于每臺機器的資源圖中只包含它自己的進程和資源。陳香蘭 65分布式系統(tǒng)同步（續(xù)）1）集中式的死鎖檢測l 集中式的死鎖檢測算法 ： 每一臺機器都有一個資源圖以描述自己所擁有的進程和資源；一臺中心機器即協(xié)調(diào)者擁有整個系統(tǒng)（所有資源圖的集合）的資源圖；當協(xié)調(diào)者檢測到了環(huán)路時它就中止一個進程以解決死鎖。l 若運氣好，事務在第二次執(zhí)行時就能成功完成。由于事務允許出現(xiàn)中止，不會導致用戶不滿，也不會導致系統(tǒng)出現(xiàn)其他后果，例如數(shù)據(jù)不一致等等。l 在一般操作系統(tǒng)中，在檢測到死鎖后，解決的方法是中止一個或幾個進程，但這必然會使一些用戶感到不滿。l 因此關于分布式系統(tǒng)中的死鎖問題的討論將只集中于兩種技術：死鎖檢測和死鎖預防。l 既然在單處理機系統(tǒng)中都不采用死鎖避免機制，那么在更復雜的分布式系統(tǒng)中我們又何必采用呢？l 該方法的問題在于銀行家算法和類似算法需要（事先）知道每個進程最終到底需要多少資源。后面將討論兩種算法。l 盡管比在單處理機系統(tǒng)中困難得多，但是死鎖預防還是能夠?qū)崿F(xiàn)的。陳香蘭 61分布式系統(tǒng)同步（續(xù)）死鎖檢測與消除l 死鎖檢測與恢復算法比較流行，原因是預防算法和避免算法太難了。l 盡管在諸如分布式數(shù)據(jù)庫等個人應用中，