分布式操作系統(tǒng)6(2)

1、 在DSM系統(tǒng)中，每個只讀頁可以有多個拷貝，而每個可 寫頁只能有一個拷貝。在最簡單的實現(xiàn)方案中，機器 遠程訪問一可寫頁會激活陷拼，然后獲取該頁。由于 可寫頁經(jīng)常共享，因此只允許有一個拷貝可能會帶來 嚴重的性能瓶頸。 只要能更新所有拷貝，允許多重拷貝就可以簡化性能 問題。但這又引起了新的問題:即如何保證所有拷貝的 一致性。當拷貝分布于不同機器上，而機器間通信只 能通過慢速的(和存儲器速度相比)網(wǎng)絡發(fā)送信包來完 成時，維護絕對的一致性就顯得尤其困難。 一致性模型本質(zhì)上是軟件與存儲器間的協(xié)約問題 它指 的是，如果軟件遵守約定的規(guī)則，存儲器就能工作正 常。如果軟件違反了這些規(guī)定，存儲器就不再保證操 作

2、的正確性。有些對軟件只有少量限制，而有些則使 普通編程幾乎成為不可能。限制少的模型沒有限制多 的模型執(zhí)行效果好。 6。3 一致性模型一致性模型 嚴格一致性 (Strict Consistency) 最嚴格的一致性模型稱為嚴格一致性，它由下述條件定 義:從存儲器地址x處讀出的值為最近寫入x的值。這個 定義自然而明白，由于它假定了絕對全局時間的存在， “最近”訪問的意義是明確的。傳統(tǒng)意義上，單一處理 機遵守嚴格一致性。 在一系統(tǒng)中編程如下:A=l;A=2;PRlNT(A); 在DSM系統(tǒng)中，假設X是存在B機器上的變量。A機器上的 進程在t1時刻讀取X,即發(fā)送信包到B以讀取X.稍后，在 t2時刻，B

3、機器上的進程寫x.若遵守嚴格一致性，不管 機器在哪里，相距多近，A都應該讀出原來的值。然而， 若t2-t1=1ns，而機器距離3米，從A到B傳送讀操作并使 之先于寫操作，信號則必須以十倍光速的速度傳遞，而 這與愛因斯坦相對論矛盾。 帶來了存儲器和軟件的協(xié)約問題。若協(xié)約或明顯或暗 示地要求嚴格一致性，存儲器則最好傳送它。為使舉 例精確，我們需要一些特定符號。先規(guī)定一些符號:p1， p2，代表不同的進程，在圖中以不同的高度表示， 每一進程完成的操作水平的顯示時間軸向右增加，直 線分割不同進程。符號 W(x)a和R(y)b分別表示在x處寫 a和從y處讀出值賦給b. 本章所有圖表中變量初值均為0。 如

4、圖6-l0(a)，P1在x處寫1之后，p2讀x，返回1。對于 嚴格一致性存儲器，操作是正確的。 相反的，如圖6-10(b)，P2在寫之后讀(或許是1納秒之 后，但仍在寫之后)，返回值為0。之后又執(zhí)行一次讀 操作，返回值為 1。對于嚴格一致性的存儲器，這個 操作是不正確的。 總之，對于嚴格一致性的存儲器，寫操作在任一時刻 對所有進程都是可見的，同時維護一個絕對全局時間。 一旦存儲器中的值改變，不管讀寫之間的事件間隔多 小，不管哪個進程執(zhí)行讀操作，也不管進程在何處， 以后讀出的都是新更改的值。同樣，不管后面的寫操 作有多迅速，執(zhí)行讀操作仍應讀出原來的值。 順序一致性(SequentialConsi

5、stency) 盡管嚴格一致性是理想的編程模式，但在分 布系統(tǒng)申，這幾乎不可能實現(xiàn)。經(jīng)驗表明，編程 人員通常對弱模式掌握得較好。比如，所有操作 系統(tǒng)課本中都談到臨界區(qū)和同步互斥的問題。人 們認為編寫這種正確的并行程序 (如生產(chǎn)者一消 費者問題)不應考慮進程間的相對速度以及語旬 的執(zhí)行在時間上如何交錯。如果一個進程的兩個 事件發(fā)生如此之快，以致其他進程不能在此之間 執(zhí)行任何操作，那可能會帶來麻煩。相反，讀者 的編程方式是:語句執(zhí)行順序(實際上是存儲器訪 問)并不重要。如果事件順序是必要的，必須要 用到信號量或其他同步操作。接受這種意見意味 著采用弱模式。經(jīng)過兒次實踐，大多數(shù)并行程序 編寫人員都能

