中科院講義_分布式操作系統(tǒng)_分布式共享內(nèi)存

1、分布式 共享內(nèi)存在本章中，我們研究實(shí)現(xiàn)分布式共享內(nèi)存(distributed shared memory簡(jiǎn)稱DSM)。第1節(jié)引論 第2節(jié)體系結(jié)構(gòu)和動(dòng)力第3節(jié)實(shí)現(xiàn)分布式共享內(nèi)存的算法第4節(jié)存儲(chǔ)一致性(Memory Coherence)第5節(jié)一致性協(xié)議引論傳統(tǒng)上，分布式計(jì)算是基于消息傳遞模型，在這種模型下進(jìn)程們經(jīng)由以消息形式交換數(shù)據(jù)來(lái)彼此互相交互和共享數(shù)據(jù)。Hoare的通訊順序進(jìn)程(communicating sequential processes)，客戶-服務(wù)器模型和遠(yuǎn)程過(guò)程調(diào)用都是這種模型的例子。引論分布式共享內(nèi)存(Distributed shared memory簡(jiǎn)稱DSM)系統(tǒng)是分布式操

2、作系統(tǒng)的一個(gè)資源管理成分，它實(shí)現(xiàn)在沒(méi)有物理地共享內(nèi)存的分布式系統(tǒng)中的共享內(nèi)存模型。見(jiàn)圖1。這個(gè)共享內(nèi)存模型提供一個(gè)虛擬地址空間，使得被在一個(gè)分布式系統(tǒng)中所有結(jié)點(diǎn)（計(jì)算機(jī)）之間共享。分布式共享內(nèi)存體系結(jié)構(gòu)和動(dòng)力具有分布式共享內(nèi)存，程序訪問(wèn)在共享地址空間中的數(shù)據(jù)正如同訪問(wèn)在傳統(tǒng)的虛存中的數(shù)據(jù)一樣。在支持分布式共享內(nèi)存的系統(tǒng)中，數(shù)據(jù)既在輔存和主存之間也在不同結(jié)點(diǎn)的主存之間移動(dòng)。體系結(jié)構(gòu)和動(dòng)力每個(gè)結(jié)點(diǎn)可以擁有存貯在共享地址空間中的數(shù)據(jù)，并且當(dāng)數(shù)據(jù)從一個(gè)結(jié)點(diǎn)移到另一個(gè)結(jié)點(diǎn)時(shí)，擁有關(guān)系可以改變。當(dāng)一個(gè)進(jìn)程訪問(wèn)在共享地址空間中的數(shù)據(jù)時(shí)，一個(gè)映照管理者(mapping manager) 映照共享內(nèi)存地址到物理

3、存儲(chǔ)，這個(gè)物理存儲(chǔ)可以是本地或遠(yuǎn)程的。體系結(jié)構(gòu)和動(dòng)力映照管理者是一個(gè)或者實(shí)現(xiàn)在操作系統(tǒng)內(nèi)核中或者作為一個(gè)運(yùn)行時(shí)庫(kù)例程的軟件層。體系結(jié)構(gòu)和動(dòng)力為了減少由于通訊誤而帶來(lái)的延遲，當(dāng)共享內(nèi)存地址映照到在在一個(gè)遠(yuǎn)程結(jié)點(diǎn)上的一個(gè)物理內(nèi)存位置時(shí)，分布式共享內(nèi)存可以移動(dòng)在共享內(nèi)存地址中的數(shù)據(jù)從一個(gè)遠(yuǎn)程結(jié)點(diǎn)到正在訪問(wèn)數(shù)據(jù)的結(jié)點(diǎn)。在這樣情況下，分布式共享內(nèi)存利用底層通訊系統(tǒng)的通訊服務(wù)。分布式共享內(nèi)存的優(yōu)點(diǎn)在消息傳遞模型中，程序通過(guò)明顯的消息傳遞使共享數(shù)據(jù)可供使用。換句話說(shuō)，程序員需要意識(shí)到進(jìn)程之間數(shù)據(jù)移動(dòng)。程序員不得不明顯地使用通訊原語(yǔ)（例如SEND和RECEIVE），放一個(gè)重要的負(fù)擔(dān)在它們身上。分布式共享內(nèi)存的

