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

分布式共享存儲(chǔ)器第1頁(yè)/共73頁(yè)6.1簡(jiǎn)介并行及分布式計(jì)算機(jī)系統(tǒng)分類

并行分布式計(jì)算機(jī)多處理機(jī)（共享存儲(chǔ)器）多計(jì)算機(jī)（私有存儲(chǔ)器）總線型總線型交換型交換型MIMD松耦合緊耦合SequentEncore超級(jí)計(jì)算機(jī)RP3LAN工作站

超立方體Transputer第2頁(yè)/共73頁(yè)6.1簡(jiǎn)介

基于總線的多處理機(jī)

基于總線的多處理機(jī)由若干個(gè)CPU組成，它們都連接到一個(gè)公共的總線上，并且共享一個(gè)存儲(chǔ)器模塊。為了避免總線過(guò)載，需要高速緩存，但帶來(lái)了不一致問(wèn)題。連接的CPU數(shù)量有限。CacheCPUBusCacheCPUCacheCPUMemory第3頁(yè)/共73頁(yè)6.1簡(jiǎn)介交換型多處理機(jī)將存儲(chǔ)器分成許多存儲(chǔ)器模塊，用十字交叉開關(guān)將它們與CPU相連。MMMMCCCC優(yōu)點(diǎn)：多個(gè)CPU能夠同時(shí)訪問(wèn)存儲(chǔ)器。缺點(diǎn)：n個(gè)CPU和n個(gè)存儲(chǔ)器模塊，需要n2個(gè)交叉開關(guān)。第4頁(yè)/共73頁(yè)6.1簡(jiǎn)介交換型多處理機(jī)Omega網(wǎng)絡(luò)結(jié)論

需要的交叉開關(guān)數(shù)量多，需要解決交換延遲，價(jià)格昂貴。建立一個(gè)大的、緊密偶合的、共享存儲(chǔ)器的多處理機(jī)系統(tǒng)是困難的。CCCCMMMM2x2開關(guān)第5頁(yè)/共73頁(yè)6.1簡(jiǎn)介基于總線的多計(jì)算機(jī)每個(gè)CPU都與它自身的存儲(chǔ)器直接相連。由于僅是CPU和CPU之間的通信，通信量比當(dāng)互連網(wǎng)絡(luò)用于CPU和存儲(chǔ)器之間的通信量低幾個(gè)數(shù)量級(jí)。CPULocalmemory網(wǎng)絡(luò)CPULocalmemoryCPULocalmemory圖1-4局域網(wǎng)上由多臺(tái)工作站組成的計(jì)算機(jī)系統(tǒng)工作站工作站工作站第6頁(yè)/共73頁(yè)6.1簡(jiǎn)介交換型多計(jì)算機(jī)

兩種流行的拓?fù)浣Y(jié)構(gòu)：網(wǎng)格和超立方體第7頁(yè)/共73頁(yè)6.1

簡(jiǎn)介多處理機(jī)和多計(jì)算機(jī)的比較從硬件角度

設(shè)計(jì)一種使多個(gè)處理機(jī)同時(shí)使用同一存儲(chǔ)器的機(jī)器是非常困難的。由于總線會(huì)成為一種瓶頸，基于總線的多處理機(jī)總數(shù)最多只能有幾個(gè)。交換式多處理機(jī)可應(yīng)用于大系統(tǒng)，但相比之下過(guò)于昂貴、緩慢、復(fù)雜以及難以維護(hù)。大的多計(jì)算機(jī)系統(tǒng)易于建立，單主板計(jì)算機(jī)（包含一個(gè)CPU、一個(gè)存儲(chǔ)器、一個(gè)網(wǎng)絡(luò)接口）可以相互連接在一起，不受數(shù)量的限制。

結(jié)論：從硬件設(shè)計(jì)者的角度看，多計(jì)算機(jī)系統(tǒng)比多處理機(jī)系統(tǒng)更優(yōu)越。第8頁(yè)/共73頁(yè)6.1

簡(jiǎn)介多處理機(jī)和多計(jì)算機(jī)的比較從軟件角度

用于多處理機(jī)編程的技術(shù)很多。大量的理論和實(shí)踐知識(shí)可用于多處理機(jī)編程。對(duì)于多計(jì)算機(jī)系統(tǒng)，通信一般使用消息傳遞。復(fù)雜。

結(jié)論：從軟件設(shè)計(jì)者的角度看，多處理機(jī)系統(tǒng)比多計(jì)算機(jī)系統(tǒng)更優(yōu)越。

