第6章分布式共享存儲(chǔ)

1、第6章 分布式共享存儲(chǔ)分布式共享存儲(chǔ) 中國科技大學(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ī)和多計(jì)算機(jī)回顧l對(duì)硬件的影響 設(shè)計(jì)一種使多個(gè)處理機(jī)同時(shí)使用同一存儲(chǔ)器的機(jī)器是非常困難的 大的多計(jì)算機(jī)系統(tǒng)更易于建立 l對(duì)軟件的影響 用于多處理機(jī)編程的技術(shù)很多，可以使用臨界區(qū)（critical region），信號(hào)量或管程（monitor） 提供必要的互斥。對(duì)多計(jì)算機(jī)系統(tǒng)，通信一般使用消息

2、傳遞，這使輸入/輸出更為抽象。消息傳遞帶來了許多復(fù)雜的問題， 5分布式共享存儲(chǔ)器分布式共享存儲(chǔ)器(DSM) lLi 和Hudak提出讓一組由局域網(wǎng)互連的工作站共享一個(gè)分頁的虛擬地址空間。 l不共享整個(gè)地址空間，而只共享其中所選擇的一部分，即那些由多個(gè)進(jìn)程引用的變量和數(shù)據(jù)結(jié)構(gòu)。 l在多臺(tái)計(jì)算機(jī)上復(fù)制共享變量，通過共享復(fù)制的變量而不是整個(gè)頁，模擬處理機(jī)的問題可簡(jiǎn)化為保證一組數(shù)據(jù)結(jié)構(gòu)的多個(gè)拷貝一致性的問題。 6lDSM的很多研究工作都受到了多處理機(jī)結(jié)構(gòu)發(fā)展的啟發(fā)!l首先比較幾種共享存儲(chǔ)器（內(nèi)存）的多處理機(jī) 7芯片存儲(chǔ)器芯片存儲(chǔ)器 CPU與存儲(chǔ)器連接模型l單片機(jī)l理想的共享存儲(chǔ)器多處理機(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é)議事件對(duì)本地CPU操作響應(yīng)對(duì)遠(yuǎn)程CPU響應(yīng)讀失?。╩iss）從內(nèi)存中取得數(shù)據(jù)并存儲(chǔ)到緩存中（MC）（無動(dòng)作）讀命中(hit)從本地緩存中取得數(shù)據(jù)（無動(dòng)作）寫失敗更新內(nèi)存中的數(shù)據(jù)并存儲(chǔ)到緩存中（ C M ）（無動(dòng)作）寫命中更新存儲(chǔ)器和緩存（MC M ）置為無效11緩存擁有權(quán)（緩存擁有權(quán)（owne

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

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

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

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

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