4、優(yōu)點(diǎn)相反，分布式共享內(nèi)存系統(tǒng)隱藏這個(gè)明顯的數(shù)據(jù)移動(dòng)并且提供一個(gè)較簡(jiǎn)單的程序員已經(jīng)精通的共享數(shù)據(jù)抽象。因此，利用分布式共享內(nèi)存比通過(guò)明顯的消息傳遞更容易地設(shè)計(jì)和編寫(xiě)并行算法。分布式共享內(nèi)存的優(yōu)點(diǎn)在消息傳遞模型中，數(shù)據(jù)在兩個(gè)不同的地址空間之間移動(dòng)。這使得它難以在兩個(gè)進(jìn)程之間傳遞復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。而且傳遞由“引用”的數(shù)據(jù)和傳遞包含指針的數(shù)據(jù)結(jié)構(gòu)一般是困難的和貴的。相反，分布式共享內(nèi)存系統(tǒng)允許傳遞由“引用”的復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，于是簡(jiǎn)化了對(duì)分布式應(yīng)用的算法的開(kāi)發(fā)。分布式共享內(nèi)存的優(yōu)點(diǎn)僅移動(dòng)規(guī)定的所引用的數(shù)據(jù)片來(lái)代替由移動(dòng)整塊或包含所引用的引用場(chǎng)點(diǎn)的數(shù)據(jù)頁(yè)，分布式共享內(nèi)存利用程序所顯示的引用局部性，因此削減了

5、在網(wǎng)絡(luò)上的通信開(kāi)銷(xiāo)。分布式共享內(nèi)存的優(yōu)點(diǎn)分布式共享內(nèi)存系統(tǒng)比緊偶合多機(jī)系統(tǒng)更便宜。這是因?yàn)榉植际焦蚕韮?nèi)存系統(tǒng)可以利用off-the-shelf硬件建立不需要復(fù)雜的接口把共享內(nèi)存連接到處理機(jī)。分布式共享內(nèi)存的優(yōu)點(diǎn)在一個(gè)分布式共享內(nèi)存系統(tǒng)所有結(jié)點(diǎn)中可供使用物理內(nèi)存組合在一起是巨大的。這個(gè)大的內(nèi)存可以用于有效地運(yùn)行要求大內(nèi)存的程序而不用招致由于在傳統(tǒng)的分布系統(tǒng)中對(duì)換引起的磁盤(pán)延遲。這個(gè)事實(shí)也由處理機(jī)速度相對(duì)于內(nèi)存速度預(yù)料的增加和非常高速網(wǎng)絡(luò)出現(xiàn)所支持分布式共享內(nèi)存的優(yōu)點(diǎn)在具有單個(gè)共享內(nèi)存的緊偶合多機(jī)系統(tǒng)中主存經(jīng)由一個(gè)公共總線訪問(wèn)，這限制多機(jī)系統(tǒng)為幾十個(gè)處理機(jī)。分布式共享內(nèi)存系統(tǒng)沒(méi)有這個(gè)缺點(diǎn)，并且可以

