分布式共享內(nèi)存

1、第第 7 章章分布式共享內(nèi)存分布式共享內(nèi)存在本章中，我們研究實(shí)現(xiàn)分布式共享內(nèi)存(distributed shared memory 簡(jiǎn)稱 DSM)。7.1 引論引論傳統(tǒng)上，分布式計(jì)算是基于消息傳遞模型，在這種模型下進(jìn)程們經(jīng)由以消息形式交換數(shù)據(jù)來(lái)彼此互相交互和共享數(shù)據(jù)。Hoare 的通訊順序進(jìn)程(communicating sequential processes)，客戶-服務(wù)器模型和遠(yuǎn)程過(guò)程調(diào)用都是這種模型的例子。分布式共享內(nèi)存(Distributed shared memory 簡(jiǎn)稱 DSM)系統(tǒng)是分布式操作系統(tǒng)的一個(gè)資源管理成分，它實(shí)現(xiàn)在沒(méi)有物理地共享內(nèi)存的分布式系統(tǒng)中的共享內(nèi)存模型。見(jiàn)圖

2、 7.1。圖 7.1 分布式系統(tǒng)中的共享內(nèi)存模型這個(gè)共享內(nèi)存模型提供一個(gè)虛擬地址空間，使得被在一個(gè)分布式系統(tǒng)中所有結(jié)點(diǎn)（計(jì)算機(jī)）之間共享。7.2 體系結(jié)構(gòu)和動(dòng)力體系結(jié)構(gòu)和動(dòng)力具有分布式共享內(nèi)存，程序訪問(wèn)在共享地址空間中的數(shù)據(jù)正如同訪問(wèn)在傳統(tǒng)的虛存中的數(shù)據(jù)一樣。在支持分布式共享內(nèi)存的系統(tǒng)中，數(shù)據(jù)既在輔存和主存之間也在不同結(jié)點(diǎn)的主存之間移動(dòng)。每個(gè)結(jié)點(diǎn)可以擁有存貯在共享地址空間中的數(shù)據(jù)，并且當(dāng)數(shù)據(jù)從一個(gè)結(jié)點(diǎn)移到另一個(gè)結(jié)點(diǎn)時(shí)，擁有關(guān)系可以改變。當(dāng)一個(gè)進(jìn)程訪問(wèn)在共享地址空間中的數(shù)據(jù)時(shí)，一個(gè)映照管理者(mapping manager) 映照共享內(nèi)存地址到物理存儲(chǔ)，這個(gè)物理存儲(chǔ)可以是本地或遠(yuǎn)程的。映照管理者

3、是一個(gè)或者實(shí)現(xiàn)在操作系統(tǒng)內(nèi)核中或者作為一個(gè)運(yùn)行時(shí)庫(kù)例程的軟件層。為了減少由于通訊誤而帶來(lái)的延遲，當(dāng)共享內(nèi)存地址映照到在在一個(gè)遠(yuǎn)程結(jié)點(diǎn)上的一個(gè)物理內(nèi)存位置時(shí)，分布式共享內(nèi)存可以移動(dòng)在共享內(nèi)存地址中的數(shù)據(jù)從一個(gè)遠(yuǎn)程結(jié)點(diǎn)到正在訪問(wèn)數(shù)據(jù)的結(jié)點(diǎn)。在這樣情況下，分布式共享內(nèi)存利用底層通訊系統(tǒng)的通訊服務(wù)。7.2.1 分布式共享內(nèi)存的優(yōu)點(diǎn)分布式共享內(nèi)存的優(yōu)點(diǎn)在消息傳遞模型中，程序通過(guò)明顯的消息傳遞使共享數(shù)據(jù)可供使用。換句話說(shuō)，程序員需要意識(shí)到進(jìn)程之間數(shù)據(jù)移動(dòng)。程序員不得不明顯地使用通訊原語(yǔ)（例如 SEND 和 RECEIVE），放一個(gè)重要的負(fù)擔(dān)在它們身上。相反，分布式共享內(nèi)存系統(tǒng)隱藏這個(gè)明顯的數(shù)據(jù)移動(dòng)并且提供