6、適應這種模式。 順序一致是比嚴格一致稍弱的存儲器模式，首先定義了順 序一致存儲器應符合的條件:如果所有進程以一定的順序 執(zhí)行操作，每一進程的操作都以程序規(guī)定的順序出現(xiàn)，則 任何操作的結果都是一樣的。 這個定義說明:對于在不同機器上并行運行的進程， 任何有效的交錯都是可以接受的行為，但所有進程必須遵 守同一訪問存儲器順序。在一塊存儲器中，若一個進程 (或處理機)看到一種交錯另一進程看到另一個交錯，這就 不是順序一致存儲器。注意，這與時間無關，沒有最近存 入的概念。在這里，進程可以看到所有進程寫，但只能看 到本進程讀。 順序一致 從圖6-11可以看出這里不考慮時間。圖6-11(a)表示 的存儲器行

7、為是順序一致的，盡管P2執(zhí)行的第一次讀 操作返回初值0而不是新值l。圖6-11 運行同一個程序 得到的兩個可能的結果。 順序一致存儲器不保證讀返回的值是lns、lms甚至 1分鐘以前另一進程寫入的。它只保證所有進程以相同 的順序看見存儲器訪問。如果根據(jù)圖6-11(a)編寫的程 序在一次運行后，或許會得到圖6-11(b)的結果。結果 是不確定的。如果缺少明確的同步操作，在此運行程 序或許不能得到相同的結果。 P1:w(x)1P1:w(x)1 P2: R(x)0R(x)1P2: R(x)1R(x)1 圖6-11 運行同一個程序得到的兩個可能的結果。 三個并行運行的進程的代碼。三個進程共享相同 的順

8、序一致分布式共享存儲器，并都訪問變量a,b,c。 從存儲器訪問的角度看，賦值應被看作寫操作，打印 應被看作同時讀取它的兩個參數(shù)。所有語句都是原子 操作。各種交錯執(zhí)行的順序都是可能的。六個獨立的 語句，將會有720(6!)種可能的執(zhí)行順序，盡管它們可 能會破壞程序順序。從a=I開始的考慮的順序有120(5!) 種。其中一半將在b=l前執(zhí)行print(a，c)，這就打亂 了程序次序。還有一半將在c=1前執(zhí)行print(a，b),打 亂程序次序。120中順序中只有1/4即30個是有效的。 另外30個有效順序是以b=I開頭的，還有30個以c=l開 頭。共有90個有效執(zhí)行順序。 如圖6-13(a)，三個

9、進程以p1， p12、P3的次序 運行，另三個例子(b) (c) (d ) 則不同，但 同樣是有效的，語句按時間交錯執(zhí)行，三個進 程部打印兩個參數(shù)。由于每個變量只可能是初 值0或被賦值為1，每個進程產(chǎn)生一個二位字串。 在print操作之后的數(shù)字是在輸出設備上的實 際輸出。下面可以標記項而不用打印輸出表示 每個次序。 若以這種次序順序輸出p1， p12、P3的結果，將 得到六位字串，這標明了語句 (以及存儲器訪 問)的一個特定交錯。這就是圖6-13中的標記 項 (Signature)所寫的字符串。 并非所有64種標記項都是允許的。如000000就不允許， 因為這意味著打印語句先于賦值執(zhí)行，違反了