6、容易地向上擴(kuò)充。分布式共享內(nèi)存的優(yōu)點(diǎn)為共享內(nèi)存多處理機(jī)寫(xiě)的程序原則上可以不加改變地運(yùn)行在分布式共享內(nèi)存系統(tǒng)。至少這樣的程序可以容易地移到分布式共享內(nèi)存系統(tǒng)中。分布式共享內(nèi)存的優(yōu)點(diǎn)本質(zhì)上，分布式共享內(nèi)存系統(tǒng)努力克服共享內(nèi)存機(jī)器體系結(jié)構(gòu)的限制并且減少在分布系統(tǒng)中寫(xiě)并行程序。所需的努力。實(shí)現(xiàn)分布式共享內(nèi)存的算法實(shí)現(xiàn)分布式共享內(nèi)存的中心課題是：F如何追蹤遠(yuǎn)程數(shù)據(jù)的位置；F當(dāng)訪問(wèn)遠(yuǎn)程數(shù)據(jù)時(shí)，.如何克服.通信延遲和在分布系統(tǒng)中通信協(xié)議的執(zhí)行相聯(lián)的開(kāi)銷(xiāo)；F為了改善系統(tǒng)性能，.如何使共享數(shù)據(jù)在幾個(gè)結(jié)點(diǎn)上并發(fā)地可供訪問(wèn)。實(shí)現(xiàn)分布式共享內(nèi)存的算法現(xiàn)在我們描述實(shí)現(xiàn)分布式共享內(nèi)存的四個(gè)基本算法。F中央服務(wù)器(Cent

7、ral-Server)算法F遷移算法F讀復(fù)制(Read-Replicatin)算法F完全復(fù)制算法中央服務(wù)器(Central-Server)算法中央服務(wù)器算法在中央服務(wù)器(Central-Server)算法中，一個(gè)中央服務(wù)器維護(hù)所有的共享數(shù)據(jù)。它服務(wù)從其它結(jié)點(diǎn)或者客戶來(lái)的讀請(qǐng)求，返回?cái)?shù)據(jù)項(xiàng)給它們（見(jiàn)圖）。在客戶寫(xiě)請(qǐng)求時(shí)，它更新數(shù)據(jù)并返回表示收到的消息。中央服務(wù)器算法在表示收到的消息失效情況一個(gè)超時(shí)(timeout)可以被采用來(lái)重發(fā)請(qǐng)求。重復(fù)的寫(xiě)請(qǐng)求可以由寫(xiě)請(qǐng)求所伴隨的順序號(hào)檢測(cè)。在幾次重新傳輸而又無(wú)響應(yīng)后一個(gè)失敗的條件被返回到企圖訪問(wèn)共享數(shù)據(jù)的應(yīng)用。中央服務(wù)器算法雖然中央服務(wù)器算法其實(shí)現(xiàn)是簡(jiǎn)單的

8、，但中央服務(wù)器可能變成一個(gè)瓶頸。為了克服這個(gè)問(wèn)題，共享數(shù)據(jù)可以分布在幾個(gè)服務(wù)器上。在這種情況下，客戶必須能夠?qū)γ看螖?shù)據(jù)訪問(wèn)定位適當(dāng)?shù)姆?wù)器。中央服務(wù)器算法多點(diǎn)廣播式的數(shù)據(jù)訪問(wèn)請(qǐng)求是不希望的，因?yàn)榕c中央服務(wù)器方案相比，它并不減少服務(wù)器的負(fù)載。分布數(shù)據(jù)的一種較好的方法是按地址劃分共享數(shù)據(jù)并且利用一個(gè)映照函數(shù)定位適當(dāng)?shù)姆?wù)器。遷移算法在中央服務(wù)器算法中，每個(gè)數(shù)據(jù)訪問(wèn)請(qǐng)求被發(fā)送到數(shù)據(jù)的位置，與之相比，在遷移算法中的數(shù)據(jù)被轉(zhuǎn)移到數(shù)據(jù)訪問(wèn)請(qǐng)求的地點(diǎn)，允許隨后的對(duì)該數(shù)據(jù)的訪問(wèn)被本地地執(zhí)行。遷移算法每次僅允許一個(gè)結(jié)點(diǎn)訪問(wèn)一個(gè)共享數(shù)據(jù)。遷移算法遷移算法在中央服務(wù)器算法中，每個(gè)數(shù)據(jù)訪問(wèn)請(qǐng)求被發(fā)送到數(shù)據(jù)的位置，與之

