【正文】 2023/1/25 21:23:5521:23:5525 January 20231一個人即使已登上頂峰，也仍要自強不息。勝人者有力，自勝者強。 一月 21一月 21Monday, January 25, 2023閱讀一切好書如同和過去最杰出的人談話。 。 一月 2121:23:5521:23Jan2125Jan211世間成事，不求其絕對圓滿，留一份不足，可得無限完美。 2023/1/25 21:23:5521:23:5525 January 20231做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點的射線向前。 一月 21一月 2121:23:5521:23:55January 25, 20231他鄉(xiāng)生白發(fā)，舊國見青山。 一月 21一月 21Monday, January 25, 2023雨中黃葉樹，燈下白頭人。盡管它還會重新開始，但很可能又會立即被中止。陳香蘭 86分布式系統(tǒng)同步（續(xù)）傷 等算法（ woundwait）l 傷 等算法允許搶占：假設只允許老進程搶占新進程，因此圖 a被標記為搶先，圖 b為等待。也即 等 死算法陳香蘭 85分布式系統(tǒng)同步（續(xù)）等 死算法（ waitdie）舉例l 假設標記圖 a為中止、圖 b為等待。l 只有當?shù)却M程的時間戳小于（早于）被等待進程的時間戳，才允許等待發(fā)生（ 只允許老進程等待 ）l 沿著等待進程鏈，時間戳遞增，不可能發(fā)生環(huán)路l 或只有當?shù)却M程擁有大于（晚于）被等待進程的時間戳時，才允許等待發(fā)生（ 只允許新進程等待 ）l 沿著等待進程鏈，時間戳遞減陳香蘭 83分布式系統(tǒng)同步（續(xù)）老進程？新進程？l 盡管兩種方法都能預防死鎖，但是給予老的進程以優(yōu)先權可能更好一點。l 這兩種算法都是基于在一個事務開始時給它分配一個全局時間戳的思想。l 已有的一些辦法在實際應用中都不太理想：l 在某一時刻只允許進程占有一個資源l 要求進程在初始階段請求所有的資源l 當進程請求新資源時必須釋放所有資源。陳香蘭 79分布式系統(tǒng)同步（續(xù)）處理死鎖的方法（ 2）l 另一種算法是將每個進程的標識符添加到探測消息的末尾，這樣當它返回到最初的發(fā)送者時完整的環(huán)路就可以列出來了。l 一種方法是 使最初發(fā)送探測消息的進程自殺 。（ 0,0,1）（ 0,1,2）陳香蘭 77分布式系統(tǒng)同步（續(xù)）ChandyMisraHaas算法（ cont’d）l 不論資源在本地還是在遠程，該算法都要繼續(xù)下去。（ 0,0,1）陳香蘭 76分布式系統(tǒng)同步（續(xù)）ChandyMisraHaas算法（ cont’d）l 消息到達后，接收者檢查以確認它自己是否也在等待其他進程。陳香蘭 75分布式系統(tǒng)同步（續(xù)）ChandyMisraHaas算法l 當某個進程等待資源時，例如 P0等待 P1，將調(diào)用 ChandyMisraHaas算法。l 每條弧穿過一個資源，為簡單起見從圖中刪除了資源l 連接機器的弧使得尋找環(huán)路更加困難。陳香蘭 73分布式系統(tǒng)同步（續(xù)）2）分布式的死鎖檢測l ChandyMisraHaas算法（ Chandy等， 1983）允許進程一次請求多個資源（如鎖）而不是一次一個。l 既然機器 1發(fā)送到協(xié)調(diào)者的消息是由機器 0的請求發(fā)引起的，那么，機器 1發(fā)給協(xié)調(diào)者消息的時間戳就應該晚于機器 0發(fā)送到協(xié)調(diào)者消息的時間戳。陳香蘭 70分布式系統(tǒng)同步（續(xù)）l 根據(jù)上圖中的信息，協(xié)調(diào)者將 錯誤的得出死鎖存在的結(jié)論 ，并中止某個進程。l 這種情況是不會產(chǎn)生死鎖的。例如有這樣一種系統(tǒng)l A和 B運行在機器 0上， C運行在機器 1上。l 方法 2：每個進程周期性的把從上次更新后新添加的和刪除的弧的列表發(fā)送給協(xié)調(diào)者。陳香蘭 66分布式系統(tǒng)同步（續(xù)）全局資源圖信息的維護l 在分布式系統(tǒng)中需要精確維護全局資源圖。陳香蘭 64分布式系統(tǒng)同步（續(xù)）l 當一個事務因為產(chǎn)生死鎖而被中止的時候，l 首先讓系統(tǒng)恢復到事務開始前的狀態(tài)，然后事務可以從這一點重新開始。陳香蘭 63分布式系統(tǒng)同步（續(xù)） 分布式死鎖檢測l 在一些分布式系統(tǒng)中原子事務的提出使得在死鎖可以得到解決。死鎖的預防陳香蘭 62分布式系統(tǒng)同步（續(xù)）死鎖的避免l 死鎖避免在分布式系統(tǒng)中從來都不采用 。我們將討論幾種用于死鎖檢測的算法。陳香蘭 59分布式系統(tǒng)同步（續(xù)）處理死鎖的策略分類l 處理死鎖問題的策略有很多種，其中 4個最著名：1. 鴕鳥算法（忽略問題）2. 檢測（允許死鎖發(fā)生，在檢測到后想辦法消除）3. 預防（靜態(tài)的使死鎖在結(jié)構(gòu)上是不可能發(fā)生的）4. 避免（通過仔細的分配資源以避免死鎖）陳香蘭 60分布式系統(tǒng)同步（續(xù)）鴕鳥算法l 鴕鳥算法在分布式系統(tǒng)中同在單處理機系統(tǒng)中一樣好用，一樣受歡迎。 例如，進程 A試圖發(fā)送消息給進程 B，進程 B給進程C發(fā)送消息，而 C又試圖給 A發(fā)送消息，那么就會發(fā)生死鎖。陳香蘭 57分布式系統(tǒng)同步（續(xù)） 分布式系統(tǒng)中的死鎖l 分布式系統(tǒng)中的死鎖類似單處理機系統(tǒng)中的死鎖，只是情況更壞。l 當一個事務碰到了更晚的時間戳時，就要中止，l 加鎖法在相同的情況下要么等待要么立即執(zhí)行。需要中止陳香蘭 55分布式系統(tǒng)同步（續(xù)）時間戳（ cont’d）l 在某種意義上，這種方案同 Kung和 Robinson的方案一樣，也是樂觀的，盡管兩者的細節(jié)完全不同。陳香蘭 53分布式系統(tǒng)同步（續(xù)）時間戳（ cont’d）l 若事務都很短小且在時間間隔上比較大，那么一般來說當一個進程試圖訪問某個文件時，該文件的讀寫時間戳將早于當前事務的時間戳。l 每個事務都獨立地修改各自的文件，不會涉及其他的事務。l 在提交時刻，檢測其他的事務以判斷在本事務開始后它的文件是否被其他事務修改過。如果有問題出現(xiàn)，那么以后再考慮吧 。2）通過對一張描述哪個進程可以擁有哪個鎖，它還想請求哪個鎖的圖進行死鎖掃描，以便檢查是否有環(huán)路出現(xiàn)，以防止死鎖。這也是兩階段加鎖法廣泛使用的原因。陳香蘭 46分布式系統(tǒng)同步（續(xù)）兩階段加鎖法l 在需要或不再需要鎖時去請求或釋放鎖可能會導致 不一致和死鎖 。但在實際中，l 可能是更小一些的單位，比如 記錄 或 頁面 ，l 也可能是大一些，比如 整個數(shù)據(jù)庫 。l 讀鎖用來確保文件不會被改寫（也即排斥所有的寫入者），但不禁止其他讀取文件的事務。陳香蘭 43分布式系統(tǒng)同步（續(xù)）加鎖法實現(xiàn)1. 可以使用一個 集中式加鎖管理程序 來實現(xiàn)2. 可以在每臺機器上有一個 本地加鎖管理程序 來管理本地文件。l 本節(jié)將研究三個不同的算法1）加鎖法2）樂觀并發(fā)控制3）時間戳陳香蘭 42分布式系統(tǒng)同步（續(xù)）加鎖法l 最古老而且使用最廣泛的并發(fā)控制算法是加鎖法。l 如果在響應第一條消息之前某個下屬崩潰了，那么協(xié)調(diào)者將會給它不斷地發(fā)送消息。l 無論是提交還是終止，協(xié)調(diào)者都要寫一條日志記錄并給每個下屬發(fā)送一條消息以便將決定通知它們。陳香蘭 39分布式系統(tǒng)同步（續(xù)）l 當一個下屬收到消息后，它先進行檢查以確認是否為提交作好了準備，然后將它是否準備提交的決定發(fā)回給協(xié)調(diào)者。l 在分布式系統(tǒng)中，提交操作 可能需要不同機器上的多個進程的協(xié)作 ，這些進程中的每一個都有一些 被事務改動過的變量、文件、數(shù)據(jù)庫 或者其他對象。l 經(jīng)過更進一步的計算，父事務被中止，并將系統(tǒng)恢復到了頂層事務開始前的狀態(tài)。l 頂層事務可以在不同的處理機上創(chuàng)建并運行子事務，以提高性能簡化編程。陳香蘭 35分布式系統(tǒng)同步（續(xù)）4）事務的持久性l 第四個特性說明事務是持久的。在任何內(nèi)部轉(zhuǎn)帳之后，銀行的資金賬目應與轉(zhuǎn)帳前保持一致，但是在 事