多計(jì)算機(jī)系統(tǒng)易于建立但難于編程，多處理機(jī)系統(tǒng)易于編程但難于建立！第9頁(yè)/共73頁(yè)6.1簡(jiǎn)介分布式共享存儲(chǔ)器設(shè)計(jì)思想一組由局域網(wǎng)互聯(lián)的工作站共享一個(gè)分頁(yè)的虛擬地址空間。設(shè)置每頁(yè)剛好在一臺(tái)機(jī)器上。對(duì)本地頁(yè)的訪問(wèn)由硬件實(shí)現(xiàn)。試圖訪問(wèn)其他機(jī)器上的頁(yè)時(shí)，由操作系統(tǒng)處理。既易于編程，又易于建立！與虛擬存儲(chǔ)器系統(tǒng)比較相同點(diǎn)：當(dāng)一進(jìn)程訪問(wèn)一未駐留存儲(chǔ)器的頁(yè)時(shí)，激活陷阱，操作系統(tǒng)獲取相應(yīng)頁(yè)并將其調(diào)入。不同點(diǎn)：操作系統(tǒng)不是從磁盤而是通過(guò)網(wǎng)絡(luò)從另一個(gè)處理機(jī)中獲取頁(yè)。

第10頁(yè)/共73頁(yè)6.1簡(jiǎn)介分布式共享存儲(chǔ)器不足之處頁(yè)在網(wǎng)上頻繁的調(diào)入調(diào)出。改進(jìn)不共享整個(gè)地址空間，而只共享那些由多個(gè)進(jìn)程引用的變量和數(shù)據(jù)結(jié)構(gòu)。在多臺(tái)計(jì)算機(jī)上復(fù)制共享變量，通過(guò)共享復(fù)制的變量而不是整個(gè)頁(yè)。讀操作可以可以在本地進(jìn)行而不引起任何的網(wǎng)絡(luò)通信，寫則可以通過(guò)多拷貝更新協(xié)議完成。

第11頁(yè)/共73頁(yè)6.2共享存儲(chǔ)器6.2.1芯片存儲(chǔ)器芯片包含CPU和存儲(chǔ)器。CPU和存儲(chǔ)器通過(guò)地址線和數(shù)據(jù)線直接相連。廣泛用于汽車、電氣用具、玩具等。將芯片擴(kuò)展，使多個(gè)CPU可以共享同一存儲(chǔ)器。不僅復(fù)雜，而且非常昂貴和不實(shí)用。第12頁(yè)/共73頁(yè)6.2共享存儲(chǔ)器6.2.2基于總線的多處理機(jī)基于總線的多處理機(jī)：當(dāng)任一CPU要從存儲(chǔ)器中讀取數(shù)據(jù)時(shí)，它將數(shù)據(jù)的地址放在總線上，并在控制總線上加上“讀”信號(hào)。存儲(chǔ)器讀出需要的數(shù)據(jù)，將其放在總線上，在控制總線上加“準(zhǔn)備好”信號(hào)，CPU可讀到相應(yīng)的數(shù)據(jù)。為防止多個(gè)CPU同時(shí)訪問(wèn)存儲(chǔ)器，需要總線仲裁機(jī)制。CPU總線CPUCPU存儲(chǔ)器第13頁(yè)/共73頁(yè)6.2共享存儲(chǔ)器6.2.2基于總線的多處理機(jī)基于總線的多處理機(jī)容易超載。為了降低總線負(fù)載，將每個(gè)CPU提供一個(gè)監(jiān)聽高速緩存。緩存一致性協(xié)議總線存儲(chǔ)器CPU緩存CPU緩存CPU緩存第14頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.2基于總線的多處理機(jī)通寫緩存一致性協(xié)議

事件緩存響應(yīng)本地CPU操作時(shí)執(zhí)行的動(dòng)作緩存響應(yīng)遠(yuǎn)程CPU操作時(shí)執(zhí)行的動(dòng)作讀失敗從存儲(chǔ)器中取得數(shù)據(jù)并存儲(chǔ)到緩存中無(wú)動(dòng)作讀命中從本地緩存中取得數(shù)據(jù)無(wú)動(dòng)作寫失敗更新存儲(chǔ)器中的數(shù)據(jù)并存儲(chǔ)到緩存中無(wú)動(dòng)作寫命中更新存儲(chǔ)器和緩存使緩存項(xiàng)無(wú)效易于理解和使用。缺點(diǎn)：所有寫操作必須通過(guò)總線。第15頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.2基于總線的多處理機(jī)Writeonce協(xié)議