9、相比，在遷移算法中的數(shù)據(jù)被轉(zhuǎn)移到數(shù)據(jù)訪問(wèn)請(qǐng)求的地點(diǎn)，允許隨后的對(duì)該數(shù)據(jù)的訪問(wèn)被本地地執(zhí)行。遷移算法每次僅允許一個(gè)結(jié)點(diǎn)訪問(wèn)一個(gè)共享數(shù)據(jù)。遷移算法典型地，包含數(shù)據(jù)項(xiàng)的整個(gè)頁(yè)或塊遷移以代替單個(gè)請(qǐng)求項(xiàng)。這個(gè)算法利用由程序所展示的引用的局部性把遷移的費(fèi)用分?jǐn)偟蕉鄠€(gè)訪問(wèn)遷移數(shù)據(jù)上。但是這種途徑對(duì)抖動(dòng)(thrashing)敏感，其中頁(yè)頻繁地在結(jié)點(diǎn)間遷移，而僅服務(wù)少數(shù)請(qǐng)求。遷移算法為了減少抖動(dòng)，Mirage系統(tǒng)使用一個(gè)可調(diào)的參量決定一個(gè)結(jié)點(diǎn)可以擁有一個(gè)共享數(shù)據(jù)項(xiàng)的期間。這允許在頁(yè)被遷移到另一結(jié)點(diǎn)之前一個(gè)結(jié)點(diǎn)對(duì)該頁(yè)作若干次訪問(wèn)。Munin系統(tǒng)力求采用適合不同的數(shù)據(jù)訪問(wèn)模式的協(xié)議來(lái)減少數(shù)據(jù)移動(dòng)。遷移算法遷移算法提

10、供了一個(gè)機(jī)會(huì)把分布式共享內(nèi)存與運(yùn)行在單個(gè)結(jié)點(diǎn)上操作系統(tǒng)所提供的虛存集成在一起。當(dāng)分布式共享內(nèi)存所用的頁(yè)大小是虛存頁(yè)大小的倍數(shù)時(shí)，一個(gè)本地掌握的共享內(nèi)存頁(yè)可以被映照到一個(gè)應(yīng)用的虛地址空間并且利用正常的機(jī)器指令訪問(wèn)。遷移算法在一個(gè)內(nèi)存訪問(wèn)失效時(shí)，如果內(nèi)存地址映照到一個(gè)遠(yuǎn)程頁(yè)，在映照頁(yè)到進(jìn)程的地址空間之前，一個(gè)頁(yè)失效處理程序?qū)⑦w移該頁(yè)。在遷移一頁(yè)時(shí)，該頁(yè)從所有在以前結(jié)點(diǎn)被映照到的地址空間移開(kāi)。注意，幾個(gè)進(jìn)程可以共享在一個(gè)結(jié)點(diǎn)上的一頁(yè)。遷移算法為了定位一個(gè)數(shù)據(jù)塊，遷移算法可以利用一個(gè)服務(wù)器追蹤頁(yè)的位置或者通過(guò)在結(jié)點(diǎn)上所維持的提示。這些提示指向搜尋當(dāng)前占有該頁(yè)的結(jié)點(diǎn)。另外，一個(gè)詢問(wèn)可以廣播來(lái)定位一頁(yè)。讀

