分布計(jì)算系統(tǒng)-分布式共享存儲(chǔ)器

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

11.1基本概念

什么是分布式共享存儲(chǔ)器系統(tǒng)

分布式共享存儲(chǔ)器系統(tǒng)是分布式操作系統(tǒng)中的一個(gè)資源管理部件，它在沒(méi)有物理上共享的存儲(chǔ)器的分布式操作系統(tǒng)中實(shí)現(xiàn)了共享存儲(chǔ)器模式。這種共享存儲(chǔ)器模式在分布式系統(tǒng)中提供了一個(gè)可供系統(tǒng)內(nèi)所有節(jié)點(diǎn)所共享的虛擬地址空間。程序設(shè)計(jì)者可以像使用傳統(tǒng)的存儲(chǔ)器一樣使用該虛擬地址空間。這種物理上分布邏輯上共享的存儲(chǔ)器就叫做分布式共享存儲(chǔ)器(DistributedSharedMemory—DSM)。每一個(gè)節(jié)點(diǎn)都可以擁有存儲(chǔ)在共享空間的數(shù)據(jù)，數(shù)據(jù)的所有者也可以跟隨數(shù)據(jù)從一個(gè)節(jié)點(diǎn)移到另一個(gè)節(jié)點(diǎn)。當(dāng)一個(gè)進(jìn)程訪問(wèn)共享地址空間中的數(shù)據(jù)時(shí)，映像管理員就把共享存儲(chǔ)器地址變換到本地地址或遠(yuǎn)程的物理存儲(chǔ)器地址。分布式共享存儲(chǔ)器

11.1基本概念

什么是分布式共享存儲(chǔ)器系統(tǒng)

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

11.1基本概念

為什么需要分布式共享存儲(chǔ)器DSM的計(jì)算模型和RPC的計(jì)算模型相比各有優(yōu)缺點(diǎn)：DSM的計(jì)算模型支持?jǐn)?shù)據(jù)在系統(tǒng)內(nèi)移動(dòng)，使數(shù)據(jù)更容易訪問(wèn)。RPC計(jì)算模型是把操作移到數(shù)據(jù)所在位置。RPC不支持程序利用其訪問(wèn)的局部性優(yōu)點(diǎn)，對(duì)一塊遠(yuǎn)程數(shù)據(jù)的每個(gè)操作都產(chǎn)生通信，對(duì)數(shù)據(jù)的操作必須先定義好。但是RPC支持異構(gòu)型。DSM可把數(shù)據(jù)移到本地節(jié)點(diǎn)，允許程序利用其訪問(wèn)的局部性優(yōu)點(diǎn)，使用緩存器可以改善響應(yīng)時(shí)間。移動(dòng)性要求對(duì)數(shù)據(jù)位置進(jìn)行跟蹤；緩存要求解決各副本的一致性。當(dāng)數(shù)據(jù)正向某個(gè)主機(jī)移動(dòng)時(shí)，不能對(duì)它進(jìn)行處理。如果數(shù)據(jù)經(jīng)常修改，RPC模型可能更好些。分布式共享存儲(chǔ)器

11.1基本概念

為什么需要分布式共享存儲(chǔ)器從通信機(jī)制來(lái)看，DSM與報(bào)文傳遞方式有以下不同：訪問(wèn)的透明性。使用報(bào)文傳遞方式訪問(wèn)共享的數(shù)據(jù)變量時(shí)，程序必須明確地使用節(jié)點(diǎn)地址信息和通信原語(yǔ)(如SEND和RECEIVE)。而在DSM中系統(tǒng)提供了一種抽象的共享地址空間從而隱匿了物理地址和通信細(xì)節(jié)，使得程序直接面向共享的數(shù)據(jù)。共享數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和異構(gòu)性。使用報(bào)文傳遞方式，由于數(shù)據(jù)是在不同的地址空間之間傳遞，從而使得具有復(fù)雜數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)難于在不同類型的計(jì)算機(jī)及進(jìn)程之間傳遞。而在DSM中，可以借助引用機(jī)制(reference)去實(shí)現(xiàn)上述數(shù)據(jù)訪問(wèn)，復(fù)雜性與異構(gòu)性的問(wèn)題由引用機(jī)制去處理，從而進(jìn)一步簡(jiǎn)化了并行程序設(shè)計(jì)。分布式共享存儲(chǔ)器

11.1基本概念

為什么需要分布式共享存儲(chǔ)器從通信機(jī)制來(lái)看，DSM與報(bào)文傳遞方式有以下不同：(3)數(shù)據(jù)的局部性。在DSM中，新訪問(wèn)的數(shù)據(jù)項(xiàng)與其周圍的數(shù)據(jù)一起按塊或按頁(yè)移動(dòng)，而不是只移動(dòng)新訪問(wèn)的數(shù)據(jù)本身。根據(jù)程序的局部性原理，這樣可以大大地減小網(wǎng)絡(luò)的通信開(kāi)銷。分布式共享存儲(chǔ)器

11.1基本概念

