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

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

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

3、的軟件層。為了減少由于通訊誤而帶來的延遲，當共享內(nèi)存地址映照到在在一個遠程結(jié)點上的一個物理內(nèi)存位置時，分布式共享內(nèi)存可以移動在共享內(nèi)存地址中的數(shù)據(jù)從一個遠程結(jié)點到正在訪問數(shù)據(jù)的結(jié)點。在這樣情況下，分布式共享內(nèi)存利用底層通訊系統(tǒng)的通訊服務。7.2.1 分布式共享內(nèi)存的優(yōu)點在消息傳遞模型中，程序通過明顯的消息傳遞使共享數(shù)據(jù)可供使用。換句話說，程序員需要意識到進程之間數(shù)據(jù)移動。程序員不得不明顯地使用通訊原語（例如SEND和RECEIVE），放一個重要的負擔在它們身上。相反，分布式共享內(nèi)存系統(tǒng)隱藏這個明顯的數(shù)據(jù)移動并且提供一個較簡單的程序員已經(jīng)精通的共享數(shù)據(jù)抽象。因此，利用分布式共享內(nèi)存比通過明顯的消

4、息傳遞更容易地設(shè)計和編寫并行算法。在消息傳遞模型中，數(shù)據(jù)在兩個不同的地址空間之間移動。這使得它難以在兩個進程之間傳遞復雜的數(shù)據(jù)結(jié)構(gòu)。而且傳遞由“引用”的數(shù)據(jù)和傳遞包含指針的數(shù)據(jù)結(jié)構(gòu)一般是困難的和貴的。相反，分布式共享內(nèi)存系統(tǒng)允許傳遞由“引用”的復雜的數(shù)據(jù)結(jié)構(gòu)，于是簡化了對分布式應用的算法的開發(fā)。僅移動規(guī)定的所引用的數(shù)據(jù)片來代替由移動整塊或包含所引用的引用場點的數(shù)據(jù)頁，分布式共享內(nèi)存利用程序所顯示的引用局部性，因此削減了在網(wǎng)絡(luò)上的通信開銷。分布式共享內(nèi)存系統(tǒng)比緊偶合多機系統(tǒng)更便宜。這是因為分布式共享內(nèi)存系統(tǒng)可以利用貨架上的（off-the-shelf）硬件建立不需要復雜的接口把共享內(nèi)存連接到處理

5、機。在一個分布式共享內(nèi)存系統(tǒng)所有結(jié)點中可供使用物理內(nèi)存組合在一起是巨大的。這個大的內(nèi)存可以用于有效地運行要求大內(nèi)存的程序而不用招致由于在傳統(tǒng)的分布系統(tǒng)中對換引起的磁盤延遲。這個事實也由處理機速度相對于內(nèi)存速度預料的增加和非常高速網(wǎng)絡(luò)出現(xiàn)所支持。在具有單個共享內(nèi)存的緊偶合多機系統(tǒng)中主存經(jīng)由一個公共總線訪問，這限制多機系統(tǒng)為幾十個處理機。分布式共享內(nèi)存系統(tǒng)沒有這個缺點，并且可以容易地向上擴充。為共享內(nèi)存多處理機寫的程序原則上可以不加改變地運行在分布式共享內(nèi)存系統(tǒng)。至少這樣的程序可以容易地移到分布式共享內(nèi)存系統(tǒng)中。本質(zhì)上，分布式共享內(nèi)存系統(tǒng)努力克服共享內(nèi)存機器體系結(jié)構(gòu)的限制并且減少在分布系統(tǒng)中寫并行

6、程序。所需的努力。7.3 實現(xiàn)分布式共享內(nèi)存的算法實現(xiàn)分布式共享內(nèi)存的中心課題是：l 如何追蹤遠程數(shù)據(jù)的位置；l 當訪問遠程數(shù)據(jù)時，.如何克服.通信延遲和在分布系統(tǒng)中通信協(xié)議的執(zhí)行相聯(lián)的開銷；l 為了改善系統(tǒng)性能，.如何使共享數(shù)據(jù)在幾個結(jié)點上并發(fā)地可供訪問?，F(xiàn)在我們描述實現(xiàn)分布式共享內(nèi)存的四個基本算法。l 中央服務器(Central-Server)算法l 遷移算法l 讀復制(Read-Replicatin)算法l 完全復制算法7.3.1 中央服務器(Central-Server)算法在中央服務器(Central-Server)算法中，一個中央服務器維護所有的共享數(shù)據(jù)。它服務從其它結(jié)點或者客戶來

