第四章分布式資源管理

1第四章分布式資源管理4.1資源共享4.2資源管理策略4.3分布式系統(tǒng)中的死鎖處理24.1資源共享實現資源共享的三種方法。4.1.1數據遷移數據遷移的兩種方法：

第一種方法是將整個文件轉移給場點A，爾后，所有對該文件的存取都是局部的了。當用戶不再需要訪問該文件時，它的副本（如果它被修改過）被回送給場點B。對一個文件的任何微小的修改，都得將這整個文件傳送回去。3

另一種方法是只將該文件中實際需要的部分轉移給A。一旦用戶不再使用該文件，該文件的任何已作過修改時部分必須回送給場點B。顯然，如果只訪問一個較大文件的一小部分，那么采用后一種方法較好；否則采用第一種方法較合適。不過，僅僅從一個場點向另一個場點轉移數據是不夠的，系統(tǒng)還得執(zhí)行各種數據轉換（如果兩個場點不是直接兼容的話）。例如，如果它們使用了不同的字符代碼表示。

4

4.1.2計算遷移

在某些情形中，轉移計算比轉移數據更有效。例如，考慮這樣一個作業(yè)，它需要存取位于不同場點上的若干較大的文件，以獲得它們的概況。一種比較有效的辦法是在它們駐留的場點上各自存取這些文件，然后分別回送所需要的值給初啟該計算的那個場點。計算的實現方式：可用一個遠程過程調用來初啟。進程p引用場點A上預定義的一個過程，該過程執(zhí)行完后給p回送所需要的結果。5

通過消息傳遞的方式。進程p可以發(fā)送一條消息給場點A，操作系統(tǒng)在場點A創(chuàng)建一個新進程q，q的功能是執(zhí)行由該消息所指定的任務，當q完成其執(zhí)行后，它又通過消息系統(tǒng)給p回送所需要的結果。這兩種方案都可用來存取駐留在各個場點上的若干文件。64.1.3作業(yè)遷移當一個作業(yè)提交給系統(tǒng)后，系統(tǒng)可以在一特定的場點上執(zhí)行這整個作業(yè)，或在不同的場點上執(zhí)行它的某一部分利用這種方案的主要原因是：⑴負載均衡：作業(yè)（或子作業(yè)）可以分散到系統(tǒng)中以均衡系統(tǒng)的工作負載。⑵計算速度的提高：如果單個作業(yè)可以分解成若干子作業(yè)，這些子作業(yè)可以在不同的場點并發(fā)地執(zhí)行，那么，整個作業(yè)的周轉時間將會減少。

7

⑶硬件特性：該作業(yè)可能有這祥一些特性，即它比較適合于在某些特殊的處理機上執(zhí)行。例如，矩陣轉換就比較適合于在陣列機上執(zhí)行。⑷軟件特性：該作業(yè)可能需要特定場點上的軟件或不能移動的軟件，或者移動該作業(yè)比較劃算。顯示遷移隱式遷移84.2資源管理管理策略

分布式系統(tǒng)對于資源管理有兩種基本的觀點：單個資源管理單個資源與多個管理機構相互關系的角度進行分析。多個資源管理多個資源與多個管理機構相互關系的角度進行分析。前者是后者的基礎，后者是前者的提高。9

