Chapter分布式共享存儲(chǔ)器

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

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

3、布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 42022-3-23中南大學(xué)軟件學(xué)院11.1 基本概念基本概念v 為什么需要分布式共享存儲(chǔ)器為什么需要分布式共享存儲(chǔ)器 松散耦合分布式系統(tǒng)中的計(jì)算機(jī)如果沒(méi)有分布式共享存儲(chǔ)器，為了使這些計(jì)算機(jī)合作完成一個(gè)共同的任務(wù)，就必須共享狀態(tài)。共享狀態(tài)有兩種方式，第一種是使用報(bào)文傳遞原語(yǔ)顯示地移動(dòng)數(shù)據(jù)。第二種是，共享數(shù)據(jù)在一個(gè)專(zhuān)用進(jìn)程中實(shí)現(xiàn)，其他進(jìn)程向此進(jìn)程發(fā)送事先規(guī)定的操作，然后由此進(jìn)程對(duì)該數(shù)據(jù)執(zhí)行所需的操作，這就是遠(yuǎn)程過(guò)程調(diào)用(RPC)的方法。 報(bào)文傳遞方式中，數(shù)據(jù)在程序之間移來(lái)移去極大地增加了應(yīng)用程序設(shè)計(jì)者的負(fù)擔(dān)。RPC的顧客和服務(wù)員也是在分隔的地址空間執(zhí)行的，顧客用數(shù)

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

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

6、M系統(tǒng)具有以下特點(diǎn)：(1) 規(guī)?？蓴U(kuò)充。 (2) 廉價(jià)。(3) 兼容性。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 82022-3-23中南大學(xué)軟件學(xué)院11.1 基本概念基本概念v 共享存儲(chǔ)器中緩存一致性方法共享存儲(chǔ)器中緩存一致性方法 有兩類(lèi)基本方法實(shí)現(xiàn)緩存一致性：即探聽(tīng)緩存方法和使用目錄的方法。 探聽(tīng)(snooping)緩存方法用于具有廣播能力的通信介質(zhì)中，例如共享總線。每個(gè)緩存器為了保持自己數(shù)據(jù)的一致性要監(jiān)聽(tīng)共享總線上進(jìn)行的由其他處理機(jī)發(fā)出的存儲(chǔ)器操作。Berkeley是一個(gè)典型例子，它是一種寫(xiě)無(wú)效協(xié)議，它假設(shè)通過(guò)單總線訪問(wèn)共享的物理存儲(chǔ)器。此協(xié)議采用一個(gè)所有權(quán)方案。一個(gè)數(shù)據(jù)塊的所

7、有者是一個(gè)緩存器，是上次對(duì)該數(shù)據(jù)塊的修改者，如果該塊被其所有者清除，則主存作為其所有者。 探聽(tīng)緩存方法支持的系統(tǒng)規(guī)模有限，因?yàn)樗偸且蕾囉诠蚕砜偩€，而且，由于在總線上監(jiān)聽(tīng)存儲(chǔ)器每個(gè)操作時(shí)要對(duì)緩存器進(jìn)行檢查，處理機(jī)與其緩存器之間的正常通信會(huì)產(chǎn)生延遲。可以使用目錄解決這個(gè)問(wèn)題。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 92022-3-23中南大學(xué)軟件學(xué)院11.1 基本概念基本概念v 共享存儲(chǔ)器中緩存一致性方法共享存儲(chǔ)器中緩存一致性方法 使用目錄即在共享存儲(chǔ)器中設(shè)置存儲(chǔ)器塊的目錄。當(dāng)發(fā)生緩存不命中時(shí)，先把請(qǐng)求轉(zhuǎn)到此目錄。通常目錄項(xiàng)中包含所有權(quán)、副本集(copyset)和該塊的重寫(xiě)位。副本集

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

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

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

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

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

13、進(jìn)程對(duì)同一個(gè)數(shù)據(jù)項(xiàng)的寫(xiě)操作，應(yīng)該被所有進(jìn)程以相同的順序看見(jiàn)。 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 142022-3-23中南大學(xué)軟件學(xué)院11.1 基本概念基本概念v 一致性語(yǔ)義一致性語(yǔ)義 （4）弱一致性。程序員使用同步算符，使得對(duì)數(shù)據(jù)的多個(gè)操作組來(lái)說(shuō)是順序一致性的。即不同進(jìn)程的多個(gè)操作組可以認(rèn)為是按照某個(gè)順序進(jìn)行的，任何進(jìn)程對(duì)這個(gè)順序的觀點(diǎn)是一樣的。但是操作組內(nèi)的多個(gè)操作其他進(jìn)程是不可見(jiàn)的。對(duì)同步算符是順序一致性的。 （5）釋放一致性。使用了“獲得”和“釋放”這兩類(lèi)同步算符，對(duì)同步算符是處理機(jī)一致的。 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 152022-3-23中