7、的讀請求，返回數(shù)據(jù)項給它們（見圖7.2）。在客戶寫請求時，它更新數(shù)據(jù)并返回表示收到的消息。在表示收到的消息失效情況一個超時(timeout)可以被采用來重發(fā)請求。重復的寫請求可以由寫請求所伴隨的順序號檢測。在幾次重新傳輸而又無響應后一個失敗的條件被返回到企圖訪問共享數(shù)據(jù)的應用。雖然中央服務器算法其實現(xiàn)是簡單的，但中央服務器可能變成一個瓶頸。為了克服這個問題，共享數(shù)據(jù)可以分布在幾個服務器上。在這種情況下，客戶必須能夠?qū)γ看螖?shù)據(jù)訪問定位適當?shù)姆掌?。多點廣播式的數(shù)據(jù)訪問請求是不希望的，因為與中央服務器方案相比，它并不減少服務器的負載。分布數(shù)據(jù)的一種較好的方法是按地址劃分共享數(shù)據(jù)并且利用一個映照函數(shù)

8、定位適當?shù)姆掌鳌D7.2中央服務器算法7.3.2 遷移算法在中央服務器算法中，每個數(shù)據(jù)訪問請求被發(fā)送到數(shù)據(jù)的位置，與之相比，在遷移算法中的數(shù)據(jù)被轉(zhuǎn)移到數(shù)據(jù)訪問請求的地點，允許隨后的對該數(shù)據(jù)的訪問被本地地執(zhí)行（見圖7.3）。遷移算法每次僅允許一個結(jié)點訪問一個共享數(shù)據(jù)。在中央服務器算法中，每個數(shù)據(jù)訪問請求被發(fā)送到數(shù)據(jù)的位置，與之相比，在遷移算法中的數(shù)據(jù)被轉(zhuǎn)移到數(shù)據(jù)訪問請求的地點，允許隨后的對該數(shù)據(jù)的訪問被本地地執(zhí)行。圖7.3遷移算法典型地，包含數(shù)據(jù)項的整個頁或塊遷移以代替單個請求項。這個算法利用由程序所展示的引用的局部性把遷移的費用分攤到多個訪問遷移數(shù)據(jù)上。但是這種途徑對抖動(thrashing

9、)敏感，其中頁頻繁地在結(jié)點間遷移，而僅服務少數(shù)請求。為了減少抖動，Mirage系統(tǒng)使用一個可調(diào)的參量決定一個結(jié)點可以擁有一個共享數(shù)據(jù)項的期間。這允許在頁被遷移到另一結(jié)點之前一個結(jié)點對該頁作若干次訪問。Munin系統(tǒng)力求采用適合不同的數(shù)據(jù)訪問模式的協(xié)議來減少數(shù)據(jù)移動。遷移算法提供了一個機會把分布式共享內(nèi)存與運行在單個結(jié)點上操作系統(tǒng)所提供的虛存集成在一起。當分布式共享內(nèi)存所用的頁大小是虛存頁大小的倍數(shù)時，一個本地掌握的共享內(nèi)存頁可以被映照到一個應用的虛地址空間并且利用正常的機器指令訪問。在一個內(nèi)存訪問失效時，如果內(nèi)存地址映照到一個遠程頁，在映照頁到進程的地址空間之前，一個頁失效處理程序?qū)⑦w移該頁。

10、在遷移一頁時，該頁從所有在以前結(jié)點被映照到的地址空間移開。注意，幾個進程可以共享在一個結(jié)點上的一頁。為了定位一個數(shù)據(jù)塊，遷移算法可以利用一個服務器追蹤頁的位置或者通過在結(jié)點上所維持的提示。這些提示指向搜尋當前占有該頁的結(jié)點。另外，一個詢問可以廣播來定位一頁。7.3.3 讀復制(Read-Replicatin)算法在前面途徑中僅僅在一個結(jié)點上的進程可以在如何時刻訪問一個共享數(shù)據(jù)。讀復制(Read-Replicatin)算法擴充了遷移算法，即復制數(shù)據(jù)塊并且允許多個結(jié)點具有讀訪問或一個結(jié)點具有讀寫訪問（多個讀者-一個作者協(xié)議）（見圖7.4）。圖7.4讀復制由允許多個結(jié)點并發(fā)地訪問數(shù)據(jù)，讀復制可以改善

11、系統(tǒng)性能。但是，寫操作是昂貴的，因為一個共享塊在各種結(jié)點上的所有副本將或者不得不是無效的，或者用當前值來更新以維護共享數(shù)據(jù)塊的一致性。在讀復制算法中分布式共享內(nèi)存必須追蹤所有數(shù)據(jù)塊副本的位置。在IVY系統(tǒng)中，一個數(shù)據(jù)塊的擁有者結(jié)點追蹤具有該數(shù)據(jù)塊的一個副本的所有結(jié)點。在PLUS系統(tǒng)中，一個分布式鏈接列表用來追蹤具有該數(shù)據(jù)塊的一個副本的所有結(jié)點。然而，當讀對寫的比例是大的時候，讀復制有減少讀操作平均費用的潛力。在節(jié)描述在IVY系統(tǒng)中實現(xiàn)的許多讀復制算法。7.3.4 完全復制算法完全復制算法是讀復制算法的一種擴充（見圖7.5）。讀復制算法它允許多個結(jié)點具有對共享數(shù)據(jù)塊的讀和寫兩種訪問（多個讀者-多