⑴單個資源管理，有四種資源管理方式：集中管理方式：只有一個管理者對該資源的各種活動統(tǒng)一進行管理，其它管理者對該資源均不具有管理職能和責任。該方式也稱為專制（autocratic）管理方式。功能分布管理方式：多個管理者按照不同的資源活動分擔管理職能和責任，且每種活動只由一個管理者管理。該方式也稱為分擔管理方式或分割（partitioned)管理方式。10浮動管理方式：多個管理者均可同等地擔負管理職能和責任，但在一段時間內，只有一個管理者行使職權，“任期”滿后再由另一管理者接替，如此輪流下去。該方式也稱輪流（successive）管理方式。分散管理方式：多個管理者采取協商一致的原則對資源活動進行全面管理，其中各個管理者的地位和功能是完全平等的。該方式也稱民主(democratic）管理方式。

11⑵從多個資源管理，可分為如下四種管理方式：

集中：每一類資源只屬一個管理者管理。它控制該類全部資源。

分管（集中分布式）：每一類資源由多個管理者管理，但每一資源只屬一個管理者管理。

合管（完全分布式）：不僅每一類資源存在多個管理者管理，而且該類中每個資源屬于全部管理者共同管理。

部分管理：每一類資源由多個管理者管理，每一資源屬于若干管理者管理。如圖4.1所示。其中圓圈表示管理者，三角形表示資源。12圖4.1資源管理方式13

分布式管理方式和集中式管理方式的主要區(qū)別是對同類資源是采用多個管理者還是一個管理者。集中分布管理和完全分布管理的主要區(qū)別是前者讓資源管理者對它管理的資源擁有全部控制權，而后者只允許資源管理者對它管理的資源擁有部分控制權。從上述兩種管理方式的角度來考慮系統(tǒng)資源的劃分。從實用的角度講，分布式系統(tǒng)中的資源管理方式主要有局部集中式、分散式和分級式。

14

4.2.2局部集中管理

每個資源由一個且僅由一個資源管理者管理，具體講就是，資源按其在各場點上的分布情況分別由其所在的場點進行局部的集中管理，不存在全系統(tǒng)范圍的集中管理者。這種管理方式主要適用于和處理機緊密相連的資源，如內存、鍵盤、顯示器，當與它們緊密相連的處理機失效時，這些資源也就隨之失效了。15

4.2.2分散式管理

一個資源由多個場點上的管理者在協商一致的原則下共同管理。

這類則和處理機的關系不甚緊密，例如多副本文件，網絡打印機等。164.2.3分級式管理分級式管理的基本原理是：⑴針對實際的分布式系統(tǒng)對其中的各種資源進行分析，然后根據其重要性、常用性和隸屬關系將資源分為兩個級別：第一級是被多個場點經常使用的資源；第二級是僅被本場點使用的資源。⑵采用不同的方式管理不同級別的資源。即對第一級資源，由于它們被系統(tǒng)中的多個場點經常使用，因此，必須采用分散式管理方式，由多個場點在協商一致的原則下共同管理。對第二級資源，由于它們屬于某個場點，不被其它場點使用，可以采用集中式管理方式，由某個場點集中管理。

174.2.4一個分散式資源管理算法

1.基本說明⑴占有資源的進程，必須先釋放資源，系統(tǒng)才能把該資源分配給另一進程；⑵多個進程申請同一資源時，必須按其請求的先后次序來分配；⑶若每個分配到資源的進程都在有限時間內釋放所占有的資源，則每個資源申者就可能在有限時間內獲得該資源；⑷假定系統(tǒng)由n個場點組成，每個場點運行一個進程，它們的編號依次為p1,p2,…,pn。每個進程都有一個自己管理的申請隊列．用以存放請求消息。182.算法描述

該算法利用時間戳來標明申請資源的先后次序，以此來盡量消除對共享資源的競爭。

⑴當系統(tǒng)中的任一進程pi，申請資源rj時，向系統(tǒng)中的其它每一進程發(fā)一Request(Ti,pi,rj)消息，（其中Ti為此時的時間戳）并把它存入自己的請求隊列；⑵進程pk，接收到這一消息后，將其存入自己的請求隊列，若pk當前未請求該資源，則它馬上給Pi發(fā)送一個帶有時間戳的認可消息；若pk也正在請求使用該資源，且其時間戳Tk先于Ti，則它暫不給Pi發(fā)送認可消息；

19⑶僅當下列條件成立時，Pi才可以分配該資源;①在其請求隊列中，它的Request(Ti,pi,rj)消息中的Ti比所有其它請求消息中的時間戳都要??；②pi已接收到所有其它進程發(fā)來的時間戳遲于Ti的認可消息。⑷在釋放資源時，pi從自己的請求隊列中去掉Request(Ti,pi,ri)消息，并向系統(tǒng)中每個正等待請求使用該資源的進程發(fā)一條Release(Ti’,pi,ri)消息和一條帶時間戳的認可消息。⑸當進程pj收到pi發(fā)來的Release(Ti’,pi,ri)消息后，從其請求隊列中去掉Request(Ti,pi,ri)消息。201.算法描述

⑴當一資源管理者打算向其它場點的資源管理者申請資源時，先將招標消息廣播出去；⑵當一資源管理者接收到這一招標消息后，若該場點有所需資源，則它根據一定方法計算出”標數”。然后，給申請者發(fā)一條投標消息，否則回復一條拒絕投標的消息；

4.2.5招標算法21⑶當申請者接收到所有的投標消息后，根據一定的策略選擇一個投標者，并直接向它發(fā)送一條申請資源的消息；⑷接收到此申請資源消息的資源管理者，將申請者的名字排入其等待隊列，并在可以分配所指資源時再發(fā)消息通知申請者；⑸申請者在使用完所需資源后，通知分配資源者回收資源。22

投標與選標策略可視具體情況而定，例如，可用等待隊列中排隊等待的申請者的個數作為標數來投標，選標時則選擇標數最小的投標者中標，或者不僅考慮有多個資源申請者，還考慮到投標者與招標者之間的距離，如，可規(guī)定標數為：

x＝c1

a＋c2

b

選取最小的x中標，其中a為等待的申請者的個數，b為投標者與招標者之間的距離c1和c2為兩個常數。采用這種投標與選標策略考慮到了資源使用的均衡性和有效性。23若考慮場點故障而仍使該算法有效，則可增加如下措施：⑹若資源申請者發(fā)出申請消息后久末獲得所需資源，則向中標者發(fā)一詢問消息，若中標者末故障就立即予以回復；若發(fā)出詢問消息后仍無回復，則申請者重新廣播招標消息。

此時，⑶修改為：“當申請者接收到所有的投標消息后，或等待時間超過預定時間值T后，根據一定的策略選擇一個投標者，并直接向它發(fā)送一條申請資源的消息”。容易看出，該算法有如下特點：

⑴不會出現饑餓現象，因為只要系統(tǒng)中有所申請的資源就必有一個中標者，只要每個資源占有者在有限長時間內歸還所占資源，申請者總能從中標者處獲得所需資源。⑵在無場點故障情況下，從廣播招標消息到接到獲得資源的通知，一共交換了2(n-1)＋2＝2n條消息。24252.適用于環(huán)形結構的招標算法

對于具有環(huán)形結構的分布式計算機系統(tǒng)，相應的招標算法為：

⑴申請資源者向其鄰近場點發(fā)一招標消息；⑵接收到招標消息后，若本場點上無所指資源，則它將招標消息沿環(huán)轉移給下一鄰近場點，否則:①若此消息中未附投標信息，則它將本場點的投標信息附上，并將這一新形成的消息轉移給下一鄰近場點；②若此消息中已附有投標消息，則它就將本場點的投標消息同此消息進行比較，優(yōu)選一個附上轉移給下一鄰近場點；

26

⑶某場點接收到自己發(fā)出的招標消息后，從其中所附的投標信息可知中標者是誰，直接向中標的資源管理者發(fā)一申請資源的消息；

⑷中標者接收到申請消息后，將申請者的名字排入其等待隊列，并在可以分配所需資源時向申請者發(fā)通知；⑸當資源使用完后，申請者通知分配資源者回收資源。對于非環(huán)結構的分布式計算機系統(tǒng)，也可采用上述算法，只要規(guī)定消息統(tǒng)一按“邏輯環(huán)”轉移即可。

27

4.3分布式系統(tǒng)中的死鎖處理分布式系統(tǒng)中用于解決死鎖問題的方法。基于死鎖預防基于死鎖檢測。引入資源分配圖和進程等待圖的概念。

284.3.1資源分配圖

考慮如圖4.2所示的資源分配圖G。其中，V=P∪R，P={p1,p2,p3}，R={r1,r2,r3,r4}，E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3)}

