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

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

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

4、致性存儲器，操作是正確的。 相反的，如圖6-10(b)，P2在寫之后讀(或許是1納秒之后，但仍在寫之后)，返回值為0。之后又執行一次讀操作，返回值為 1。對于嚴格一致性的存儲器，這個操作是不正確的。總之，對于嚴格一致性的存儲器，寫操作在任一時刻對所有進程都是可見的，同時維護一個絕對全局時間。一旦存儲器中的值改變，不管讀寫之間的事件間隔多小，不管哪個進程執行讀操作，也不管進程在何處，以后讀出的都是新更改的值。同樣，不管后面的寫操作有多迅速，執行讀操作仍應讀出原來的值。 順序一致性(SequentialConsistency) 盡管嚴格一致性是理想的編程模式，但在分布系統申，這幾乎不可能實現。經驗

5、表明，編程人員通常對弱模式掌握得較好。比如，所有操作系統課本中都談到臨界區和同步互斥的問題。人們認為編寫這種正確的并行程序 (如生產者一消費者問題)不應考慮進程間的相對速度以及語旬的執行在時間上如何交錯。如果一個進程的兩個事件發生如此之快，以致其他進程不能在此之間執行任何操作，那可能會帶來麻煩。相反，讀者的編程方式是:語句執行順序(實際上是存儲器訪問)并不重要。如果事件順序是必要的，必須要用到信號量或其他同步操作。接受這種意見意味著采用弱模式。經過兒次實踐，大多數并行程序編寫人員都能適應這種模式。 順序一致是比嚴格一致稍弱的存儲器模式，首先定義了順序一致存儲器應符合的條件:如果所有進程以一定的

6、順序執行操作，每一進程的操作都以程序規定的順序出現，則任何操作的結果都是一樣的。 這個定義說明:對于在不同機器上并行運行的進程，任何有效的交錯都是可以接受的行為，但所有進程必須遵守同一訪問存儲器順序。在一塊存儲器中，若一個進程 (或處理機)看到一種交錯另一進程看到另一個交錯，這就不是順序一致存儲器。注意，這與時間無關，沒有最近存入的概念。在這里，進程可以看到所有進程寫，但只能看到本進程讀。順序一致 從圖6-11可以看出這里不考慮時間。圖6-11(a)表示的存儲器行為是順序一致的，盡管P2執行的第一次讀操作返回初值0而不是新值l。圖6-11 運行同一個程序得到的兩個可能的結果。 順序一致存儲器不

7、保證讀返回的值是lns、lms甚至1分鐘以前另一進程寫入的。它只保證所有進程以相同的順序看見存儲器訪問。如果根據圖6-11(a)編寫的程序在一次運行后，或許會得到圖6-11(b)的結果。結果是不確定的。如果缺少明確的同步操作，在此運行程序或許不能得到相同的結果。P1:w(x)1P1:w(x)1P2: R(x)0R(x)1P2: R(x)1R(x)1圖6-11 運行同一個程序得到的兩個可能的結果。 三個并行運行的進程的代碼。三個進程共享相同的順序一致分布式共享存儲器，并都訪問變量a,b,c。從存儲器訪問的角度看，賦值應被看作寫操作，打印應被看作同時讀取它的兩個參數。所有語句都是原子操作。各種交錯

8、執行的順序都是可能的。六個獨立的語句，將會有720(6!)種可能的執行順序，盡管它們可能會破壞程序順序。從a=I開始的考慮的順序有120(5!)種。其中一半將在b=l前執行print(a，c)，這就打亂了程序次序。還有一半將在c=1前執行print(a，b),打亂程序次序。120中順序中只有1/4即30個是有效的。另外30個有效順序是以b=I開頭的，還有30個以c=l開頭。共有90個有效執行順序。如圖6-13(a)，三個進程以p1， p12、P3的次序運行，另三個例子(b) (c) (d ) 則不同，但同樣是有效的，語句按時間交錯執行，三個進程部打印兩個參數。由于每個變量只可能是初值0或被賦值

