【正文】 復(fù)丟失的消息。 這種能力是原子事務(wù)必須提供的 。l 需要解決的關(guān)鍵問題是事務(wù)執(zhí)行失敗后能返回到最初狀態(tài) 。陳香蘭 23分布式系統(tǒng)同步（續(xù)）l 將這兩個操作組成一個原子事務(wù)可以解決這個問題。l 操作通過下面兩步執(zhí)行：1. 提?。ń痤~，賬戶 1）2. 存入（金額，賬戶 2）l 如果電話線在第一步之后第二步之前中斷，那么第一個賬戶已被取出而第二個賬戶卻沒有存入。l 因此， 老式的磁帶系統(tǒng)具有了原子事務(wù)要么全有要么全無的特性 。l 假設(shè)有一個有自動盤點系統(tǒng)的超級市場，每天關(guān)門后，計算機對兩盤作為輸入的磁帶進行處理 :l 第一盤磁帶存有當(dāng)天早晨開門以前的所有庫存，l 第二盤存有當(dāng)天已銷售給客戶的產(chǎn)品和交付給供應(yīng)商的產(chǎn)品。陳香蘭 20分布式系統(tǒng)同步（續(xù)）磁帶系統(tǒng)模型l 計算機系統(tǒng)中對 事務(wù)的使用 可以回溯到 20世紀 60年代。這時對象、文件、數(shù)據(jù)庫等方面的副作用都不會發(fā)生。l 如果其他進程都同意，那么就達成了永久的協(xié)議。l 一個進程宣布它想和其他一個或幾個進程開始一個事務(wù)，它們可以就不同的選擇進行協(xié)商、創(chuàng)建、刪除對象，執(zhí)行一段時間的操作。l 因此，在雙方還未簽字前，任何一方都可以反悔，就像什么都沒有發(fā)生一樣，但是一旦雙方都簽了字，他們就不能再反悔，合同就必須被執(zhí)行。陳香蘭 18分布式系統(tǒng)同步（續(xù)）l 到此為止，雙方就可以自由中斷本次談判，返回到開始談判前的狀態(tài)。 W公司答復(fù)說 10月份提供3 15/16英寸的淡紫色裝飾品。 W公司提出 12月份交付 10萬件淡紫色裝飾品。陳香蘭 17分布式系統(tǒng)同步（續(xù)） 原子事務(wù)簡介商業(yè)模型原子事務(wù)的最初模型來源于商業(yè)社會。我們稱其為 原子事務(wù) ，或簡稱事務(wù)。l 而程序員喜歡的是 更高層次的抽象 ，l 也就是要隱藏這些技術(shù)問題，允許編程人員將精力集中在 算法和進程如何并行運行 上。陳香蘭 16分布式系統(tǒng)同步（續(xù)） 原子事務(wù)l 迄今為止我們研究的所有同步技術(shù)本質(zhì)上都是處于底層的，比如信號量。陳香蘭 14分布式系統(tǒng)同步（續(xù)）舉例l 進程 5同時發(fā)現(xiàn)前任協(xié)調(diào)者進程 7失效，它們各自建立一個選舉消息沿環(huán)發(fā)送。陳香蘭 13分布式系統(tǒng)同步（續(xù)）l 最后，消息到達了始發(fā)者手中，始發(fā)者接收到包括自己進程號的消息后，將消息的類型轉(zhuǎn)化為協(xié)調(diào)者消息，該消息將再一次繞環(huán)運行，向所有的進程通知誰是協(xié)調(diào)者（在成員表中進程號最大的那個）。l 如果下鄰居失效，消息將繞過它到達它的下鄰居，或者再下一個，直到找到一個運行進程。l 這樣，進程 7的失效得到了處理陳香蘭 12分布式系統(tǒng)同步（續(xù)） 環(huán)算法l 環(huán)算法（基于沒有令牌的環(huán)）l 假設(shè)所有的進程是按物理或邏輯環(huán)排序的，每個進程都知道誰是它的下鄰居。陳香蘭 9分布式系統(tǒng)同步（續(xù)）l 進程 5和 6都主持選舉，每個進程僅把消息發(fā)送給比自己進程號大的進程陳香蘭 10分布式系統(tǒng)同步（續(xù)）l 進程 6向進程 5發(fā) OK消息，進程 5收到 OK消息后停止選舉，而這個時候進程 6知道進程 7已經(jīng)死了，所以，它將是獲勝者。陳香蘭 8分布式系統(tǒng)同步（續(xù)）l 進程 5和 6接收消息后發(fā)送回 OK。l 若一個進程剛剛崩潰過，但又很快恢復(fù)，它主持選舉，若它剛好是當(dāng)前運行進程中號最大的，它就會獲得選舉的勝利，從而接管協(xié)調(diào)者的工作。陳香蘭 6分布式系統(tǒng)同步（續(xù)）欺負（ Bully）算法l 在某一時刻， 一個進程只能從進程號比它小的進程那里得到一個選舉（ ELECTION）消息 ，當(dāng)它到達時，接收者就發(fā)送回 OK消息，表明它的存在并接管，然后接收者主持選舉（除非它正在主持別的選舉）。進程 P負責(zé)選舉如下：1. P向所有進程號比它大的進程發(fā)送選舉（ELECTION）消息；2. 若無人響應(yīng)， P獲勝成為協(xié)調(diào)者；3. 若有進程號比它大的進程響應(yīng)，響應(yīng)者接管， P的工作完成。陳香蘭 3分布式系統(tǒng)同步（續(xù)）選舉的目的l 我們 假設(shè) 每個進程都知道所有其他進程的進程號，但不知道目前哪些進程在工作，哪些進程不在工作；l 選舉算法的 目的 是在選舉開始后，確保 在所有進程都同意的基礎(chǔ)上選出協(xié)調(diào)者。高級操作系統(tǒng)Advanced Operating System熊 焰0551_3600689中國科學(xué)技術(shù)大學(xué)計算機系陳香蘭 1分布式系統(tǒng)同步（續(xù)） 選舉算法l 許多分布式算法需要一個進程充當(dāng)協(xié)調(diào)者、發(fā)起者、排序者或者其他特定的角色l 例如：集中式互斥算法中的協(xié)調(diào)者進程l 通常，選擇哪個進程充當(dāng)協(xié)調(diào)者并不重要，重要的是要有進程負責(zé) ,并且需要所有進程的一致認可。陳香蘭 2分布式系統(tǒng)同步（續(xù)）最大進程號l 如果所有進程的地位都相同，沒有特性上的區(qū)別，就無法選擇其中一個為特殊進程；l 假設(shè)每個進程都有一個特殊的號，通常選舉算法總是找擁有最大號的進程，將它指定為協(xié)調(diào)者，不同的選舉算法在選舉時采用不同的方法。陳香蘭 4分布式系統(tǒng)同步（續(xù)）兩個選舉算法l 欺負（ Bully）算法l 環(huán)算法陳香蘭 5分布式系統(tǒng)同步（續(xù)） 欺負（ Bully）算法l Bully算法由 GarciaMolina在 1982年提出l 當(dāng)一個進程 P發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)請求時，它就發(fā)起選舉。l 由于總是進程號最大的進程獲勝，故該算法命名為欺負算法。l 除了一個進程外即進程號最大的進程，其余進程都會放棄選舉，這個進程就是新的協(xié)調(diào)者， 它將選舉獲勝的消息發(fā)送給所有進程 ，告之自己是新的協(xié)調(diào)者。陳香蘭 7分布式系統(tǒng)同步（續(xù)）欺負（ Bully）算法舉例l 一組由 0~7號共 8個進程組成，開始 7號進程是協(xié)調(diào)者，但是它突然發(fā)生了故障，進程 4第一個注意到這一點，所以它向所有比它進程號大的進程，即進程 7發(fā)送選舉消息。進程 4接收到第一個應(yīng)答時就知道自己已經(jīng)結(jié)束了，因為已經(jīng)有比它進程號大的進程即將接管它的工作成為新的協(xié)調(diào)者，它就等待著看誰將在選舉中獲勝。陳香蘭 11分布式系統(tǒng)同步（續(xù)）l 進程 6接管，向所有的運行進程發(fā)送 COORDINATOR協(xié)調(diào)者消息l 進程 4收到消息，發(fā)現(xiàn)進程 7已死，進程 6是新協(xié)調(diào)者，進程 4就可繼續(xù)工作。l 當(dāng)一個進程發(fā)現(xiàn)協(xié)調(diào)者不再起作用時，它就創(chuàng)建一個包含它自身進程號的選舉消息發(fā)送給它的下鄰居。l 每一個發(fā)送者都將自己的進程號加入到消息表中。l 當(dāng)消息循環(huán)一周后，被銷毀，每個進程都恢復(fù)工作。陳香蘭 15分布式系統(tǒng)同步（續(xù)）l 最終，兩條消息都將沿環(huán)運動，進程 2和 5分別將它們轉(zhuǎn)化成協(xié)調(diào)者消息，消息中有完全一樣的成員，相互順序也相同，當(dāng)兩條消息再繞環(huán)一周后，均被銷毀，有多余的消息循環(huán)沒有壞處，最多是浪費了一點帶寬。l 這些技術(shù)都需要編程人員涉及互斥、臨界區(qū)管理、死鎖預(yù)防、崩潰恢復(fù)等問題的細節(jié)。l 這樣的抽象是存在的，而且被廣泛應(yīng)用在分布式系統(tǒng)中。術(shù)語原子操作也被廣泛使用。l 假設(shè) D公司需要一批裝飾品，他們與潛在的供應(yīng)商 W公司進行聯(lián)系，希望 6月份能交付 10萬件 10厘米的裝飾品。D公司同意對方開出的價格，但不喜歡紫色，并且希望 6月份到貨，而且因為自己的客戶是國際客戶，因此，堅持要 10厘米的產(chǎn)品。經(jīng)過更進一步的談判，雙方最終同意 8月 15日交付 3 959/1024英寸的紫羅蘭裝飾品。l 然而，一旦公司雙方簽訂了合同，那么不論發(fā)生什么事情，他們在法律上都有責(zé)任完成該合約。陳香蘭 19分布式系統(tǒng)同步（續(xù)）多進程之間的模型分布式系統(tǒng)中多進程之間的模型和商業(yè)模型相類似。l 然后發(fā)起者宣布它希望其他進程能保證任務(wù)完成。l 如果有一個或幾個進程拒絕（或在同意前崩潰），那么就會返回到事務(wù)開始前的狀態(tài)。l 這種 要么全