資源類 該類例示個數r1 1r2 2r3 1r4 2圖4.2資源分配圖29可以證明，對于給定的資源分配圖G，若G中不含環(huán)路，則表明系統(tǒng)未發(fā)生死鎖，反之，若G中含有環(huán)路，則表明系統(tǒng)可能存在死鎖。例如，若在圖4.2中插入邊(p3,r2)（如虛線所示），則在這種情形，系統(tǒng)可能出現死鎖。圖4.3含有環(huán)路的資源分配圖圖4.4含有環(huán)路的非死鎖資源分配圖304.3.2進程等待圖

從資源分配圖中去掉表示資源類的方形并且合并相關的有向邊便可得到對應的進程等待圖(processwaitinggraph)。例如，與圖4.3中資源分配圖對應的進程等待圖如圖4.5所示。進程等待圖中從pi到pj的有向邊(pi,pj)意指：pi等待pj釋被它所需要的資源。而有向邊(pi,pj)在進程等待圖中存在，當且僅當對應的資源分配圖中，對某個資源類rk存在兩條邊，(pi,rk)和(rk,pj)。若系統(tǒng)中的每一資源類僅含一個例示，則系統(tǒng)發(fā)生死鎖的充要條件是進程等待圖中存在環(huán)路。進程等待圖常簡稱為等待圖。圖4.5進程等待圖