9、為1，每個進程產生一個二位字串。在print操作之后的數字是在輸出設備上的實際輸出。下面可以標記項而不用打印輸出表示每個次序。若以這種次序順序輸出p1， p12、P3的結果，將得到六位字串，這標明了語句 (以及存儲器訪問)的一個特定交錯。這就是圖6-13中的標記項 (Signature)所寫的字符串。 并非所有64種標記項都是允許的。如000000就不允許，因為這意味著打印語句先于賦值執行，違反了關于語句必須按照程序順序執行的規定。另一的例子是001001，前兩位00即當p1打印時，b,c都是0。這種情況只發生在p1在p2,p3開始前執行所有語句。下面二位10，即p2必須在p1之后P3之前開始

10、執行，最后兩位01，即p3必須在開始之前完成。但我們已經看到p1必須先運行，因此001001是不可能的。 總之，在假定順序一致的情況下，90種不同的有效語句次序導致了不同的(但少于64種)運行結果，這些都是允許的。軟件與存儲器在這里的約定是:軟件必須承認它們都是有效結果。也就是軟件必須接受圖6-13的4個結果以及其他有效結果為正確答案。若任何一種情況發生，這就仍須正常工作。順序一致存儲器可在DSM或多處理機系統上實現。有很多正式系統使用了順序存儲器(和其他模式)思想。我們簡單看一下Ahamad系統。在這種系統中，進程i讀寫操作順序由Hi(Pi的歷史)確定，圖6-10b顯示兩種次序H1和H2，分

11、別對應于p1和p2，表示如下: H1=W(x)1;H2=R(x)OR(x)1 這種次序的集合稱為H。 為得到操作執行的相對順序，必須合并H中的操作串為一個單獨串S，每個操作在S中出現一次。S的合法值須遵守兩個限制:(1)維持程序次序;(2)保證存儲相關性。第一條限制:如果在H的字串中，讀或寫訪問A出現在另一訪問B之前，那么S中A也應出現于B之前。若所有操作遵守這個規定，則S中不會出現違反程序的執行順序。第二條限制意味著在地址x處讀出的值必須是最新寫入的x,即在R(x)之前由最近的W(x)v寫入的值v。 圖6-10(b)中，S只有一個合法值:s=R(x)0W(x)1R(x)1，對于更復雜的例子，

12、S可能會有更多的合法值，若操作順序是按照S的一些合法值進行的，則程序運行被認為是正確的。 雖然順序一致性是對編程人員友好的模式，但有嚴重的性能問題。若讀時間為r寫時間為w，節點間信包傳輸最小時間為t則總有r+w=t.換而言之也就是對所有順序一致存儲器來說，改變協議試圖提高讀性能只能導致寫性能下降，反之亦然。 633 因果一致性(CausaICons;stency) 因果一致模型是順序一致的淡化，它按有無可能的因果聯系區分各事件。現在看看存儲器的例子。假設進程P1寫變量x然后P2讀出x寫入y。這里讀出x和寫入y之間可能有潛在的因果聯系，因為y的計算很可能決定于P2讀到的x值 (即P1寫入的值)。

13、另一方面，若兩進程自然而同時地寫兩個變量，就沒有因果聯系。先有讀操作之后執行寫操作，兩個事件就可能有因果聯系。相似的，讀和提供所讀數據的寫有因果關系。沒有因果關系的操作稱為并發的(concurrent)。 因果一致的存儲器應遵守以下條件: 可能因果相關的寫操作應對所有進程可見，且順序一致。并發寫操作在不同機器看來順序可能是不同的。 圖6.14是一個因果一致性的例子。這里我們有-個在因果一致存儲器下允許的事件順序，在順序一致存儲器和嚴格一致存儲器中這是禁止的。要注意的是，W(X)2和 W(x)3是并發的，所以不須所有進程將他們視為同一順序。若不同進程以不同次序看待并發事件，而導致軟件失敗，則違反

