1、2022-3-231 1第十一章第十一章 分布式共享存儲器分布式共享存儲器第十一章第十一章 分布式共享存儲器分布式共享存儲器 22022-3-23中南大學軟件學院11.1 基本概念基本概念v 什么是分布式共享存儲器系統什么是分布式共享存儲器系統 分布式共享存儲器系統是分布式操作系統中的一個資源管理部件，它在沒有物理上共享的存儲器的分布式操作系統中實現了共享存儲器模式。這種共享存儲器模式在分布式系統中提供了一個可供系統內所有節點所共享的虛擬地址空間。程序設計者可以像使用傳統的存儲器一樣使用該虛擬地址空間。這種物理上分布邏輯上共享的存儲器就叫做分布式共享存儲器(Distributed Shared

2、 MemoryDSM)。 如圖所示，程序員訪問DSM系統的虛擬地址空間的數據就像訪問傳統的虛擬存儲器一樣，每一個節點都可以擁有存儲在共享空間的數據，數據的所有者也可以跟隨數據從一個節點移到另一個節點。當一個進程訪問共享地址空間中的數據時，映像管理員就把共享存儲器地址變換到本地地址或遠程的物理存儲器地址。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 32022-3-23中南大學軟件學院11.1 基本概念基本概念v 什么是分布式共享存儲器系統什么是分布式共享存儲器系統 本地存儲器 本地存儲器 本地存儲器 節點 節點 節點 映像管理員 映像管理員 映像管理員 共享存儲器 第十一章第十一章 分

3、布式共享存儲器分布式共享存儲器 42022-3-23中南大學軟件學院11.1 基本概念基本概念v 為什么需要分布式共享存儲器為什么需要分布式共享存儲器 松散耦合分布式系統中的計算機如果沒有分布式共享存儲器，為了使這些計算機合作完成一個共同的任務，就必須共享狀態。共享狀態有兩種方式，第一種是使用報文傳遞原語顯示地移動數據。第二種是，共享數據在一個專用進程中實現，其他進程向此進程發送事先規定的操作，然后由此進程對該數據執行所需的操作，這就是遠程過程調用(RPC)的方法。 報文傳遞方式中，數據在程序之間移來移去極大地增加了應用程序設計者的負擔。RPC的顧客和服務員也是在分隔的地址空間執行的，顧客用數

4、值傳遞參數、傳送復雜的數據結構或上下文有關的數據很困難。第十一章第十一章 分布式共享存儲器分布式共享存儲器 52022-3-23中南大學軟件學院11.1 基本概念基本概念v為什么需要分布式共享存儲器為什么需要分布式共享存儲器 1) DSM的計算模型支持數據在系統內移動，使數據更容易訪問。 2) RPC計算模型是把操作移到數據所在位置。RPC不支持程序利用其訪問的局部性優點，對一塊遠程數據的每個操作都產生通信，對數據的操作必須先定義好。但是RPC支持異構型。 3) DSM可把數據移到本地節點，允許程序利用其訪問的局部性優點，使用緩存器可以改善響應時間。移動性要求對數據位置進行跟蹤；緩存要求解決各

5、副本的一致性。當數據正向某個主機移動時，不能對它進行處理。如果數據經常修改，RPC模型可能更好些。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 62022-3-23中南大學軟件學院11.1 基本概念基本概念v 為什么需要分布式共享存儲器為什么需要分布式共享存儲器 從通信機制來看，DSM與報文傳遞方式有以下不同 ：(1)訪問的透明性。(2)共享數據結構的復雜性和異構性。(3)數據的局部性。第十一章第十一章 分布式共享存儲器分布式共享存儲器 72022-3-23中南大學軟件學院11.1 基本概念基本概念v 為什么需要分布式共享存儲器為什么需要分布式共享存儲器 與緊密耦合的多機系統相比，DS

6、M系統具有以下特點：(1) 規模可擴充。 (2) 廉價。(3) 兼容性。第十一章第十一章 分布式共享存儲器分布式共享存儲器 82022-3-23中南大學軟件學院11.1 基本概念基本概念v 共享存儲器中緩存一致性方法共享存儲器中緩存一致性方法 有兩類基本方法實現緩存一致性：即探聽緩存方法和使用目錄的方法。 探聽(snooping)緩存方法用于具有廣播能力的通信介質中，例如共享總線。每個緩存器為了保持自己數據的一致性要監聽共享總線上進行的由其他處理機發出的存儲器操作。Berkeley是一個典型例子，它是一種寫無效協議，它假設通過單總線訪問共享的物理存儲器。此協議采用一個所有權方案。一個數據塊的所

7、有者是一個緩存器，是上次對該數據塊的修改者，如果該塊被其所有者清除，則主存作為其所有者。 探聽緩存方法支持的系統規模有限，因為它總是依賴于共享總線，而且，由于在總線上監聽存儲器每個操作時要對緩存器進行檢查，處理機與其緩存器之間的正常通信會產生延遲。可以使用目錄解決這個問題。第十一章第十一章 分布式共享存儲器分布式共享存儲器 92022-3-23中南大學軟件學院11.1 基本概念基本概念v 共享存儲器中緩存一致性方法共享存儲器中緩存一致性方法 使用目錄即在共享存儲器中設置存儲器塊的目錄。當發生緩存不命中時，先把請求轉到此目錄。通常目錄項中包含所有權、副本集(copyset)和該塊的重寫位。副本集