11、復(fù)制(Read-Replicatin)算法在前面途徑中僅僅在一個(gè)結(jié)點(diǎn)上的進(jìn)程可以在如何時(shí)刻訪問(wèn)一個(gè)共享數(shù)據(jù)。讀復(fù)制(Read-Replicatin)算法擴(kuò)充了遷移算法，即復(fù)制數(shù)據(jù)塊并且允許多個(gè)結(jié)點(diǎn)具有讀訪問(wèn)或一個(gè)結(jié)點(diǎn)具有讀寫(xiě)訪問(wèn)（多個(gè)讀者-一個(gè)作者協(xié)議）。讀復(fù)制算法讀復(fù)制算法由允許多個(gè)結(jié)點(diǎn)并發(fā)地訪問(wèn)數(shù)據(jù)，讀復(fù)制可以改善系統(tǒng)性能。但是，寫(xiě)操作是昂貴的，因?yàn)橐粋€(gè)共享塊在各種結(jié)點(diǎn)上的所有副本將或者不得不是無(wú)效的，或者用當(dāng)前值來(lái)更新以維護(hù)共享數(shù)據(jù)塊的一致性。讀復(fù)制算法在讀復(fù)制算法中分布式共享內(nèi)存必須追蹤所有數(shù)據(jù)塊副本的位置。在IVY系統(tǒng)中，一個(gè)數(shù)據(jù)塊的擁有者結(jié)點(diǎn)追蹤具有該數(shù)據(jù)塊的一個(gè)副本的所有結(jié)點(diǎn)。在

12、PLUS系統(tǒng)中，一個(gè)分布式鏈接列表用來(lái)追蹤具有該數(shù)據(jù)塊的一個(gè)副本的所有結(jié)點(diǎn)。讀復(fù)制算法然而，當(dāng)讀對(duì)寫(xiě)的比例是大的時(shí)候，讀復(fù)制有減少讀操作平均費(fèi)用的潛力。在節(jié)描述在IVY系統(tǒng)中實(shí)現(xiàn)的許多讀復(fù)制算法。完全復(fù)制算法完全復(fù)制算法是讀復(fù)制算法的一種擴(kuò)充。讀復(fù)制算法它允許多個(gè)結(jié)點(diǎn)具有對(duì)共享數(shù)據(jù)塊的讀和寫(xiě)兩種訪問(wèn)（多個(gè)讀者-多個(gè)作者協(xié)議）。由于許多結(jié)點(diǎn)可以并發(fā)地寫(xiě)共享數(shù)據(jù)，對(duì)共享數(shù)據(jù)的訪問(wèn)必須被控制以維持它的一致性。完全復(fù)制算法維持一致性的一個(gè)簡(jiǎn)單方法是利用一個(gè)無(wú)間隙的順序器(gap-free sequencer)。在這種方案下，所有希望修改共享數(shù)據(jù)的結(jié)點(diǎn)將發(fā)送修改給一個(gè)順序器。這個(gè)順序器將賦予一個(gè)順序號(hào)并

13、且多點(diǎn)廣播這個(gè)修改及順序號(hào)到所有具有該共享數(shù)據(jù)項(xiàng)副本的結(jié)點(diǎn)。完全復(fù)制算法每個(gè)結(jié)點(diǎn)以順序號(hào)次序處理修改請(qǐng)求。在一個(gè)結(jié)點(diǎn)上一個(gè)修改請(qǐng)求的順序號(hào)和期待的順序號(hào)之間的間隙指示一個(gè)或多個(gè)修改已被遺漏。在這種情況下結(jié)點(diǎn)將被請(qǐng)求重新傳送已經(jīng)遺漏的修改。這蘊(yùn)涵在某個(gè)結(jié)點(diǎn)保留修改的日記。在第5節(jié)將討論若干其它維護(hù)共享數(shù)據(jù)的一致性的協(xié)議。完全復(fù)制算法存儲(chǔ)一致性(Memory coherence)為了改善性能分布式共享內(nèi)存系統(tǒng)依賴復(fù)制共享數(shù)據(jù)項(xiàng)和允許在許多結(jié)點(diǎn)上并發(fā)訪問(wèn)。但是，如果并發(fā)訪問(wèn)不仔細(xì)地加以控制，內(nèi)存訪問(wèn)可能以不同于程序員所期望的次序被執(zhí)行。非正式講，一個(gè)內(nèi)存是一致的，如果由讀操作返回的值總歸是程序員所期