4、一個(gè)較簡(jiǎn)單的程序員已經(jīng)精通的共享數(shù)據(jù)抽象。因此，利用分布式共享內(nèi)存比通過(guò)明顯的消息傳遞更容易地設(shè)計(jì)和編寫并行算法。在消息傳遞模型中，數(shù)據(jù)在兩個(gè)不同的地址空間之間移動(dòng)。這使得它難以在兩個(gè)進(jìn)程之間傳遞復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。而且傳遞由“引用”的數(shù)據(jù)和傳遞包含指針的數(shù)據(jù)結(jié)構(gòu)一般是困難的和貴的。相反，分布式共享內(nèi)存系統(tǒng)允許傳遞由“引用”的復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，于是簡(jiǎn)化了對(duì)分布式應(yīng)用的算法的開(kāi)發(fā)。僅移動(dòng)規(guī)定的所引用的數(shù)據(jù)片來(lái)代替由移動(dòng)整塊或包含所引用的引用場(chǎng)點(diǎn)的數(shù)據(jù)頁(yè)，分布式共享內(nèi)存利用程序所顯示的引用局部性，因此削減了在網(wǎng)絡(luò)上的通信開(kāi)銷。分布式共享內(nèi)存系統(tǒng)比緊偶合多機(jī)系統(tǒng)更便宜。這是因?yàn)榉植际焦蚕韮?nèi)存系統(tǒng)可以利用貨

5、架上的（off-the-shelf）硬件建立不需要復(fù)雜的接口把共享內(nèi)存連接到處理機(jī)。在一個(gè)分布式共享內(nèi)存系統(tǒng)所有結(jié)點(diǎn)中可供使用物理內(nèi)存組合在一起是巨大的。這個(gè)大的內(nèi)存可以用于有效地運(yùn)行要求大內(nèi)存的程序而不用招致由于在傳統(tǒng)的分布系統(tǒng)中對(duì)換引起的磁盤延遲。這個(gè)事實(shí)也由處理機(jī)速度相對(duì)于內(nèi)存速度預(yù)料的增加和非常高速網(wǎng)絡(luò)出現(xiàn)所支持。在具有單個(gè)共享內(nèi)存的緊偶合多機(jī)系統(tǒng)中主存經(jīng)由一個(gè)公共總線訪問(wèn)，這限制多機(jī)系統(tǒng)為幾十個(gè)處理機(jī)。分布式共享內(nèi)存系統(tǒng)沒(méi)有這個(gè)缺點(diǎn)，并且可以容易地向上擴(kuò)充。為共享內(nèi)存多處理機(jī)寫的程序原則上可以不加改變地運(yùn)行在分布式共享內(nèi)存系統(tǒng)。至少這樣的程序可以容易地移到分布式共享內(nèi)存系統(tǒng)中。本質(zhì)上