14、了因果存儲器協約。P1:w(x)1 w(x)3P2: R(x)1 w(x)2P2: 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所讀的值計算的結果。兩個寫操作是因果聯系的，所有進程必須視它們為同一順序。因此6-15(a)不正確。6-15(b)中，讀被取掉，w(x)1/和W(x)2變為并發事件。因果一致性存儲器不要求并發寫有全局一致的次序，因此6-15(b)是正確的。在因果一致性存儲器中，所有機器看到的因果相關寫操作的順序是一致的，而并發寫操作的順序

15、可以不同。進一步放松對存儲器限制可以去掉前面的要求。這樣就給出了PRAM一致(管道RAM)，它要遵守的條件是:一個進程的寫操作可以被其他進程以指定的順序接收到，但不同進程的寫操作在不同進程看來次序可以是不同的。PRAM一致和因果一致的對比如圖6-16所示。這里的時間順序在PRAM一致的存儲器中是允許的。PRAM 一致性和處理器一致性 PRAM一致由于易于應用而得到關注。它不保證不同進程看到的寫操作順序是一致的，除非是一個源的一個或多個寫操作，才必須按次序到達，就好像在管道中。換而言之，在這種模式申，由不同進程產生的巧操作是并發的。 圖6-17，在PRAM一致下，不同進程所看到的語句執行順序不同

16、，如圖6-17(a)顯示p1怎樣看到事件，而6-17(b)顯示p2所看到的，6-17(c)則是P3所見。對于順序一致存儲器，三個不同顯示是不允許的。 我們使三個進程的輸出順序相接，得到結果為001001，正如我們早先看到的，這在順序一致性下是不可能的。順序一致與PRAM一致的關鍵不同在于:前者盡管末確定語句(和存儲器訪問)的執行順序，但至少所有進程都遵守共同的順序。后者就不遵守。不同進程看到的操作順序不同。有時，PRAM一致導致的結果不那么直觀。在下面的例子中提出了一種略微不同但仍支持PRAM一致的存儲器形式 。如圖6-18，有人可能會天真地期待出現三種結果之一:P1被 KlL；P2被KILL

17、;或兩者都不被KILL(如果兩個賦值語句先執行了)。在PRAM一致下，可能兩個進程都被KlLL，即若P1在看到P2中b賦值之前讀取b,p2在看到P1中a賦值之前讀取a.在順序一致存儲器下可能有6種語句交錯，沒有一種可以導致兩進程都被KlLL。6.3.5 弱一致性(Week Consistency) 通過同步變量，可以讓進程完成臨界區操作以后，將最后結果發送到各處，而不必太關心甚至不用關心中間結果是否也按順序發送到存儲器。 Dubois定義這種模式為弱一致性，它有三個屬性： 對同步變量的訪問是順序一致性的； 在所有先前的寫操作完成之前，不能訪問同步變量； 在先前所有同步變量的訪問完成之前，不能訪

18、問同步變量。 弱一致性要求只有訪問同步變量時，存儲器才需要更新，新的寫操作可以在前一寫操作完成之前開始，在一些情況下完全可以避免寫； 弱一致性是對一組操作的約定； 弱一致性實現與某些編譯器優化原理類似。 由于同步變量的偏差，在某些特殊情況下，弱一致性存在偏差。6.3.6 釋放一致性(Release Consistency) 在弱一致性下，當訪問同步變量時，存儲器不能判斷進程變量的訪問類型。 釋放一致性提供分離的兩種變量：獲取和釋放。 在釋放一致性下，通過屏障，在進程完成程序的n階段之前，會被禁止開始n+1階段。 在釋放一致性下，當軟件執行獲取訪問時，存儲器會根據需要確保被保護變量的本地拷貝被更新，并與遠程變量保持一致；當執行釋放操作時，被修改的被保護變量要傳送到其他機器上。 釋放一致性遵守以下規定： 在訪問共享變量前，進程所有先前的獲取訪問都必須成功完成； 在允許釋放訪問前，進程先前的所有讀寫操作都必須結束； 獲取訪問和釋放訪問必須是處理