第四章分布式資源管理

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

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

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

4

4.1.2計(jì)算遷移

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

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

7

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

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

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

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

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

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

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

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

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

14

4.2.2局部集中管理

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

4.2.2分散式管理

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

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

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

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

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

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

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

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

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

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

x＝c1

a＋c2

b

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

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

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

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

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

26

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

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

27

4.3分布式系統(tǒng)中的死鎖處理分布式系統(tǒng)中用于解決死鎖問題的方法?；谒梨i預(yù)防基于死鎖檢測。引入資源分配圖和進(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)}

資源類 該類例示個數(shù)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)可能出現(xiàn)死鎖。圖4.3含有環(huán)路的資源分配圖圖4.4含有環(huán)路的非死鎖資源分配圖304.3.2進(jìn)程等待圖

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

314.3.3利用時間戳預(yù)防死鎖方法預(yù)防死鎖即破壞導(dǎo)致死鎖成立的四個必要條件之一入手。四個必要條件：互斥請求與保持不剝奪環(huán)路等待我們可以通過搶占資源（如果必要）來破壞循環(huán)等待條件。為了控制搶占，我們給每個進(jìn)程賦一個唯一的優(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)閷τ诘却龍D中的每一條邊(pi,pj)，pi的優(yōu)先數(shù)高于pj的優(yōu)先數(shù)，因此也就不存在循環(huán)等待現(xiàn)象?？赡軙l(fā)生饑餓現(xiàn)象？提出了使用時間戳作為優(yōu)先數(shù)的方法。對系統(tǒng)中的每一進(jìn)程，當(dāng)創(chuàng)建它時，就賦給它一個時間戳，3233

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

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

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

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

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

36

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

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

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

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

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

41

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

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

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

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

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