14、南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算法 v 算法使用的模型和環(huán)境算法使用的模型和環(huán)境 （1）首先，要對(duì)實(shí)現(xiàn)算法所需環(huán)境作些假定總的說(shuō)來(lái)，分布式和并行應(yīng)用程序的性能主要由通行代價(jià)決定，而通行代價(jià)由基本硬件決定。假定一個(gè)分布式系統(tǒng)是由像以太網(wǎng)這樣的局域網(wǎng)鎖連接的一群主機(jī)組成的。在這個(gè)系統(tǒng)中，處理機(jī)之間的通信比起本地內(nèi)存訪問(wèn)來(lái)是不可靠和低速的。假定廣播和組通信是可利用的，大多數(shù)總線和環(huán)形網(wǎng)絡(luò)符合這些假定。（2）為了便于分析性能，通信代價(jià)用發(fā)送的報(bào)文數(shù)和包事件數(shù)衡量。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 162022-3-23中南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算

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

16、復(fù)制 遷移 遷移 讀復(fù)制 DSM 的四種算法的四種算法 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 182022-3-23中南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算法v 中央服務(wù)員算法中央服務(wù)員算法 該算法使用一個(gè)中央服務(wù)員，負(fù)責(zé)為所有對(duì)共享數(shù)據(jù)的訪問(wèn)提供服務(wù)并保持共享數(shù)據(jù)唯一的副本。讀和寫(xiě)操作都包括由執(zhí)行該操作的進(jìn)程向中央服務(wù)員發(fā)送請(qǐng)求 報(bào)文，如圖所示。中央服務(wù)員執(zhí)行請(qǐng)求并回答，讀操作時(shí)回答，數(shù)據(jù)項(xiàng)，寫(xiě)操作時(shí)回答一個(gè)承認(rèn)。 顧客 中央服務(wù)員 發(fā)送數(shù)據(jù)請(qǐng)求 接收回答 接收請(qǐng)求，執(zhí)行數(shù)據(jù)訪問(wèn)，發(fā)送回答 中央服務(wù)員 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 192022-

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

18、來(lái)一個(gè)包事件的開(kāi)銷(xiāo)，因此，這不能顯著減少所有服務(wù)員的負(fù)載。一個(gè)更好的方法是按地址分割數(shù)據(jù)，并使用某一簡(jiǎn)單變換函數(shù)決定和那個(gè)服務(wù)員接觸。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 202022-3-23中南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算法v 遷移算法遷移算法 如圖所示，數(shù)據(jù)總是被遷移到訪問(wèn)它的節(jié)點(diǎn)。這是一個(gè)“單讀者/單寫(xiě)者”(SRSW)協(xié)議，因?yàn)樵谡麄€(gè)系統(tǒng)中，一次只有一個(gè)進(jìn)程讀或?qū)懸粋€(gè)給定的數(shù)據(jù)項(xiàng)。 顧客 遠(yuǎn)程主機(jī) 如果數(shù)據(jù)塊不在本地，則確定位置，發(fā)送請(qǐng)求 接收回答，訪問(wèn)數(shù)據(jù) 接收請(qǐng)求，發(fā)送塊 遷移請(qǐng)求 傳送數(shù)據(jù)塊 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 21

19、2022-3-23中南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算法v 遷移算法遷移算法 典型的數(shù)據(jù)遷移是在服務(wù)員之間以被稱為快形式的固定大小單元而不是單個(gè)數(shù)據(jù)項(xiàng)進(jìn)行，以使數(shù)據(jù)管理更容易。這個(gè)算法的優(yōu)點(diǎn)在于當(dāng)進(jìn)程訪問(wèn)本地的數(shù)據(jù)時(shí)，無(wú)通信開(kāi)銷(xiāo)。 如果一個(gè)應(yīng)用程序表現(xiàn)出很強(qiáng)的訪問(wèn)局部性，數(shù)據(jù)遷移的代價(jià)將因?yàn)槎啻卧L問(wèn)而減少。但是使用這個(gè)算法，有可能在 主機(jī)之間發(fā)生頁(yè)顛簸，在遷移之間，幾乎不能對(duì)共享內(nèi)存進(jìn)行訪問(wèn)，性能極差。所以應(yīng)用程序設(shè)計(jì)時(shí)要小心地將數(shù)據(jù)分配給快，以控制顛簸。 遷移算法第二個(gè)好處是，如果快的大小和虛存頁(yè)的大小相同，此算法可集成到主機(jī)操作系統(tǒng)的虛擬系統(tǒng)中。第十一章第十一章 分布式共享存