8、指出該塊數據在哪些緩存器中有副本，可用位向量來實現。發生讀未命中時，先檢查重寫位，如果該塊不處于重寫狀態，則共享存儲器中的版本是有效的，于是簡單地返回該塊，并對副本集信息進行更新；如果該塊的重寫位置位，則該塊的所有者必須修改該塊，并且要更新共享存儲器中的版本，向讀者提供讀副本。寫未命中或者從讀權變成寫權時，要求目錄的副本集使其他副本無效。與探聽緩存方案不同，讀副本的位置都已經知道，因此，可以用順序方式而不是以廣播方式發送“無效”報文。目錄方案不要求廣播介質，但在每次緩存未命中時要增加一次查表。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 102022-3-23中南大學軟件學院11.1

9、基本概念基本概念vDSM的設計與實現問題的設計與實現問題 （1）共享地址空間結構和粒度。共享地址空間的結構指的是存儲器中共享數據的布局方法，它依賴于應用程序類型，地址空間可以是平面的，分段的或物理的。粒度是指共享單元的大小，可以是字節、字、頁或復雜的數據結構，它也是可用的并行性的度量，依賴于通信開銷和應用程序表現的局部性類型。結構和粒度是密切相關的。 （2）緩存一致性協議。不同的協議有不同的假設，選擇協議依賴于存儲器訪問模式和支持環境。在寫無效協議中，一塊共享數據可能有很多個只讀副本，但僅有一個可寫副本，每進行一次寫時，除了一個以外，其他副本均變成無效。在寫更新協議中。每次寫都要對所有副本進行

10、更新。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 112022-3-23中南大學軟件學院11.1 基本概念基本概念v DSM的設計與實現問題的設計與實現問題 （3）同步原語。在并發訪問下，光有緩存一致性協議還不能維持共享數據一致性。尚需要同步原語對訪問共享數據的活動進行同步，例如信號燈、事件計數和鎖等。（4）替換策略。在允許數據遷移的系統中，當共享數據占滿了緩存器的有效空間時，必須決定將那些數據轉移出去并且放到哪里去。（5）可擴充性。DSM系統比起緊密耦合系統來，一個重大的優點是具有可擴充性。限制可擴充性有兩個因素：集中的瓶頸(像緊密耦合系統中的總線)和全局公用信息的操作及存儲(如廣

11、播報文或目錄等)。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 122022-3-23中南大學軟件學院11.1 基本概念基本概念v DSM的設計與實現問題的設計與實現問題 （6）異構性。如何實現對兩個具有不同體系結構的機器的存儲器共享是個很困難的問題。兩個機器甚至對基本數據類型(如整數、浮點數等)都使用不同的表達方式。（7）數據定位和訪問。為了在一個DSM系統中共享數據，應用程序必須能找到并且檢索所需要的數據。對于一個支持數據遷移的系統，實現這一點就更為復雜。（8）顛簸。DSM系統特別容易出現顛簸，例如若兩個節點對一個數據項同時進行寫，就可能產生以高速率來回傳送數據的現象(乒乓效應)，

12、使得任何實際工作都不能進行。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 132022-3-23中南大學軟件學院11.1 基本概念基本概念v一致性語義一致性語義 下面是在共享存儲器中常使用的一些一致性語義，從強到弱分別是嚴格一致性、順序一致性、處理一致性、弱一致性和釋放一致性。（1）嚴格一致性。對一個數據項所進行的任何讀操作所返回的值總是對該數據項最近一次進行寫操作的結果。（2）順序一致性。所有進程對數據項的所有操作可以認為是按照某個順序進行的，任何進程對這個順序的觀點是一樣的。（3）處理機一致性。不僅要求一個進程中的所有寫操作能夠以它在該進程中出現的順序被所有其他進程看見，還要求不同

13、進程對同一個數據項的寫操作，應該被所有進程以相同的順序看見。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 142022-3-23中南大學軟件學院11.1 基本概念基本概念v 一致性語義一致性語義 （4）弱一致性。程序員使用同步算符，使得對數據的多個操作組來說是順序一致性的。即不同進程的多個操作組可以認為是按照某個順序進行的，任何進程對這個順序的觀點是一樣的。但是操作組內的多個操作其他進程是不可見的。對同步算符是順序一致性的。 （5）釋放一致性。使用了“獲得”和“釋放”這兩類同步算符，對同步算符是處理機一致的。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 152022-3-23中

14、南大學軟件學院11.2 實現實現DSM的算法的算法 v 算法使用的模型和環境算法使用的模型和環境 （1）首先，要對實現算法所需環境作些假定總的說來，分布式和并行應用程序的性能主要由通行代價決定，而通行代價由基本硬件決定。假定一個分布式系統是由像以太網這樣的局域網鎖連接的一群主機組成的。在這個系統中，處理機之間的通信比起本地內存訪問來是不可靠和低速的。假定廣播和組通信是可利用的，大多數總線和環形網絡符合這些假定。（2）為了便于分析性能，通信代價用發送的報文數和包事件數衡量。第十一章第十一章 分布式共享存儲器分布式共享存儲器 162022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算

