【正文】 務執(zhí)行的短暫時刻內(nèi)，這種不變性會改變 。l 當一個事務處在處理過程中，其他進程（無論是否與事務有關(guān)）都不能看到任何 中間狀態(tài) 。l 這幾個屬性通常按其字母簡稱為 ACID。 下面通過 3個操作預定了這 3條獨立的路線的座票。l 這些操作也可能是 系統(tǒng)調(diào)用，庫過程 ，或者是某種語言中用括號括起來的語句，這取決于應用的需要。l 在一個事務中，也允許使用 普通語句 、 過程調(diào)用 等等。它不受其他任何錯誤的影響。陳香蘭 25分布式系統(tǒng)同步（續(xù)）假設(shè) 3： 穩(wěn)定存儲器l 存儲器有三種分類。我們真正需要的是像使用磁帶時那樣的對數(shù)據(jù)庫倒卷的方法。錢就消失在了未知的空間中。l 計算機從兩盤磁帶上讀取數(shù)據(jù)，并生成新的主庫存磁帶，如圖所示：陳香蘭 21分布式系統(tǒng)同步（續(xù)）l 這種設(shè)計的最大優(yōu)點（盡管與它生活在一起的人們并沒有意識到）在于l 對任何原因引起的運行錯誤，所有的磁帶都可以倒卷（rewound），其工作可以毫無損失地重新開始。l 這種 要么全有要么全無 的特性簡化了編程人員的工作。l 然后發(fā)起者宣布它希望其他進程能保證任務完成。l 然而，一旦公司雙方簽訂了合同，那么不論發(fā)生什么事情，他們在法律上都有責任完成該合約。D公司同意對方開出的價格，但不喜歡紫色，并且希望 6月份到貨，而且因為自己的客戶是國際客戶，因此，堅持要 10厘米的產(chǎn)品。術(shù)語原子操作也被廣泛使用。l 這些技術(shù)都需要編程人員涉及互斥、臨界區(qū)管理、死鎖預防、崩潰恢復等問題的細節(jié)。l 當消息循環(huán)一周后，被銷毀，每個進程都恢復工作。l 當一個進程發(fā)現(xiàn)協(xié)調(diào)者不再起作用時，它就創(chuàng)建一個包含它自身進程號的選舉消息發(fā)送給它的下鄰居。進程 4接收到第一個應答時就知道自己已經(jīng)結(jié)束了，因為已經(jīng)有比它進程號大的進程即將接管它的工作成為新的協(xié)調(diào)者，它就等待著看誰將在選舉中獲勝。l 除了一個進程外即進程號最大的進程，其余進程都會放棄選舉，這個進程就是新的協(xié)調(diào)者， 它將選舉獲勝的消息發(fā)送給所有進程 ，告之自己是新的協(xié)調(diào)者。陳香蘭 4分布式系統(tǒng)同步（續(xù)）兩個選舉算法l 欺負（ Bully）算法l 環(huán)算法陳香蘭 5分布式系統(tǒng)同步（續(xù)） 欺負（ Bully）算法l Bully算法由 GarciaMolina在 1982年提出l 當一個進程 P發(fā)現(xiàn)協(xié)調(diào)者不再響應請求時，它就發(fā)起選舉。高級操作系統(tǒng)Advanced Operating System熊 焰0551_3600689中國科學技術(shù)大學計算機系陳香蘭 1分布式系統(tǒng)同步（續(xù)） 選舉算法l 許多分布式算法需要一個進程充當協(xié)調(diào)者、發(fā)起者、排序者或者其他特定的角色l 例如：集中式互斥算法中的協(xié)調(diào)者進程l 通常，選擇哪個進程充當協(xié)調(diào)者并不重要，重要的是要有進程負責 ,并且需要所有進程的一致認可。進程 P負責選舉如下：1. P向所有進程號比它大的進程發(fā)送選舉（ELECTION）消息；2. 若無人響應， P獲勝成為協(xié)調(diào)者；3. 若有進程號比它大的進程響應，響應者接管， P的工作完成。l 若一個進程剛剛崩潰過，但又很快恢復，它主持選舉，若它剛好是當前運行進程中號最大的，它就會獲得選舉的勝利，從而接管協(xié)調(diào)者的工作。陳香蘭 9分布式系統(tǒng)同步（續(xù)）l 進程 5和 6都主持選舉，每個進程僅把消息發(fā)送給比自己進程號大的進程陳香蘭 10分布式系統(tǒng)同步（續(xù)）l 進程 6向進程 5發(fā) OK消息，進程 5收到 OK消息后停止選舉，而這個時候進程 6知道進程 7已經(jīng)死了，所以，它將是獲勝者。l 如果下鄰居失效，消息將繞過它到達它的下鄰居，或者再下一個，直到找到一個運行進程。陳香蘭 14分布式系統(tǒng)同步（續(xù)）舉例l 進程 5同時發(fā)現(xiàn)前任協(xié)調(diào)者進程 7失效，它們各自建立一個選舉消息沿環(huán)發(fā)送。l 而程序員喜歡的是 更高層次的抽象 ，l 也就是要隱藏這些技術(shù)問題，允許編程人員將精力集中在 算法和進程如何并行運行 上。陳香蘭 17分布式系統(tǒng)同步（續(xù)） 原子事務簡介商業(yè)模型原子事務的最初模型來源于商業(yè)社會。 W公司答復說 10月份提供3 15/16英寸的淡紫色裝飾品。l 因此，在雙方還未簽字前，任何一方都可以反悔，就像什么都沒有發(fā)生一樣，但是一旦雙方都簽了字，他們就不能再反悔，合同就必須被執(zhí)行。l 如果其他進程都同意，那么就達成了永久的協(xié)議。陳香蘭 20分布式系統(tǒng)同步（續(xù)）磁帶系統(tǒng)模型l 計算機系統(tǒng)中對 事務的使用 可以回溯到 20世紀 60年代。l 因此， 老式的磁帶系統(tǒng)具有了原子事務要么全有要么全無的特性 。陳香蘭 23分布式系統(tǒng)同步（續(xù)）l 將這兩個操作組成一個原子事務可以解決這個問題。 這種能力是原子事務必須提供的 。l 第一種是普通的 RAM存儲器，當電源出錯或機器崩潰時會丟失信息。陳香蘭 26分布式系統(tǒng)同步（續(xù)）事務原語l 使用 事務編程 需要由操作系統(tǒng)提供或者由語言運行系統(tǒng)提供特殊的 原語語句 ，例如：1. BEGIN_TRANSACTION：標記一個事務的開始2. END_TRANSACTION：結(jié)束事務并設(shè)法提交3. ABORT_TRANSACTION：取消事務；恢復舊值4. READ：從一個文件（或其他對象）讀取數(shù)據(jù)5. WRITE：將數(shù)據(jù)寫入一個文件（或其他對象）陳香蘭 27分布式系統(tǒng)同步（續(xù)）l 事物原語取決于 事務中正在使用的 對象類型 。陳香蘭 28分布式系統(tǒng)同步（續(xù)）事務體l BEGIN_TRANSACTION和END_TRANSACTIONl 限定事務的范圍 。陳香蘭 29分布式系統(tǒng)同步（續(xù)）事務舉例l 考慮到合肥火車站買一張從合肥到長沙的座票。BEGIN_TRANSACTIONreserve 合肥 阜陽reserve 阜陽 武漢reserve 武漢 長沙END_TRANSACTION陳香蘭 30分布式系統(tǒng)同步（續(xù)）事務舉例（ cont’d）l 現(xiàn)在假設(shè)前 兩條路線 已經(jīng) 預定成功 ，但是第三條已經(jīng)定滿了。陳香蘭 32分布式系統(tǒng)同步（續(xù)）1）事務的原子性l 所有事務具有的第一個特性是 原子性 。陳香蘭 33分布式系統(tǒng)同步（續(xù)）2）事務的一致性l 第二個特性說明事務是一致的。但是， 事務結(jié)束之后 ，這種改變就不存在了。l 即一旦事務提交，無論發(fā)生什么，這個事務都會向前進行，結(jié)果不會再變了。l 這些子事務中的任何一個都可以執(zhí)行一個或多個子事務，或者創(chuàng)建自己的子事務。l 但是，已經(jīng)提交了的子事務卻沒有被恢復。一個事務提交協(xié)議：陳香蘭 38分布式系統(tǒng)同步（續(xù)）兩階段提交協(xié)議l twophase mit protocol（ Gray， 1978）l 盡管它不是此類協(xié)議中唯一的一個，但它卻是使用最廣泛的一個l 基本思想：l 系統(tǒng)中有一個進程作為協(xié)調(diào)者。l 當協(xié)調(diào)者收到了所有的響應后，它就知道是否可以提交或中止。正是因為寫入的 日志 才使得 事務能真正被提交 。l 如果協(xié)調(diào)者以后崩潰了，那么它就可以從日志中看出自己所處的位置，并能決定該作些什么。l 最簡單形式是：l 作為一個事務的一部分 ，當一個進程需要讀或?qū)懸粋€文件（或其他對象）時，它首先將這個文件加鎖。l 兩種情況下 加鎖管理程序 都擁有一個 鎖定的文件列表 ， 所有對已加鎖文件進行的加鎖嘗試都將被拒絕 。l 與此相反，當一個文件被設(shè)置寫鎖時，其他任何類型的鎖都被禁止。l 一個加鎖單位究竟取多大 的問題稱為鎖的粒度。因此，常用的加鎖方法是兩階段加鎖法。陳香蘭 48分布式系統(tǒng)同步（續(xù)）死鎖l 加鎖即使兩階段加鎖都可能會導致死鎖。3）如果事先知道一個鎖的擁有時間不會超過 T秒，也可以采用一個