為什么需要分布式共享存儲(chǔ)器與緊密耦合的多機(jī)系統(tǒng)相比，DSM系統(tǒng)具有以下特點(diǎn)：(1)規(guī)?？蓴U(kuò)充。在緊密耦合的多機(jī)系統(tǒng)中，由于各處理機(jī)共享的是一個(gè)單一的物理存儲(chǔ)器，主存訪問(wèn)都要經(jīng)過(guò)一個(gè)集中環(huán)節(jié)(例如總線)進(jìn)行，這就限制了多機(jī)系統(tǒng)的規(guī)模(一般為幾十臺(tái)處理機(jī))。DSM不存在這樣的限制，可以擴(kuò)充至很大的規(guī)模(多至上千個(gè)節(jié)點(diǎn))。(2)廉價(jià)。由于DSM系統(tǒng)可以用現(xiàn)有的硬件來(lái)構(gòu)造，并且無(wú)需連接共享存儲(chǔ)器與處理機(jī)的復(fù)雜接口，因而DSM的構(gòu)造成本要低于緊密耦合的多機(jī)系統(tǒng)。(3)兼容性。在共享存儲(chǔ)器多機(jī)系統(tǒng)上編寫的程序原則上都可以無(wú)需修改或稍加修改后轉(zhuǎn)換到DSM系統(tǒng)上運(yùn)行。分布式共享存儲(chǔ)器

11.1基本概念

共享存儲(chǔ)器中緩存一致性方法

有兩類基本方法實(shí)現(xiàn)緩存一致性：即探聽(tīng)緩存方法和使用目錄的方法。探聽(tīng)(snooping)緩存方法用于具有廣播能力的通信介質(zhì)中，例如共享總線。每個(gè)緩存器為了保持自己數(shù)據(jù)的一致性要監(jiān)聽(tīng)共享總線上進(jìn)行的由其他處理機(jī)發(fā)出的存儲(chǔ)器操作。Berkeley是一個(gè)典型例子，它是一種寫無(wú)效協(xié)議，它假設(shè)通過(guò)單總線訪問(wèn)共享的物理存儲(chǔ)器。此協(xié)議采用一個(gè)所有權(quán)方案。一個(gè)數(shù)據(jù)塊的所有者是一個(gè)緩存器，是上次對(duì)該數(shù)據(jù)塊的修改者，如果該塊被其所有者清除，則主存作為其所有者。分布式共享存儲(chǔ)器

11.1基本概念

共享存儲(chǔ)器中緩存一致性方法

Berkeley探聽(tīng)協(xié)議數(shù)據(jù)塊有四種狀態(tài)：重寫(dirty)、共享重寫、有效和無(wú)效：(1)無(wú)效。該緩存塊不包含有效數(shù)據(jù)。(2)有效。該緩存塊中數(shù)據(jù)是有效的。(3)重寫。共享存儲(chǔ)器中的數(shù)據(jù)是不正確的，該緩存塊是唯一有效的數(shù)據(jù)副本。該緩存塊是數(shù)據(jù)的所有者。(4)共享重寫。共享存儲(chǔ)器中的數(shù)據(jù)是不正確的，該緩存塊是數(shù)據(jù)的所有者，其他緩存中有同樣的副本。分布式共享存儲(chǔ)器

11.1基本概念

共享存儲(chǔ)器中緩存一致性方法

探聽(tīng)協(xié)議的寫操作：數(shù)據(jù)只能由所有者提供。有效塊和無(wú)效塊在替換時(shí)可以簡(jiǎn)單地扔掉。重寫塊和共享重寫塊在替換時(shí)要寫回共享存儲(chǔ)器，并把共享存儲(chǔ)器設(shè)置為所有者。如果對(duì)緩存塊進(jìn)行寫，而緩存塊的狀態(tài)是重寫的，則寫操作可以直接進(jìn)行；但是如果緩存塊是共享重寫、或有效，則必須向其他緩存器發(fā)送“無(wú)效”信號(hào)，然后可以進(jìn)行寫操作；如果緩存塊是無(wú)效的，要從當(dāng)前所有者那里取得數(shù)據(jù)塊，再向其他緩存器發(fā)送“無(wú)效”信號(hào)，然后可以進(jìn)行寫操作。分布式共享存儲(chǔ)器

11.1基本概念

共享存儲(chǔ)器中緩存一致性方法

目錄協(xié)議：在共享存儲(chǔ)器中設(shè)置存儲(chǔ)器塊的目錄。當(dāng)發(fā)生緩存不命中時(shí)，先把請(qǐng)求轉(zhuǎn)到此目錄。通常目錄項(xiàng)中包含所有權(quán)、副本集(copyset)和該塊的重寫位。副本集指出該塊數(shù)據(jù)在哪些緩存器中有副本，可用位向量來(lái)實(shí)現(xiàn)。發(fā)生讀未命中時(shí)，先檢查重寫位，如果該塊不處于重寫狀態(tài)，則共享存儲(chǔ)器中的版本是有效的，于是簡(jiǎn)單地返回該塊，并對(duì)副本集信息進(jìn)行更新；如果該塊的重寫位置位，則該塊的所有者必須修改該塊，并且要更新共享存儲(chǔ)器中的版本，向讀者提供讀副本。寫未命中或者從讀權(quán)變成寫權(quán)時(shí)，要求目錄的副本集使其他副本無(wú)效。與探聽(tīng)緩存方案不同，讀副本的位置都已經(jīng)知道，因此，可以用順序方式而不是以廣播方式發(fā)送“無(wú)效”報(bào)文。目錄方案不要求廣播介質(zhì)，但在每次緩存未命中時(shí)要增加一次查表。分布式共享存儲(chǔ)器

11.1基本概念