15、法v 算法使用的模型和環境算法使用的模型和環境 （3）共享存儲器模型為訪問共享數據提供了兩個基本操作： data:=read(address) write(data,address) read返回由address指出的數據項。Write把由地址address指出的內容設置為data。第十一章第十一章 分布式共享存儲器分布式共享存儲器 172022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 算法使用的模型和環境算法使用的模型和環境 根據是否允許遷移或復制，可以將DSM的實現算法分成四類：中央服務員算法、遷移算法、讀復制算法和全復制算法。 非復制 復制 非遷移 中央服務員 全

16、復制 遷移 遷移 讀復制 DSM 的四種算法的四種算法 第十一章第十一章 分布式共享存儲器分布式共享存儲器 182022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 中央服務員算法中央服務員算法 該算法使用一個中央服務員，負責為所有對共享數據的訪問提供服務并保持共享數據唯一的副本。讀和寫操作都包括由執行該操作的進程向中央服務員發送請求 報文，如圖所示。中央服務員執行請求并回答，讀操作時回答，數據項，寫操作時回答一個承認。 顧客 中央服務員 發送數據請求 接收回答 接收請求，執行數據訪問，發送回答 中央服務員 第十一章第十一章 分布式共享存儲器分布式共享存儲器 192022-

17、3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 中央服務員算法中央服務員算法 實現這個算法的通信使用簡單的請求-回答協議。為了可靠性，一個請求如在一定時間內沒有得到回答，則被重新發送。讀請求是冪等的。對于寫請求，服務員必須保持每一個顧客的順序號，從而可以檢驗重復發送和相應地承認它們。若幾次超時都無法回答，則請求失敗。 由于需要為所有顧客的請求服務，中央服務員的一個問題是它可能成為一個瓶頸。為了分配服務員的負載，可把共享數據分配給幾個服務員，在此情況下，顧客應能夠在進行數據訪問時確定正確的服務員。一個顧客可以將它的訪問請求廣播給所有的服務員，由于每個服務員可能為每一個這樣的請求引

18、來一個包事件的開銷，因此，這不能顯著減少所有服務員的負載。一個更好的方法是按地址分割數據，并使用某一簡單變換函數決定和那個服務員接觸。第十一章第十一章 分布式共享存儲器分布式共享存儲器 202022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 遷移算法遷移算法 如圖所示，數據總是被遷移到訪問它的節點。這是一個“單讀者/單寫者”(SRSW)協議，因為在整個系統中，一次只有一個進程讀或寫一個給定的數據項。 顧客 遠程主機 如果數據塊不在本地，則確定位置，發送請求 接收回答，訪問數據 接收請求，發送塊 遷移請求 傳送數據塊 第十一章第十一章 分布式共享存儲器分布式共享存儲器 21

19、2022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 遷移算法遷移算法 典型的數據遷移是在服務員之間以被稱為快形式的固定大小單元而不是單個數據項進行，以使數據管理更容易。這個算法的優點在于當進程訪問本地的數據時，無通信開銷。 如果一個應用程序表現出很強的訪問局部性，數據遷移的代價將因為多次訪問而減少。但是使用這個算法，有可能在 主機之間發生頁顛簸，在遷移之間，幾乎不能對共享內存進行訪問，性能極差。所以應用程序設計時要小心地將數據分配給快，以控制顛簸。 遷移算法第二個好處是，如果快的大小和虛存頁的大小相同，此算法可集成到主機操作系統的虛擬系統中。第十一章第十一章 分布式共享存

20、儲器分布式共享存儲器 222022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 讀復制算法讀復制算法 在上述描述的算法的不足之處是，在任何給定時刻，只有在一臺主機上的各進程能夠訪問同一個快中的開銷。 若允許一個節點對一個指定快的副本進行一個讀/寫或多個節點對該塊的副本進行只讀，則復制可以自然地加入到遷移算法中去。這種復制的類型被稱作多讀者/多寫者復制。 對于一個當前不在本地的塊中的一個數據項進行讀操作時，先與遠程節點通信以獲得那個塊的一個只讀副本，然后再進行讀操作。若被執行寫操作的數據所在的塊不在本地或在本地但主機無寫權時，必須先使此塊在其他節點的所有副本無效，之后再進行寫

21、操作。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 232022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 讀復制算法讀復制算法 顧客 遠程主機 如果數據塊不在本地，則確定位置，發送請求 接收塊，廣播“無效”報文 接收請求，發送塊 接收“無效”報文，使塊無效 遷移請求 傳送數據塊 “無效”報文 “無效”報文 第十一章第十一章 分布式共享存儲器分布式共享存儲器 242022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 全復制算法全復制算法 全復制算法允許數據塊在進行寫時也可以復制，因而它遵從了“多讀者/多寫者”(MRMW)協議。保持復制數據一致性

22、的一種可能的方法是對所有的寫操作進行全局排序，而只對與發生在執行讀操作節點上的寫操作相關的那些讀操作進行排序 。 基于排序的一個簡單策略是,使用一個簡單的全局無間隙排序器，如圖所示，它是一個進程，在DSM的一個主機上執行。當一個主機試圖寫共享存儲器時，把預定的修改送到排序器，排序器給此修改指定一個序號，并將此修改及序號廣播給所有節點。 每個節點按序號的次序處理廣播寫操作。當一個修改到達一個節點時，節點檢查序號是否為下一個。如果在序號的序列中發現不連續的，或者修改信息被丟失、未按序接受，則要重發修改報文。第十一章第十一章 分布式共享存儲器分布式共享存儲器 252022-3-23中南大學軟件學院1

