第6章分布式共享存儲

1、第6章 分布式共享存儲分布式共享存儲 中國科技大學(xué)軟件學(xué)院丁箐2主要內(nèi)容主要內(nèi)容6.1 共享內(nèi)存6.2 一致性模型6.3 基于頁面的DSM6.4 其它的分布式共享內(nèi)存3主要內(nèi)容主要內(nèi)容6.1 共享內(nèi)存共享內(nèi)存6.2 一致性模型6.3 基于頁面的DSM6.4 其它的分布式共享內(nèi)存4多處理機(jī)和多計算機(jī)回顧多處理機(jī)和多計算機(jī)回顧l對硬件的影響 設(shè)計一種使多個處理機(jī)同時使用同一存儲器的機(jī)器是非常困難的 大的多計算機(jī)系統(tǒng)更易于建立 l對軟件的影響 用于多處理機(jī)編程的技術(shù)很多，可以使用臨界區(qū)（critical region），信號量或管程（monitor） 提供必要的互斥。對多計算機(jī)系統(tǒng)，通信一般使用消息

2、傳遞，這使輸入/輸出更為抽象。消息傳遞帶來了許多復(fù)雜的問題， 5分布式共享存儲器分布式共享存儲器(DSM) lLi 和Hudak提出讓一組由局域網(wǎng)互連的工作站共享一個分頁的虛擬地址空間。 l不共享整個地址空間，而只共享其中所選擇的一部分，即那些由多個進(jìn)程引用的變量和數(shù)據(jù)結(jié)構(gòu)。 l在多臺計算機(jī)上復(fù)制共享變量，通過共享復(fù)制的變量而不是整個頁，模擬處理機(jī)的問題可簡化為保證一組數(shù)據(jù)結(jié)構(gòu)的多個拷貝一致性的問題。 6lDSM的很多研究工作都受到了多處理機(jī)結(jié)構(gòu)發(fā)展的啟發(fā)!l首先比較幾種共享存儲器（內(nèi)存）的多處理機(jī) 7芯片存儲器芯片存儲器 CPU與存儲器連接模型l單片機(jī)l理想的共享存儲器多處理機(jī)8Pentiu

3、m D with 975X ChipsetInter-Core Bus InterfaceMemory ControllerHubI/O Controller HubDDR2 MemoryPCI Express x166 PCI4 Serial ATA Ports6 PCI Express x1High-Definition Audio2 PCI Express x8orDMI (2 GB/s)1066 / 800 MHz FSBCore 1L2 Cache(for Core 1)Core 0L2 Cache(for Core 0)6 USB 2.0Intel Matrix StorageBI

4、OS SupportIntel Pro 1000 LAN91.多處理器結(jié)構(gòu)2.帶緩存的多處理器結(jié)構(gòu)總線仲裁機(jī)制：集中式和非集中式基于總線的多處理機(jī)基于總線的多處理機(jī)CPU內(nèi)存總線(a)總線(b)緩存CPUCPUCPU內(nèi)存緩存CPU緩存CPU10通寫緩沖通寫緩沖(write-though)一致性協(xié)議一致性協(xié)議事件對本地CPU操作響應(yīng)對遠(yuǎn)程CPU響應(yīng)讀失?。╩iss）從內(nèi)存中取得數(shù)據(jù)并存儲到緩存中（MC）（無動作）讀命中(hit)從本地緩存中取得數(shù)據(jù)（無動作）寫失敗更新內(nèi)存中的數(shù)據(jù)并存儲到緩存中（ C M ）（無動作）寫命中更新存儲器和緩存（MC M ）置為無效11緩存擁有權(quán)（緩存擁有權(quán)（owne