思想：允許正被多個(gè)CPU讀取的字出現(xiàn)在它們所有的緩存中。而僅被一個(gè)CPU經(jīng)常寫的字將只保存在它的緩存中，為減少總線流量，不必每次都寫回存儲(chǔ)器。該協(xié)議管理緩存塊，每個(gè)塊處于以下三種狀態(tài)之一：無(wú)效——本緩存塊無(wú)有效數(shù)據(jù)干凈——存儲(chǔ)器被更新，該塊可能在別的緩存中臟——存儲(chǔ)器錯(cuò)誤，該數(shù)據(jù)塊不在其他緩存中第16頁(yè)/共73頁(yè)Writeonce協(xié)議初始狀態(tài)含有值W1的字W在主存中，同時(shí)也在B的緩存中。ABCW1W1CPU干凈存儲(chǔ)器正確圖6-3（a）第17頁(yè)/共73頁(yè)Writeonce協(xié)議A讀取字W獲取W1，B不響應(yīng)讀操作，只是內(nèi)存響應(yīng)。ABCW1W1W1CPU干凈存儲(chǔ)器正確干凈圖6-3（b）第18頁(yè)/共73頁(yè)Writeonce協(xié)議A寫入值W2，B在總線上監(jiān)聽，一旦發(fā)現(xiàn)寫操作，將自己的緩存項(xiàng)置無(wú)效。A的拷貝標(biāo)記為臟數(shù)據(jù)。ABCW1W2W1CPU無(wú)效存儲(chǔ)器錯(cuò)誤臟圖6-3（c）第19頁(yè)/共73頁(yè)Writeonce協(xié)議A再次寫W，A所進(jìn)行的這些和以后的寫操作都在本地執(zhí)行，沒(méi)有任何的總線通信。ABCW1W3W1CPU無(wú)效存儲(chǔ)器錯(cuò)誤臟圖6-3（d）第20頁(yè)/共73頁(yè)Writeonce協(xié)議C讀寫W，A通過(guò)在總線上監(jiān)聽而發(fā)現(xiàn)請(qǐng)求，則發(fā)信號(hào)禁止存儲(chǔ)器響應(yīng)。然后A提供C所需要的字，并將自己的緩存項(xiàng)置無(wú)效。C發(fā)現(xiàn)該字來(lái)自其他的緩存而不是存儲(chǔ)器，并且其狀態(tài)為Dirty，則響應(yīng)的標(biāo)示為dirty。C現(xiàn)在有唯一的有效的拷貝。ABCW1W3W1W3CPU無(wú)效存儲(chǔ)器錯(cuò)誤無(wú)效圖6-3（e）臟第21頁(yè)/共73頁(yè)Writeonce協(xié)議存儲(chǔ)器何時(shí)更新？當(dāng)緩存缺乏空間而必須清除某一字時(shí)，如果該字的狀態(tài)為dirty。那時(shí)，該字從所有的緩存中消失，寫回到存儲(chǔ)器。緩存一致性協(xié)議具有三個(gè)重要的屬性緩存對(duì)總線的監(jiān)聽保證了一致性。協(xié)議建立在存儲(chǔ)器管理單元中整個(gè)算法在一個(gè)存儲(chǔ)器周期中完成第22頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.3基于環(huán)的多處理機(jī)一個(gè)獨(dú)立的地址空間被分成一個(gè)私有區(qū)和一個(gè)共享區(qū)。私有區(qū)被分成段，使得每個(gè)機(jī)器都有一個(gè)段用來(lái)存放堆棧和其他非共享的數(shù)據(jù)和代碼。共享區(qū)對(duì)所有的機(jī)器都是一樣的。共享存儲(chǔ)器被分成32字節(jié)的塊，是機(jī)器間傳輸?shù)膯卧?。Memnet環(huán)第23頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.3基于環(huán)的多處理機(jī)環(huán)接口、MMU（存儲(chǔ)器管理單元）、緩存和一部分存儲(chǔ)器集成在一個(gè)稱為Memnet設(shè)備的器件中。Memnet中沒(méi)有集中式的全局存儲(chǔ)器。共享地址空間中的每個(gè)32字節(jié)數(shù)據(jù)塊都有一個(gè)屬主機(jī)器。屬主機(jī)器在其屬主存儲(chǔ)器域中為32字節(jié)數(shù)據(jù)塊保留物理存儲(chǔ)器。數(shù)據(jù)塊可被置于除屬主機(jī)器以外的任何機(jī)器的緩存中。單一主機(jī)第24頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.3基于環(huán)的多處理機(jī)每個(gè)機(jī)器的Memnet設(shè)備上有一個(gè)塊表，包括每個(gè)塊在共享地址空間的入口，以塊序號(hào)為索引。塊表有效位：判斷塊是否在緩存中且已被更新互斥位：確定本地拷貝是否唯一屬主位：只有當(dāng)本機(jī)是該塊的屬主機(jī)器時(shí)才置位。中斷位：用于強(qiáng)制中斷定位位：表明若塊存在并有效，它定位在緩存中何處。第25頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.3基于環(huán)的多處理機(jī)讀操作當(dāng)CPU要從共享存儲(chǔ)器中讀一個(gè)字時(shí)，該存儲(chǔ)器地址傳送給Memnet設(shè)備，Memnet設(shè)備檢查表項(xiàng)以確定該塊是否存在。若存在，讀請(qǐng)求立即的到滿足。否則，Memnet設(shè)備捕獲令牌，將請(qǐng)求信包送入環(huán)中。請(qǐng)求信包包含目標(biāo)地址和32字節(jié)的啞域。信包在環(huán)中傳遞，每個(gè)Memnet設(shè)備檢查自己是否有所需的塊，若有則將塊置于啞域。第26頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.3基于環(huán)的多處理機(jī)寫操作若包含要寫字的塊存在于本地并且是系統(tǒng)中的唯一拷貝，字就在本地寫入。若所需塊在本地存在，但不是系統(tǒng)中的唯一拷貝

