分布式操作系統ppt課件-資料下載頁

　　

【正文】 塊可以通過另一臺驅動器上的相應塊恢復。 108 一、穩定存儲器 （續） ? 實現穩定存儲器的 價值： ? 它很適合于需要高度容錯的應用，例如原子事務。 ? 當數據寫入穩定存儲器并讀出以檢驗它們是否正確寫入時，它們相繼丟失的機會非常小。 109 二、事務原語 ? 使用事務編程需要由 操作系統 提供或者由 語言運行系統 提供特殊 原語 ，例如： ? BEGIN_TRANSACTION：標記一個事務的開始。 ? END_ TRANSACTION：結束事務并設法提交。 ? ABORT_ TRANSACTION：取消事務；恢復舊值。 ? READ：從一個文件（或其它對象）讀取數據。 ? WRITE：將數據寫入一個文件（或其它對象）。 110 二、事務原語 （續） ? 更精確的原語 列表取決于事務中正在使用的對象類型。 ? 在一個郵件系統中，可能有發送、接收以及轉發郵件等原語。 ? 而在一個帳目系統中可能會有很大的不同。 ? 讀取和寫入卻是 典型的應用 。 ? 在一個事務中，也允許使用普通語句、過程調用等。 111 二、事務原語 （續） —— 事務體 ? BEGIN_TRANSACTION 和 END_ TRANSACTION用來限定事務的范圍。 ? 介于它們之間的操作構成了 事務體 。 ? 這些操作要么全部執行，要么一個也不執行 。 ? 這些操作可能是系統調用，庫過程，或者是某種語言中用括號括起來的語句，這取決于實現的需要。 112 二、事務原語 例子 ? 考慮到保定火車站買一張從保定到汕頭的火車。由于沒有直達火車，只能買聯票。保定 ?石家莊；石家莊 ?廣州；廣州 ?汕頭。 下面通過 3個操作預定了這 3條獨立的路線的座票。 BEGIN_TRANSACTION reserve 保定 石家莊 reserve 石家莊 廣州 reserve 廣州 汕頭 END_TRANSACTION 113 二、事務原語 例子（續） ? 現在假設前兩條路線已經預定成功，但是第三條已經定滿了。那么事務就會因此而中止， 前兩個預定的結果也將被取消 —— 售票系統的數據庫恢復到了事務開始前的狀態，就像什么也沒有發生一樣。 BEGIN_TRANSACTION reserve 保定 石家莊 reserve 石家莊 廣州 廣州 汕頭 full →ABORT _ TRANSACTION END_TRANSACTION 114 三、事務的特性 ? 事務有四個重要的特性，它們是： ? 原子性 (Atomic)：對外部世界來說，事務的發生是不可分割的。 ? 一致性 (Consistent)：事務不會破壞系統的恒定。 ? 獨立性 (Isolated)：并發的事務不會互相干擾。 ? 持久性 (Durable)：一旦一個事務提交，改變就是永遠存在的。 ? 這幾個屬性通常按其首字母簡稱為 ACID。 115 原子性 ? 所有事務具有的第一個特性是 原子性 。 ? 這個特性 確保了每個事務要么全部發生，要么全部不發生 。 ? 如果發生，就是不可分割的， 瞬間 的操作。 ? 當一個事務處在處理過程中時，其它進程（無論是否與事務有關）都 不能看到任何中間狀態 。 116 原子性 — 例 ? 假設某個事務要在一個 10字節的文件末尾添加數據。 ? 如果在事務處理過程中其它進程讀取了這個文件，那么無論該事務已添加了多少內容，那些進程看到的只能是 10個字節。 ? 如果事務成功結束，這時文件在結束的 瞬時增長到 了新的大小，無論有多少個操作存在，都不會有中間狀態。 117 一致性 ? 第二個特性說明事務是 一致 的，這 意味著如果系統擁有某種必須經常保持的不變性，那么一旦在事務開始之前保持有這樣的性質，則事務結束后該性質就還應該存在 。 ? 例如在一個銀行系統中，最關鍵的不變性是資金守恒規則。 ? 在任何內部轉帳之后，銀行的資金帳目應與轉帳前保持一致，但是在事務執行的短暫時刻內，這種不變性會受到損害。然而事務結束之后，這種損害就沒有了。 118 獨立性 ? 第三個特性說明事務是 獨立的或連續的 。 ? 這意味著如果兩個或兩個以上的事務在同時運行，那么對它們自己和其它進程來說，最終結果看起來就象是所有的事務是 按某種次序 （ 依賴于系統 ）順序運行的。 119 獨立性 — 例 ? 下面三個事務被三個獨立的進程同時執行。 ? 如果它們順序執行，那么 X的最終結果應該是1， 2或 3，取決于哪一個事務最后運行（ X可以是一個共享變量，一個文件或其他對象）。 120 獨立性 — 例 ? 在 d中我們看到了稱之為 調度表 的不同次序，其中事務可以是交錯的。 ? 調度 1是真正串行的，即事務嚴格按順序來運行，因此它滿足連續性的定義。 ? 調度 2不是串行的，但是它也是合法的，因為它返回的 X值與嚴格串行返回的值一致。 ? 第三個調度是非法的，因為它將 X的值置成了 5，這是順序執行所不可能產生的。 121 獨立性（續） ? 為保證獨立的操作正確交替執行是系統的責任 。 ? 通過給予系統按照自己需要選擇操作執行順序的自由 —— 假設它得到的答案是正確的 —— 我們消除了程序員自己進行互斥處理的需要，因此簡化了編程。 122 持久性 ? 第四個特性說明事務是 持久 的。 ? 這是指這樣一個事實，即一旦一個事務提交，無論發生什么，這個事務都會向前進行，結果不會再變了。 提交之后發生的任何錯誤都不可能使結果取消或丟失。 123 四、嵌套事務 ? 事務可以包含子事務，這通常稱作 嵌套事務 。 ? 頂層事務可以在不同的處理機上創建并行運行的子事務，以提高性能、簡化編程。 ? 這些子事務中的任何一個都可以執行一個或多個子事務，或者創建自己的子事務。 124 四、嵌套事務 （續） ? 子事務引起的問題： ? 假設一個事務啟動了幾個并行的子事務，其中一個已經提交，其操作結果在父事務中已經生效。 ? 經過更進一步的計算，父事務被終止，并將系統恢復到了頂層事務開始前的狀態。 ? 結果，已經提交了的子事務的結果也必須被恢復。于是 上面提到的的持久性只是對頂層事務而言 。 ? 持久性：提交之后發生的任何錯誤都不可能使結果取消或丟失。 125 四、嵌套事務 （續） ? 由于事務可以嵌套任意多層，因此需要管理措施以使其一切正常。但 語義卻是清楚 的。 ? 當任何事務或子事務開始的時候，在概念上給予它一個整個系統全部對象的私有拷貝，可以按照其意愿進行操作。 ? 如果事務被終止，那么它的私有空間就會消失，就象事務從來都沒有存在過一樣。 ? 如果事務提交了，那么它的私有空間就會取代父輩的空間。 ? 因此如果一個子事務提交后又開始了一個新的子事務，那么它就可以看到第一個子事務的結果了。 126 ? 如果每個進程執行一個事務僅僅只是更新它自己使用的對象（文件、數據庫記錄等），那么事務就不會是原子的，而且事務異常終止時它所作的更改也不會神奇的消失。 ? 此外，運行多個事務時也不會是串行的。 ? 顯然，需要其它的實現方法。經常使用的有兩種方法： ? 私有工作空間 ? 寫前日志 127 一、私有工作空間 ? 第一種實現方法： 在進程開始一個事務的時刻給它分配一個私有工空間 。 ? 從概念上講，當一個進程開始一個事務時，會給它一個包含了所有需要訪問的文件（和其它對象）的私有工作空間 。 ? 在事務提交或終止前所有的讀寫操作都是在私有工空間而不是在通常所說的真正的文件系統中進行的。 ? 問題： ? 把所有內容都拷貝到一個私有工空間，其 代價是難以承受 的，但存在一些優化使得該方法更可行些。 128 一、私有工作空間 （續） ? 第一個優化 基于這樣的一種認識， ? 當一個進程讀取文件而不作修改時，就不需要私有拷貝了。 ? 該進程可以直接讀取真正的文件（除非當事務開始后文件已被改動）。 129 一、私有工作空間 （續） ? 當某個進程開始一個事務的時候，只要創建一私有工作空間，該私有工空間只包含一個指向父輩工作區的指針就足夠了。 ? 當事務處于最頂層的時候，它的工作區就是真正的文件系統。 ? 當一個進程打開文件進行讀取的時候，指針向回指直到可以在父輩（或更老的祖先）工作區中定位文件為止。 ? 當打開一個文件進行 寫入 時，它可用同讀取時一樣的方法進行定位，不過首先要將其復制到私有工作空間。 130 一、私有工作空間 （續） ? 第二個優化方法 大大減少了拷貝工作。 ? 該方法并不是將全部文件都拷入私有工空間，而只將其索引拷入。索引是一個與判斷文件所在磁盤塊位置有關的數據塊。 131 一、私有工作空間 （續） ? 通過私有索引，文件可以按通常的方式讀取。 ? 因為索引中包含有文件開始幾個塊的磁盤地址。 132 一、私有工作空間 （續） ? 當一個文件塊第一次被修改時，將會生成該塊的拷貝，其地址也將被插入索引中，然后就可以在不影響原始塊的情況下更新這個塊。 ? 添加塊也是用這個方法解決的。新塊有時也稱作 影象塊 (shadow block)。 ? 如圖所示，運行事務的進程看到了被修改的文件，但是其它進程看到的仍是原來的文件。 133 一、私有工作空間 （續） ? 在一個更復雜的事務中，私有工空間可能包含了大量的文件而不僅僅是一個。 ? 如果事務 異常終止 ，那么私有工空間就會被刪除，它所指向的所有私有塊也將被釋放回自由列表中。 ? 如果事務 成功結束 ，那么私有索引將會被自動移到父輩的工作區中，如圖所示。不需要的塊將它放回自由列表中。 134 二、寫前日志 ? 另一個實現事務的常用方法是 寫前日志(Writehead log)。有時也稱為計劃列表、意向表 (intentions list)。 ? 使用這種方法時， 文件會真正被修改 。但是在改動任何塊之前，將一條記錄寫入 穩定存儲器 的寫前日志中，以判斷是哪一個事務在進行修改操作，哪一個文件的哪一塊被改動了，舊值與新值分別是什么。 ? 只有當日志被成功的寫入之后才可以進行文件的修改。 ? 先寫寫前日志再修改！ 135 二、寫前日志 — 例子 ? 以下是一個日志如何工作的例子。 ? 圖 (a)中有一個使用兩個初值均是 0的共享變量（或其它對象） x， y的簡單事務。 ? 對事務中三條語句中的每一條，在執行之前都要寫入一條日志，以記錄新值和舊值，它們用斜杠來區分。 136 二、寫前日志 — 例子（續） ? 如果事務 執行成功并被提交 ，那么它的提交記錄將被寫入日志，但數據結構不需要變動，因為它們已經被更新了。 ? 如果 事務異常終止 ，那么可用日志來備份初始狀態。 137 二、寫前日志 — 例子（續） —— 日志用來進行系統崩潰后的恢復 ? 假設執行事務的進程在寫入圖 (d)中的最后一條記錄之后及改變 x之前崩潰。 ? 在機器重啟動后，日志可以用來檢查在系統崩時刻是否有事務正在處理中。 ? 當讀到最后一條記錄時顯示 x的當前值是 1，那么說明崩潰顯然是在更新之前發生的，所以 x的值應被改為 4。 ? 相反，如果在系統恢復時 x的值是 4，那也同樣清楚的說明崩潰是在更新后發生的，因此不需要進行任何變動。 138 二、寫前日志 — 例子（續） ? 從日志的末尾開始向回讀取每條記錄，再將記錄中描述的改動復原。這個操作稱之為 滾回 。 ? 使用日志使得向前（處理事務）和向后（撤消事務）成為了可能。 139 三、兩階段提交協議 ? 事務提交操作必須是原子性的，即 瞬時的和不可再分的。 ? 在分布式系統中，提交操作可能需要 不同機器上的多個進程 的協作，這些進程中的每一個都有一些被事務改動過的變量、文件、數據庫或者其它對象。 ? 本節將研究一個在分布式系統中實現原子性提交的協議。 ? 該協議稱為 兩階段提交協議 （ twophase mit protocol）（ Gray,1978）。盡管它不是此類協議中唯一的一個，但它卻是使用最廣泛的一個 。 140 三、兩階段提交協議（續） ? 基本思想：進程中的某一個會起到 協調者 的作用。一般來說這個進程就是執行事務的進程。①提交協議開始時協調者先寫入一條日志條目以表明它要開始提交協議。 141 三、兩階段提交協議（續） ② 然后它給每個相關進程（下屬