5、rship）協(xié)議）協(xié)議lCache分成若干個cache塊l每個Cache塊處于三種狀態(tài)：1.Invalid數(shù)據(jù)無效2.Clean與存儲器數(shù)據(jù)一致3.Dirty數(shù)據(jù)被更新，與存儲器數(shù)據(jù)不一致l各CPU監(jiān)聽（snoopy）其它CPU在總線的操作12緩存擁有權(quán)（緩存擁有權(quán)（ownership）協(xié)議）協(xié)議l多個CPU可有讀擁有權(quán)l(xiāng)只有一個CPU有寫擁有權(quán)l(xiāng)當(dāng)一個CPU寫一個數(shù)據(jù)取得對該數(shù)據(jù)的擁有權(quán)其它CPU將該數(shù)據(jù)的緩存塊置為“invalid”在本地緩存塊中，寫數(shù)據(jù)，并置為“dirty”適當(dāng)時候，刷新存儲區(qū)，或提供給其它CPU13緩存擁有權(quán)（緩存擁有權(quán)（ownership）協(xié)議）協(xié)議l特點1.通過各C

6、PU對總線的監(jiān)聽保持緩存一致性2.該協(xié)議實現(xiàn)在存儲器管理單元中3.整個算法在一個存儲器周期中完成召回（callback）協(xié)議如果用軟件實現(xiàn)14緩存擁有權(quán)協(xié)議操作過程緩存擁有權(quán)協(xié)議操作過程15緩存擁有權(quán)協(xié)議操作過程緩存擁有權(quán)協(xié)議操作過程16重要屬性重要屬性l緩存對總線的監(jiān)聽保證了一致性。l協(xié)議建立在存儲器管理單元中。l整個算法在一個存儲器周期中完成。 17基于環(huán)的多處理機(jī)基于環(huán)的多處理機(jī)沒有集中式全局存儲器耦合得較松一些 (a)Memnet環(huán) (b)單一主機(jī) (c)塊表 18交換式多處理機(jī)交換式多處理機(jī)lCPU增加到一定數(shù)量時，總線或環(huán)的帶寬達(dá)到飽和，再增加額外的CPU也不會提高系統(tǒng)性能減少通信

7、流量l采用兩種方法解決帶寬不足的問題l減少通信流量改善緩沖協(xié)議，優(yōu)化塊大小，重組程序，以提高存儲器訪問的本地命中率。 l增加通信容量改變拓?fù)浣Y(jié)構(gòu) 為系統(tǒng)建立層次結(jié)構(gòu) 19(a) 三個簇由簇間總線連接組成一個超級簇三個簇由簇間總線連接組成一個超級簇 (b) 由超級簇總線相連的兩個超級簇由超級簇總線相連的兩個超級簇分級層次結(jié)構(gòu)分級層次結(jié)構(gòu)20DASH示例示例l目錄目錄每一簇都以目錄來記錄哪些簇現(xiàn)在擁有哪些塊的拷貝 l緩存（緩存（caching）緩存分為兩級：第一級緩存和更大的第二級緩存 l協(xié)議（協(xié)議（protocul）DASH協(xié)議是基于擁有權(quán)和置無效的 21NUMA多處理機(jī)多處理機(jī)l和傳統(tǒng)UMA(

8、Uniform Memory Access)多處理機(jī)一樣，NUMA機(jī)的虛擬地址空間對所有CPU都可見。任何CPU在地址A寫入值，接下來別的處理機(jī)對A的讀操作將讀取剛剛寫入的值。lUMA與NUMA的區(qū)別不是在語義上，而是在性能上。在NUMA機(jī)上，訪問遠(yuǎn)程存儲器要比訪問本地存儲器慢得多，而硬件緩存并不試圖掩蓋這個問題。 22NUMA示例示例23NUMA多處理機(jī)的屬性多處理機(jī)的屬性 l可以訪問遠(yuǎn)程存儲器。l訪問遠(yuǎn)程存儲器比訪問本地存儲器慢。l沒有緩沖機(jī)制隱藏訪問遠(yuǎn)程存儲器的時間。 24分布式共享系統(tǒng)的比較分布式共享系統(tǒng)的比較 25六種共享處理器系統(tǒng)的比較六種共享處理器系統(tǒng)的比較 項多處理機(jī)DSM單總