DSM的設(shè)計(jì)與實(shí)現(xiàn)問(wèn)題共享地址空間結(jié)構(gòu)和粒度。共享地址空間的結(jié)構(gòu)指的是存儲(chǔ)器中共享數(shù)據(jù)的布局方法，它依賴于應(yīng)用程序類型，地址空間可以是平面的，分段的或物理的。粒度是指共享單元的大小，可以是字節(jié)、字、頁(yè)或復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，它也是可用的并行性的度量，依賴于通信開(kāi)銷和應(yīng)用程序表現(xiàn)的局部性類型。結(jié)構(gòu)和粒度是密切相關(guān)的。緩存一致性協(xié)議。不同的協(xié)議有不同的假設(shè)，選擇協(xié)議依賴于存儲(chǔ)器訪問(wèn)模式和支持環(huán)境。在寫無(wú)效協(xié)議中，一塊共享數(shù)據(jù)可能有很多個(gè)只讀副本，但僅有一個(gè)可寫副本，每進(jìn)行一次寫時(shí)，除了一個(gè)以外，其他副本均變成無(wú)效。在寫更新協(xié)議中。每次寫都要對(duì)所有副本進(jìn)行更新。分布式共享存儲(chǔ)器

11.1基本概念

DSM的設(shè)計(jì)與實(shí)現(xiàn)問(wèn)題同步原語(yǔ)。在并發(fā)訪問(wèn)下，光有緩存一致性協(xié)議還不能維持共享數(shù)據(jù)一致性。尚需要同步原語(yǔ)對(duì)訪問(wèn)共享數(shù)據(jù)的活動(dòng)進(jìn)行同步，例如信號(hào)燈、事件計(jì)數(shù)和鎖等。替換策略。在允許數(shù)據(jù)遷移的系統(tǒng)中，當(dāng)共享數(shù)據(jù)占滿了緩存器的有效空間時(shí)，必須決定將那些數(shù)據(jù)轉(zhuǎn)移出去并且放到哪里去?？蓴U(kuò)充性。DSM系統(tǒng)比起緊密耦合系統(tǒng)來(lái)，一個(gè)重大的優(yōu)點(diǎn)是具有可擴(kuò)充性。限制可擴(kuò)充性有兩個(gè)因素：集中的瓶頸(像緊密耦合系統(tǒng)中的總線)和全局公用信息的操作及存儲(chǔ)(如廣播報(bào)文或目錄等)。分布式共享存儲(chǔ)器

11.1基本概念

DSM的設(shè)計(jì)與實(shí)現(xiàn)問(wèn)題異構(gòu)性。如何實(shí)現(xiàn)對(duì)兩個(gè)具有不同體系結(jié)構(gòu)的機(jī)器的存儲(chǔ)器共享是個(gè)很困難的問(wèn)題。兩個(gè)機(jī)器甚至對(duì)基本數(shù)據(jù)類型(如整數(shù)、浮點(diǎn)數(shù)等)都使用不同的表達(dá)方式。數(shù)據(jù)定位和訪問(wèn)。為了在一個(gè)DSM系統(tǒng)中共享數(shù)據(jù)，應(yīng)用程序必須能找到并且檢索所需要的數(shù)據(jù)。對(duì)于一個(gè)支持?jǐn)?shù)據(jù)遷移的系統(tǒng)，實(shí)現(xiàn)這一點(diǎn)就更為復(fù)雜。顛簸。DSM系統(tǒng)特別容易出現(xiàn)顛簸，例如若兩個(gè)節(jié)點(diǎn)對(duì)一個(gè)數(shù)據(jù)項(xiàng)同時(shí)進(jìn)行寫，就可能產(chǎn)生以高速率來(lái)回傳送數(shù)據(jù)的現(xiàn)象(乒乓效應(yīng))，使得任何實(shí)際工作都不能進(jìn)行。分布式共享存儲(chǔ)器

11.1基本概念

一致性語(yǔ)義共享存儲(chǔ)器中常使用的一些一致性語(yǔ)義：嚴(yán)格一致性。對(duì)一個(gè)數(shù)據(jù)項(xiàng)所進(jìn)行的任何讀操作所返回的值總是對(duì)該數(shù)據(jù)項(xiàng)最近一次進(jìn)行寫操作的結(jié)果。順序一致性。所有進(jìn)程對(duì)數(shù)據(jù)項(xiàng)的所有操作可以認(rèn)為是按照某個(gè)順序進(jìn)行的，任何進(jìn)程對(duì)這個(gè)順序的觀點(diǎn)是一樣的。處理機(jī)一致性。不僅要求一個(gè)進(jìn)程中的所有寫操作能夠以它在該進(jìn)程中出現(xiàn)的順序被所有其他進(jìn)程看見(jiàn)，還要求不同進(jìn)程對(duì)同一個(gè)數(shù)據(jù)項(xiàng)的寫操作，應(yīng)該被所有進(jìn)程以相同的順序看見(jiàn)。分布式共享存儲(chǔ)器

11.1基本概念

一致性語(yǔ)義共享存儲(chǔ)器中常使用的一些一致性語(yǔ)義：弱一致性。程序員使用同步算符，使得對(duì)數(shù)據(jù)的多個(gè)操作組來(lái)說(shuō)是順序一致性的。即不同進(jìn)程的多個(gè)操作組可以認(rèn)為是按照某個(gè)順序進(jìn)行的，任何進(jìn)程對(duì)這個(gè)順序的觀點(diǎn)是一樣的。但是操作組內(nèi)的多個(gè)操作其他進(jìn)程是不可見(jiàn)的。對(duì)同步算符是順序一致性的。釋放一致性。使用了“獲得”和“釋放”這兩類同步算符，對(duì)同步算符是處理機(jī)一致的。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

算法使用的模型和環(huán)境

共享存儲(chǔ)器模型為訪問(wèn)共享數(shù)據(jù)提供了兩個(gè)基本操作：data:=read(address)write(data,address)read返回由address指出的數(shù)據(jù)項(xiàng)。Write把由地址address指出的內(nèi)容設(shè)置為data。