20、儲(chǔ)器分布式共享存儲(chǔ)器 222022-3-23中南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算法v 讀復(fù)制算法讀復(fù)制算法 在上述描述的算法的不足之處是，在任何給定時(shí)刻，只有在一臺(tái)主機(jī)上的各進(jìn)程能夠訪問(wèn)同一個(gè)快中的開(kāi)銷(xiāo)。 若允許一個(gè)節(jié)點(diǎn)對(duì)一個(gè)指定快的副本進(jìn)行一個(gè)讀/寫(xiě)或多個(gè)節(jié)點(diǎn)對(duì)該塊的副本進(jìn)行只讀，則復(fù)制可以自然地加入到遷移算法中去。這種復(fù)制的類(lèi)型被稱作多讀者/多寫(xiě)者復(fù)制。 對(duì)于一個(gè)當(dāng)前不在本地的塊中的一個(gè)數(shù)據(jù)項(xiàng)進(jìn)行讀操作時(shí)，先與遠(yuǎn)程節(jié)點(diǎn)通信以獲得那個(gè)塊的一個(gè)只讀副本，然后再進(jìn)行讀操作。若被執(zhí)行寫(xiě)操作的數(shù)據(jù)所在的塊不在本地或在本地但主機(jī)無(wú)寫(xiě)權(quán)時(shí)，必須先使此塊在其他節(jié)點(diǎn)的所有副本無(wú)效，之后再進(jìn)行寫(xiě)

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

22、的一種可能的方法是對(duì)所有的寫(xiě)操作進(jìn)行全局排序，而只對(duì)與發(fā)生在執(zhí)行讀操作節(jié)點(diǎn)上的寫(xiě)操作相關(guān)的那些讀操作進(jìn)行排序 。 基于排序的一個(gè)簡(jiǎn)單策略是,使用一個(gè)簡(jiǎn)單的全局無(wú)間隙排序器，如圖所示，它是一個(gè)進(jìn)程，在DSM的一個(gè)主機(jī)上執(zhí)行。當(dāng)一個(gè)主機(jī)試圖寫(xiě)共享存儲(chǔ)器時(shí)，把預(yù)定的修改送到排序器，排序器給此修改指定一個(gè)序號(hào)，并將此修改及序號(hào)廣播給所有節(jié)點(diǎn)。 每個(gè)節(jié)點(diǎn)按序號(hào)的次序處理廣播寫(xiě)操作。當(dāng)一個(gè)修改到達(dá)一個(gè)節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)檢查序號(hào)是否為下一個(gè)。如果在序號(hào)的序列中發(fā)現(xiàn)不連續(xù)的，或者修改信息被丟失、未按序接受，則要重發(fā)修改報(bào)文。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 252022-3-23中南大學(xué)軟件學(xué)院1

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

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

25、性。(6) f：讀復(fù)制算法用于對(duì)復(fù)制數(shù)據(jù)塊訪問(wèn)故障的概率。它是連續(xù)訪問(wèn)本地?cái)?shù)據(jù)塊中數(shù)據(jù)項(xiàng)(以后訪問(wèn)一個(gè)非本地?cái)?shù)據(jù)塊中某數(shù)據(jù)項(xiàng))的平均次數(shù)的倒數(shù)。它說(shuō)明讀復(fù)制算法數(shù)據(jù)訪問(wèn)的本地性 f和f對(duì)于相應(yīng)算法的性能有重大影響，但也最難計(jì)算，因?yàn)樗鼈冸S不同應(yīng)用程序的變化十分大。這些參數(shù)不是完全相互獨(dú)立的。為了集中研究算法性能的主要特征和簡(jiǎn)化分析，作如下的假設(shè)：第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 282022-3-23中南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算法v 算法性能算法性能（1）報(bào)文數(shù)量不會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞。（2）服務(wù)員擁塞沒(méi)有嚴(yán)重到能夠極大地延遲遠(yuǎn)程進(jìn)程訪問(wèn)。（3）訪問(wèn)本地可利用

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

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

28、。 如果同一塊中的不同數(shù)據(jù)項(xiàng)由不同節(jié)點(diǎn)訪問(wèn)，則簡(jiǎn)單的遷移算法的故障率可能由于交疊訪問(wèn)而增加，因?yàn)樗耆珱](méi)有利用局部性。全復(fù)制算法適合小范圍的復(fù)制和不經(jīng)常地更新。 相反，讀復(fù)制算法對(duì)于許多應(yīng)用是一個(gè)好的選擇。中央服務(wù)器和全復(fù)制算法都具有訪問(wèn)的局部性不敏感的特性，因此，當(dāng)應(yīng)用程序訪問(wèn)的局部性很差時(shí)，它們比讀復(fù)制算法好。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 312022-3-23中南大學(xué)軟件學(xué)院11.2 實(shí)現(xiàn)實(shí)現(xiàn)DSM的算法的算法v 算法比較算法比較 移動(dòng)大數(shù)據(jù)塊的算法的一個(gè)可能的嚴(yán)重問(wèn)題是塊顛簸。對(duì)于遷移算法，表現(xiàn)為當(dāng)兩個(gè)或更多的節(jié)點(diǎn)進(jìn)行交疊的數(shù)據(jù)訪問(wèn)時(shí)，它快速連續(xù)地來(lái)回移動(dòng)數(shù)據(jù)。對(duì)

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