14、望的值。存儲(chǔ)一致性例如，對(duì)一個(gè)程序員期待一個(gè)讀操作返回一個(gè)最近寫(xiě)操作所存貯的值是相當(dāng)自然的。存儲(chǔ)一致性因此，為了維護(hù)共享數(shù)據(jù)項(xiàng)的一致性，一個(gè)控制或同步訪問(wèn)的機(jī)制是必要的。同樣為了寫(xiě)正確的程序，程序員需要理解如何進(jìn)行對(duì)共享內(nèi)存的并發(fā)更新。允許的內(nèi)存訪問(wèn)次序集合構(gòu)成了存儲(chǔ)一致性模型。字一致性用于說(shuō)明一種特殊類(lèi)型的一致性。存儲(chǔ)一致性存儲(chǔ)一致性最直觀語(yǔ)義是嚴(yán)格一致性(strict consistency)，其定義如下：一個(gè)讀返回最近寫(xiě)的值。嚴(yán)格一致性要求具有決定最近寫(xiě)的能力，依次它蘊(yùn)涵請(qǐng)求的全序。由于比一個(gè)程序可能實(shí)際需要更多的數(shù)據(jù)移動(dòng)和同步要求，請(qǐng)求的全序?qū)е路怯行裕ㄕ?qǐng)參考4）。存儲(chǔ)一致性為了解決

15、這個(gè)問(wèn)題，某些分布式共享內(nèi)存系統(tǒng)企圖由提供不嚴(yán)格的一致性語(yǔ)義來(lái)改善性能。下列是幾種內(nèi)存一致性形式：存儲(chǔ)一致性F順序的一致性 (Sequential consistency)F一般一致性(General Consistency)F處理機(jī)一致性 (Processor consistency)F弱一致性(Weak consistency)F釋放一致性(Release consistency)一致性模型實(shí)質(zhì)上是軟件和存儲(chǔ)器間的契約（Adve和Hill，1990），它是說(shuō)，如果軟件同意服從某模型給出的規(guī)則，則存儲(chǔ)器允諾軟件在這種模型下正確地工作；否則，存儲(chǔ)器操作的正確性將得不到保證。存儲(chǔ)器一致性問(wèn)題對(duì)于

16、共享地址空間的并行計(jì)算機(jī)特別重要，已提出二三十種一致性模型。 最嚴(yán)格的一致性模型稱為嚴(yán)格一致性，它由下述條件定義：這個(gè)定義自然而明白，由于它假定了絕對(duì)全局時(shí)間（就像在牛頓物理中）的存在，“最近”訪問(wèn)的意義是明確的。傳統(tǒng)意義上，單處理機(jī)遵守嚴(yán)格一致性，單處理機(jī)的編程者正希望這樣。 最嚴(yán)格的也是最理想的存儲(chǔ)器一致性模型是嚴(yán)格一致性。它定義為：假設(shè)X是存在B機(jī)器上的變量。A機(jī)器上的進(jìn)程在T1時(shí)刻讀取X，即發(fā)送信包到B以讀取X。稍后，在T2時(shí)刻，B機(jī)器上的進(jìn)程寫(xiě)X。若遵守嚴(yán)格一致性，不管機(jī)器在哪里，也不管T1和T2相距多近，A都應(yīng)該讀出原來(lái)的值。然而，若T2 - T1 = 1ns，而機(jī)器距離 3米，從