10、能問題。但這又引起了新的問題：即如何保證所有拷貝的一致性。 l緩存一致性（coherency）數(shù)據(jù)在各個(gè)緩存中的值保持一致l一致性模型軟件與存儲(chǔ)器間的約定（contract）如果軟件遵守約定的規(guī)則，存儲(chǔ)器就能工作正常。如果軟件違反了這些規(guī)定，存儲(chǔ)器就不再保證操作的正確性 28嚴(yán)格一致性嚴(yán)格一致性l從存儲(chǔ)器地址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運(yùn)行同一個(gè)程序得到的兩個(gè)可能的結(jié)果P1: W(x)1P2: R(x)0 R(x)1P1: W(x)1P2: R(x)1 R(x)130l3個(gè)并行執(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ū)分各事件，對(duì)于因果相關(guān)的寫操作，所有進(jìn)程看到的執(zhí)行順序應(yīng)相同。l可能因果相關(guān)的寫操作應(yīng)對(duì)所有進(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因果一致性存儲(chǔ)器允許的序列,但是順序一致性 存儲(chǔ)器和嚴(yán)格一致性存儲(chǔ)器不允許 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同一個(gè)進(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附加條件：存儲(chǔ)相關(guān)性：對(duì)于任意存儲(chǔ)器地址X, 對(duì)于寫入X的順序是全局一致的。寫

15、入不同地址,對(duì)于不同進(jìn)程來看,不需要相同順序 36弱一致性弱一致性l同步變量：廣播導(dǎo)出所有寫操作，導(dǎo)入所有寫操作 l對(duì)同步變量的訪問必須是順序一致性的。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獲?。╝cquire）訪問用于通知存儲(chǔ)器系統(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通常，分布式共享存儲(chǔ)器在遵守以下規(guī)定時(shí)就是釋放一致的：在訪問共享變量前，進(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í)行釋放時(shí)，不發(fā)送任何數(shù)據(jù)。在執(zhí)行獲取操作時(shí)，處理機(jī)試圖從擁有這些變量的機(jī)器上取得它們的最新值 40入口一致性入口一致性當(dāng)存儲(chǔ)器滿足下列所有條件時(shí)，就成為入口一致性存儲(chǔ)器 ：（1）只有某一進(jìn)程的保護(hù)共享變量全部被更新以后，該進(jìn)程才允許執(zhí)行同步變量的獲取訪問；（2）在一進(jìn)程以互斥模式訪問該進(jìn)程的同步變量之前，不允許其他進(jìn)程持有此同步變量，即使在非互斥模式下；（3）在結(jié)束互斥模式下對(duì)一個(gè)同步變量的訪問后，任意其他進(jìn)程必須與該變量的擁有者核查，才能試圖

18、以非互斥模式訪問該同步變量。41一致性模型總結(jié)一致性模型總結(jié)不用同步操作的一致性模型不用同步操作的一致性模型 一致性說明嚴(yán)格所有的共享訪問事件都有絕對(duì)時(shí)間順序順序所有進(jìn)程都以相同的順序檢測(cè)到所有的共享訪問事件因果所有進(jìn)程都以相同的順序檢測(cè)到所有因果聯(lián)系的事件PRAM所有的進(jìn)程按照預(yù)定的順序檢測(cè)到來自一個(gè)處理器的寫操作,來自其它處理器的寫操作不必以相同的順序看見處理器PRAM一致性+存儲(chǔ)器相關(guān)性42一致性模型總結(jié)一致性模型總結(jié)使用同步操作的一致性模型使用同步操作的一致性模型 一致性說明弱同步完成后,共享數(shù)據(jù)才可能保持一致釋放當(dāng)離開臨界區(qū)時(shí),共享數(shù)據(jù)就保持一致入口當(dāng)進(jìn)入臨界區(qū)時(shí),和該臨界區(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ī)只能訪問本地存儲(chǔ)器。不像在NUMA或UMA多處理機(jī)系統(tǒng)中，這里沒有全局共享變量的概念。然而，DSM的目的就是在系統(tǒng)中增加軟件，以允許多計(jì)算機(jī)系統(tǒng)運(yùn)行多處理機(jī)上的程序。 45基本設(shè)計(jì)基本設(shè)計(jì) l頁塊：地址空間管理的基本單位0 1 2 3 4 5 6 7 8 9CPU 10259CPU 21368CPU 347CPU 4存儲(chǔ)器(a)全局共享地址空間10 111512 131411101

20、2 1413 15(b)CPU 10259CPU 21368CPU 347CPU 41112 1413 1510(c)CPU 10259CPU 21368CPU 347CPU 4111012 1413 151046實(shí)現(xiàn)技術(shù)實(shí)現(xiàn)技術(shù)l虛擬地址空間l內(nèi)存映射（memory mapping）l缺頁中斷（pagefault）47存儲(chǔ)映射技術(shù)存儲(chǔ)映射技術(shù)l兩個(gè)進(jìn)程共享同一個(gè)文件48存儲(chǔ)映射技術(shù)存儲(chǔ)映射技術(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)是多大：字、塊（少量字）、頁或段（多個(gè)頁）。 包含兩個(gè)無關(guān)變量的頁的錯(cuò)誤共享50實(shí)現(xiàn)順序一致性（實(shí)現(xiàn)順序一致性（Sequential Consistency） l多處理機(jī)一般有兩種處理方法 ：更新置無效 l基于分頁的DSM系統(tǒng)通常使用置無效協(xié)議而不是更新協(xié)議 51處理機(jī)讀頁舉例處理機(jī)讀頁舉例 PW擁有者1.讀PR擁有者1.讀PR擁有者1.讀頁面處理器1處理器2RPR1.讀P1.請(qǐng)求復(fù)制2.

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