314.3.3利用時間戳預防死鎖方法預防死鎖即破壞導致死鎖成立的四個必要條件之一入手。四個必要條件：互斥請求與保持不剝奪環(huán)路等待我們可以通過搶占資源（如果必要）來破壞循環(huán)等待條件。為了控制搶占，我們給每個進程賦一個唯一的優(yōu)先數，這些優(yōu)先數用以決定進程pi是否等待進程pj。例如，如果pi的優(yōu)先數高于pj的優(yōu)先數，我們可以讓pi等待pj，否則pi被撤離。這種方法能防止死鎖，因為對于等待圖中的每一條邊(pi,pj)，pi的優(yōu)先數高于pj的優(yōu)先數，因此也就不存在循環(huán)等待現象?？赡軙l(fā)生饑餓現象？提出了使用時間戳作為優(yōu)先數的方法。對系統(tǒng)中的每一進程，當創(chuàng)建它時，就賦給它一個時間戳，3233

⑴等死（wait-die）方法：是一種基于非搶占性技術的方法。當進程申請當前己由pj占有的資源時，僅當pi的時間戳小于pj的時間戳（即pi比pj年長）時，讓pi等待,否則pi被撤離（死去）。例如，假定進程p1，p2和p3分別有時間戳5，10和15，若p1申請已由p2占有的資源，p1就等待；如果p3申請已由p2占有的資源，p3就被撤離。

利用時間戳預防死鎖的兩種方法是：34

⑵因傷等待(wound-wait)：是一種基于搶占性技術的方法。而且與上述方法對應。當pi申請當前已由pj占有的資源時，如果pi的時間戳大于pj的時間戳（即pi比pj年輕）時．讓pi等待，否則pj被撤離（即pj被pi致傷），pi占有資源。再考慮前面的例子，如果p1申請已由p2占有的資源，那么該資源從p2手中搶占，而且p2被撤離；如果p3申請已由p2占有的資源，則p3就等待。35

這兩種方案都可以避免饑餓現象發(fā)生，只要對被撤離的進程不再賦以新的時間戳，因為時間戳總是遞增的，因此，被撤離的進程最終將具有最小的時間戳，因此它將不會再次被撤離。但這兩種方案是有差別的：

⑴在“等死”方案中，年長的進程必須等待年輕的進程釋放它的資源，因此進程越“年長”，它就越容易引起等待。與此相反，在“因傷等待”方案中，年長的進程決不會等待年輕的進程。

36

⑵在“等死”方案中，如果進程pi因為申請已由進程pj占領的資源而被撤離和死掉，那么當它再次激活時，它又可能再次發(fā)出相同的申請，此時，若資源仍由pj占有，那么，pi將再次“死’’掉。因此在得到所需要的資源之前。pi可能被撤離若干次。但在“因傷等待”方案中，進程pi因為pj申請已由它所占有的資源而被撤離和致傷，當pi再次激話并申請正由pj占有的資源時，pi就等待。因此，在“因傷等待”方案中撤離的次數較少。37

死鎖預防算法甚至在不發(fā)生死鎖時也可能搶占資源。死鎖檢測算法構造一等待圖來描述資源分配狀態(tài)。因為我們假定每類資源只有單個例示，因此，等待圖中的環(huán)路就表示死鎖發(fā)生。如何管理等待圖？要求每一場點管理一個局部等待圖。圖中的結點對應所有這樣的進程（本地及遠程的），這些進程當前正占有或者正在申請局部于該場點的任何資源。例如，圖4.6中的系統(tǒng)由兩個場點組成，每個場點都管理它的局部等待圖。注意進程p2和p3出現在兩個圖中，表示它們在兩個場點中申請資源。4.3.4死鎖檢測方法38圖4.6局部等待圖和全局等待圖39