30、一個(gè)目錄項(xiàng)還有一個(gè)“重寫(xiě)”位用來(lái)指明是否允許某一個(gè)(只有一個(gè))緩存器進(jìn)行寫(xiě)。 目錄協(xié)議有三種主要類(lèi)型：全映像目錄、有限目錄和鏈?zhǔn)侥夸?。全映像目錄的每個(gè)目錄項(xiàng)保持N個(gè)指針，這里N是系統(tǒng)中處理器的個(gè)數(shù)。有限目錄和全映像目錄的不同之處在于，有限目錄的每個(gè)目錄項(xiàng)具有固定數(shù)量的指針，與系統(tǒng)中處理機(jī)數(shù)量無(wú)關(guān)。鏈?zhǔn)侥夸浥c全映像目錄相似，只是它將目錄分布于各緩存器。 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 332022-3-23中南大學(xué)軟件學(xué)院11.3 使用目錄的使用目錄的DSMv 全映像目錄全映像目錄 全映像目錄協(xié)議使用的目錄每項(xiàng)包含每個(gè)處理機(jī)，有一個(gè)指針并且有一個(gè)“重寫(xiě)”位。指針?biāo)鶎?duì)應(yīng)的每一

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

32、映像目錄全映像目錄 共享存儲(chǔ)器 C - - - 數(shù)據(jù) X： 共享存儲(chǔ)器 C 數(shù)據(jù) 共享存儲(chǔ)器 D - - 數(shù)據(jù) X： X： Cache Cache Cache P1 讀 X P2 讀 X P3 讀 X Cache X： 數(shù)據(jù) Cache X： 數(shù)據(jù) Cache X： 數(shù)據(jù) P1 P2 P3 寫(xiě) X Cache Cache Cache X： 數(shù)據(jù) P1 P2 P3 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 352022-3-23中南大學(xué)軟件學(xué)院11.3 使用目錄的使用目錄的DSMv 全映像目錄全映像目錄 寫(xiě)過(guò)程：(1) C3檢測(cè)到包含單元X的數(shù)據(jù)塊是有效的，但是該處理機(jī)對(duì)數(shù)據(jù)塊無(wú)寫(xiě)的權(quán)

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

34、而設(shè)計(jì)的。限制對(duì)同一數(shù)據(jù)塊同時(shí)進(jìn)行緩存的任務(wù)數(shù)目，即限制一個(gè)數(shù)據(jù)塊的緩存數(shù)目，就可以將每個(gè)目錄項(xiàng)的大小限定為一個(gè)常數(shù)。 共享存儲(chǔ)器 C 數(shù)據(jù) 共享存儲(chǔ)器 D 數(shù)據(jù) X： X： Cache X： 數(shù)據(jù) Cache X： 數(shù)據(jù) Cache P1 P2 P3 讀 X Cache X： 數(shù)據(jù) Cache Cache X： 數(shù)據(jù) P1 P2 P3 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 372022-3-23中南大學(xué)軟件學(xué)院11.3 使用目錄的使用目錄的DSMv 鏈?zhǔn)侥夸涙準(zhǔn)侥夸?它不用廣播機(jī)制實(shí)現(xiàn)有限目錄的可擴(kuò)充性，也不限制數(shù)據(jù)塊的共享副本數(shù)，這種緩存器一致性方案叫做鏈?zhǔn)浇Y(jié)構(gòu)是因?yàn)樗ㄟ^(guò)保

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

36、能性： (1) 沿著鏈路向Ci-1發(fā)送一個(gè)報(bào)文，將Ci-1的指針指向Ci+1，將Ci從鏈路中脫離開(kāi)。(2) 使從Ci到CN中的單元X無(wú)效。 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 392022-3-23中南大學(xué)軟件學(xué)院11.3 使用目錄的使用目錄的DSMv鏈?zhǔn)侥夸涙準(zhǔn)侥夸?雙向鏈?zhǔn)浇Y(jié)構(gòu)：另外一種解決替換問(wèn)題的方法是使用雙向鏈。這種方案為每個(gè)緩存器副本保持一個(gè)向前和一個(gè)向后的指針，這樣當(dāng)緩存器替換時(shí)，協(xié)議不必遍歷整個(gè)鏈。雙向鏈目錄優(yōu)化替換條件是以更大的平均報(bào)文長(zhǎng)度(由于傳送更多的目錄指針)、緩存器中的指針的存儲(chǔ)空間加倍和更為復(fù)雜的一致性協(xié)議為代價(jià)的。 盡管鏈?zhǔn)絽f(xié)議比有限目錄協(xié)議復(fù)雜，