17、A到B傳送讀操作并使之先于寫(xiě)操作，信號(hào)則必須以十倍光速的速度（ ）傳遞，而這與愛(ài)因斯坦相對(duì)論矛盾。編程人員有理由在違反了物理原則的情況下要求嚴(yán)格一致性嗎？ 秒米秒米/3000000100000013TSVF但是無(wú)法保證每個(gè)時(shí)間間隔內(nèi)最多只發(fā)生一個(gè)單一操作。因此，仍需要處理在同一時(shí)間間隔內(nèi)所發(fā)生的多個(gè)操作。如果同一時(shí)間間隔內(nèi)的兩個(gè)操作是對(duì)相同數(shù)據(jù)進(jìn)行操作，并且其中一個(gè)操作是寫(xiě)操作，那么稱這兩個(gè)操作是沖突的。F定義一致性模型的一個(gè)重要問(wèn)題就是準(zhǔn)確定義出現(xiàn)沖突時(shí)，哪些行為是可接受的。F這就要求在軟件和存儲(chǔ)之間做一個(gè)約定。如果這種約定顯式或隱式地承諾滿足嚴(yán)格一致性，那么存儲(chǔ)器就能正常地工作。F另一方面

18、，編程人員也希望能夠滿足嚴(yán)格一致性。如果不支持嚴(yán)格一致性，程序發(fā)生問(wèn)題就很難說(shuō)是那方面的問(wèn)題。F例如，在一個(gè)小型多處理機(jī)系統(tǒng)中，如果某個(gè)處理機(jī)寫(xiě)存儲(chǔ)器a單元，1ns以后，另一個(gè)處理機(jī)讀存儲(chǔ)器a單元，這個(gè)處理機(jī)可能是從它的局部高速緩存中獲得了老的值。這樣就很可能同樣的程序運(yùn)行多次得到 的結(jié)果卻是多個(gè)，而不是唯一的。先規(guī)定一些符號(hào)：P1，P2，代表不同的進(jìn)程，在圖中以不同的高度表示。每一進(jìn)程完成的操作按水平的顯示時(shí)間軸向右增加，直線分割不同進(jìn)程。符號(hào)Wi(X)a和Ri(Y)b分別表示進(jìn)程Pi在X處寫(xiě)a和從Y處讀出值為b。當(dāng)進(jìn)程訪問(wèn)數(shù)據(jù)而未發(fā)生沖突時(shí)，忽略符號(hào)Wi(X)和Ri(Y)的下標(biāo)i。本章中所

19、有圖表中變量初值均為0。 總之，對(duì)于嚴(yán)格一致性的存儲(chǔ)器，寫(xiě)操作在任一時(shí)刻對(duì)所有進(jìn)程都是可見(jiàn)的，同時(shí)維護(hù)一個(gè)絕對(duì)全局時(shí)間順序。一旦存儲(chǔ)器中的值改變，不管讀寫(xiě)之間的事件間隔多小，不管哪個(gè)進(jìn)程執(zhí)行讀操作，也不管進(jìn)程在何處，以后讀出的都是新更改的值。同樣，如果執(zhí)行了讀操作，不管后面的寫(xiě)操作有多迅速，該讀操作仍應(yīng)讀出原來(lái)的值。 F嚴(yán)格一致性是理想的編程模式，在一個(gè)實(shí)際的NUMA系統(tǒng)中，若不采取特殊措施，就不一定能得到保證。例如，在一個(gè)處理機(jī)訪問(wèn)本地存儲(chǔ)器的時(shí)間為T(mén)1，訪問(wèn)遠(yuǎn)程存儲(chǔ)器的時(shí)間為T(mén)2的NUMA系統(tǒng)中，記T2-T1=2d。設(shè)處理機(jī)P1的本地存儲(chǔ)器單元x的初值為0，在t時(shí)刻處理機(jī)P2向遠(yuǎn)程存儲(chǔ)器單