10、關于語 句必須按照程序順序執(zhí)行的規(guī)定。另一的例子是 001001，前兩位00即當p1打印時，b,c都是0。這種情 況只發(fā)生在p1在p2,p3開始前執(zhí)行所有語句。下面二位 10，即p2必須在p1之后P3之前開始執(zhí)行，最后兩位01， 即p3必須在開始之前完成。但我們已經(jīng)看到p1必須先 運行，因此001001是不可能的。 總之，在假定順序一致的情況下，90種不同的有效語 句次序?qū)е铝瞬煌?但少于64種)運行結果，這些都 是允許的。軟件與存儲器在這里的約定是:軟件必須承 認它們都是有效結果。也就是軟件必須接受圖6-13的4 個結果以及其他有效結果為正確答案。若任何一種情 況發(fā)生，這就仍須正常工作。

11、順序一致存儲器可在DSM或多處理機系統(tǒng)上實現(xiàn)。有很多正式系統(tǒng) 使用了順序存儲器(和其他模式)思想。我們簡單看一下Ahamad系 統(tǒng)。在這種系統(tǒng)中，進程i讀寫操作順序由Hi(Pi的歷史)確定，圖 6-10b顯示兩種次序H1和H2，分別對應于p1和p2，表示如下: H1=W(x)1;H2=R(x)OR(x)1 這種次序的集合稱為H。 為得到操作執(zhí)行的相對順序，必須合并H中的操作串為一個單獨 串S，每個操作在S中出現(xiàn)一次。S的合法值須遵守兩個限制:(1)維 持程序次序;(2)保證存儲相關性。 第一條限制:如果在H的字串中，讀或?qū)懺L問A出現(xiàn)在另一訪問B之前， 那么S中A也應出現(xiàn)于B之前。若所有操作遵守

12、這個規(guī)定，則S中不 會出現(xiàn)違反程序的執(zhí)行順序。 第二條限制意味著在地址x處讀出的值必須是最新寫入的x,即在R(x) 之前由最近的W(x)v寫入的值v。 圖6-10(b)中，S只有一個合法值:s=R(x)0W(x)1R(x)1，對于更復 雜的例子，S可能會有更多的合法值，若操作順序是按照S的一些 合法值進行的，則程序運行被認為是正確的。 雖然順序一致性是對編程人員友好的模式，但有嚴重的性能問題。 若讀時間為r寫時間為w，節(jié)點間信包傳輸最小時間為t則總有 r+w=t.換而言之也就是對所有順序一致存儲器來說，改變協(xié)議試 圖提高讀性能只能導致寫性能下降，反之亦然。 633 因果一致性(CausaICo

13、ns;stency) 因果一致模型是順序一致的淡化，它按有無可能 的因果聯(lián)系區(qū)分各事件?，F(xiàn)在看看存儲器的例子。假 設進程P1寫變量x然后P2讀出x寫入y。這里讀出x和寫 入y之間可能有潛在的因果聯(lián)系，因為y的計算很可能 決定于P2讀到的x值 (即P1寫入的值)。另一方面，若 兩進程自然而同時地寫兩個變量，就沒有因果聯(lián)系。 先有讀操作之后執(zhí)行寫操作，兩個事件就可能有因果 聯(lián)系。相似的，讀和提供所讀數(shù)據(jù)的寫有因果關系。 沒有因果關系的操作稱為并發(fā)的(concurrent)。 因果一致的存儲器應遵守以下條件: 可能因果相關的寫操作應對所有進程可見，且順序 一致。并發(fā)寫操作在不同機器看來順序可能是不同