6、，分布式共享內(nèi)存系統(tǒng)努力克服共享內(nèi)存機(jī)器體系結(jié)構(gòu)的限制并且減少在分布系統(tǒng)中寫并行程序。所需的努力。7.3 實(shí)現(xiàn)分布式共享內(nèi)存的算法實(shí)現(xiàn)分布式共享內(nèi)存的算法實(shí)現(xiàn)分布式共享內(nèi)存的中心課題是：如何追蹤遠(yuǎn)程數(shù)據(jù)的位置；當(dāng)訪問(wèn)遠(yuǎn)程數(shù)據(jù)時(shí)，.如何克服.通信延遲和在分布系統(tǒng)中通信協(xié)議的執(zhí)行相聯(lián)的開(kāi)銷；為了改善系統(tǒng)性能，.如何使共享數(shù)據(jù)在幾個(gè)結(jié)點(diǎn)上并發(fā)地可供訪問(wèn)?，F(xiàn)在我們描述實(shí)現(xiàn)分布式共享內(nèi)存的四個(gè)基本算法。中央服務(wù)器(Central-Server)算法遷移算法讀復(fù)制(Read-Replicatin)算法完全復(fù)制算法7.3.1 中央服務(wù)器中央服務(wù)器(Central-Server)算法算法在中央服務(wù)器(Cent

7、ral-Server)算法中，一個(gè)中央服務(wù)器維護(hù)所有的共享數(shù)據(jù)。它服務(wù)從其它結(jié)點(diǎn)或者客戶來(lái)的讀請(qǐng)求，返回?cái)?shù)據(jù)項(xiàng)給它們（見(jiàn)圖 7.2）。在客戶寫請(qǐng)求時(shí)，它更新數(shù)據(jù)并返回表示收到的消息。在表示收到的消息失效情況一個(gè)超時(shí)(timeout)可以被采用來(lái)重發(fā)請(qǐng)求。重復(fù)的寫請(qǐng)求可以由寫請(qǐng)求所伴隨的順序號(hào)檢測(cè)。在幾次重新傳輸而又無(wú)響應(yīng)后一個(gè)失敗的條件被返回到企圖訪問(wèn)共享數(shù)據(jù)的應(yīng)用。雖然中央服務(wù)器算法其實(shí)現(xiàn)是簡(jiǎn)單的，但中央服務(wù)器可能變成一個(gè)瓶頸。為了克服這個(gè)問(wèn)題，共享數(shù)據(jù)可以分布在幾個(gè)服務(wù)器上。在這種情況下，客戶必須能夠?qū)γ看螖?shù)據(jù)訪問(wèn)定位適當(dāng)?shù)姆?wù)器。多點(diǎn)廣播式的數(shù)據(jù)訪問(wèn)請(qǐng)求是不希望的，因?yàn)榕c中央服務(wù)器方案相

8、比，它并不減少服務(wù)器的負(fù)載。分布數(shù)據(jù)的一種較好的方法是按地址劃分共享數(shù)據(jù)并且利用一個(gè)映照函數(shù)定位適當(dāng)?shù)姆?wù)器。圖 7.2 中央服務(wù)器算法7.3.2 遷移算法遷移算法在中央服務(wù)器算法中，每個(gè)數(shù)據(jù)訪問(wèn)請(qǐng)求被發(fā)送到數(shù)據(jù)的位置，與之相比，在遷移算法中的數(shù)據(jù)被轉(zhuǎn)移到數(shù)據(jù)訪問(wèn)請(qǐng)求的地點(diǎn)，允許隨后的對(duì)該數(shù)據(jù)的訪問(wèn)被本地地執(zhí)行（見(jiàn)圖 7.3）。遷移算法每次僅允許一個(gè)結(jié)點(diǎn)訪問(wèn)一個(gè)共享數(shù)據(jù)。在中央服務(wù)器算法中，每個(gè)數(shù)據(jù)訪問(wèn)請(qǐng)求被發(fā)送到數(shù)據(jù)的位置，與之相比，在遷移算法中的數(shù)據(jù)被轉(zhuǎn)移到數(shù)據(jù)訪問(wèn)請(qǐng)求的地點(diǎn)，允許隨后的對(duì)該數(shù)據(jù)的訪問(wèn)被本地地執(zhí)行。圖 7.3 遷移算法典型地，包含數(shù)據(jù)項(xiàng)的整個(gè)頁(yè)或塊遷移以代替單個(gè)請(qǐng)求項(xiàng)。這個(gè)

9、算法利用由程序所展示的引用的局部性把遷移的費(fèi)用分?jǐn)偟蕉鄠€(gè)訪問(wèn)遷移數(shù)據(jù)上。但是這種途徑對(duì)抖動(dòng)(thrashing)敏感，其中頁(yè)頻繁地在結(jié)點(diǎn)間遷移，而僅服務(wù)少數(shù)請(qǐng)求。為了減少抖動(dòng)，Mirage 系統(tǒng)使用一個(gè)可調(diào)的參量決定一個(gè)結(jié)點(diǎn)可以擁有一個(gè)共享數(shù)據(jù)項(xiàng)的期間。這允許在頁(yè)被遷移到另一結(jié)點(diǎn)之前一個(gè)結(jié)點(diǎn)對(duì)該頁(yè)作若干次訪問(wèn)。Munin 系統(tǒng)力求采用適合不同的數(shù)據(jù)訪問(wèn)模式的協(xié)議來(lái)減少數(shù)據(jù)移動(dòng)。遷移算法提供了一個(gè)機(jī)會(huì)把分布式共享內(nèi)存與運(yùn)行在單個(gè)結(jié)點(diǎn)上操作系統(tǒng)所提供的虛存集成在一起。當(dāng)分布式共享內(nèi)存所用的頁(yè)大小是虛存頁(yè)大小的倍數(shù)時(shí)，一個(gè)本地掌握的共享內(nèi)存頁(yè)可以被映照到一個(gè)應(yīng)用的虛地址空間并且利用正常的機(jī)器指令訪問(wèn)