根據(jù)是否允許遷移或復(fù)制，可以將DSM的實(shí)現(xiàn)算法分成四類：中央服務(wù)員算法、遷移算法、讀復(fù)制算法和全復(fù)制算法。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

算法使用的模型和環(huán)境

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

11.2實(shí)現(xiàn)DSM的算法

中央服務(wù)員算法

使用一個(gè)中央服務(wù)員，負(fù)責(zé)為所有對(duì)共享數(shù)據(jù)的訪問(wèn)提供服務(wù)并保持共享數(shù)據(jù)唯一的副本。讀和寫操作都包括由執(zhí)行該操作的進(jìn)程向中央服務(wù)員發(fā)送請(qǐng)求報(bào)文，中央服務(wù)員執(zhí)行請(qǐng)求并回答，讀操作時(shí)回答數(shù)據(jù)項(xiàng)，寫操作時(shí)回答一個(gè)承認(rèn)。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

遷移算法

數(shù)據(jù)總是被遷移到訪問(wèn)它的節(jié)點(diǎn)。這是一個(gè)“單讀者/單寫者”(SRSW)協(xié)議，因?yàn)樵谡麄€(gè)系統(tǒng)中，一次只有一個(gè)進(jìn)程讀或?qū)懸粋€(gè)給定的數(shù)據(jù)項(xiàng)。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

讀復(fù)制算法

對(duì)于一個(gè)當(dāng)前不在本地的塊中的一個(gè)數(shù)據(jù)項(xiàng)進(jìn)行讀操作時(shí)，先與遠(yuǎn)程節(jié)點(diǎn)通信以獲得那個(gè)塊的一個(gè)只讀副本，然后再進(jìn)行讀操作。若被執(zhí)行寫操作的數(shù)據(jù)所在的塊不在本地或在本地但主機(jī)無(wú)寫權(quán)時(shí)，必須先使此塊在其他節(jié)點(diǎn)的所有副本無(wú)效，之后再進(jìn)行寫操作。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

全復(fù)制算法

全復(fù)制算法允許數(shù)據(jù)塊在進(jìn)行寫時(shí)也可以復(fù)制，因而它遵從了“多讀者/多寫者”(MRMW)協(xié)議。保持復(fù)制數(shù)據(jù)一致性的一種可能的方法是對(duì)所有的寫操作進(jìn)行全局排序，而只對(duì)與發(fā)生在執(zhí)行讀操作節(jié)點(diǎn)上的寫操作相關(guān)的那些讀操作進(jìn)行排序。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

算法性能基本代價(jià)：

(1)p：一個(gè)包事件的代價(jià)，即發(fā)送或接收一個(gè)短包的處理代價(jià)，包括可能的任務(wù)切換、數(shù)據(jù)復(fù)制及中斷處理開(kāi)銷。實(shí)際系統(tǒng)的典型值的變化范圍是1到幾個(gè)毫秒。(2)P：發(fā)送或接收一個(gè)數(shù)據(jù)塊的代價(jià)。這與p十分相似，但P值要高得多。對(duì)于一個(gè)通常需要多個(gè)包的8K字節(jié)的塊來(lái)說(shuō)，典型值的范圍是20至40個(gè)毫秒。(3)S：參與分布式共享內(nèi)存的節(jié)點(diǎn)數(shù)。(4)r：讀/寫比，即平均有r個(gè)讀操作時(shí)才有一個(gè)寫操作。這個(gè)參數(shù)也用于整個(gè)塊的訪問(wèn)模式。顯然這兩個(gè)比可能不同，但為了簡(jiǎn)化分析假定相等。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

算法性能基本代價(jià)：

(5)f：非復(fù)制數(shù)據(jù)塊(用于遷移算法)訪問(wèn)故障的概率。它等于單一節(jié)點(diǎn)連續(xù)訪問(wèn)一個(gè)塊(以后由另一個(gè)節(jié)點(diǎn)訪問(wèn)此塊導(dǎo)致故障)的平均次數(shù)的倒數(shù)。它說(shuō)明遷移算法數(shù)據(jù)訪問(wèn)的局部性。(6)f’：讀復(fù)制算法用于對(duì)復(fù)制數(shù)據(jù)塊訪問(wèn)故障的概率。它是連續(xù)訪問(wèn)本地?cái)?shù)據(jù)塊中數(shù)據(jù)項(xiàng)(以后訪問(wèn)一個(gè)非本地?cái)?shù)據(jù)塊中某數(shù)據(jù)項(xiàng))的平均次數(shù)的倒數(shù)。它說(shuō)明讀復(fù)制算法數(shù)據(jù)訪問(wèn)的本地性。分布式共享存儲(chǔ)器

11.2實(shí)現(xiàn)DSM的算法

算法性能四種算法的平均訪問(wèn)代價(jià)：

中央服務(wù)員算法：Cc=(1-1/S)·4p遷移算法：Cm=f·(2P+4p)讀復(fù)制算法：Crr=f’·[2P+4p+Sp/(r+1)]全復(fù)制算法：Cfr=[1/(r+1)]·(S+2)p每一個(gè)表達(dá)式都有兩部分，第一部分在“·”的左邊，表示訪問(wèn)遠(yuǎn)程數(shù)據(jù)項(xiàng)的概率。第二部分在“·”的右邊，等于訪問(wèn)遠(yuǎn)程數(shù)據(jù)項(xiàng)的平均代價(jià)。分布式共享存儲(chǔ)器

11.3使用目錄的DSM

目錄方案的分類