20、元x發(fā)出寫(xiě)入值1的指令，在在t+d時(shí)刻處理機(jī)P1讀本地存儲(chǔ)器單元x，由于P2的指令尚未到達(dá)P1的存儲(chǔ)器的控制器，故P1讀得的值仍為0。對(duì)于常規(guī)的編程模式，這無(wú)疑會(huì)導(dǎo)致程序的結(jié)果不正確。盡管?chē)?yán)格一致性是理想的編程模式，但在分布式系統(tǒng)中，這幾乎不可能實(shí)現(xiàn)。經(jīng)驗(yàn)表明，編程人員通常對(duì)弱模式掌握得較好。比如，所有操作系統(tǒng)課本中都談到臨界區(qū)和同步互斥的問(wèn)題。人們認(rèn)為編寫(xiě)這種正確的并行程序（如生產(chǎn)者-消費(fèi)者問(wèn)題）不應(yīng)考慮進(jìn)程間的相對(duì)速度以及語(yǔ)句的執(zhí)行在時(shí)間上如何交錯(cuò)。 如果一個(gè)進(jìn)程的兩個(gè)事件發(fā)生如此之快，以致其他進(jìn)程不能在此之間執(zhí)行任何操作，那可能會(huì)帶來(lái)麻煩。相反，讀者的編程方式是：語(yǔ)句執(zhí)行的確切時(shí)間（實(shí)際

21、上是存儲(chǔ)器訪問(wèn)）并不重要，而當(dāng)事件（讀或?qū)懀┑捻樞蚴侵陵P(guān)重要時(shí)，可以使用信號(hào)量等方法實(shí)現(xiàn)同步操作。接受這種意見(jiàn)意味著采用較弱的一致性模式來(lái)編程。經(jīng)過(guò)幾次實(shí)踐，大多數(shù)并行程序編寫(xiě)人員都能適應(yīng)這種模式。因此，程序設(shè)計(jì)者使用較弱的一致性模式同樣可以使存儲(chǔ)器正常工作。順序一致是比嚴(yán)格一致稍弱的存儲(chǔ)器模式，Lamport（1979）首先定義了順序一致存儲(chǔ)器應(yīng)符合的條件： Lamport （1979）定義的順序一致性存儲(chǔ)器滿足如下條件： 這個(gè)定義意味著，當(dāng)程序在各個(gè)機(jī)器上并行運(yùn)行時(shí)，任何一種有效的交錯(cuò)存儲(chǔ)器訪問(wèn)順序都是可認(rèn)可的行為，但所有處理器必須看見(jiàn)的是同樣的訪問(wèn)順序。如果一個(gè)進(jìn)程（處理器）看見(jiàn)的是一種

22、交錯(cuò)，另一進(jìn)程看見(jiàn)的是另一種交錯(cuò)，則這樣的存儲(chǔ)器不是一個(gè)順序一致性的存儲(chǔ)器。然而，同一程序再次并行運(yùn)行，其存儲(chǔ)器訪問(wèn)的交錯(cuò)次序會(huì)不同于上次的交錯(cuò)次序，這是允許的。 這個(gè)定義說(shuō)明：對(duì)于在不同機(jī)器上（甚至在偽并行的分時(shí)系統(tǒng)上）并行運(yùn)行的進(jìn)程，任何有效的交錯(cuò)都是可以接受的行為，但所有進(jìn)程必須遵守同一訪問(wèn)存儲(chǔ)器順序。在一塊存儲(chǔ)器中，若一個(gè)進(jìn)程（或處理機(jī)）看到一種交錯(cuò)，另一進(jìn)程看到另一個(gè)交錯(cuò)，這就不是順序一致存儲(chǔ)器。注意，這與時(shí)間無(wú)關(guān)，沒(méi)有最近存入的概念。在這里，進(jìn)程可以看到所有進(jìn)程寫(xiě)，但只能看到本進(jìn)程讀。 順序一致存儲(chǔ)器不保證讀返回的值是1ns、1ms甚至1分鐘以前另一進(jìn)程寫(xiě)入的。它只保證所有進(jìn)程以相同的順序看見(jiàn)存儲(chǔ)器訪問(wèn)。如果根據(jù)圖（a）編寫(xiě)的程序在一次運(yùn)行后，或許會(huì)得到圖（b）的結(jié)果。結(jié)果是不確定的。如果缺少明確的同步操作，在此運(yùn)行程序或許不能