12、個作者協(xié)議）。由于許多結(jié)點可以并發(fā)地寫共享數(shù)據(jù)，對共享數(shù)據(jù)的訪問必須被控制以維持它的一致性。維持一致性的一個簡單方法是利用一個無間隙的順序器(gap-free sequencer)。在這種方案下，所有希望修改共享數(shù)據(jù)的結(jié)點將發(fā)送修改給一個順序器。這個順序器將賦予一個順序號并且多點廣播這個修改及順序號到所有具有該共享數(shù)據(jù)項副本的結(jié)點。每個結(jié)點以順序號次序處理修改請求。在一個結(jié)點上一個修改請求的順序號和期待的順序號之間的間隙指示一個或多個修改已被遺漏。在這種情況下結(jié)點將被請求重新傳送已經(jīng)遺漏的修改。這蘊涵在某個結(jié)點保留修改的日記。在第5節(jié)將討論若干其它維護共享數(shù)據(jù)的一致性的協(xié)議。圖7.5完全復制算

13、法7.4 存儲一致性(Memory coherence)為了改善性能分布式共享內(nèi)存系統(tǒng)依賴復制共享數(shù)據(jù)項和允許在許多結(jié)點上并發(fā)訪問。但是，如果并發(fā)訪問不仔細地加以控制，內(nèi)存訪問可能以不同于程序員所期望的次序被執(zhí)行。非正式講，一個內(nèi)存是一致的，如果由讀操作返回的值總歸是程序員所期望的值。例如，對一個程序員期待一個讀操作返回一個最近寫操作所存貯的值是相當自然的。因此，為了維護共享數(shù)據(jù)項的一致性，一個控制或同步訪問的機制是必要的。同樣為了寫正確的程序，程序員需要理解如何進行對共享內(nèi)存的并發(fā)更新。允許的內(nèi)存訪問次序集合構(gòu)成了存儲一致性模型。字一致性用于說明一種特殊類型的一致性。存儲一致性最直觀語義是嚴

14、格一致性(strict consistency)，其定義如下：一個讀返回最近寫的值。嚴格一致性要求具有決定最近寫的能力，依次它蘊涵請求的全序。由于比一個程序可能實際需要更多的數(shù)據(jù)移動和同步要求，請求的全序?qū)е路怯行裕ㄕ垍⒖?）。為了解決這個問題，某些分布式共享內(nèi)存系統(tǒng)企圖由提供不嚴格的一致性語義來改善性能。下列是幾種內(nèi)存一致性形式：l 順序的一致性(Sequential consistency)l 一般一致性(General Consistency)l 處理機一致性(Processor consistency)l 弱一致性(Weak consistency)l 釋放一致性(Release c

15、onsistency)7.4.1 順序的一致性(Sequential consistency)：一個系統(tǒng)是序列的一致性，如果所有處理機任何操作執(zhí)行的結(jié)果是和它們以順序次序執(zhí)行一樣，并且每個單個處理機的操作以其程序規(guī)定的次序出現(xiàn)在這個順序中。7.4.2 一般一致性一個系統(tǒng)支持一般一致性，當每個處理機所執(zhí)行的所有寫已被完成時，如果一個內(nèi)存位置的所有副本最終地包含同樣的數(shù)據(jù)。7.4.3 處理機一致性由一個處理機發(fā)出的寫以他們所發(fā)出的同樣次序被觀察到。但是，從兩個進程寫的次序出現(xiàn)作為由它們自身或第三個處理機所觀察到的次序不一定相同。即從不同的處理機的同時對同樣的位置的兩個讀可以產(chǎn)生不同的結(jié)果。7.4.

16、4 弱一致性同步訪問（訪問要求執(zhí)行同步操作）是順序一致的。在一個同步訪問可以被執(zhí)行之前，所有以前正常的數(shù)據(jù)訪問必須完成。在一個正常的數(shù)據(jù)訪問可以被執(zhí)行之前，所有以前同步訪問必須完成。這實質(zhì)上把一致性問題留給程序員決定。在一個同步操作之后，內(nèi)存將立即是一致的。7.4.5 釋放一致性釋放一致性本質(zhì)上和弱一致性相同，但是同步訪問必須僅是處理機一致的。同步操作被分裂成獲得(acquire)和釋放(release)操作。所有懸而未決的獲得（例如，一個鎖操作）必須在一個正常訪問完成之前完成，并且所有正常訪問必須在一個釋放（例如，一個去鎖操作）完成之前完成。在同一處理機內(nèi)的局部依賴性必須仍然遵守。釋放一致性