目錄：不用廣播的緩存器一致性協(xié)議必須保存每塊共享數(shù)據(jù)的所有緩存器副本的位置。此緩存位置表，不管是集中的還是分散的，都叫做目錄。每個(gè)數(shù)據(jù)的目錄項(xiàng)包括許多指針，用來(lái)指出此塊各副本所在位置。每一個(gè)目錄項(xiàng)還有一個(gè)“重寫”位用來(lái)指明是否允許某一個(gè)(只有一個(gè))緩存器進(jìn)行寫。目錄協(xié)議有三種主要類型：全映像目錄、有限目錄和鏈?zhǔn)侥夸?。全映像目錄的每個(gè)目錄項(xiàng)保持N個(gè)指針，這里N是系統(tǒng)中處理器的個(gè)數(shù)。有限目錄和全映像目錄的不同之處在于，有限目錄的每個(gè)目錄項(xiàng)具有固定數(shù)量的指針，與系統(tǒng)中處理機(jī)數(shù)量無(wú)關(guān)。鏈?zhǔn)侥夸浥c全映像目錄相似，只是它將目錄分布于各緩存器。分布式共享存儲(chǔ)器

11.3使用目錄的DSM

全映像目錄

全映像目錄協(xié)議使用的目錄每項(xiàng)包含每個(gè)處理機(jī)，有一個(gè)指針并且有一個(gè)“重寫”位。指針?biāo)鶎?duì)應(yīng)的每一位代表該塊在相應(yīng)處理機(jī)緩存器中的狀態(tài)(存在或不存在)。如果“重寫”位置位，那么有且只有一個(gè)處理機(jī)的指針位被置位，允許這個(gè)處理機(jī)對(duì)該數(shù)據(jù)塊進(jìn)行寫操作。緩存器保存每塊數(shù)據(jù)的兩個(gè)狀態(tài)位：一位表明此數(shù)據(jù)塊是否有效，另一位表明一個(gè)有效的數(shù)據(jù)塊是否可寫。緩存器一致性協(xié)議必須在存儲(chǔ)器目錄中保存這些狀態(tài)位，并維持緩存一致性。分布式共享存儲(chǔ)器

11.3使用目錄的DSM

全映像目錄

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

11.3使用目錄的DSM

全映像目錄

寫過(guò)程：(1)C3檢測(cè)到包含單元X的數(shù)據(jù)塊是有效的，但是該處理機(jī)對(duì)數(shù)據(jù)塊無(wú)寫的權(quán)限，這由塊的允許寫位表示。(2)C3發(fā)出一個(gè)對(duì)包含單元X的存儲(chǔ)模塊的寫請(qǐng)求，并且停止處理機(jī)P3。(3)存儲(chǔ)器模塊向C1和C2發(fā)出無(wú)效請(qǐng)求。(4)C1和C2收到無(wú)效請(qǐng)求后，設(shè)置對(duì)應(yīng)的位指出包含單元X的數(shù)據(jù)塊是無(wú)效的，并向存儲(chǔ)器模塊發(fā)回一個(gè)承認(rèn)。(5)存儲(chǔ)器模塊收到這個(gè)承認(rèn)，將“重寫”位置位，清除指向C1和C2的指針，并向C3發(fā)出寫允許報(bào)文。(6)C3收到寫允許報(bào)文，更新該緩存器中的狀態(tài)，并且激活處理機(jī)P3。分布式共享存儲(chǔ)器

11.3使用目錄的DSM

有限目錄

有限目錄協(xié)議是為解決目錄大小問(wèn)題而設(shè)計(jì)的。限制對(duì)同一數(shù)據(jù)塊同時(shí)進(jìn)行緩存的任務(wù)數(shù)目，即限制一個(gè)數(shù)據(jù)塊的緩存數(shù)目，就可以將每個(gè)目錄項(xiàng)的大小限定為一個(gè)常數(shù)。分布式共享存儲(chǔ)器

11.3使用目錄的DSM

鏈?zhǔn)侥夸?/p>

它通過(guò)保持一個(gè)目錄指針鏈對(duì)共享副本進(jìn)行跟蹤。單向鏈?zhǔn)浇Y(jié)構(gòu)：分布式共享存儲(chǔ)器

11.3使用目錄的DSM

鏈?zhǔn)侥夸?/p>

緩存器塊的替換：假設(shè)從C1到CN都有單元X的副本，并且單元X和單元Y都直接映射到緩存器同一行上。如果處理機(jī)Pi讀單元Y，必須從它的緩存器中先驅(qū)逐單元X。在這種情況下，有兩種可能性：(1)沿著鏈路向Ci-1發(fā)送一個(gè)報(bào)文，將Ci-1的指針指向Ci+1，將Ci從鏈路中脫離開(kāi)。(2)使從Ci到CN中的單元X無(wú)效。分布式共享存儲(chǔ)器

11.3使用目錄的DSM

鏈?zhǔn)侥夸?/p>

雙向鏈?zhǔn)浇Y(jié)構(gòu)：另外一種解決替換問(wèn)題的方法是使用雙向鏈。這種方案為每個(gè)緩存器副本保持一個(gè)向前和一個(gè)向后的指針，這樣當(dāng)緩存器替換時(shí)，協(xié)議不必遍歷整個(gè)鏈。雙向鏈目錄優(yōu)化替換條件是以更大的平均報(bào)文長(zhǎng)度(由于傳送更多的目錄指針)、緩存器中的指針的存儲(chǔ)空間加倍和更為復(fù)雜的一致性協(xié)議為代價(jià)的。分布式共享存儲(chǔ)器

11.4DSM系統(tǒng)的實(shí)現(xiàn)實(shí)現(xiàn)DSM的基本方法