顯然，如果任何局部等待圖中存在環(huán)路，則表明發(fā)生了死鎖。但任何局部等待圖中不出現環(huán)路并不意味不存在死鎖。例如，考慮圖4.6中的情況，其中每個局部等待圖中均無環(huán)路，但該系統(tǒng)卻存在死鎖，因為在它的所有局部等待圖之并圖中存在環(huán)路。圖4.7中的等待圖就是圖4.6中兩個（局部）等待圖之并，它的確含有環(huán)路，這隱含該系統(tǒng)存在死鎖。

有許多不同的方法構造分布式系統(tǒng)中的等待圖，幾個常用的方法介紹如下：404.3.5集中式死鎖檢測方式

采用集中式方式，全局等待圖是取所有局部等待圖之并構造而成的，它是由單一進程管理的，這個特殊的進程稱為”死鎖檢測協調者（coordinator）”進程，等待圖可以在不同時刻構造：⑴每當從局部等待圖中去掉一條邊或向局部等待圖插入一條新的邊時；⑵周期性地當等待圖中已經發(fā)生了若干改變時；⑶每當協調者需要引用環(huán)路檢測算法時。

41

當引用該死鎖檢測算法時，協調者搜索它的全局圖，如果發(fā)現一環(huán)路，則挑選一個進程作為犧牲者予以撤離，從而破壞環(huán)路。事后協調者必須通知所有的場點“此時某一進程已經選作為犧牲者”。接到通知的場點也應作相應的處理。

42這種方案可能導致不必要的撤離，因為存在下述幾種現象：⑴在全局等待圖中可能存在假環(huán)路。例如，考慮圖4.7中的系統(tǒng)。假定p2釋放了它在場點A中占有的資源，從而導致場點A中刪除邊(p1,p2)，然后進程p2申請場點B中已由p3占有的資源，于是導致場點B中插入邊(p2,p3)。如果來自場點B的消息insert(p2,p3)在來自場點A的delete(p1,p2)消息之前到達，那么，在“插入”之后“刪去”之前的這段時間隔，協調者可能發(fā)現假環(huán)路[p1，p2，p3]，我們稱這種情況為假死鎖（falsedeadlock）。這時就得調用死鎖解除算法，盡管實際上并沒有發(fā)生死鎖。43⑵當死鎖的確發(fā)生而且已選定了一個犧牲者，但在同時某進程由于與死鎖毫不相干的原因被暫時夭折（如進程的執(zhí)行時間超過了分配給它的時間片）時，也可能導致不必要的撤離。例如，假定圖4.6中的場點A決定讓p2夭折，但在同時協調者已發(fā)現一個環(huán)路并選定p3作為犧牲者。于是p2和p3現在都得撤離，盡管此時實際上僅p2需要撤離。44為了避免報告假死鎖，它要求來自不同場點的請求消息附上唯一的標識（時間戳）。當場點A上的進程pi申請位于場點B的進程pj占有的資源時，應發(fā)送一條帶有時間戳n的申請消息。于是，邊(pi,pj,n)被插入到A的局部等待圖中，如果pj已經接收到這一請求消息但不能馬上釋放所請求的資源時，邊(pi,pj,n)也插入場點B的局部等待圖中；圖4.7全局等待圖中的假環(huán)路45

如果同一場點中的進程pi向pj提出申請，則相應的請求消息中不必附上時間戳。該檢測算法的執(zhí)行過程如下：

⑴協調者向系統(tǒng)中每一場點發(fā)送一條初始消息；⑵當接收到這一消息后，各場點將它的局部等待圖發(fā)送給協調者。注意，每一個等待圖包含該場點的所有局部信息。這種等待圖反映了相應場點瞬時的狀態(tài)，但它并不與反映任何其它場點的等待圖同步。

46⑶當協調者接收到來自每一場點的回復消息后，它就按如下方法構造等待圖：①系統(tǒng)中的每一進程作為圖中一個結點；