10、。在一個(gè)內(nèi)存訪問(wèn)失效時(shí)，如果內(nèi)存地址映照到一個(gè)遠(yuǎn)程頁(yè)，在映照頁(yè)到進(jìn)程的地址空間之前，一個(gè)頁(yè)失效處理程序?qū)⑦w移該頁(yè)。在遷移一頁(yè)時(shí)，該頁(yè)從所有在以前結(jié)點(diǎn)被映照到的地址空間移開(kāi)。注意，幾個(gè)進(jìn)程可以共享在一個(gè)結(jié)點(diǎn)上的一頁(yè)。為了定位一個(gè)數(shù)據(jù)塊，遷移算法可以利用一個(gè)服務(wù)器追蹤頁(yè)的位置或者通過(guò)在結(jié)點(diǎn)上所維持的提示。這些提示指向搜尋當(dāng)前占有該頁(yè)的結(jié)點(diǎn)。另外，一個(gè)詢問(wèn)可以廣播來(lái)定位一頁(yè)。7.3.3 讀復(fù)制讀復(fù)制(Read-Replicatin)算法算法在前面途徑中僅僅在一個(gè)結(jié)點(diǎn)上的進(jìn)程可以在如何時(shí)刻訪問(wèn)一個(gè)共享數(shù)據(jù)。讀復(fù)制(Read-Replicatin)算法擴(kuò)充了遷移算法，即復(fù)制數(shù)據(jù)塊并且允許多個(gè)結(jié)點(diǎn)具有讀訪

11、問(wèn)或一個(gè)結(jié)點(diǎn)具有讀寫訪問(wèn)（多個(gè)讀者-一個(gè)作者協(xié)議）（見(jiàn)圖 7.4）。圖 7.4 讀復(fù)制由允許多個(gè)結(jié)點(diǎn)并發(fā)地訪問(wèn)數(shù)據(jù)，讀復(fù)制可以改善系統(tǒng)性能。但是，寫操作是昂貴的，因?yàn)橐粋€(gè)共享塊在各種結(jié)點(diǎn)上的所有副本將或者不得不是無(wú)效的，或者用當(dāng)前值來(lái)更新以維護(hù)共享數(shù)據(jù)塊的一致性。在讀復(fù)制算法中分布式共享內(nèi)存必須追蹤所有數(shù)據(jù)塊副本的位置。在 IVY 系統(tǒng)中，一個(gè)數(shù)據(jù)塊的擁有者結(jié)點(diǎn)追蹤具有該數(shù)據(jù)塊的一個(gè)副本的所有結(jié)點(diǎn)。在 PLUS 系統(tǒng)中，一個(gè)分布式鏈接列表用來(lái)追蹤具有該數(shù)據(jù)塊的一個(gè)副本的所有結(jié)點(diǎn)。然而，當(dāng)讀對(duì)寫的比例是大的時(shí)候，讀復(fù)制有減少讀操作平均費(fèi)用的潛力。在節(jié)描述在 IVY 系統(tǒng)中實(shí)現(xiàn)的許多讀復(fù)制算法。7