DSM有三種實(shí)現(xiàn)方法，有的系統(tǒng)使用了不止一種方法。(1)硬件實(shí)現(xiàn)。把傳統(tǒng)的高速緩存技術(shù)擴(kuò)展到可擴(kuò)充的體系結(jié)構(gòu)中。(2)操作系統(tǒng)和程序庫(kù)的實(shí)現(xiàn)。通過(guò)虛擬存儲(chǔ)器的管理機(jī)構(gòu)達(dá)到共享和一致性。(3)編譯程序的實(shí)現(xiàn)。把共享訪問(wèn)自動(dòng)轉(zhuǎn)換成同步和一致性原語(yǔ)。分布式共享存儲(chǔ)器

11.4DSM系統(tǒng)的實(shí)現(xiàn)結(jié)構(gòu)和粒度

DSM的硬件實(shí)現(xiàn)方法典型地支持了較小的粒度。頁(yè)的大?。狠^大的頁(yè)能夠減少分頁(yè)的開(kāi)銷，但是可能引起爭(zhēng)用可能性越大。另一個(gè)影響頁(yè)大小選擇的因素是必須保留該系統(tǒng)中有關(guān)頁(yè)的目錄信息：頁(yè)越小，則目錄越大。結(jié)構(gòu)化共享存儲(chǔ)器的一個(gè)實(shí)現(xiàn)方法是根據(jù)數(shù)據(jù)類型進(jìn)行共享。這種方法是把共享存儲(chǔ)器作為面向?qū)ο蟮姆植际较到y(tǒng)中的對(duì)象而進(jìn)行構(gòu)造。另一個(gè)方法是把共享存儲(chǔ)器構(gòu)造成像一個(gè)數(shù)據(jù)庫(kù)。Linda就是一個(gè)這種模式的系統(tǒng)。它把它的共享存儲(chǔ)器安排成為一個(gè)相聯(lián)存儲(chǔ)器，叫做元組(tuple)空間。分布式共享存儲(chǔ)器

11.4DSM系統(tǒng)的實(shí)現(xiàn)數(shù)據(jù)定位與訪問(wèn)

集中的服務(wù)員：集中的服務(wù)員來(lái)跟蹤所有共享數(shù)據(jù)。這種集中的方法有兩個(gè)缺陷：服務(wù)員串行執(zhí)行定位查詢，從而削弱了并行性；服務(wù)員負(fù)載過(guò)重，降低了整個(gè)系統(tǒng)的速度。廣播數(shù)據(jù)請(qǐng)求：不幸的是，廣播的可擴(kuò)充性不好，所有的節(jié)點(diǎn)(不僅是數(shù)據(jù)所在的節(jié)點(diǎn))都必須處理廣播請(qǐng)求。廣播在網(wǎng)絡(luò)上的等待有可能使訪問(wèn)花費(fèi)很長(zhǎng)時(shí)間才能完成?；谒姓叩姆植际降哪Ｐ停好恳粔K數(shù)據(jù)都有一個(gè)與之相聯(lián)系的所有者，這個(gè)所有者就是擁有數(shù)據(jù)主副本的節(jié)點(diǎn)。當(dāng)數(shù)據(jù)在整個(gè)系統(tǒng)中遷移時(shí)，它的所有者也會(huì)隨之而改變。當(dāng)另一個(gè)節(jié)點(diǎn)需要數(shù)據(jù)的一個(gè)副本時(shí)，就向所有者發(fā)送請(qǐng)求。所有者如果仍保留著這個(gè)數(shù)據(jù)，就返回該數(shù)據(jù)；若所有者已將數(shù)據(jù)發(fā)送給其他節(jié)點(diǎn)，則把這一請(qǐng)求轉(zhuǎn)發(fā)給那個(gè)新所有者。缺點(diǎn)是一個(gè)請(qǐng)求可能被轉(zhuǎn)發(fā)多次后才能到達(dá)當(dāng)前所有者。分布式共享存儲(chǔ)器

11.4DSM系統(tǒng)的實(shí)現(xiàn)一致性協(xié)議

兩類一致性協(xié)議：寫無(wú)效協(xié)議和寫更新協(xié)議在寫無(wú)效協(xié)議中，一塊數(shù)據(jù)可能有很多個(gè)只讀副本，但是，只有一個(gè)是可寫副本。這種協(xié)議之所以被稱作寫無(wú)效協(xié)議，是因?yàn)樵陂_(kāi)始一次寫操作之前，除了將被寫的那個(gè)副本之外，其他副本均變成無(wú)效。在寫更新方式中，一次寫操作將更新所有副本。Dash系統(tǒng)簡(jiǎn)化的寫無(wú)效協(xié)議(DC代表目錄控制器)

Plus寫更新協(xié)議，MCM代表存儲(chǔ)一致性控制器分布式共享存儲(chǔ)器

11.4DSM系統(tǒng)的實(shí)現(xiàn)顛簸

DSM系統(tǒng)特別容易出現(xiàn)顛簸。如果兩個(gè)節(jié)點(diǎn)對(duì)一個(gè)數(shù)據(jù)項(xiàng)同時(shí)進(jìn)行寫，該數(shù)據(jù)項(xiàng)就有可能以高速率來(lái)來(lái)回回地被傳送(乒乓效應(yīng))，任何實(shí)際工作都做不成。Munin系統(tǒng)允許程序員把共享數(shù)據(jù)和類型聯(lián)系起來(lái)：寫一次、寫多次、生產(chǎn)者—消費(fèi)者、專用、遷移、結(jié)果、常讀、同步及一般的讀/寫。為避免兩個(gè)競(jìng)爭(zhēng)寫者的顛簸，一個(gè)程序員可以把類型指定為寫多次，系統(tǒng)將使用延遲寫策略。Mirage系統(tǒng)在一致性協(xié)議中，增加了一個(gè)動(dòng)態(tài)可調(diào)整參數(shù)，它決定一頁(yè)在一個(gè)節(jié)點(diǎn)上保持可用的最小時(shí)間量(△)。例如若一個(gè)節(jié)點(diǎn)對(duì)一個(gè)共享頁(yè)執(zhí)行一次寫操作，則此頁(yè)在該節(jié)點(diǎn)上時(shí)間△內(nèi)是可寫的。分布式共享存儲(chǔ)器