CPU將在環(huán)中發(fā)出置無(wú)效信包，強(qiáng)制其它機(jī)器拋棄此塊的拷貝。

置無(wú)效信包返回時(shí)，將該塊的互斥位置位，字在本地寫入。第27頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.3基于環(huán)的多處理機(jī)寫操作若本地不存在所需塊，CPU發(fā)出包含讀請(qǐng)求和置無(wú)效請(qǐng)求的信包。第一個(gè)有此數(shù)據(jù)塊的機(jī)器將該塊拷入信包，同時(shí)拋棄自己的拷貝。其余機(jī)器僅從自己的緩存中拋棄該數(shù)據(jù)塊。當(dāng)信包返回到發(fā)送者時(shí)，本地存儲(chǔ)該數(shù)據(jù)塊并執(zhí)行寫操作。第28頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.3基于環(huán)的多處理機(jī)Memnet和基于總線的多處理機(jī)比較相似之處：讀操作返回的都是最近寫入的值。讀操作時(shí)，數(shù)據(jù)塊可能在一個(gè)緩存中，也可能在多個(gè)緩存中。寫操作時(shí)，數(shù)據(jù)塊只能在一個(gè)緩存中。區(qū)別：基于總線的多處理機(jī)是緊耦合的，基于環(huán)的多處理機(jī)是耦合的較松一些?；诃h(huán)的多處理機(jī)沒(méi)有集中式全局存儲(chǔ)器。第29頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.4交換式多處理機(jī)基于總線和基于環(huán)的多處理機(jī)當(dāng)CPU增加到一定數(shù)量時(shí)，總線或環(huán)的帶寬達(dá)到飽和。兩種方法解決帶寬不足問(wèn)題：減少通信流量增加通信容量增加總線帶寬改變互聯(lián)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，增加通信容量。建立層次結(jié)構(gòu)第30頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.4交換式多處理機(jī)建立層次結(jié)構(gòu)仍在一根總線上掛一些CPU，當(dāng)將整個(gè)單元看作一個(gè)簇。系統(tǒng)中有多個(gè)簇，用簇間總線相連。簇內(nèi)總線簇間總線超級(jí)簇間總線第31頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.4交換式多處理機(jī)基于網(wǎng)狀簇的分層設(shè)計(jì)16個(gè)簇、每簇有一條總線，4個(gè)CPU，16M全局存儲(chǔ)器和一些I/O設(shè)備總共地址空間256M，分為16塊，每塊16M存儲(chǔ)器以16字節(jié)的塊為單位，因此1簇有1M存儲(chǔ)器塊。第32頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.4交換式多處理機(jī)目錄記錄哪些簇?fù)碛心男K的拷貝。因?yàn)槊看赜?M存儲(chǔ)塊，目錄中有1M個(gè)項(xiàng)。每一簇的每個(gè)表項(xiàng)保留一個(gè)一位的位圖，以判定簇是否將該塊放入緩沖區(qū)。簇0是否擁有存儲(chǔ)器中的塊3的拷貝第33頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.4交換式多處理機(jī)緩存每個(gè)緩存塊有以下三個(gè)狀態(tài)之一：未緩存——存儲(chǔ)器中有此塊的唯一拷貝干凈——存儲(chǔ)器已更新，塊可能在若干緩存中臟——存儲(chǔ)器錯(cuò)誤，塊僅在一個(gè)緩存中每個(gè)緩存塊的狀態(tài)存于其目錄項(xiàng)的狀態(tài)域中第34頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.4交換式多處理機(jī)協(xié)議（讀操作）塊狀態(tài)R的緩存鄰近者緩存屬主所在簇的存儲(chǔ)器簇緩存未緩存發(fā)送塊到R；標(biāo)記為干凈，僅在R簇的緩存中干凈使用塊復(fù)制塊到R的緩存中從存儲(chǔ)器到R拷貝塊；標(biāo)記表明仍然在R簇的緩存中臟使用塊發(fā)送塊到R和屬主所在簇，通知屬主所在簇將其標(biāo)記為干凈，并存儲(chǔ)在R所在簇發(fā)送塊到R和屬主所在簇（如果在其他地方緩存過(guò)），通知屬主所在簇將其標(biāo)記為干凈且它在R簇的緩存中第35頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.4交換式多處理機(jī)協(xié)議（寫操作）塊狀態(tài)R的緩存鄰近者緩存屬主所在簇的存儲(chǔ)器簇緩存未緩存發(fā)送塊到R；標(biāo)記為臟，只有在R簇中才緩存干凈發(fā)送信息給屬主所載簇，請(qǐng)求臟狀態(tài)的唯一擁有權(quán)如果被允許，使用塊復(fù)制塊并使其無(wú)效，發(fā)送信息給屬主所在簇，請(qǐng)求臟狀態(tài)的唯一擁有權(quán)發(fā)送塊給R，將所有的緩存置無(wú)效；將它標(biāo)記為臟并存在于R簇的緩存中臟使用塊緩存到緩存地傳送到R中，將鄰近的拷貝置無(wú)效發(fā)送塊到R和屬主所在簇（如果在其他地方緩存過(guò)），通知屬主所在簇將其標(biāo)記為臟并只存在于R簇的緩存中第36頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.5NUMA多處理機(jī)特點(diǎn)在大型多處理機(jī)上實(shí)現(xiàn)硬件緩存并不簡(jiǎn)單。硬件必須維護(hù)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。緩存機(jī)制不復(fù)雜。NUMA機(jī)的虛擬地址空間對(duì)所有CPU都可見。任何CPU在地址a寫入值，接下來(lái)別的處理機(jī)對(duì)a的讀操作將讀取剛剛寫入的值。第37頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.5NUMA多處理機(jī)例子（Cm*）CPU訪問(wèn)存儲(chǔ)器時(shí)，請(qǐng)求到達(dá)CPU的MMU，MMU檢查高位地址以確定需要哪塊存儲(chǔ)器。若為本地地址，MMU僅在本地總線發(fā)出請(qǐng)求。若為遠(yuǎn)程存儲(chǔ)器，MMU建立一個(gè)包括地址的請(qǐng)求信包，通過(guò)簇間總線發(fā)送到目的簇。第38頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.5NUMA多處理機(jī)例子（BBN碟形）每個(gè)CPU和一塊存儲(chǔ)器直接相連。右邊CPU和存儲(chǔ)器對(duì)和左邊的相同。通過(guò)8個(gè)交換器相連。每個(gè)交換器4個(gè)入口，4個(gè)出口。本地訪問(wèn)的請(qǐng)求直接完成如果訪問(wèn)遠(yuǎn)程存儲(chǔ)器，發(fā)送請(qǐng)求信包，通過(guò)交換網(wǎng)絡(luò)將信包發(fā)送入相應(yīng)存儲(chǔ)器。第39頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.5NUMA多處理機(jī)NUMA機(jī)器的三個(gè)主要屬性可以訪問(wèn)遠(yuǎn)程存儲(chǔ)器訪問(wèn)遠(yuǎn)程存儲(chǔ)器比訪問(wèn)本地存儲(chǔ)器慢沒(méi)有緩沖機(jī)制隱藏訪問(wèn)遠(yuǎn)程存儲(chǔ)器的時(shí)間NUMA軟件設(shè)計(jì)的一個(gè)重要問(wèn)題是決定每頁(yè)放在何處以尋求最好的性能第40頁(yè)/共73頁(yè)6.2