12、.3.4 完全復(fù)制算法完全復(fù)制算法完全復(fù)制算法是讀復(fù)制算法的一種擴(kuò)充（見(jiàn)圖 7.5）。讀復(fù)制算法它允許多個(gè)結(jié)點(diǎn)具有對(duì)共享數(shù)據(jù)塊的讀和寫兩種訪問(wèn)（多個(gè)讀者-多個(gè)作者協(xié)議）。由于許多結(jié)點(diǎn)可以并發(fā)地寫共享數(shù)據(jù)，對(duì)共享數(shù)據(jù)的訪問(wèn)必須被控制以維持它的一致性。維持一致性的一個(gè)簡(jiǎn)單方法是利用一個(gè)無(wú)間隙的順序器(gap-free sequencer)。在這種方案下，所有希望修改共享數(shù)據(jù)的結(jié)點(diǎn)將發(fā)送修改給一個(gè)順序器。這個(gè)順序器將賦予一個(gè)順序號(hào)并且多點(diǎn)廣播這個(gè)修改及順序號(hào)到所有具有該共享數(shù)據(jù)項(xiàng)副本的結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)以順序號(hào)次序處理修改請(qǐng)求。在一個(gè)結(jié)點(diǎn)上一個(gè)修改請(qǐng)求的順序號(hào)和期待的順序號(hào)之間的間隙指示一個(gè)或多個(gè)修改已

13、被遺漏。在這種情況下結(jié)點(diǎn)將被請(qǐng)求重新傳送已經(jīng)遺漏的修改。這蘊(yùn)涵在某個(gè)結(jié)點(diǎn)保留修改的日記。在第 5 節(jié)將討論若干其它維護(hù)共享數(shù)據(jù)的一致性的協(xié)議。圖 7.5 完全復(fù)制算法7.4 存儲(chǔ)一致性存儲(chǔ)一致性(Memory coherence)為了改善性能分布式共享內(nèi)存系統(tǒng)依賴復(fù)制共享數(shù)據(jù)項(xiàng)和允許在許多結(jié)點(diǎn)上并發(fā)訪問(wèn)。但是，如果并發(fā)訪問(wèn)不仔細(xì)地加以控制，內(nèi)存訪問(wèn)可能以不同于程序員所期望的次序被執(zhí)行。非正式講，一個(gè)內(nèi)存是一致的，如果由讀操作返回的值總歸是程序員所期望的值。例如，對(duì)一個(gè)程序員期待一個(gè)讀操作返回一個(gè)最近寫操作所存貯的值是相當(dāng)自然的。因此，為了維護(hù)共享數(shù)據(jù)項(xiàng)的一致性，一個(gè)控制或同步訪問(wèn)的機(jī)制是必要的

14、。同樣為了寫正確的程序，程序員需要理解如何進(jìn)行對(duì)共享內(nèi)存的并發(fā)更新。允許的內(nèi)存訪問(wèn)次序集合構(gòu)成了存儲(chǔ)一致性模型。字一致性用于說(shuō)明一種特殊類型的一致性。存儲(chǔ)一致性最直觀語(yǔ)義是嚴(yán)格一致性(strict consistency)，其定義如下：一個(gè)讀返回最近寫的值。嚴(yán)格一致性要求具有決定最近寫的能力，依次它蘊(yùn)涵請(qǐng)求的全序。由于比一個(gè)程序可能實(shí)際需要更多的數(shù)據(jù)移動(dòng)和同步要求，請(qǐng)求的全序?qū)е路怯行裕ㄕ?qǐng)參考4）。為了解決這個(gè)問(wèn)題，某些分布式共享內(nèi)存系統(tǒng)企圖由提供不嚴(yán)格的一致性語(yǔ)義來(lái)改善性能。下列是幾種內(nèi)存一致性形式：順序的一致性(Sequential consistency)一般一致性(General C

15、onsistency)處理機(jī)一致性(Processor consistency)弱一致性(Weak consistency)釋放一致性(Release consistency)7.4.1 順序的一致性(Sequential consistency)：一個(gè)系統(tǒng)是序列的一致性，如果所有處理機(jī)任何操作執(zhí)行的結(jié)果是和它們以順序次序執(zhí)行一樣，并且每個(gè)單個(gè)處理機(jī)的操作以其程序規(guī)定的次序出現(xiàn)在這個(gè)順序中。7.4.2 一般一致性一般一致性一個(gè)系統(tǒng)支持一般一致性，當(dāng)每個(gè)處理機(jī)所執(zhí)行的所有寫已被完成時(shí)，如果一個(gè)內(nèi)存位置的所有副本最終地包含同樣的數(shù)據(jù)。7.4.3 處理機(jī)一致性處理機(jī)一致性由一個(gè)處理機(jī)發(fā)出的寫以他們所