11.4DSM系統(tǒng)的實(shí)現(xiàn)可擴(kuò)充性

DSM系統(tǒng)一個(gè)理論上的優(yōu)點(diǎn)是它們比緊密耦合系統(tǒng)具有更好的可擴(kuò)充性。前面說(shuō)過(guò)，對(duì)可擴(kuò)充性限制有兩種因素：集中瓶頸(例如緊密耦合系統(tǒng)中的總線)和全局公用信息的操作及存儲(chǔ)(例如廣播報(bào)文或目錄，它的大小與節(jié)點(diǎn)數(shù)成比例)。分布式共享存儲(chǔ)器

11.4DSM系統(tǒng)的實(shí)現(xiàn)異構(gòu)性

在Agora系統(tǒng)中，把存儲(chǔ)器構(gòu)造為在異構(gòu)性機(jī)器之間共享對(duì)象。Mermaid探索了另一種不同尋常的方法：存儲(chǔ)器以頁(yè)方式共享，并且一頁(yè)只包含一種數(shù)據(jù)類型。當(dāng)在不同體系結(jié)構(gòu)的兩個(gè)系統(tǒng)之間移動(dòng)一頁(yè)時(shí)，變換子程序都會(huì)把該頁(yè)上的數(shù)據(jù)轉(zhuǎn)換成適當(dāng)?shù)母袷?。分布式共享存?chǔ)器

11.5DSM實(shí)例：Ivy和MemNetIvy—軟件實(shí)現(xiàn)的DSM

Ivy中進(jìn)程地址空間分成專用和共享兩部分。專用部分不能由其他進(jìn)程尋址。共享部分由虛擬共享存儲(chǔ)器實(shí)現(xiàn)，是個(gè)平面地址空間，為運(yùn)行在不同節(jié)點(diǎn)上的所有進(jìn)程所共享，也就是被各線程共享的單地址空間。地址空間是分頁(yè)的。一頁(yè)是同步的最小單位，當(dāng)需要時(shí)它可以從一個(gè)節(jié)點(diǎn)遷移到另一個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)上有一個(gè)存儲(chǔ)器管理程序，滿足本地和遠(yuǎn)程請(qǐng)求并實(shí)現(xiàn)緩存器一致性協(xié)議。當(dāng)訪問(wèn)共享空間的一個(gè)地址時(shí)，阻塞故障進(jìn)程，Ivy存儲(chǔ)器管理程序檢查待訪問(wèn)頁(yè)是否在本地。如果不在本地，向遠(yuǎn)程存儲(chǔ)器發(fā)送請(qǐng)求。得到該頁(yè)后，發(fā)生頁(yè)故障的進(jìn)程恢復(fù)執(zhí)行。分布式共享存儲(chǔ)器

11.5DSM實(shí)例：Ivy和MemNetIvy一致性協(xié)議

Ivy所使用的一致性概念是多個(gè)讀/單個(gè)寫的語(yǔ)義。對(duì)某地址的讀操作總是得到最近對(duì)該地址寫的值，一致性協(xié)議保證執(zhí)行這一語(yǔ)義。Ivy的每個(gè)處理機(jī)都有自己的頁(yè)表。表中的每一項(xiàng)紀(jì)錄著該主機(jī)的訪問(wèn)權(quán)，可以對(duì)一頁(yè)擁有讀、寫權(quán)或無(wú)任何權(quán)利。一頁(yè)的訪問(wèn)權(quán)是與緩存器中一個(gè)塊的狀態(tài)相當(dāng)?shù)?。分布式共享存?chǔ)器

11.5DSM實(shí)例：Ivy和MemNetIvy一致性協(xié)議

當(dāng)訪問(wèn)一個(gè)共享地址時(shí)，該主機(jī)檢查它是否有權(quán)在指定方式下訪問(wèn)含有此地址的那一頁(yè)。如果沒(méi)有，則根據(jù)訪問(wèn)方式產(chǎn)生一個(gè)讀或者寫故障，其步驟如下：讀故障：(1)找出誰(shuí)是所有者；(2)所有者把該故障主機(jī)填入副本集；(3)所有者把自己的訪問(wèn)權(quán)變成只讀；(4)所有者向故障主機(jī)發(fā)送該頁(yè)。分布式共享存儲(chǔ)器

11.5DSM實(shí)例：Ivy和MemNetIvy一致性協(xié)議

當(dāng)訪問(wèn)一個(gè)共享地址時(shí)，該主機(jī)檢查它是否有權(quán)在指定方式下訪問(wèn)含有此地址的那一頁(yè)。如果沒(méi)有，則根據(jù)訪問(wèn)方式產(chǎn)生一個(gè)讀或者寫故障，其步驟如下：寫故障：(1)找到所有者；(2)所有者向故障主機(jī)發(fā)送該頁(yè)和該頁(yè)的副本集，并將它的那項(xiàng)標(biāo)為無(wú)效；(3)故障主機(jī)根據(jù)副本集送出“無(wú)效”報(bào)文；(4)返回對(duì)“無(wú)效”報(bào)文的承認(rèn)，進(jìn)程繼續(xù)執(zhí)行。分布式共享存儲(chǔ)器

