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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、了因果存儲器協(xié)約。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，因?yàn)?可能是R(x)1所讀的值計(jì)算的結(jié)果。兩個(gè)寫操作是因果聯(lián)系的，所有進(jìn)程必須視它們?yōu)橥豁樞颉Ｒ虼?-15(a)不正確。6-15(b)中，讀被取掉，w(x)1/和W(x)2變?yōu)椴l(fā)事件。因果一致性存儲器不要求并發(fā)寫有全局一致的次序，因此6-15(b)是正確的。在因果一致性存儲器中，所有機(jī)器看到的因果相關(guān)寫操作的順序是一致的，而并發(fā)寫操作的順序

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

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

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

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