9、線交換NUMA基于頁式共享變量基于對象線性、共享虛擬地址空間嗎？是是是是否否可能的操作讀/寫讀/寫讀/寫讀/寫讀/寫常規(guī)有封裝及方法？否否否否否是是否由硬件執(zhí)行遠(yuǎn)程訪問？是是是否否否有獨立存儲器？是是是否否否誰將遠(yuǎn)程存儲器的訪問轉(zhuǎn)化為消息？MMUMMUMMU操作系統(tǒng)運行期系統(tǒng)運行期系統(tǒng)傳輸介質(zhì)總線總線總線網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)誰執(zhí)行數(shù)據(jù)遷移硬件硬件軟件軟件軟件軟件傳輸單元塊塊頁頁共享變量對象26主要內(nèi)容主要內(nèi)容6.1 共享內(nèi)存6.2 一致性模型一致性模型6.3 基于頁面的DSM6.4 其它的分布式共享內(nèi)存276.2 一致性模型一致性模型 只允許有一個拷貝可能會帶來嚴(yán)重的性能瓶頸。允許多重拷貝可以就簡化性

10、能問題。但這又引起了新的問題：即如何保證所有拷貝的一致性。 l緩存一致性（coherency）數(shù)據(jù)在各個緩存中的值保持一致l一致性模型軟件與存儲器間的約定（contract）如果軟件遵守約定的規(guī)則，存儲器就能工作正常。如果軟件違反了這些規(guī)定，存儲器就不再保證操作的正確性 28嚴(yán)格一致性嚴(yán)格一致性l從存儲器地址X處讀出的值為最近寫入X的值 l非嚴(yán)格一致性P1: W(x)1P2: R(x)1P1: W(x)1P2: R(x)0 R(x)129順序一致性順序一致性l如果所有進(jìn)程以一定的順序執(zhí)行操作，每一進(jìn)程的操作都以程序規(guī)定的順序出現(xiàn)，則任何操作的結(jié)果都是一樣的。l每一進(jìn)程的操作都按程序規(guī)定的順序執(zhí)

11、行。l所有進(jìn)程看到相同的內(nèi)存訪問操作次序l運行同一個程序得到的兩個可能的結(jié)果P1: W(x)1P2: R(x)0 R(x)1P1: W(x)1P2: R(x)1 R(x)130l3個并行執(zhí)行的進(jìn)程l4種正確的執(zhí)行順序順序一致性舉例順序一致性舉例print(b,c);(a)a=1;print(a,c);(b)b=1;print(a,b);(c)c=1;a=1;a=1;b=1;b=1; print(b,c);b=1;c=1;a=1;b=1;print(a,c);print(a,b); c=1;print(a,c);print(b,c);print(a,c);print(a,c);c=1; c=1;

12、a=1; print(b,c);print(a,c);print(a,b);print(b,c);print(a,b); (a) (b) (c) (d)31因果一致性因果一致性l按有無可能的因果聯(lián)系區(qū)分各事件，對于因果相關(guān)的寫操作，所有進(jìn)程看到的執(zhí)行順序應(yīng)相同。l可能因果相關(guān)的寫操作應(yīng)對所有進(jìn)程可見，且順序一致。并發(fā)寫操作在不同機(jī)器看來順序可能是不同的 P1：W(x)1 W(x)3P2： R(x)1 W(x)2P3： R(x)1 R(x)3 R(x)2P4： R(x)1 R(x)2 R(x)3因果一致性存儲器允許的序列,但是順序一致性 存儲器和嚴(yán)格一致性存儲器不允許 32因果一致性舉例因果一致

13、性舉例（1）違反因果一致性（2）符合因果一致性P1：W(x)1P2： R(x)1 W(x)2P3： R(x)2 R(x)1P4： R(x)1 R(x)2P1：W(x)1P2： W(x)2P3： R(x)2 R(x)1P4： R(x)1 R(x)233管道內(nèi)存（管道內(nèi)存（PRAM ）一致性）一致性l同一個進(jìn)程的寫操作的執(zhí)行次序，其它進(jìn)程看到的都相同l不同進(jìn)程的寫操作的執(zhí)行次序，不同進(jìn)程看到的可以是不同的l例：符合PRAM一致性，但不符合因果一致性P1：W(x)1P2： R(x)1 W(x)2P3： R(x)1 R(x)2P4： R(x)2 R(x)134管道內(nèi)存（管道內(nèi)存（PRAM ）一致性示例