11.5DSM實(shí)例：Ivy和MemNetIvy一致性協(xié)議

三種不同的一致性協(xié)議：集中管理者方法類似于管程，管程由一個(gè)數(shù)據(jù)結(jié)構(gòu)和一些過(guò)程組成，提供對(duì)數(shù)據(jù)結(jié)構(gòu)的互斥訪問(wèn)。集中管理者固定在一個(gè)處理機(jī)上，維持一張頁(yè)表。每個(gè)處理機(jī)也有一張頁(yè)表，每一項(xiàng)有兩個(gè)域：訪問(wèn)和鎖。訪問(wèn)域記錄本地處理機(jī)上的頁(yè)面的可訪問(wèn)信息。每個(gè)處理機(jī)知道中心管理者，并且在本地沒(méi)有數(shù)據(jù)對(duì)象時(shí)能夠向管理者發(fā)出請(qǐng)求。當(dāng)一個(gè)處理機(jī)上有多個(gè)進(jìn)程等待同一個(gè)頁(yè)面時(shí)，加鎖機(jī)制防止處理機(jī)發(fā)出多個(gè)請(qǐng)求。對(duì)一個(gè)頁(yè)面成功執(zhí)行寫操作就會(huì)成為頁(yè)面的所有者。

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

11.5DSM實(shí)例：Ivy和MemNetIvy一致性協(xié)議

三種不同的一致性協(xié)議：有兩種類型的固定分布式管理者算法：固定的和廣播的。固定算法中，每個(gè)處理機(jī)預(yù)定管理一部分頁(yè)面。通常一個(gè)適當(dāng)?shù)纳⒘泻瘮?shù)用于把頁(yè)面映射到處理機(jī)。廣播算法中，訪問(wèn)頁(yè)面出故障的處理機(jī)發(fā)出廣播確定頁(yè)面的真正所有者。廣播算法性能比較差，因?yàn)樗刑幚頇C(jī)必須處理每個(gè)請(qǐng)求，減慢處理機(jī)的計(jì)算。分布式共享存儲(chǔ)器

11.5DSM實(shí)例：Ivy和MemNetIvy一致性協(xié)議

三種不同的一致性協(xié)議：動(dòng)態(tài)分布式管理者方法的核心是每個(gè)處理機(jī)的頁(yè)表中記錄所有頁(yè)的所有者。頁(yè)表中，集中管理者算法中的所有者域被替換成另一個(gè)域，叫做可能所有者(probowner)域，它可能是頁(yè)面的真正所有者，也可能是頁(yè)面的可能所有者?？赡芩姓哂驑?gòu)成一個(gè)鏈，從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)，最終會(huì)指向真正的所有者。分布式共享存儲(chǔ)器

11.5DSM實(shí)例：Ivy和MemNetIvy存儲(chǔ)器管理頁(yè)替換。Ivy的虛擬共享存儲(chǔ)器的頁(yè)有五種：可寫的、所有者可讀的、只讀的、空的和不使用的?？枕?yè)和不用頁(yè)都具有最高的被替換優(yōu)先權(quán)，即如果需要一頁(yè)則先替換它們。由于只讀頁(yè)可被其所有者制造備份，所以可以簡(jiǎn)單地丟棄。對(duì)于所有者讀的頁(yè)和可寫頁(yè)的丟棄當(dāng)然需要所有權(quán)的轉(zhuǎn)讓。存儲(chǔ)器分配。為了支持動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，使用動(dòng)態(tài)存儲(chǔ)器分配方案是必要的。Ivy有兩種方法。第一種是集中式方法，即所有進(jìn)程向集中式的“存儲(chǔ)器分配程序”請(qǐng)求存儲(chǔ)器和歸還存儲(chǔ)器。這是個(gè)簡(jiǎn)單的方法。第二個(gè)方法，除了集中式分配程序外，每個(gè)節(jié)點(diǎn)還有它自己的分配子程序。每個(gè)節(jié)點(diǎn)請(qǐng)求一大塊存儲(chǔ)器并執(zhí)行來(lái)自本地進(jìn)程的存儲(chǔ)器請(qǐng)求。僅在本地節(jié)點(diǎn)用完存儲(chǔ)器時(shí)才和集中式管理程序聯(lián)系。分布式共享存儲(chǔ)器

11.5DSM實(shí)例：Ivy和MemNetMemNet—硬件實(shí)現(xiàn)的DSM在MemNet中，全部主機(jī)共享一個(gè)公共的地址空間。此地址空間是分頁(yè)的，這些頁(yè)可根據(jù)要求在系統(tǒng)內(nèi)遷移。對(duì)此地址空間的訪問(wèn)被直接送到主機(jī)內(nèi)的接口部件(作為一個(gè)智能存儲(chǔ)器模塊)。這個(gè)部件能緩存一部分共享存儲(chǔ)器并和其他主機(jī)的這種部件相互作用調(diào)進(jìn)另外的頁(yè)。分布式共享存儲(chǔ)器

11.5DSM實(shí)例：Ivy和MemNetMemNet緩存一致性協(xié)議MemNet使用的緩存一致性協(xié)議和Ivy使用的相同，即讀操作必須總是返回該數(shù)據(jù)最近的值。每個(gè)MemNet部件有一塊表，表中每項(xiàng)對(duì)應(yīng)整個(gè)共享地址空間中的每一塊，還包括下述狀態(tài)標(biāo)志：(1)有效。指出此緩存器對(duì)該塊是否有一個(gè)有效副本。(2)獨(dú)占。指出本