37、但從用于目錄的存儲(chǔ)空間大小來(lái)看，仍是可擴(kuò)充的。指針?biāo)嫉拇鎯?chǔ)空間隨處理機(jī)的數(shù)目的對(duì)數(shù)增長(zhǎng)。每個(gè)緩存器存儲(chǔ)塊的指針數(shù)目與處理機(jī)數(shù)目無(wú)關(guān)。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 402022-3-23中南大學(xué)軟件學(xué)院11.3 使用目錄的使用目錄的DSMv 只對(duì)專(zhuān)用數(shù)據(jù)進(jìn)行緩存的方案只對(duì)專(zhuān)用數(shù)據(jù)進(jìn)行緩存的方案 本章到此為止，已經(jīng)假定允許存儲(chǔ)器存儲(chǔ)共享變量的本地副本，這樣就導(dǎo)致了緩存器一致性問(wèn)題。另一種共享存儲(chǔ)器的方法是通過(guò)不允許對(duì)共享數(shù)據(jù)進(jìn)行緩存來(lái)避免緩存器一致性問(wèn)題。這個(gè)方案只對(duì)專(zhuān)用數(shù)據(jù)、只讀的共享數(shù)據(jù)和指令進(jìn)行緩存，而訪問(wèn)可修改的共享數(shù)據(jù)時(shí)，不使用緩存器。在實(shí)踐中，為了使用這個(gè)方案，

38、必須靜態(tài)地識(shí)別共享變量。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 412022-3-23中南大學(xué)軟件學(xué)院11.3 使用目錄的使用目錄的DSMv 性能比較性能比較 在多處理機(jī)系統(tǒng)中，處理機(jī)的利用率受存儲(chǔ)器訪問(wèn)頻繁程度和存儲(chǔ)器系統(tǒng)的等待時(shí)間影響。報(bào)文通過(guò)互聯(lián)網(wǎng)絡(luò)的等待時(shí)間依賴于網(wǎng)絡(luò)拓?fù)浜退俣?、系統(tǒng)中處理機(jī)的個(gè)數(shù)、報(bào)文頻率和長(zhǎng)度以及存儲(chǔ)器訪問(wèn)時(shí)間。存儲(chǔ)器一致性協(xié)議決定了請(qǐng)求率、報(bào)文長(zhǎng)度及存儲(chǔ)器等待時(shí)間。為了計(jì)算處理機(jī)的利用率，需要用緩存器一致性協(xié)議和互聯(lián)網(wǎng)絡(luò)更具體的模型。 對(duì)于大多數(shù)應(yīng)用，同只對(duì)專(zhuān)用數(shù)據(jù)進(jìn)行緩存的方案相比，全映像目錄方案的處理機(jī)利用率要高得多?？偟目磥?lái)，在16和64個(gè)處理機(jī)

39、的機(jī)器中，全映像方案的性能是好的。這表明，即使應(yīng)用程序不是對(duì)使用目錄的緩存器一致性系統(tǒng)專(zhuān)門(mén)寫(xiě)的或編譯的、緩存器對(duì)共享數(shù)據(jù)也是有用的。 有限目錄方案的性能比全映像目錄方案的性能好多少與共享數(shù)據(jù)的量、對(duì)每個(gè)存儲(chǔ)單元進(jìn)行訪問(wèn)的處理機(jī)數(shù)和同步方法有關(guān)。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 422022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v 實(shí)現(xiàn)實(shí)現(xiàn)DSM的基本方法的基本方法 DSM有三種實(shí)現(xiàn)方法，有的系統(tǒng)使用了不止一種方法。(1) 硬件實(shí)現(xiàn)。把傳統(tǒng)的高速緩存技術(shù)擴(kuò)展到可擴(kuò)充的體系結(jié)構(gòu)中。(2) 操作系統(tǒng)和程序庫(kù)的實(shí)現(xiàn)。通過(guò)虛擬存儲(chǔ)器的管理機(jī)構(gòu)達(dá)到共享和一致性。(

40、3) 編譯程序的實(shí)現(xiàn)。把共享訪問(wèn)自動(dòng)轉(zhuǎn)換成同步和一致性原語(yǔ)。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 432022-3-23中南大學(xué)軟件學(xué)院一部分一部分 DSM 系統(tǒng)的主要實(shí)現(xiàn)技術(shù)系統(tǒng)的主要實(shí)現(xiàn)技術(shù) 系統(tǒng) 名稱 當(dāng)時(shí)實(shí)現(xiàn) 結(jié)構(gòu)和粒度 一致性語(yǔ)義 一致性協(xié)議 改進(jìn)性能方法 同步支持 異構(gòu)支持 Dash 硬件，4D/340 工作站，網(wǎng)狀網(wǎng) 16 字節(jié) 釋放 寫(xiě)無(wú)效 松弛的一致性，預(yù)取 排隊(duì)鎖，原子增減 不 Ivy 軟件，Apollo 工作站，Apollo 環(huán) !KB 頁(yè) 嚴(yán)格 寫(xiě)無(wú)效 指針鏈斷開(kāi)，可選廣播 同步的頁(yè)，信號(hào)燈事件計(jì)數(shù) 不 Linda 軟件， 各種不同的環(huán)境 元組 無(wú)可變數(shù)據(jù)

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

