




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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階段。 在釋放一致性下,當軟件執行獲取訪問時,存儲器會根據需要確保被保護變量的本地拷貝被更新,并與遠程變量保持一致;當執行釋放操作時,被修改的被保護變量要傳送到其他機器上。 釋放一致性遵守以下規定: 在訪問共享變量前,進程所有先前的獲取訪問都必須成功完成; 在允許釋放訪問前,進程先前的所有讀寫操作都必須結束; 獲取訪問和釋放訪問必須是處理
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 材料員崗位面試問題及答案
- 廣東省揭陽市產業園2025屆化學高一下期末綜合測試試題含解析
- 天津耀華嘉誠國際中學2025屆高二化學第二學期期末預測試題含解析
- 湖北省仙桃、天門、潛江三市2025屆高一下化學期末監測試題含解析
- 北斗監控動態管理辦法
- 農村產權交易管理辦法
- 保安制服收繳管理辦法
- 北京招聘醫療管理辦法
- 制程物料標識管理辦法
- 新質生產力背景下元宇宙賦能圖書館數字化轉型的策略與挑戰
- 廣州市藝術中學招聘教師考試真題2024
- 工業自動化設備保修及維修管理措施
- 期末作文預測外研版七年級英語下冊
- 2025-2030中國兒童魚油行業銷售動態及競爭策略分析報告
- 統編版五年級升六年級語文暑期銜接《課外閱讀》專項測試卷及答案
- 小小理財家課件
- DB43-T 2622-2023 醫療導管標識管理規范
- 譯林版一年級下冊全冊英語知識點梳理
- 案場物業制度管理制度
- 護理事業十五五發展規劃(2026-2030)
- CJ/T 316-2009城鎮供水服務
評論
0/150
提交評論