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

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

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

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

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

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

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

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

8、，但中央服務器可能變成一個瓶頸。為了克服這個問題，共享數(shù)據(jù)可以分布在幾個服務器上。在這種情況下，客戶必須能夠對每次數(shù)據(jù)訪問定位適當?shù)姆掌鳌Ｖ醒敕掌魉惴ǘ帱c廣播式的數(shù)據(jù)訪問請求是不希望的，因為與中央服務器方案相比，它并不減少服務器的負載。分布數(shù)據(jù)的一種較好的方法是按地址劃分共享數(shù)據(jù)并且利用一個映照函數(shù)定位適當?shù)姆掌?。遷移算法在中央服務器算法中，每個數(shù)據(jù)訪問請求被發(fā)送到數(shù)據(jù)的位置，與之相比，在遷移算法中的數(shù)據(jù)被轉移到數(shù)據(jù)訪問請求的地點，允許隨后的對該數(shù)據(jù)的訪問被本地地執(zhí)行。遷移算法每次僅允許一個結點訪問一個共享數(shù)據(jù)。遷移算法遷移算法在中央服務器算法中，每個數(shù)據(jù)訪問請求被發(fā)送到數(shù)據(jù)的位置，與之

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

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

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

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

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

14、望的值。存儲一致性例如，對一個程序員期待一個讀操作返回一個最近寫操作所存貯的值是相當自然的。存儲一致性因此，為了維護共享數(shù)據(jù)項的一致性，一個控制或同步訪問的機制是必要的。同樣為了寫正確的程序，程序員需要理解如何進行對共享內存的并發(fā)更新。允許的內存訪問次序集合構成了存儲一致性模型。字一致性用于說明一種特殊類型的一致性。存儲一致性存儲一致性最直觀語義是嚴格一致性(strict consistency)，其定義如下：一個讀返回最近寫的值。嚴格一致性要求具有決定最近寫的能力，依次它蘊涵請求的全序。由于比一個程序可能實際需要更多的數(shù)據(jù)移動和同步要求，請求的全序導致非有效性（請參考4）。存儲一致性為了解決

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

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

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

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

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

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

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

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