42、主的協(xié)議，延遲寫(xiě)更新 延遲修改隊(duì)列 對(duì)象同步 不 Plus 軟件和硬件，Motorola88000，Caltech 網(wǎng)狀網(wǎng)， Plus內(nèi)核 頁(yè)用于共享，字用于一致性 處理器 非請(qǐng)求寫(xiě)更新 延遲操作 復(fù)雜的同步指令 不 Shiva 軟件，InteliPSC/2，超立方體，Shiva 固有操作系統(tǒng) 4KB 頁(yè) 嚴(yán)格 寫(xiě)無(wú)效 數(shù)據(jù)結(jié)構(gòu)緊湊，存儲(chǔ)器用作后備存儲(chǔ) 信號(hào)燈，Signal/wait 報(bào)文 不 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 442022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v結(jié)構(gòu)和粒度結(jié)構(gòu)和粒度 Ivy是最早的透明式DSM系統(tǒng)之一，用虛擬存儲(chǔ)器實(shí)現(xiàn)

43、了存儲(chǔ)器的共享。 DSM的硬件實(shí)現(xiàn)方法典型地支持了較小的粒度。 頁(yè)的大?。狠^大的頁(yè)能夠減少分頁(yè)的開(kāi)銷(xiāo)，但是可能引起爭(zhēng)用可能性越大。另一個(gè)影響頁(yè)大小選擇的因素是必須保留該系統(tǒng)中有關(guān)頁(yè)的目錄信息：頁(yè)越小，則目錄越大。 結(jié)構(gòu)化共享存儲(chǔ)器的一個(gè)實(shí)現(xiàn)方法是根據(jù)數(shù)據(jù)類(lèi)型進(jìn)行共享。這種方法是把共享存儲(chǔ)器作為面向?qū)ο蟮姆植际较到y(tǒng)中的對(duì)象而進(jìn)行構(gòu)造。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 452022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v 結(jié)構(gòu)和粒度結(jié)構(gòu)和粒度 另一個(gè)方法是把共享存儲(chǔ)器構(gòu)造成像一個(gè)數(shù)據(jù)庫(kù)。Linda就是一個(gè)這種模式的系統(tǒng)。它把它的共享存儲(chǔ)器安排成為一個(gè)相聯(lián)存

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

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

46、一個(gè)節(jié)點(diǎn)需要數(shù)據(jù)的一個(gè)副本時(shí)，就向所有者發(fā)送請(qǐng)求。所有者如果仍保留著這個(gè)數(shù)據(jù)，就返回該數(shù)據(jù)；若所有者已將數(shù)據(jù)發(fā)送給其他節(jié)點(diǎn)，則把這一請(qǐng)求轉(zhuǎn)發(fā)給那個(gè)新所有者。缺點(diǎn)是一個(gè)請(qǐng)求可能被轉(zhuǎn)發(fā)多次后才能到達(dá)當(dāng)前所有者。 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 482022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v 一致性協(xié)議一致性協(xié)議 為了提高并行度，所有DSM系統(tǒng)都進(jìn)行數(shù)據(jù)復(fù)制。但是這樣會(huì)使一致性協(xié)議復(fù)雜化。有兩類(lèi)協(xié)議用來(lái)控制復(fù)制，即寫(xiě)無(wú)效協(xié)議和寫(xiě)更新協(xié)議。 大多數(shù)DSM系統(tǒng)都有寫(xiě)無(wú)效一致性協(xié)議，在寫(xiě)無(wú)效協(xié)議中一塊數(shù)據(jù)可能有很多個(gè)只讀副本，但是，只有一個(gè)是可寫(xiě)副本。這種

47、協(xié)議之所以被稱作寫(xiě)無(wú)效協(xié)議，是因?yàn)樵陂_(kāi)始一次寫(xiě)操作之前，除了將被寫(xiě)的那個(gè)副本之外，其他副本均變成無(wú)效。在寫(xiě)更新方式中，一次寫(xiě)操作將更新所有副本。下圖說(shuō)明了Dash系統(tǒng)中基于目錄的一致性協(xié)議。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 492022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn) DC 向請(qǐng)求者發(fā)送數(shù)據(jù)和無(wú)效個(gè)數(shù)， DC 向 B發(fā)送無(wú)效請(qǐng)求 新目錄塊項(xiàng)： 遠(yuǎn)程寫(xiě) C中副本 副本無(wú)效 CPU 向基地組發(fā)出寫(xiě)命令 寫(xiě)操作完成 A 組(基地組) B 組 C 組(申請(qǐng)組) (a)數(shù)據(jù)是遠(yuǎn)程共享的 DC向所有者組轉(zhuǎn)發(fā)請(qǐng)求 新目錄塊項(xiàng)： 遠(yuǎn)程重寫(xiě) B 中副本 DC 向新

48、所有者發(fā)送承認(rèn) A 組(基地組) CPU 向基地組發(fā)出寫(xiě)請(qǐng)求 寫(xiě)完成 DC 向請(qǐng)求者發(fā)送數(shù)據(jù)并向基地組發(fā)送修改所有權(quán)報(bào)文 B 組(申請(qǐng)組) C 組(所有者組) (b)數(shù)據(jù)是遠(yuǎn)程重寫(xiě)的(在(a)中畫(huà)出的時(shí)間后) Dash系統(tǒng)簡(jiǎn)化的寫(xiě)無(wú)效協(xié)議系統(tǒng)簡(jiǎn)化的寫(xiě)無(wú)效協(xié)議(DC代表目錄控制器代表目錄控制器)第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 502022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn) 復(fù)制表 X 主本在 A 下一個(gè)副本在 B 復(fù)制表 X 主本在 A 下一個(gè)副本在 B 復(fù)制表 X 主本在 A 下一個(gè)副本在 NIL MCM 更新 X MCM 將更新報(bào)文發(fā)送到下一個(gè)