16、發(fā)出的同樣次序被觀察到。但是，從兩個(gè)進(jìn)程寫的次序出現(xiàn)作為由它們自身或第三個(gè)處理機(jī)所觀察到的次序不一定相同。即從不同的處理機(jī)的同時(shí)對(duì)同樣的位置的兩個(gè)讀可以產(chǎn)生不同的結(jié)果。7.4.4 弱一致性弱一致性同步訪問(wèn)（訪問(wèn)要求執(zhí)行同步操作）是順序一致的。在一個(gè)同步訪問(wèn)可以被執(zhí)行之前，所有以前正常的數(shù)據(jù)訪問(wèn)必須完成。在一個(gè)正常的數(shù)據(jù)訪問(wèn)可以被執(zhí)行之前，所有以前同步訪問(wèn)必須完成。這實(shí)質(zhì)上把一致性問(wèn)題留給程序員決定。在一個(gè)同步操作之后，內(nèi)存將立即是一致的。7.4.5 釋放一致性釋放一致性釋放一致性本質(zhì)上和弱一致性相同，但是同步訪問(wèn)必須僅是處理機(jī)一致的。同步操作被分裂成獲得(acquire)和釋放(release

17、)操作。所有懸而未決的獲得（例如，一個(gè)鎖操作）必須在一個(gè)正常訪問(wèn)完成之前完成，并且所有正常訪問(wèn)必須在一個(gè)釋放（例如，一個(gè)去鎖操作）完成之前完成。在同一處理機(jī)內(nèi)的局部依賴性必須仍然遵守。釋放一致性是弱一致性的進(jìn)一步放寬而又不丟失一致性。事實(shí)上，釋放一致性由包含下列次序的放寬而區(qū)別于弱一致性。正常的數(shù)據(jù)訪問(wèn)不.必等待釋放操作完成，.因?yàn)獒尫挪僮鳂?biāo).志正常的訪問(wèn)完成并且不.涉及訪問(wèn)的次序。獲得操作不必等待以前的正常的訪問(wèn)完成。.同步操作僅要求是處理機(jī)一致的的，而非順序一致的。7.5 一致性協(xié)議一致性協(xié)議為了提供并發(fā)訪問(wèn)，分布式共享內(nèi)存系統(tǒng)數(shù)據(jù)復(fù)制，其中數(shù)據(jù)的副本在所有訪問(wèn)該數(shù)據(jù)的結(jié)點(diǎn)上維護(hù)。數(shù)據(jù)復(fù)制

18、的一個(gè)基礎(chǔ)問(wèn)題是確保所有副本具有同樣的信息以及結(jié)點(diǎn)沒(méi)有訪問(wèn)過(guò)時(shí)的數(shù)據(jù)的困難性。換句話說(shuō)，需要一個(gè)保持復(fù)制一致的協(xié)議。兩個(gè)維持一致性的基本協(xié)議是寫-使無(wú)效協(xié)議和寫更新協(xié)議。7.5.1 寫寫-使無(wú)效協(xié)議使無(wú)效協(xié)議(WRITE-INVALIDATE PROTOCOL)在寫-使無(wú)效方法中，一個(gè)對(duì)共享數(shù)據(jù)的寫，在寫能夠進(jìn)行之前，引起那個(gè)數(shù)據(jù)除了一個(gè)之外的所有副本使之無(wú)效。一旦無(wú)效，副本不再可訪問(wèn)。這種方案的一個(gè)主要缺點(diǎn)是無(wú)效被發(fā)送到所有具有副本的結(jié)點(diǎn)，而不管它們是否將使用這個(gè)數(shù)據(jù)。這個(gè)協(xié)議較好地適合于幾個(gè)更新出現(xiàn)在讀之間這類應(yīng)用，以及一個(gè)程序顯示了高度的每個(gè)結(jié)點(diǎn)引用局部性。另一方面，如果許多結(jié)點(diǎn)頻繁地訪

