【正文】 如果需要就可以實現(xiàn)它們自己的死鎖機制。l 既然進程可以請求或釋放通信信道、緩沖區(qū)等資源，它也可以按資源死鎖處理，因此 這里并不區(qū)分 這兩種死鎖。在這種情況下導致死鎖的原因可能有多種，例如無法得到緩沖區(qū)。陳香蘭 58分布式系統(tǒng)同步（續(xù)）關于死鎖的分類l 有人將分布式死鎖分成了兩類： 通信死鎖和資源死鎖。l 它們更難于避免、預防或者檢測，即使在檢測到以后也很難處理，因為所有的相關信息都分散在多臺機器上。l 它的主要問題在于實現(xiàn)的復雜性，這將導致降低性能。l 另一方面，時間戳方法不會出現(xiàn)死鎖，這是極大的改進。陳香蘭 56分布式系統(tǒng)同步（續(xù)）l 同加鎖法相比，時間戳有著不同的特性。l 在 Kung和 Robinson的方法中，我們希望并發(fā)事務不使用同一個文件。l 這種情況意味著當前事務開始得過早了，因此需要中止。l 這種次序意味著事務正在以正確的順序進行處理。陳香蘭 52分布式系統(tǒng)同步（續(xù)）時間戳l 一個完全不同的并發(fā)控制方法是： 在一個事務開始做 BEGIN_TRANSACTION的時候給它分配一個時間戳 （ Reed， 1983）l 通過使用 Lamport的算法，我們可以確保時間戳是唯一的l 系統(tǒng)中， 每個文件都擁有一個讀取時間戳和寫入時間戳 ，以判斷哪個已提交的進程最近一次讀取或寫入過該文件。l 在結束的時候，新的文件要么被提交要么被釋放。陳香蘭 51分布式系統(tǒng)同步（續(xù)）l 樂觀并發(fā)控制算法 最適合于基于私有工作空間 的情況。l 如果被修改過，那么本事務將被中止。l 樂觀并發(fā)控制算法：l 記錄下有哪些文件曾經被讀寫過。l 在實際情況中， 沖突相對來說非常少 ，所以這個策略大部分時間都可以正常工作。l 這種方法的思想比較簡單：l 盡管放心去做你想做的，不用在意其他人正在做什么。3）如果事先知道一個鎖的擁有時間不會超過 T秒，也可以采用一個超時方案：如果某個擁有者連續(xù)擁有同一個鎖超過了 T秒，那么一定是出現(xiàn)了死鎖。l 解決方法：1）采用以某種順序請求所有鎖的方法來防止保持 等待循環(huán)的出現(xiàn)。陳香蘭 48分布式系統(tǒng)同步（續(xù)）死鎖l 加鎖即使兩階段加鎖都可能會導致死鎖。陳香蘭 47分布式系統(tǒng)同步（續(xù)）l Eswaran等人在 1976年證明：如果所有的事務都使用兩階段加鎖法，那么通過交錯事務進行的所有調度都是串行的。因此，常用的加鎖方法是兩階段加鎖法。l 另一方面， 鎖分得越細致，也就越需要更多的鎖，這樣的開銷也就越大，也就更容易導致死鎖 。l 一個加鎖單位究竟取多大 的問題稱為鎖的粒度。陳香蘭 45分布式系統(tǒng)同步（續(xù)）鎖的粒度l 為簡單起見，我們曾經假設加鎖的單位是整個文件。l 與此相反，當一個文件被設置寫鎖時，其他任何類型的鎖都被禁止。l 如果在一個文件上設置了讀鎖，那么在它上面設置其他的讀鎖也是允許的，寫鎖是禁止的。l 兩種情況下 加鎖管理程序 都擁有一個 鎖定的文件列表 ， 所有對已加鎖文件進行的加鎖嘗試都將被拒絕 。l 鎖一般由事務系統(tǒng)請求和釋放 ，不需要編程人員的操作。l 最簡單形式是：l 作為一個事務的一部分 ，當一個進程需要讀或寫一個文件（或其他對象）時，它首先將這個文件加鎖。這種機制稱為并發(fā)控制算法。l 如果協(xié)調者以后崩潰了，那么它就可以從日志中看出自己所處的位置，并能決定該作些什么。l 如果協(xié)調者在寫入了初始化日志后崩潰，那么在恢復時只需要從停止的地方開始繼續(xù)工作就可以了。正是因為寫入的 日志 才使得 事務能真正被提交 。l 如果一個或幾個進程不能提交（或沒有響應），那么事務就得終止。l 當協(xié)調者收到了所有的響應后，它就知道是否可以提交或中止。l 提交協(xié)議開始時協(xié)調者先寫入一條日志條目以表明它要開始執(zhí)行提交協(xié)議，然后，它給每個相關進程（下屬 )發(fā)送一條消息通知它們?yōu)樘峤蛔骱脺蕚?。一個事務提交協(xié)議：陳香蘭 38分布式系統(tǒng)同步（續(xù)）兩階段提交協(xié)議l twophase mit protocol（ Gray， 1978）l 盡管它不是此類協(xié)議中唯一的一個，但它卻是使用最廣泛的一個l 基本思想：l 系統(tǒng)中有一個進程作為協(xié)調者。陳香蘭 37分布式系統(tǒng)同步（續(xù)）事務提交l 事務提交操作 必須是 原子 的，即瞬時的和不可再分的。l 但是，已經提交了的子事務卻沒有被恢復。l 假設一個事務啟動了幾個并行的子事務，其中一個已經提交，并使自己的結果對父事務是可見的。l 這些子事務中的任何一個都可以執(zhí)行一個或多個子事務，或者創(chuàng)建自己的子事務。陳香蘭 36分布式系統(tǒng)同步（續(xù)）嵌套事務l 事務可以包含子事務，這通常稱作嵌套事務。l 即一旦事務提交，無論發(fā)生什么，這個事務都會向前進行，結果不會再變了。l 這意味著如果兩個或兩個以上的事務在同時運行，那么對它們自己和其他進程來說，最終結果看起來就像是所有的 事務是按某種次序（依賴于系統(tǒng)）順序運行的。但是， 事務結束之后 ，這種改變就不存在了。l 例如在一個銀行系統(tǒng)中，最關鍵的 不變性是資金守恒規(guī)則 。陳香蘭 33分布式系統(tǒng)同步（續(xù)）2）事務的一致性l 第二個特性說明事務是一致的。如果發(fā)生，就是 不可分割 的瞬間的操作。陳香蘭 32分布式系統(tǒng)同步（續(xù)）1）事務的原子性l 所有事務具有的第一個特性是 原子性 。l BEGIN_TRANSACTIONl reserve 合肥 阜陽l reserve 阜陽 武漢l 武漢 長沙 已滿 ?ABORT_TRANSACTION陳香蘭 31分布式系統(tǒng)同步（續(xù)）事務的特性l 事務有四個重要的特性，它們是：1. 原子性（ Atomic）：對外部世界來說，事務的發(fā)生是不可分割的；2. 一致性（ Consistent）：事務不會破壞系統(tǒng)的恒定；3. 孤立性（ Isolated）：并發(fā)的事務不會互相干擾；4. 持久性（ Durable）：一旦一個事務提交，改變就是永遠存在的。BEGIN_TRANSACTIONreserve 合肥 阜陽reserve 阜陽 武漢reserve 武漢 長沙END_TRANSACTION陳香蘭 30分布式系統(tǒng)同步（續(xù)）事務舉例（ cont’d）l 現(xiàn)在假設前 兩條路線 已經 預定成功 ，但是第三條已經定滿了。合肥 ?阜陽；阜陽 ?武漢；武漢 ?長沙。陳香蘭 29分布式系統(tǒng)同步（續(xù)）事務舉例l 考慮到合肥火車站買一張從合肥到長沙的座票。l 事務體中的操作要么全部執(zhí)行，要么一個也不執(zhí)行。陳香蘭 28分布式系統(tǒng)同步（續(xù)）事務體l BEGIN_TRANSACTION和END_TRANSACTIONl 限定事務的范圍 。l 而在一個賬目系統(tǒng)中可能會有很大的不同，讀取和寫入是典型的原語應用。陳香蘭 26分布式系統(tǒng)同步（續(xù)）事務原語l 使用 事務編程 需要由操作系統(tǒng)提供或者由語言運行系統(tǒng)提供特殊的 原語語句 ，例如：1. BEGIN_TRANSACTION：標記一個事務的開始2. END_TRANSACTION：結束事務并設法提交3. ABORT_TRANSACTION：取消事務；恢復舊值4. READ：從一個文件（或其他對象）讀取數(shù)據(jù)5. WRITE：將數(shù)據(jù)寫入一個文件（或其他對象）陳香蘭 27分布式系統(tǒng)同步（續(xù)）l 事物原語取決于 事務中正在使用的 對象類型 。l 最后一種是穩(wěn)定存儲器（ stable storage）。l 第一種是普通的 RAM存儲器，當電源出錯或機器崩潰時會丟失信息。l 假設 2： 通信錯誤已經被底層軟件透明地處理l 盡管通信一般來說是不太可靠的，消息會丟失，但是底層可以采用超時重發(fā)協(xié)議恢