第四章分布式資源管理

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

第一種方法是將整個(gè)文件轉(zhuǎn)移給場(chǎng)點(diǎn)A，爾后，所有對(duì)該文件的存取都是局部的了。當(dāng)用戶不再需要訪問(wèn)該文件時(shí)，它的副本（如果它被修改過(guò)）被回送給場(chǎng)點(diǎn)B。對(duì)一個(gè)文件的任何微小的修改，都得將這整個(gè)文件傳送回去。3

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

4

4.1.2計(jì)算遷移

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

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

7

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

分布式系統(tǒng)對(duì)于資源管理有兩種基本的觀點(diǎn)：?jiǎn)蝹€(gè)資源管理單個(gè)資源與多個(gè)管理機(jī)構(gòu)相互關(guān)系的角度進(jìn)行分析。多個(gè)資源管理多個(gè)資源與多個(gè)管理機(jī)構(gòu)相互關(guān)系的角度進(jìn)行分析。前者是后者的基礎(chǔ)，后者是前者的提高。9

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

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

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

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

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

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

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

14

4.2.2局部集中管理

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

4.2.2分散式管理

一個(gè)資源由多個(gè)場(chǎng)點(diǎn)上的管理者在協(xié)商一致的原則下共同管理。

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

174.2.4一個(gè)分散式資源管理算法

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

該算法利用時(shí)間戳來(lái)標(biāo)明申請(qǐng)資源的先后次序，以此來(lái)盡量消除對(duì)共享資源的競(jìng)爭(zhēng)。

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

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

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

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

投標(biāo)與選標(biāo)策略可視具體情況而定，例如，可用等待隊(duì)列中排隊(duì)等待的申請(qǐng)者的個(gè)數(shù)作為標(biāo)數(shù)來(lái)投標(biāo)，選標(biāo)時(shí)則選擇標(biāo)數(shù)最小的投標(biāo)者中標(biāo)，或者不僅考慮有多個(gè)資源申請(qǐng)者，還考慮到投標(biāo)者與招標(biāo)者之間的距離，如，可規(guī)定標(biāo)數(shù)為：

x＝c1

a＋c2

b

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

此時(shí)，⑶修改為：“當(dāng)申請(qǐng)者接收到所有的投標(biāo)消息后，或等待時(shí)間超過(guò)預(yù)定時(shí)間值T后，根據(jù)一定的策略選擇一個(gè)投標(biāo)者，并直接向它發(fā)送一條申請(qǐng)資源的消息”。容易看出，該算法有如下特點(diǎn)：

⑴不會(huì)出現(xiàn)饑餓現(xiàn)象，因?yàn)橹灰到y(tǒng)中有所申請(qǐng)的資源就必有一個(gè)中標(biāo)者，只要每個(gè)資源占有者在有限長(zhǎng)時(shí)間內(nèi)歸還所占資源，申請(qǐng)者總能從中標(biāo)者處獲得所需資源。⑵在無(wú)場(chǎng)點(diǎn)故障情況下，從廣播招標(biāo)消息到接到獲得資源的通知，一共交換了2(n-1)＋2＝2n條消息。24252.適用于環(huán)形結(jié)構(gòu)的招標(biāo)算法

對(duì)于具有環(huán)形結(jié)構(gòu)的分布式計(jì)算機(jī)系統(tǒng)，相應(yīng)的招標(biāo)算法為：

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

26

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

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

27

4.3分布式系統(tǒng)中的死鎖處理分布式系統(tǒng)中用于解決死鎖問(wèn)題的方法?；谒梨i預(yù)防基于死鎖檢測(cè)。引入資源分配圖和進(jìn)程等待圖的概念。

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)}

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

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

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

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

利用時(shí)間戳預(yù)防死鎖的兩種方法是：34

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

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

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

36

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

死鎖預(yù)防算法甚至在不發(fā)生死鎖時(shí)也可能搶占資源。死鎖檢測(cè)算法構(gòu)造一等待圖來(lái)描述資源分配狀態(tài)。因?yàn)槲覀兗俣款愘Y源只有單個(gè)例示，因此，等待圖中的環(huán)路就表示死鎖發(fā)生。如何管理等待圖？要求每一場(chǎng)點(diǎn)管理一個(gè)局部等待圖。圖中的結(jié)點(diǎn)對(duì)應(yīng)所有這樣的進(jìn)程（本地及遠(yuǎn)程的），這些進(jìn)程當(dāng)前正占有或者正在申請(qǐng)局部于該場(chǎng)點(diǎn)的任何資源。例如，圖4.6中的系統(tǒng)由兩個(gè)場(chǎng)點(diǎn)組成，每個(gè)場(chǎng)點(diǎn)都管理它的局部等待圖。注意進(jìn)程p2和p3出現(xiàn)在兩個(gè)圖中，表示它們?cè)趦蓚€(gè)場(chǎng)點(diǎn)中申請(qǐng)資源。4.3.4死鎖檢測(cè)方法38圖4.6局部等待圖和全局等待圖39

顯然，如果任何局部等待圖中存在環(huán)路，則表明發(fā)生了死鎖。但任何局部等待圖中不出現(xiàn)環(huán)路并不意味不存在死鎖。例如，考慮圖4.6中的情況，其中每個(gè)局部等待圖中均無(wú)環(huán)路，但該系統(tǒng)卻存在死鎖，因?yàn)樵谒乃芯植康却龍D之并圖中存在環(huán)路。圖4.7中的等待圖就是圖4.6中兩個(gè)（局部）等待圖之并，它的確含有環(huán)路，這隱含該系統(tǒng)存在死鎖。

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

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

41

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

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

如果同一場(chǎng)點(diǎn)中的進(jìn)程pi向pj提出申請(qǐng)，則相應(yīng)的請(qǐng)求消息中不必附上時(shí)間戳。該檢測(cè)算法的執(zhí)行過(guò)程如下：

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

46⑶當(dāng)協(xié)調(diào)者接收到來(lái)自每一場(chǎng)點(diǎn)的回復(fù)消息后，它就按如下方法構(gòu)造等待圖：①系統(tǒng)中的每一進(jìn)程作為圖中一個(gè)結(jié)點(diǎn)；