19、問(wèn)一個(gè)對(duì)象，這個(gè)協(xié)議是低效率的，因?yàn)橐粋€(gè)更新的對(duì)象在每次無(wú)效后，將不得不被立即復(fù)制回許多結(jié)點(diǎn)。寫-使無(wú)效協(xié)議已經(jīng)被用于大多數(shù)分布式共享內(nèi)存系統(tǒng)：IVY27，Clouds34，DASH26，Memnet12，Mermaid41和 Mirage18。其中 IVY 支持嚴(yán)格一致性，DASH 支持釋放一致性。7.5.2 寫更新協(xié)議寫更新協(xié)議(WRITE-UPDATE PROTOCOL)在寫更新方法中，一個(gè)對(duì)共享數(shù)據(jù)的寫引起那個(gè)數(shù)據(jù)的所有副本被更新。這種途徑比前一種途徑更難實(shí)現(xiàn)，因?yàn)橐粋€(gè)新值不得不被發(fā)送以代替使無(wú)效消息。這個(gè)協(xié)議可以期望產(chǎn)生相當(dāng)網(wǎng)絡(luò)交通。在 PLUS 系統(tǒng)中的高速緩存一致性(Cache

20、coherence)PLUS 系統(tǒng)采用寫更新協(xié)議和支持一般一致性8。一個(gè)運(yùn)行在每個(gè)結(jié)點(diǎn)上的內(nèi)存一致性管理程序(memory coherence manager 簡(jiǎn)稱 MCM)負(fù)責(zé)維護(hù)一致性。復(fù)制的單位是頁(yè)，在目前的實(shí)現(xiàn)中每頁(yè) 4 字節(jié)，但是，內(nèi)存訪問(wèn)和一致性維護(hù)的單位是一個(gè) 32 位字。7.5.3 PLUS 系統(tǒng)系統(tǒng)在 PLUS 系統(tǒng)中一個(gè)虛頁(yè)對(duì)應(yīng)于一頁(yè)的一個(gè)復(fù)制品的列表。復(fù)制品之一被設(shè)定為主副本(master copy)。在每個(gè)結(jié)點(diǎn)上的 MCM 通過(guò)一個(gè)稱為副本列表(copy-list)的分布式鏈接列表知道一頁(yè)的其它復(fù)制品。副本列表由操作系統(tǒng)內(nèi)核構(gòu)造，在每個(gè)結(jié)點(diǎn)上有兩個(gè)指針，主指針和下一個(gè)副

21、本指針。主指針指向存放主副本的結(jié)點(diǎn)，下一個(gè)副本指針指向沿著副本列表包含該頁(yè)的另一個(gè)復(fù)制品（如果有此復(fù)制品）的結(jié)點(diǎn)。讀操作：在一個(gè)讀失敗時(shí)。如果地址指示本地內(nèi)存，本地內(nèi)存被讀，否則本地 MCM 發(fā)送一個(gè)讀請(qǐng)求給在規(guī)定的遠(yuǎn)程結(jié)點(diǎn)上的對(duì)手。由遠(yuǎn)程 MCM 返回的數(shù)據(jù)被傳回到請(qǐng)求處理機(jī)。寫操作：為了保證一般一致性，在主副本上總歸首先執(zhí)行寫，然后傳播到副本列表所鏈接的副本。在一個(gè)寫失敗時(shí)，如果本地副本不是主副本，則更新請(qǐng)求被發(fā)送到包含主副本結(jié)點(diǎn)以便更新，然后進(jìn)一步傳播。在一個(gè)寫失敗時(shí)，如果地址指示一個(gè)遠(yuǎn)程結(jié)點(diǎn)（即無(wú)本地副本出現(xiàn)），則更新請(qǐng)求被發(fā)送到遠(yuǎn)程結(jié)點(diǎn)。（在圖中，一個(gè)寫請(qǐng)求從結(jié)點(diǎn) 4 發(fā)送到結(jié)點(diǎn) 2）如果在那個(gè)接點(diǎn)上的副本不是主副本，則更新請(qǐng)求被發(fā)送到包含主副本的結(jié)點(diǎn)以便更新然后進(jìn)一步傳播。（在圖中，結(jié)點(diǎn) 2 不是 X 的