共享存儲(chǔ)器6.2.6分布式共享系統(tǒng)的比較第41頁(yè)/共73頁(yè)6.3

一致性模型6.3.1嚴(yán)格一致性嚴(yán)格一致性模型由下述條件定義：從存儲(chǔ)器地址X處讀出的值為最近寫入X的值假定絕對(duì)全局時(shí)間存在舉例：

設(shè)X是存儲(chǔ)在B機(jī)器上的變量，A機(jī)器上的進(jìn)程在T1時(shí)刻讀X，即發(fā)送信包到B以讀取X。稍后，在T2時(shí)刻，B機(jī)器上的進(jìn)程寫X。答：按照嚴(yán)格一致性模型，A應(yīng)該讀取原來(lái)的值。

如果T2-T1=1nsA機(jī)器與B機(jī)器距離3米那么，信號(hào)傳輸?shù)乃俣葢?yīng)為3*109第42頁(yè)/共73頁(yè)6.3

一致性模型6.3.1嚴(yán)格一致性符號(hào)表示

P1，P2，….代表不同的進(jìn)程，直線分割進(jìn)程，時(shí)間軸向右增加

W(X)a:在x處寫aR(Y)b：在y處讀出值賦給b

變量的初值均為0P1:P2:W(x)1R(x)1P1:P2:W(x)1R(x)0R(x)1