23、1.2 實現實現DSM的算法的算法v 全復制算法全復制算法 排序器 寫 更新 顧客 顧客 排序器 主機 若寫， 則發送數據到排序器 接收承認， 更新本地存儲器 接收數據， 添加序號，廣播 接收數據， 更新本地存儲器 第十一章第十一章 分布式共享存儲器分布式共享存儲器 262022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 算法性能算法性能 以下參數表達了訪問共享數據和應用程序的行為的基本代價:(1) p：一個包事件的代價，即發送或接收一個短包的處理代價，包括可能的任務切換、數據復制及中斷處理開銷。實際系統的典型值的變化范圍是1到幾個毫秒。(2) P：發送或接收一個數據塊的

24、代價。這與p十分相似，但P值要高得多。對于一個通常需要多個包的8K字節的塊來說，典型值的范圍是20至40個毫秒。(3) S：參與分布式共享內存的節點數。(4) r：讀/寫比，即平均有r個讀操作時才有一個寫操作。這個參數也用于整個塊的訪問模式。顯然這兩個比可能不同，但為了簡化分析假定相等。第十一章第十一章 分布式共享存儲器分布式共享存儲器 272022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 算法性能算法性能(5) f：非復制數據塊(用于遷移算法)訪問故障的概率。它等于單一節點連續訪問一個塊(以后由另一個節點訪問此塊導致故障)的平均次數的倒數。它說明遷移算法數據訪問的局部

25、性。(6) f：讀復制算法用于對復制數據塊訪問故障的概率。它是連續訪問本地數據塊中數據項(以后訪問一個非本地數據塊中某數據項)的平均次數的倒數。它說明讀復制算法數據訪問的本地性 f和f對于相應算法的性能有重大影響，但也最難計算，因為它們隨不同應用程序的變化十分大。這些參數不是完全相互獨立的。為了集中研究算法性能的主要特征和簡化分析，作如下的假設：第十一章第十一章 分布式共享存儲器分布式共享存儲器 282022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 算法性能算法性能（1）報文數量不會導致網絡擁塞。（2）服務員擁塞沒有嚴重到能夠極大地延遲遠程進程訪問。（3）訪問本地可利用

26、的數據項的代價和遠程訪問代價相比是微不足道的。（4）報文傳遞假定是可靠地。使用基本參數和以上的簡化假設，四個算法的平均訪問代價可以表示如下： 中央服務員算法：Cc=(1-1/S)4p 遷移算法：Cm=f(2P+4p) 讀復制算法：Crr=f2P+4p+Sp/(r+1) 全復制算法：Cfr=1/(r+1)(S+2)p第十一章第十一章 分布式共享存儲器分布式共享存儲器 292022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 算法性能算法性能 對于中央服務員算法，訪問遠程數據項的概率是（1-1/S），需要4個包事件。只要節點數超過4或5，整體代價Cc則主要由每個包事件代價決定。