14、）一致性示例a=1; a=1; b=1;*print(b,c)b=1; print(a,c)b=1; *print(a,c) c=1;print(a,c)print(b,c)*print(a,b)c=1; c=1; a=1;print(a,b)print(a,b)print(b,c)Prints:00Prints:10Prints:01 (a) (b) (c)print(b,c);(a)a=1;print(a,c);(b)b=1;print(a,b);(c)c=1;35處理機(jī)一致性處理機(jī)一致性l與PRAM一致性相似l附加條件：存儲相關(guān)性：對于任意存儲器地址X, 對于寫入X的順序是全局一致的。寫

15、入不同地址,對于不同進(jìn)程來看,不需要相同順序 36弱一致性弱一致性l同步變量：廣播導(dǎo)出所有寫操作，導(dǎo)入所有寫操作 l對同步變量的訪問必須是順序一致性的。l在所有前面的寫操作完成之前,不能訪問同步變量。l在前面所有同步變量的訪問完成前,不能訪問（讀或?qū)懀?shù)據(jù)。 P1：W(x)1 W(x)2 SP2： R(x)1 R(x)2 SP3： R(x)2 R(x)1 SP1: W(x)1 W(x)2 SP2: S R(x)137釋放一致性釋放一致性l獲取（acquire）訪問用于通知存儲器系統(tǒng)臨界區(qū)已就緒 l釋放(release)訪問表明臨界區(qū)剛退出。 l規(guī)則在訪問共享變量前，所有先前的acquire都必

16、須完成。在進(jìn)行release前，先前的所有讀寫操作都必須結(jié)束。acquire和release訪問必須滿足處理機(jī)一致性38釋放一致性釋放一致性P1：Acq(L) W(x)1 W(x)2 Rel(L) P2： Acq(L) R(x)2 Rel(L) P3： R(x)1l通常，分布式共享存儲器在遵守以下規(guī)定時就是釋放一致的：在訪問共享變量前，進(jìn)程所有先前的獲取訪問都必須成功地完成。在允許釋放訪問前，進(jìn)程先前的所有讀寫操作都必須結(jié)束。獲取訪問和釋放訪問必須是處理器一致的。 39釋放一致性的應(yīng)用釋放一致性的應(yīng)用 l急性釋放一致性(EAGER release consistency)當(dāng)執(zhí)行了釋放操作，執(zhí)行

17、此操作的處理機(jī)將所有修改的數(shù)據(jù)傳給所有那些已經(jīng)有其緩沖拷貝且可能需要它的處理機(jī) l惰性釋放一致性（LAZY release consistency）在執(zhí)行釋放時，不發(fā)送任何數(shù)據(jù)。在執(zhí)行獲取操作時，處理機(jī)試圖從擁有這些變量的機(jī)器上取得它們的最新值 40入口一致性入口一致性當(dāng)存儲器滿足下列所有條件時，就成為入口一致性存儲器 ：（1）只有某一進(jìn)程的保護(hù)共享變量全部被更新以后，該進(jìn)程才允許執(zhí)行同步變量的獲取訪問；（2）在一進(jìn)程以互斥模式訪問該進(jìn)程的同步變量之前，不允許其他進(jìn)程持有此同步變量，即使在非互斥模式下；（3）在結(jié)束互斥模式下對一個同步變量的訪問后，任意其他進(jìn)程必須與該變量的擁有者核查，才能試圖

18、以非互斥模式訪問該同步變量。41一致性模型總結(jié)一致性模型總結(jié)不用同步操作的一致性模型不用同步操作的一致性模型 一致性說明嚴(yán)格所有的共享訪問事件都有絕對時間順序順序所有進(jìn)程都以相同的順序檢測到所有的共享訪問事件因果所有進(jìn)程都以相同的順序檢測到所有因果聯(lián)系的事件PRAM所有的進(jìn)程按照預(yù)定的順序檢測到來自一個處理器的寫操作,來自其它處理器的寫操作不必以相同的順序看見處理器PRAM一致性+存儲器相關(guān)性42一致性模型總結(jié)一致性模型總結(jié)使用同步操作的一致性模型使用同步操作的一致性模型 一致性說明弱同步完成后,共享數(shù)據(jù)才可能保持一致釋放當(dāng)離開臨界區(qū)時,共享數(shù)據(jù)就保持一致入口當(dāng)進(jìn)入臨界區(qū)時,和該臨界區(qū)相關(guān)的共