嚴(yán)格一致性模型：讀操作所返回的值必須總是反映最近更新的結(jié)果。第43頁(yè)/共73頁(yè)6.3

一致性模型6.3.2順序一致性順序一致性模型由下述條件定義：如果所有進(jìn)程以一定的順序執(zhí)行操作，每一進(jìn)程的操作都以程序規(guī)定的順序出現(xiàn)，則任何操作的結(jié)果都是一樣的。要求分布式系統(tǒng)中的所有成員和它們的進(jìn)程共享一個(gè)通用視圖，此視圖記錄了對(duì)于共享內(nèi)存訪問(wèn)操作的順序。

運(yùn)行同一個(gè)程序得到的兩個(gè)可能的結(jié)果：P1:P2:W(x)1R(x)0R(x)1P1:P2:W(x)1R(x)1R(x)1第44頁(yè)/共73頁(yè)6.3

一致性模型6.3.2順序一致性舉例三個(gè)并行運(yùn)行的進(jìn)程，共享相同的順序一致分布式共享存儲(chǔ)器，都訪問(wèn)變量a，b，c。從存儲(chǔ)器訪問(wèn)的角度看，賦值看作是寫操作，打印被看作是讀操作。

a=1；print(b,c);

b=1；print(a,c);

c=1；print(a,b);第45頁(yè)/共73頁(yè)6.3

一致性模型6.3.2順序一致性舉例

4種有效執(zhí)行的順序（4/90種）

a=1；print(b,c);

b=1；print(a,c);

c=1；print(a,b);

a=1；b=1；

print(a,c)；print(b,c);

c=1；print(a,b);

b=1；c=1;

print(a,b)；print(a,c);

a=1；print(b,c);

b=1；a=1;

c=1；print(a,c);

print(b,c)；print(a,b);

Prints:001011Signature:001011

Prints:101011Signature:101011

Prints:010111Signature:110101

Prints:111111Signature:111111標(biāo)記項(xiàng)：順序輸出P1，P2，P3的結(jié)果，得到6位字串。<64種第46頁(yè)/共73頁(yè)6.3

一致性模型6.3.2順序一致性Ahamad系統(tǒng)進(jìn)程i的讀寫操作順序由Hi確定，下圖顯示兩種次序H1和H2，分別對(duì)應(yīng)于P1和P2；這種次序的集合稱為H。合并H中的操作串為一個(gè)單獨(dú)串S，以得到操作執(zhí)行的相對(duì)順序。S的合法值須遵守兩個(gè)限制：（1）維持程序次序（2）保證存儲(chǔ)相關(guān)性

H1=W(x)1H2=R(x)0R(x)1P1:P2:W(x)1R(x)0R(x)1第47頁(yè)/共73頁(yè)6.3

一致性模型6.3.2順序一致性Ahamad系統(tǒng)維持程序次序：如果在H的一個(gè)字串中，讀或?qū)懺L問(wèn)A出現(xiàn)在另一訪問(wèn)B之前，那么S中的A也應(yīng)出現(xiàn)在B之前。保證存儲(chǔ)相關(guān)性：在地址x處讀出的值必須是最新寫入的x。

H1=W(x)1H2=R(x)0R(x)1P1:P2:W(x)1R(x)0R(x)1根據(jù)兩個(gè)限制，S只有一個(gè)合法值：

S=R(x)0W(x)1R(x)1第48頁(yè)/共73頁(yè)6.3

一致性模型6.3.3因果一致性因果一致的存儲(chǔ)器遵循以下條件：

如果事件是因果相關(guān)的，那么它們必須以相同而且是正確的順序出現(xiàn)在所有成員面前。P1:W(x)1W(x)3P2:R(x)1W(x)2P3:R(x)1R(x)3P4:R(x)1R(x)2R(x)2R(x)3W(x)2和W(x)3是并發(fā)的第49頁(yè)/共73頁(yè)6.3

一致性模型6.3.3因果一致性因果一致的存儲(chǔ)器遵循以下條件：兩個(gè)寫操作存在因果關(guān)系：W(x)2可能決定于W(x)1不正確P1:W(x)1P2:R(x)1W(x)2P3:R(x)2P4:R(x)1R(x)1R(x)2P1:W(x)1P2:W(x)2P3:R(x)2P4:R(x)1R(x)1R(x)2正確第50頁(yè)/共73頁(yè)6.3