14、的。 圖6.14是一個因果一致性的例子。這里我們有-個在因 果一致存儲器下允許的事件順序，在順序一致存儲器和 嚴格一致存儲器中這是禁止的。要注意的是，W(X)2和 W(x)3是并發(fā)的，所以不須所有進程將他們視為同一順 序。若不同進程以不同次序看待并發(fā)事件，而導致軟件 失敗，則違反了因果存儲器協(xié)約。 P1:w(x)1 w(x)3 P2: R(x)1 w(x)2 P2: R(x)1 R(x)3 R(x)2 P2: R(x)1 R(x)2 R(x)3 圖6.14 因果一致性可， 順序一致不可 圖6-15(a)中，W(x)2可能決定于w(x)1，因為2可能是R(x)1 所讀的值計算的結果。兩個寫操作是

15、因果聯(lián)系的，所有進 程必須視它們?yōu)橥豁樞?。因?-15(a)不正確。6-15(b) 中，讀被取掉，w(x)1/和W(x)2變?yōu)椴l(fā)事件。因果一致性 存儲器不要求并發(fā)寫有全局一致的次序，因此6-15(b)是正 確的。 在因果一致性存儲器中，所有機器看到的因果相關寫操作 的順序是一致的，而并發(fā)寫操作的順序可以不同。進一步 放松對存儲器限制可以去掉前面的要求。這樣就給出了 PRAM一致(管道RAM)，它要遵守的條件是: 一個進程的寫操作可以被其他進程以指定的順序接收到， 但不同進程的寫操作在不同進程看來次序可以是不同的。 PRAM一致和因果一致的對比如圖6-16所示。這里的時間順 序在PRAM一致

16、的存儲器中是允許的。 PRAM 一致性和處理器一致性 PRAM一致由于易于應用而得到關注。它不保證不同進 程看到的寫操作順序是一致的，除非是一個源的一個或多 個寫操作，才必須按次序到達，就好像在管道中。換而言 之，在這種模式申，由不同進程產(chǎn)生的巧操作是并發(fā)的。 圖6-17，在PRAM一致下，不同進程所看到的語句執(zhí)行 順序不同，如圖6-17(a)顯示p1怎樣看到事件，而6-17(b) 顯示p2所看到的，6-17(c)則是P3所見。對于順序一致存 儲器，三個不同顯示是不允許的。 我們使三個進程的輸出順序相接，得到結果為001001， 正如我們早先看到的，這在順序一致性下是不可能的。順 序一致與PR

17、AM一致的關鍵不同在于:前者盡管末確定語句 (和存儲器訪問)的執(zhí)行順序，但至少所有進程都遵守共同 的順序。后者就不遵守。不同進程看到的操作順序不同。 有時，PRAM一致導致的結果不那么直觀。在下面的例子中 提出了一種略微不同但仍支持PRAM一致的存儲器形式 。 如圖6-18，有人可能會天真地期待出現(xiàn)三種結果之一:P1 被 KlL；P2被KILL;或兩者都不被KILL(如果兩個賦值語句 先執(zhí)行了)。在PRAM一致下，可能兩個進程都被KlLL，即 若P1在看到P2中b賦值之前讀取b,p2在看到P1中a賦值之前 讀取a.在順序一致存儲器下可能有6種語句交錯，沒有一 種可以導致兩進程都被KlLL。 6

18、.3.5 弱一致性(Week Consistency) 通過同步變量，可以讓進程完成臨界區(qū)操作以后，將 最后結果發(fā)送到各處，而不必太關心甚至不用關心中 間結果是否也按順序發(fā)送到存儲器。 Dubois定義這種模式為弱一致性，它有三個屬性： 對同步變量的訪問是順序一致性的； 在所有先前的寫操作完成之前，不能訪問同步變量； 在先前所有同步變量的訪問完成之前，不能訪問同步變量。 弱一致性要求只有訪問同步變量時，存儲器才需要更 新，新的寫操作可以在前一寫操作完成之前開始，在 一些情況下完全可以避免寫； 弱一致性是對一組操作的約定； 弱一致性實現(xiàn)與某 些編譯器優(yōu)化原理 類似。 由于同步變量的偏 差，在某些特殊情 況下，弱一致性存 在偏差。