19、享數(shù)據(jù)保持一致43主要內(nèi)容主要內(nèi)容6.1 共享內(nèi)存6.2 一致性模型6.3 基于頁面的基于頁面的DSM6.4 其它的分布式共享內(nèi)存446.3 基于頁面的基于頁面的DSM 局域網(wǎng)上的工作站從根本上不同于多處理機(jī)。處理機(jī)只能訪問本地存儲器。不像在NUMA或UMA多處理機(jī)系統(tǒng)中，這里沒有全局共享變量的概念。然而，DSM的目的就是在系統(tǒng)中增加軟件，以允許多計算機(jī)系統(tǒng)運行多處理機(jī)上的程序。 45基本設(shè)計基本設(shè)計 l頁塊：地址空間管理的基本單位0 1 2 3 4 5 6 7 8 9CPU 10259CPU 21368CPU 347CPU 4存儲器(a)全局共享地址空間10 111512 131411101

20、2 1413 15(b)CPU 10259CPU 21368CPU 347CPU 41112 1413 1510(c)CPU 10259CPU 21368CPU 347CPU 4111012 1413 151046實現(xiàn)技術(shù)實現(xiàn)技術(shù)l虛擬地址空間l內(nèi)存映射（memory mapping）l缺頁中斷（pagefault）47存儲映射技術(shù)存儲映射技術(shù)l兩個進(jìn)程共享同一個文件48存儲映射技術(shù)存儲映射技術(shù)ls is an error code addr are memory addressesllen is a length prot controls protectionlflags are misc

21、ellaneous bitslfd is a file descriptor offset is a file offset49l復(fù)制復(fù)制只讀塊 復(fù)制所有頁塊 l 粒度（Guanularity） 頁塊的大小應(yīng)是多大：字、塊（少量字）、頁或段（多個頁）。 包含兩個無關(guān)變量的頁的錯誤共享50實現(xiàn)順序一致性（實現(xiàn)順序一致性（Sequential Consistency） l多處理機(jī)一般有兩種處理方法 ：更新置無效 l基于分頁的DSM系統(tǒng)通常使用置無效協(xié)議而不是更新協(xié)議 51處理機(jī)讀頁舉例處理機(jī)讀頁舉例 PW擁有者1.讀PR擁有者1.讀PR擁有者1.讀頁面處理器1處理器2RPR1.讀P1.請求復(fù)制2.

22、將頁標(biāo)志為R3.讀PR擁有者R擁有者W擁有者1.請求降級2.請求復(fù)制3.將頁標(biāo)志為R4.讀(a)52處理機(jī)寫頁舉例處理機(jī)寫頁舉例 PW擁有者1.寫PR擁有者1.將頁標(biāo)志為W2.寫入PR擁有者1.無效的拷貝2.將頁標(biāo)志為W3.寫入RPR1.請求置無效2.請求擁有者3.將頁標(biāo)志為W4.寫入P1.請求置無效2.請求擁有者3.請求頁面4.將頁標(biāo)志為W5.寫入PR擁有者R擁有者W擁有者1.請求置無效2.請求擁有者3.請求頁面4.將頁標(biāo)志為W5.寫入(b)53尋找擁有者（尋找擁有者（Finding The Owner） l通過廣播 l擁有者定位協(xié)議(ownership location pretocol) l讓每個進(jìn)程（更可能的是每個處理機(jī)）跟蹤每一頁的可能擁有者 54擁有者定位協(xié)議擁有者定位協(xié)議 l四消息協(xié)議l三消息協(xié)議P擁有者頁面管理器1.請求2.響應(yīng)3.請求4.響應(yīng)P擁有者頁面管理器1.請求3.響應(yīng)2.移交請求(a)(b)55尋找拷貝尋找拷貝.l每個頁面的擁有者通過拷貝集得知哪個其它CPU正共享該頁面每個頁面的擁有者通過拷貝集得知哪個其它CPU正共享該頁面. 頁擁有勸用雙線框表示56頁面置換（頁面置換（Page Replacement） l類似于最近最少使用（LRU）的算法 l置換進(jìn)程擁有的那些復(fù)制頁 57同步同步 l在多處理機(jī)系統(tǒng)