一致性模型6.3.4PRAM一致性和處理器一致性PRAM一致性遵循以下條件：

一個(gè)進(jìn)程的寫操作可以被其他進(jìn)程以指定的順序接收到，但不同的進(jìn)程的寫操作在不同進(jìn)程看來(lái)次序可以是不同的。

PRAM代表管道RAM。由不同進(jìn)程產(chǎn)生的寫操作是并發(fā)的。P1:W(x)1P2:R(x)1W(x)2P3:R(x)1P4:R(x)2R(x)2R(x)1PRAM一致性的有效事件序第51頁(yè)/共73頁(yè)6.3

一致性模型6.3.4PRAM一致性和處理器一致性PRAM一致性舉例：三個(gè)不同進(jìn)程看到的語(yǔ)句執(zhí)行順序

a=1；*print(b,c);

b=1；print(a,c);

c=1；print(a,b);

a=1；b=1；*print(a,c)；print(b,c);

c=1；print(a,b);

b=1；print(a,c);

c=1；*print(a,b);

a=1；print(b,c);

Prints:00

Prints:10

Prints:01

將三個(gè)進(jìn)程輸出順序相接，得到：001001。在順序一致性下是不可能的。第52頁(yè)/共73頁(yè)6.3

一致性模型6.3.4PRAM一致性和處理器一致性處理器一致性舉例

a=1;if(b==0)kill(P2);

兩個(gè)并行的進(jìn)程P1和P2處理器一致性模型：若P1在看到P2的b賦值之前讀取b，P2在看到P1中的a賦值之前讀取a，那么兩個(gè)進(jìn)程都被kill。順序一致性模型：6種順序。但不可能導(dǎo)致兩個(gè)進(jìn)程都被kill。

b=1;if(a==0)kill(P1);第53頁(yè)/共73頁(yè)6.3

一致性模型6.3.5弱一致性同步變量：用于向其它機(jī)器傳播寫操作，對(duì)于全局?jǐn)?shù)據(jù)在其它地方出現(xiàn)的修改作本地更新。弱一致性的三個(gè)屬性：

對(duì)同步變量的訪問(wèn)是順序一致的。

在所有的先前的寫操作完成之前，不能訪問(wèn)同步變量。在先前所有同步變量的訪問(wèn)完成前，不能訪問(wèn)（讀或?qū)懀?shù)據(jù)。P1:W(x)1P2:SW(x)2P3:R(x)2R(x)1R(x)1R(x)2P1:W(x)1P2:SW(x)2SR(x)1弱一致性事件有效序列弱一致性事件無(wú)效序列第54頁(yè)/共73頁(yè)6.3

一致性模型6.3.6釋放一致性獲得訪問(wèn)權(quán)：通知系統(tǒng)進(jìn)程正準(zhǔn)備進(jìn)入臨界區(qū)，所有其它成員所做的修改結(jié)果都要加以傳播，并由本地的處理器來(lái)更新。釋放訪問(wèn)權(quán)：通知系統(tǒng)，進(jìn)程準(zhǔn)備退出臨界區(qū)，對(duì)共享內(nèi)存所作的本地修改將傳播到其它的各個(gè)成員。分布式共享存儲(chǔ)器在遵守以下規(guī)定時(shí)是釋放一致的在訪問(wèn)共享變量前，進(jìn)程所有先前的獲取訪問(wèn)都必須成功地完成；在允許釋放訪問(wèn)前，進(jìn)程先前的所有讀寫操作都必須結(jié)束；獲取訪問(wèn)和釋放訪問(wèn)必須是處理器一致的。第55頁(yè)/共73頁(yè)6.3

一致性模型6.3.6釋放一致性舉例釋放一致性的有效序列P1:W(x)1P2:Rel(L)W(x)2P3:R(x)1R(x)2Acq(L)Acq(L)Rel(L)說(shuō)明：進(jìn)程P1執(zhí)行獲取訪問(wèn)，兩次改變共享變量，然后執(zhí)行釋放操作進(jìn)程P2執(zhí)行獲取訪問(wèn)，讀取x。進(jìn)程P3讀共享變量，但在讀共享變量前沒(méi)有執(zhí)行獲取訪問(wèn)第56頁(yè)/共73頁(yè)6.3

一致性模型6.3.7入口一致性分布式共享存儲(chǔ)器在遵守以下規(guī)定時(shí)是入口一致的只有某一進(jìn)程的保護(hù)共享變量全部被更新后，該進(jìn)程才允許執(zhí)行同步變量的獲取訪問(wèn)在一進(jìn)程以互斥模式訪問(wèn)該進(jìn)程的同步變量前，不允許其他進(jìn)程持有此同步變量，即使在非互斥模式下。在結(jié)束互斥模式下對(duì)一個(gè)同步變量的訪問(wèn)后，任意其他進(jìn)程必須與該變量的擁有者核查，才能試圖以非互斥模式訪問(wèn)該同步變量。第57頁(yè)/共73頁(yè)6.3