49、副本 MCM 將更新報(bào)文發(fā)送到主節(jié)點(diǎn) MCM 更新 X 并且將更新報(bào)文發(fā)送到下一個(gè)副本 MCM更新X MCM 指出更新完成 頁(yè)變換表 X 節(jié)點(diǎn) B 頁(yè) P MCM 向遠(yuǎn)程節(jié)點(diǎn) B 發(fā)送寫(xiě)請(qǐng)求 節(jié)點(diǎn) A 節(jié)點(diǎn) B 節(jié)點(diǎn) C Plus寫(xiě)更新協(xié)議，寫(xiě)更新協(xié)議，MCM代表存儲(chǔ)一致性控制器代表存儲(chǔ)一致性控制器第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 512022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v替換策略替換策略 在允許數(shù)據(jù)四處遷移的系統(tǒng)中，當(dāng)共享數(shù)據(jù)占滿了高速緩沖存儲(chǔ)器的有效空間后，哪些數(shù)據(jù)將被替換出來(lái)以獲得空閑空間，并把它們送到哪里？ 在選擇被替換的數(shù)據(jù)項(xiàng)時(shí)，D

50、SM系統(tǒng)的工作幾乎和共享存儲(chǔ)器的多處理機(jī)的高速緩存所做的那些工作一樣，但并不像大多數(shù)的高速緩存那樣使用最近最少使用或隨機(jī)的替換策略，多數(shù)DSM系統(tǒng)區(qū)分?jǐn)?shù)據(jù)項(xiàng)的狀態(tài)并對(duì)他們進(jìn)行優(yōu)化。 被替換后，系統(tǒng)必須知道它未丟失。有些DSM系統(tǒng)，把數(shù)據(jù)項(xiàng)傳送到一個(gè)基地節(jié)點(diǎn)，它有一個(gè)靜態(tài)分配空間，存放一個(gè)系統(tǒng)中別處不需要的數(shù)據(jù)項(xiàng)副本。一種改進(jìn)方法是讓想要?jiǎng)h除該數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)把該數(shù)據(jù)分頁(yè)送到磁盤(pán)上。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 522022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v顛簸顛簸 DSM系統(tǒng)特別容易出現(xiàn)顛簸。如果兩個(gè)節(jié)點(diǎn)對(duì)一個(gè)數(shù)據(jù)項(xiàng)同時(shí)進(jìn)行寫(xiě)，該數(shù)據(jù)項(xiàng)就有可能以

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

52、SM系統(tǒng)一個(gè)理論上的優(yōu)點(diǎn)是它們比緊密耦合系統(tǒng)具有更好的可擴(kuò)充性。前面說(shuō)過(guò)，對(duì)可擴(kuò)充性限制有兩種因素：集中瓶頸(例如緊密耦合系統(tǒng)中的總線)和全局公用信息的操作及存儲(chǔ)(例如廣播報(bào)文或目錄，它的大小與節(jié)點(diǎn)數(shù)成比例)。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 542022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v異構(gòu)性異構(gòu)性 在Agora系統(tǒng)中，把存儲(chǔ)器構(gòu)造為在異構(gòu)性機(jī)器之間共享對(duì)象。 Mermaid探索了另一種不同尋常的方法：存儲(chǔ)器以頁(yè)方式共享，并且一頁(yè)只包含一種數(shù)據(jù)類(lèi)型。當(dāng)在不同體系結(jié)構(gòu)的兩個(gè)系統(tǒng)之間移動(dòng)一頁(yè)時(shí)，變換子程序都會(huì)把該頁(yè)上的數(shù)據(jù)轉(zhuǎn)換成適當(dāng)?shù)母袷健?第十一

53、章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 552022-3-23中南大學(xué)軟件學(xué)院11.4 DSM系統(tǒng)的實(shí)現(xiàn)系統(tǒng)的實(shí)現(xiàn)v 其他有關(guān)算法其他有關(guān)算法 為了支持DSM算法，必須對(duì)同步操作和存儲(chǔ)管理進(jìn)行調(diào)整。例如，信號(hào)量是在共享存儲(chǔ)器系統(tǒng)上使用旋轉(zhuǎn)鎖實(shí)現(xiàn)的。 可為DSM重新構(gòu)造存儲(chǔ)管理。一個(gè)常用的存儲(chǔ)器分配方案對(duì)公用庫(kù)的存儲(chǔ)器進(jìn)行分配，每次請(qǐng)求時(shí)要搜索一次該庫(kù)。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 562022-3-23中南大學(xué)軟件學(xué)院11.5 DSM實(shí)例：實(shí)例：Ivy和和MemNetv Ivy軟件實(shí)現(xiàn)的軟件實(shí)現(xiàn)的DSM Ivy中進(jìn)程地址空間分成專(zhuān)用和共享兩部分。專(zhuān)用部分不能由其他進(jìn)

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