17、是弱一致性的進一步放寬而又不丟失一致性。事實上，釋放一致性由包含下列次序的放寬而區(qū)別于弱一致性。正常的數(shù)據(jù)訪問不.必等待釋放操作完成，.因為釋放操作標.志正常的訪問完成并且不.涉及訪問的次序。獲得操作不必等待以前的正常的訪問完成。.同步操作僅要求是處理機一致的的，而非順序一致的。7.5 一致性協(xié)議為了提供并發(fā)訪問，分布式共享內(nèi)存系統(tǒng)數(shù)據(jù)復制，其中數(shù)據(jù)的副本在所有訪問該數(shù)據(jù)的結(jié)點上維護。數(shù)據(jù)復制的一個基礎(chǔ)問題是確保所有副本具有同樣的信息以及結(jié)點沒有訪問過時的數(shù)據(jù)的困難性。換句話說，需要一個保持復制一致的協(xié)議。兩個維持一致性的基本協(xié)議是寫-使無效協(xié)議和寫更新協(xié)議。7.5.1 寫-使無效協(xié)議(WRI

18、TE-INVALIDATE PROTOCOL)在寫-使無效方法中，一個對共享數(shù)據(jù)的寫，在寫能夠進行之前，引起那個數(shù)據(jù)除了一個之外的所有副本使之無效。一旦無效，副本不再可訪問。這種方案的一個主要缺點是無效被發(fā)送到所有具有副本的結(jié)點，而不管它們是否將使用這個數(shù)據(jù)。這個協(xié)議較好地適合于幾個更新出現(xiàn)在讀之間這類應用，以及一個程序顯示了高度的每個結(jié)點引用局部性。另一方面，如果許多結(jié)點頻繁地訪問一個對象，這個協(xié)議是低效率的，因為一個更新的對象在每次無效后，將不得不被立即復制回許多結(jié)點。寫-使無效協(xié)議已經(jīng)被用于大多數(shù)分布式共享內(nèi)存系統(tǒng)：IVY27，Clouds34，DASH26，Memnet12，Merma

19、id41和Mirage18。其中IVY支持嚴格一致性，DASH支持釋放一致性。7.5.2 寫更新協(xié)議(WRITE-UPDATE PROTOCOL)在寫更新方法中，一個對共享數(shù)據(jù)的寫引起那個數(shù)據(jù)的所有副本被更新。這種途徑比前一種途徑更難實現(xiàn)，因為一個新值不得不被發(fā)送以代替使無效消息。這個協(xié)議可以期望產(chǎn)生相當網(wǎng)絡(luò)交通。在PLUS系統(tǒng)中的高速緩存一致性(Cache coherence)PLUS系統(tǒng)采用寫更新協(xié)議和支持一般一致性8。一個運行在每個結(jié)點上的內(nèi)存一致性管理程序(memory coherence manager簡稱MCM)負責維護一致性。復制的單位是頁，在目前的實現(xiàn)中每頁4字節(jié)，但是，內(nèi)存訪

20、問和一致性維護的單位是一個32位字。7.5.3 PLUS系統(tǒng)在PLUS系統(tǒng)中一個虛頁對應于一頁的一個復制品的列表。復制品之一被設(shè)定為主副本(master copy)。在每個結(jié)點上的MCM通過一個稱為副本列表(copy-list)的分布式鏈接列表知道一頁的其它復制品。副本列表由操作系統(tǒng)內(nèi)核構(gòu)造，在每個結(jié)點上有兩個指針，主指針和下一個副本指針。主指針指向存放主副本的結(jié)點，下一個副本指針指向沿著副本列表包含該頁的另一個復制品（如果有此復制品）的結(jié)點。讀操作：在一個讀失敗時。如果地址指示本地內(nèi)存，本地內(nèi)存被讀，否則本地MCM發(fā)送一個讀請求給在規(guī)定的遠程結(jié)點上的對手。由遠程MCM返回的數(shù)據(jù)被傳回到請求處理機。寫操作：為了保證一般一致性，在主副本上總歸首先執(zhí)行寫，然后傳播到副本列表所鏈接的副本。在一個寫失敗時，如果本地副本不是主副本，則更新請求被發(fā)送到包含主副本結(jié)點以便更新，然后進一步傳播。在一個寫失敗時，如果地址指示一個遠程結(jié)點（即無本地副本出現(xiàn)），則更新請求被發(fā)送到遠程結(jié)點。（在圖中，一個寫請求從結(jié)點4發(fā)送到結(jié)點2）如果在那個接點上的副本不是主副本，則更新請求被發(fā)送到包含主副本的結(jié)點以便更新然后進一步傳播。（在圖中，結(jié)點2不是X的