一致性模型6.3.8一致性模型總結(jié)不用同步操作的一致性模型（限制程度遞減順序）一致性說(shuō)明嚴(yán)格所有的共享訪問(wèn)事件都有絕對(duì)時(shí)間順序順序所有進(jìn)程都以相同的順序檢測(cè)到所有的共享訪問(wèn)事件因果所有進(jìn)程都以相同的順序檢測(cè)到所有因果聯(lián)系的事件處理器PRAM一致性+存儲(chǔ)器相關(guān)性PRAM所有的進(jìn)程按照預(yù)定的順序檢測(cè)到來(lái)自一個(gè)處理器的寫操作，來(lái)自其他處理器的寫操作不必以相同的順序出現(xiàn)第58頁(yè)/共73頁(yè)6.3

一致性模型6.3.8一致性模型總結(jié)使用同步操作的一致性模型一致性說(shuō)明弱同步完成后，共享數(shù)據(jù)才能保持一致釋放當(dāng)離開臨界區(qū)時(shí)，共享數(shù)據(jù)就保持一致入口當(dāng)進(jìn)入臨界區(qū)時(shí)，和該臨界區(qū)相關(guān)的共享數(shù)據(jù)保持一致性第59頁(yè)/共73頁(yè)6.4

基于分頁(yè)的分布式共享存儲(chǔ)器6.4.1基本設(shè)計(jì)DSM系統(tǒng)設(shè)計(jì)思想試圖使用MMU或操作系統(tǒng)軟件模仿多處理機(jī)中的緩存。地址空間被分成大的頁(yè)塊，散布在系統(tǒng)中的所有的處理機(jī)上。第60頁(yè)/共73頁(yè)6.4

基于分頁(yè)的分布式共享存儲(chǔ)器6.4.1基本設(shè)計(jì)DSM系統(tǒng)設(shè)計(jì)思想如果處理機(jī)訪問(wèn)的指令或數(shù)據(jù)所在塊不在本地，會(huì)激活DSM系統(tǒng)軟件的陷阱程序，軟件將該塊從那臺(tái)機(jī)器移到本地機(jī)器上。當(dāng)CPU1訪問(wèn)地址塊10后的情形第61頁(yè)/共73頁(yè)6.4

基于分頁(yè)的分布式共享存儲(chǔ)器6.4.2復(fù)制復(fù)制只讀塊復(fù)制如程序文本、固定的內(nèi)容以及其他只讀的數(shù)據(jù)結(jié)構(gòu)，提高系統(tǒng)性能。地址塊10為只讀且使用復(fù)制后的情形第62頁(yè)/共73頁(yè)6.4

基于分頁(yè)的分布式共享存儲(chǔ)器6.4.3粒度頁(yè)調(diào)入所需的整個(gè)頁(yè)。由于使用相同的單元，設(shè)計(jì)簡(jiǎn)單。缺頁(yè)中斷時(shí)，所缺頁(yè)從另一機(jī)器而不是磁盤中換入，處理缺頁(yè)中斷的代碼和傳統(tǒng)相同。段優(yōu)點(diǎn)：當(dāng)移動(dòng)大量地址空間時(shí)，使用大單元傳輸數(shù)據(jù)可以減少傳輸?shù)拇螖?shù)?？梢院芸煸L問(wèn)保存在本地的頁(yè)。缺點(diǎn)：大量的傳輸使網(wǎng)絡(luò)連接更緊密，可能會(huì)阻塞其他進(jìn)程的缺頁(yè)中斷。有效頁(yè)太大會(huì)產(chǎn)生“錯(cuò)誤共享”問(wèn)題。第63頁(yè)/共73頁(yè)6.4

基于分頁(yè)的分布式共享存儲(chǔ)器6.4.3粒度段錯(cuò)誤共享：無(wú)關(guān)的變量出現(xiàn)在同一頁(yè)上，當(dāng)一進(jìn)程使用他們之一時(shí)，進(jìn)程也得到了其他的變量。有效頁(yè)越大，發(fā)生錯(cuò)誤共享的可能性越大。AB

使用A的代碼處理器1AB

使用B的代碼處理器2

兩個(gè)無(wú)關(guān)的共享變量

共享頁(yè)包含兩個(gè)無(wú)關(guān)變量的頁(yè)的錯(cuò)誤共享第64頁(yè)/共73頁(yè)6.4

基于分頁(yè)的分布式共