55、協(xié)議一致性協(xié)議 Ivy所使用的一致性概念是多個(gè)讀/單個(gè)寫(xiě)的語(yǔ)義。對(duì)某地址的讀操作總是得到最近對(duì)該地址寫(xiě)的值，一致性協(xié)議保證執(zhí)行這一語(yǔ)義。 Ivy的每個(gè)處理機(jī)都有自己的頁(yè)表。表中的每一項(xiàng)紀(jì)錄著該主機(jī)的訪問(wèn)權(quán)，可以對(duì)一頁(yè)擁有讀、寫(xiě)權(quán)或無(wú)任何權(quán)利。一頁(yè)的訪問(wèn)權(quán)是與緩存器中一個(gè)塊的狀態(tài)相當(dāng)?shù)摹?緩存器 Ivy 重寫(xiě) 共享重寫(xiě) 有效 無(wú)效 寫(xiě) 所有者讀 讀 無(wú)任何權(quán)力 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 582022-3-23中南大學(xué)軟件學(xué)院11.5 DSM實(shí)例：實(shí)例：Ivy和和MemNetv Ivy一致性協(xié)議一致性協(xié)議 當(dāng)訪問(wèn)一個(gè)共享地址時(shí)，該主機(jī)檢查它是否有權(quán)在指定方式下訪問(wèn)含有此地

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

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

58、出請(qǐng)求。當(dāng)一個(gè)處理機(jī)上有多個(gè)進(jìn)程等待同一個(gè)頁(yè)面時(shí)，加鎖機(jī)制防止處理機(jī)發(fā)出多個(gè)請(qǐng)求。對(duì)一個(gè)頁(yè)面成功執(zhí)行寫(xiě)操作就會(huì)成為頁(yè)面的所有者第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 612022-3-23中南大學(xué)軟件學(xué)院11.5 DSM實(shí)例：實(shí)例：Ivy和和MemNetv Ivy一致性協(xié)議一致性協(xié)議 2） 有兩種類(lèi)型的固定分布式管理者算法：固定的和廣播的。固定算法中，每個(gè)處理機(jī)預(yù)定管理一部分頁(yè)面。通常一個(gè)適當(dāng)?shù)纳⒘泻瘮?shù)用于把頁(yè)面映射到處理機(jī)。廣播算法中，訪問(wèn)頁(yè)面出故障的處理機(jī)發(fā)出廣播確定頁(yè)面的真正所有者。廣播算法性能比較差，因?yàn)樗刑幚頇C(jī)必須處理每個(gè)請(qǐng)求，減慢處理機(jī)的計(jì)算第十一章第十一章 分布式共

59、享存儲(chǔ)器分布式共享存儲(chǔ)器 622022-3-23中南大學(xué)軟件學(xué)院11.5 DSM實(shí)例：實(shí)例：Ivy和和MemNetv Ivy一致性協(xié)議一致性協(xié)議 3） 動(dòng)態(tài)分布式管理者方法的核心是每個(gè)處理機(jī)的頁(yè)表中記錄所有頁(yè)的所有者。頁(yè)表中，集中管理者算法中的所有者域被替換成另一個(gè)域，叫做可能所有者(probowner)域，它可能是頁(yè)面的真正所有者，也可能是頁(yè)面的可能所有者?？赡芩姓哂驑?gòu)成一個(gè)鏈，從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)，最終會(huì)指向真正的所有者。第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 632022-3-23中南大學(xué)軟件學(xué)院11.5 DSM實(shí)例：實(shí)例：Ivy和和MemNetvIvy存儲(chǔ)器管理存儲(chǔ)器管理 虛擬共享存儲(chǔ)器的管理與常規(guī)存儲(chǔ)器管理有很大不同，下面介紹頁(yè)替換和存儲(chǔ)器分配。 頁(yè)替換。 Ivy的虛擬共享存儲(chǔ)器的頁(yè)有五種：可寫(xiě)的、所有者可讀的、只讀的、空的和不使用的?？枕?yè)和不用頁(yè)都具有最高的被替換優(yōu)先權(quán)，即如果需要一頁(yè)則先替換它們。由于只讀頁(yè)可被其所有者制造備份，所以可以簡(jiǎn)單地丟棄。對(duì)于所有者讀的頁(yè)和可寫(xiě)頁(yè)的丟棄當(dāng)然需要所有權(quán)的轉(zhuǎn)讓。 第十一章第十一章 分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器 642022-3-23中南大學(xué)軟件學(xué)院11.5 DSM實(shí)例：實(shí)例：Ivy和和MemNetvIvy存儲(chǔ)器管理存儲(chǔ)