27、 對于遷移算法，f表示訪問非本地數據項的概率。 對于讀復制算法，除了在寫故障時(發生概率為1/(r+1)，一個多點廣播無效包必須被所有S個節點接收外，遠程訪問代價接近于遷移算法的訪問代價。 對于全復制算法，遠程訪問的概率等于寫訪問的概率。第十一章第十一章 分布式共享存儲器分布式共享存儲器 302022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 算法比較算法比較 對于這四種算法的性能有如下結論： 中央服務員算法簡單，易于實現，對于不經常訪問共享數據的場合，特別是讀/寫比很低的場合是足夠用的，但非常多的應用程序具有訪問的局部性和高的塊命中率，這使得塊遷移算法和復制算法變得優越

28、。 如果同一塊中的不同數據項由不同節點訪問，則簡單的遷移算法的故障率可能由于交疊訪問而增加，因為它完全沒有利用局部性。全復制算法適合小范圍的復制和不經常地更新。 相反，讀復制算法對于許多應用是一個好的選擇。中央服務器和全復制算法都具有訪問的局部性不敏感的特性，因此，當應用程序訪問的局部性很差時，它們比讀復制算法好。第十一章第十一章 分布式共享存儲器分布式共享存儲器 312022-3-23中南大學軟件學院11.2 實現實現DSM的算法的算法v 算法比較算法比較 移動大數據塊的算法的一個可能的嚴重問題是塊顛簸。對于遷移算法，表現為當兩個或更多的節點進行交疊的數據訪問時，它快速連續地來回移動數據。對

29、于讀復制算法，表現為當塊復制后很快使具有只讀權的塊重復地無效。這些情況表現了很差的節點訪問局部性。對于許多應用程序，可以分配共享數據，把計算分割開以使顛簸變小。由應用程序控制的鎖也可用于抑制顛簸。無論哪種情況，DSM的完全透明性都在某種程度上遭到損害。第十一章第十一章 分布式共享存儲器分布式共享存儲器 322022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 目錄方案的分類目錄方案的分類 目錄：不用廣播的緩存器一致性協議必須保存每塊共享數據的所有緩存器副本的位置。此緩存位置表，不管是集中的還是分散的，都叫做目錄。 每個數據的目錄項包括許多指針，用來指出此塊各副本所在位置。每

30、一個目錄項還有一個“重寫”位用來指明是否允許某一個(只有一個)緩存器進行寫。 目錄協議有三種主要類型：全映像目錄、有限目錄和鏈式目錄 。全映像目錄的每個目錄項保持N個指針，這里N是系統中處理器的個數。有限目錄和全映像目錄的不同之處在于，有限目錄的每個目錄項具有固定數量的指針，與系統中處理機數量無關。鏈式目錄與全映像目錄相似，只是它將目錄分布于各緩存器。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 332022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 全映像目錄全映像目錄 全映像目錄協議使用的目錄每項包含每個處理機，有一個指針并且有一個“重寫”位。指針所對應的每一

31、位代表該塊在相應處理機緩存器中的狀態(存在或不存在)。如果“重寫”位置位，那么有且只有一個處理機的指針位被置位，允許這個處理機對該數據塊進行寫操作。緩存器保存每塊數據的兩個狀態位：一位表明此數據塊是否有效，另一位表明一個有效的數據塊是否可寫。緩存器一致性協議必須在存儲器目錄中保存這些狀態位，并維持緩存一致性。 下圖說明了全映像目錄的三種不同狀態。第一種狀態，單元X不在系統中的任何緩存器中。第二種狀態是三個緩存器都請求單元X的副本。第三種情況，C3請求寫這個數據塊。第十一章第十一章 分布式共享存儲器分布式共享存儲器 342022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 全

32、映像目錄全映像目錄 共享存儲器 C - - - 數據 X： 共享存儲器 C 數據 共享存儲器 D - - 數據 X： X： Cache Cache Cache P1 讀 X P2 讀 X P3 讀 X Cache X： 數據 Cache X： 數據 Cache X： 數據 P1 P2 P3 寫 X Cache Cache Cache X： 數據 P1 P2 P3 第十一章第十一章 分布式共享存儲器分布式共享存儲器 352022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 全映像目錄全映像目錄 寫過程：(1) C3檢測到包含單元X的數據塊是有效的，但是該處理機對數據塊無寫的權

33、限，這由塊的允許寫位表示。(2) C3發出一個對包含單元X的存儲模塊的寫請求，并且停止處理機P3。(3) 存儲器模塊向C1和C2發出無效請求。(4) C1和C2收到無效請求后，設置對應的位指出包含單元X的數據塊是無效的，并向存儲器模塊發回一個承認。(5) 存儲器模塊收到這個承認，將“重寫”位置位，清除指向C1和C2的指針，并向C3發出寫允許報文。(6) C3收到寫允許報文，更新該緩存器中的狀態，并且激活處理機P3。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 362022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 有限目錄有限目錄 有限目錄協議是為解決目錄大小問題

34、而設計的。限制對同一數據塊同時進行緩存的任務數目，即限制一個數據塊的緩存數目，就可以將每個目錄項的大小限定為一個常數。 共享存儲器 C 數據 共享存儲器 D 數據 X： X： Cache X： 數據 Cache X： 數據 Cache P1 P2 P3 讀 X Cache X： 數據 Cache Cache X： 數據 P1 P2 P3 第十一章第十一章 分布式共享存儲器分布式共享存儲器 372022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 鏈式目錄鏈式目錄 它不用廣播機制實現有限目錄的可擴充性，也不限制數據塊的共享副本數，這種緩存器一致性方案叫做鏈式結構是因為它通過保

35、持一個目錄指針鏈對共享副本進行跟蹤。 單向鏈路： 共享存儲器 C 數據 共享存儲器 C 數據 X： X： Cache X： 數據 CT Cache Cache P1 P2 讀 X P3 Cache X： 數據 CT Cache X： 數據 Cache P1 P2 P3 寫 X 第十一章第十一章 分布式共享存儲器分布式共享存儲器 382022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv鏈式目錄鏈式目錄 緩存器塊的替換 ：假設從C1到CN都有單元X的副本，并且單元X和單元Y都直接映射到緩存器同一行上。如果處理機Pi讀單元Y，必須從它的緩存器中先驅逐單元X。在這種情況下，有兩種可

36、能性： (1) 沿著鏈路向Ci-1發送一個報文，將Ci-1的指針指向Ci+1，將Ci從鏈路中脫離開。(2) 使從Ci到CN中的單元X無效。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 392022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv鏈式目錄鏈式目錄 雙向鏈式結構：另外一種解決替換問題的方法是使用雙向鏈。這種方案為每個緩存器副本保持一個向前和一個向后的指針，這樣當緩存器替換時，協議不必遍歷整個鏈。雙向鏈目錄優化替換條件是以更大的平均報文長度(由于傳送更多的目錄指針)、緩存器中的指針的存儲空間加倍和更為復雜的一致性協議為代價的。 盡管鏈式協議比有限目錄協議復雜，

37、但從用于目錄的存儲空間大小來看，仍是可擴充的。指針所占的存儲空間隨處理機的數目的對數增長。每個緩存器存儲塊的指針數目與處理機數目無關。第十一章第十一章 分布式共享存儲器分布式共享存儲器 402022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 只對專用數據進行緩存的方案只對專用數據進行緩存的方案 本章到此為止，已經假定允許存儲器存儲共享變量的本地副本，這樣就導致了緩存器一致性問題。另一種共享存儲器的方法是通過不允許對共享數據進行緩存來避免緩存器一致性問題。這個方案只對專用數據、只讀的共享數據和指令進行緩存，而訪問可修改的共享數據時，不使用緩存器。在實踐中，為了使用這個方案，

38、必須靜態地識別共享變量。第十一章第十一章 分布式共享存儲器分布式共享存儲器 412022-3-23中南大學軟件學院11.3 使用目錄的使用目錄的DSMv 性能比較性能比較 在多處理機系統中，處理機的利用率受存儲器訪問頻繁程度和存儲器系統的等待時間影響。報文通過互聯網絡的等待時間依賴于網絡拓撲和速度、系統中處理機的個數、報文頻率和長度以及存儲器訪問時間。存儲器一致性協議決定了請求率、報文長度及存儲器等待時間。為了計算處理機的利用率，需要用緩存器一致性協議和互聯網絡更具體的模型。 對于大多數應用，同只對專用數據進行緩存的方案相比，全映像目錄方案的處理機利用率要高得多。總的看來，在16和64個處理機

39、的機器中，全映像方案的性能是好的。這表明，即使應用程序不是對使用目錄的緩存器一致性系統專門寫的或編譯的、緩存器對共享數據也是有用的。 有限目錄方案的性能比全映像目錄方案的性能好多少與共享數據的量、對每個存儲單元進行訪問的處理機數和同步方法有關。第十一章第十一章 分布式共享存儲器分布式共享存儲器 422022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v 實現實現DSM的基本方法的基本方法 DSM有三種實現方法，有的系統使用了不止一種方法。(1) 硬件實現。把傳統的高速緩存技術擴展到可擴充的體系結構中。(2) 操作系統和程序庫的實現。通過虛擬存儲器的管理機構達到共享和一致性。(

40、3) 編譯程序的實現。把共享訪問自動轉換成同步和一致性原語。第十一章第十一章 分布式共享存儲器分布式共享存儲器 432022-3-23中南大學軟件學院一部分一部分 DSM 系統的主要實現技術系統的主要實現技術 系統 名稱 當時實現 結構和粒度 一致性語義 一致性協議 改進性能方法 同步支持 異構支持 Dash 硬件，4D/340 工作站，網狀網 16 字節 釋放 寫無效 松弛的一致性，預取 排隊鎖，原子增減 不 Ivy 軟件，Apollo 工作站，Apollo 環 !KB 頁 嚴格 寫無效 指針鏈斷開，可選廣播 同步的頁，信號燈事件計數 不 Linda 軟件， 各種不同的環境 元組 無可變數據

41、 可變 散列法 ？ Memnet 硬件，令牌環 32 字節 嚴格 寫無效 控制流的向量中斷 不 Mermaid 軟件，Sun 工作站，DEC Firefly 多處理機， Mermaid 固有操作系統 8KB(Sun)， 1KB (Firefly) 嚴格 寫無效 信號燈，Signal/wait 報文 是 Mirage 軟件，Vax11/750,Locus 操作系統， UNIX 系統V，以太網 512 字節頁 嚴格 寫無效 內核級實現，時間窗口一致性協議 UNIX 系統 V信號燈 不 Munin 軟件，SUN 工作站UNIX 內核及 Presto并行程序設計環境，以太網 對象 弱 指定類型用于讀為

42、主的協議，延遲寫更新 延遲修改隊列 對象同步 不 Plus 軟件和硬件，Motorola88000，Caltech 網狀網， Plus內核 頁用于共享，字用于一致性 處理器 非請求寫更新 延遲操作 復雜的同步指令 不 Shiva 軟件，InteliPSC/2，超立方體，Shiva 固有操作系統 4KB 頁 嚴格 寫無效 數據結構緊湊，存儲器用作后備存儲 信號燈，Signal/wait 報文 不 第十一章第十一章 分布式共享存儲器分布式共享存儲器 442022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v結構和粒度結構和粒度 Ivy是最早的透明式DSM系統之一，用虛擬存儲器實現

43、了存儲器的共享。 DSM的硬件實現方法典型地支持了較小的粒度。 頁的大小：較大的頁能夠減少分頁的開銷，但是可能引起爭用可能性越大。另一個影響頁大小選擇的因素是必須保留該系統中有關頁的目錄信息：頁越小，則目錄越大。 結構化共享存儲器的一個實現方法是根據數據類型進行共享。這種方法是把共享存儲器作為面向對象的分布式系統中的對象而進行構造。第十一章第十一章 分布式共享存儲器分布式共享存儲器 452022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v 結構和粒度結構和粒度 另一個方法是把共享存儲器構造成像一個數據庫。Linda就是一個這種模式的系統。它把它的共享存儲器安排成為一個相聯存

44、儲器，叫做元組(tuple)空間。第十一章第十一章 分布式共享存儲器分布式共享存儲器 462022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v數據定位和訪問數據定位和訪問 如果數據在系統中不能四處移動，則定位很容易，所有進程很容易地知道在那兒能得到一塊數據。Linda的一些實現是對元組使用散列靜態地分配數據。這種方法具有又快又簡單的特點，但是，如果數據分配不當，則可能產生瓶頸。 另一種方法是允許數據在整個系統中自有遷移。這樣，數據的定位就困難了。這種情況下，數據定位最簡單的辦法是設定一個集中地服務員跟蹤所有共享數據。這種集中的方法有兩個缺陷：服務員串行執行定位查詢，從而削弱

45、了并行性；服務員負載過重，降低了整個系統的速度。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 472022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v數據定位和訪問數據定位和訪問 如果不使用集中地服務員，系統可以廣播數據請求。不幸的是，廣播的可擴充性不好，所有的節點(不僅是數據所在的節點)都必須處理廣播請求。廣播在網絡上的等待有可能使訪問花費很長時間才能完成。 為了避免廣播和更均勻地分配負載，有幾個系統使用了一個基于所有者的分布式的模型。每一塊數據都有一個與之相聯系的所有者，這個所有者就是擁有數據主副本的節點。當數據在整個系統中遷移時，它的所有者也會隨之而改變。當另

46、一個節點需要數據的一個副本時，就向所有者發送請求。所有者如果仍保留著這個數據，就返回該數據；若所有者已將數據發送給其他節點，則把這一請求轉發給那個新所有者。缺點是一個請求可能被轉發多次后才能到達當前所有者。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 482022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v 一致性協議一致性協議 為了提高并行度，所有DSM系統都進行數據復制。但是這樣會使一致性協議復雜化。有兩類協議用來控制復制，即寫無效協議和寫更新協議。 大多數DSM系統都有寫無效一致性協議，在寫無效協議中一塊數據可能有很多個只讀副本，但是，只有一個是可寫副本。這種

47、協議之所以被稱作寫無效協議，是因為在開始一次寫操作之前，除了將被寫的那個副本之外，其他副本均變成無效。在寫更新方式中，一次寫操作將更新所有副本。下圖說明了Dash系統中基于目錄的一致性協議。第十一章第十一章 分布式共享存儲器分布式共享存儲器 492022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現 DC 向請求者發送數據和無效個數， DC 向 B發送無效請求 新目錄塊項： 遠程寫 C中副本 副本無效 CPU 向基地組發出寫命令 寫操作完成 A 組(基地組) B 組 C 組(申請組) (a)數據是遠程共享的 DC向所有者組轉發請求 新目錄塊項： 遠程重寫 B 中副本 DC 向新

48、所有者發送承認 A 組(基地組) CPU 向基地組發出寫請求 寫完成 DC 向請求者發送數據并向基地組發送修改所有權報文 B 組(申請組) C 組(所有者組) (b)數據是遠程重寫的(在(a)中畫出的時間后) Dash系統簡化的寫無效協議系統簡化的寫無效協議(DC代表目錄控制器代表目錄控制器)第十一章第十一章 分布式共享存儲器分布式共享存儲器 502022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現 復制表 X 主本在 A 下一個副本在 B 復制表 X 主本在 A 下一個副本在 B 復制表 X 主本在 A 下一個副本在 NIL MCM 更新 X MCM 將更新報文發送到下一個

49、副本 MCM 將更新報文發送到主節點 MCM 更新 X 并且將更新報文發送到下一個副本 MCM更新X MCM 指出更新完成 頁變換表 X 節點 B 頁 P MCM 向遠程節點 B 發送寫請求 節點 A 節點 B 節點 C Plus寫更新協議，寫更新協議，MCM代表存儲一致性控制器代表存儲一致性控制器第十一章第十一章 分布式共享存儲器分布式共享存儲器 512022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v替換策略替換策略 在允許數據四處遷移的系統中，當共享數據占滿了高速緩沖存儲器的有效空間后，哪些數據將被替換出來以獲得空閑空間，并把它們送到哪里？ 在選擇被替換的數據項時，D

50、SM系統的工作幾乎和共享存儲器的多處理機的高速緩存所做的那些工作一樣，但并不像大多數的高速緩存那樣使用最近最少使用或隨機的替換策略，多數DSM系統區分數據項的狀態并對他們進行優化。 被替換后，系統必須知道它未丟失。有些DSM系統，把數據項傳送到一個基地節點，它有一個靜態分配空間，存放一個系統中別處不需要的數據項副本。一種改進方法是讓想要刪除該數據項的節點把該數據分頁送到磁盤上。第十一章第十一章 分布式共享存儲器分布式共享存儲器 522022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v顛簸顛簸 DSM系統特別容易出現顛簸。如果兩個節點對一個數據項同時進行寫，該數據項就有可能以

51、高速率來來回回地被傳送(乒乓效應)，任何實際工作都做不成 。 Munin系統允許程序員把共享數據和類型聯系起來：寫一次、寫多次、生產者消費者、專用、遷移、結果、常讀、同步及一般的讀/寫。為避免兩個競爭寫者的顛簸，一個程序員可以把類型指定為寫多次，系統將使用延遲寫策略。 Mirage系統在一致性協議中，增加了一個動態可調整參數，它決定一頁在一個節點上保持可用的最小時間量()。例如若一個節點對一個共享頁執行一次寫操作，則此頁在該節點上時間內是可寫的。第十一章第十一章 分布式共享存儲器分布式共享存儲器 532022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v 可擴充性可擴充性 D

52、SM系統一個理論上的優點是它們比緊密耦合系統具有更好的可擴充性。前面說過，對可擴充性限制有兩種因素：集中瓶頸(例如緊密耦合系統中的總線)和全局公用信息的操作及存儲(例如廣播報文或目錄，它的大小與節點數成比例)。第十一章第十一章 分布式共享存儲器分布式共享存儲器 542022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v異構性異構性 在Agora系統中，把存儲器構造為在異構性機器之間共享對象。 Mermaid探索了另一種不同尋常的方法：存儲器以頁方式共享，并且一頁只包含一種數據類型。當在不同體系結構的兩個系統之間移動一頁時，變換子程序都會把該頁上的數據轉換成適當的格式。 第十一

53、章第十一章 分布式共享存儲器分布式共享存儲器 552022-3-23中南大學軟件學院11.4 DSM系統的實現系統的實現v 其他有關算法其他有關算法 為了支持DSM算法，必須對同步操作和存儲管理進行調整。例如，信號量是在共享存儲器系統上使用旋轉鎖實現的。 可為DSM重新構造存儲管理。一個常用的存儲器分配方案對公用庫的存儲器進行分配，每次請求時要搜索一次該庫。第十一章第十一章 分布式共享存儲器分布式共享存儲器 562022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetv Ivy軟件實現的軟件實現的DSM Ivy中進程地址空間分成專用和共享兩部分。專用部分不能由其他進

54、程尋址。共享部分由虛擬共享存儲器實現，是個平面地址空間，為運行在不同節點上的所有進程所共享，也就是被各線程共享的單地址空間。 地址空間是分頁的。一頁是同步的最小單位，當需要時它可以從一個節點遷移到另一個節點。每個節點上有一個存儲器管理程序，滿足本地和遠程請求并實現緩存器一致性協議。當訪問共享空間的一個地址時，阻塞故障進程，Ivy存儲器管理程序檢查待訪問頁是否在本地。如果不在本地，向遠程存儲器發送請求。得到該頁后，發生頁故障的進程恢復執行。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 572022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetv Ivy一致性

55、協議一致性協議 Ivy所使用的一致性概念是多個讀/單個寫的語義。對某地址的讀操作總是得到最近對該地址寫的值，一致性協議保證執行這一語義。 Ivy的每個處理機都有自己的頁表。表中的每一項紀錄著該主機的訪問權，可以對一頁擁有讀、寫權或無任何權利。一頁的訪問權是與緩存器中一個塊的狀態相當的。 緩存器 Ivy 重寫 共享重寫 有效 無效 寫 所有者讀 讀 無任何權力 第十一章第十一章 分布式共享存儲器分布式共享存儲器 582022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetv Ivy一致性協議一致性協議 當訪問一個共享地址時，該主機檢查它是否有權在指定方式下訪問含有此地

56、址的那一頁。如果沒有，則根據訪問方式產生一個讀或者寫故障，其步驟如下： 讀故障：(1) 找出誰是所有者；(2) 所有者把該故障主機填入副本集；(3) 所有者把自己的訪問權變成只讀；(4) 所有者向故障主機發送該頁。第十一章第十一章 分布式共享存儲器分布式共享存儲器 592022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetv Ivy一致性協議一致性協議 當訪問一個共享地址時，該主機檢查它是否有權在指定方式下訪問含有此地址的那一頁。如果沒有，則根據訪問方式產生一個讀或者寫故障，其步驟如下： 寫故障：(1) 找到所有者；(2) 所有者向故障主機發送該頁和該頁的副本集，

57、并將它的那項標為無效；(3) 故障主機根據副本集送出“無效”報文；(4) 返回對“無效”報文的承認，進程繼續執行第十一章第十一章 分布式共享存儲器分布式共享存儲器 602022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetvIvy一致性協議一致性協議 有三種不同的一致性協議 ：1） 集中管理者方法類似于管程，管程由一個數據結構和一些過程組成，提供對數據結構的互斥訪問。集中管理者固定在一個處理機上，維持一張頁表。每個處理機也有一張頁表，每一項有兩個域：訪問和鎖。訪問域記錄本地處理機上的頁面的可訪問信息。每個處理機知道中心管理者，并且在本地沒有數據對象時能夠向管理者發

58、出請求。當一個處理機上有多個進程等待同一個頁面時，加鎖機制防止處理機發出多個請求。對一個頁面成功執行寫操作就會成為頁面的所有者第十一章第十一章 分布式共享存儲器分布式共享存儲器 612022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetv Ivy一致性協議一致性協議 2） 有兩種類型的固定分布式管理者算法：固定的和廣播的。固定算法中，每個處理機預定管理一部分頁面。通常一個適當的散列函數用于把頁面映射到處理機。廣播算法中，訪問頁面出故障的處理機發出廣播確定頁面的真正所有者。廣播算法性能比較差，因為所有處理機必須處理每個請求，減慢處理機的計算第十一章第十一章 分布式共

59、享存儲器分布式共享存儲器 622022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetv Ivy一致性協議一致性協議 3） 動態分布式管理者方法的核心是每個處理機的頁表中記錄所有頁的所有者。頁表中，集中管理者算法中的所有者域被替換成另一個域，叫做可能所有者(probowner)域，它可能是頁面的真正所有者，也可能是頁面的可能所有者。可能所有者域構成一個鏈，從一個節點到另一個節點，最終會指向真正的所有者。第十一章第十一章 分布式共享存儲器分布式共享存儲器 632022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetvIvy存儲器管理存儲器管理 虛擬共享存儲器的管理與常規存儲器管理有很大不同，下面介紹頁替換和存儲器分配。 頁替換。 Ivy的虛擬共享存儲器的頁有五種：可寫的、所有者可讀的、只讀的、空的和不使用的。空頁和不用頁都具有最高的被替換優先權，即如果需要一頁則先替換它們。由于只讀頁可被其所有者制造備份，所以可以簡單地丟棄。對于所有者讀的頁和可寫頁的丟棄當然需要所有權的轉讓。 第十一章第十一章 分布式共享存儲器分布式共享存儲器 642022-3-23中南大學軟件學院11.5 DSM實例：實例：Ivy和和MemNetvIvy存儲器管理存儲