摘 要：網(wǎng)格中資源協(xié)同分配是資源組織和調(diào)度的一個重要組成部分，如何檢測應(yīng)用之間的死鎖是資源協(xié)同分配過程中需要解決的重要問題。通過對網(wǎng)格中死鎖原因的分析，對死鎖的特點進(jìn)行描述。提出基于Agent的網(wǎng)格資源協(xié)同分配死鎖處理算法，并對算法進(jìn)行實驗驗證。實驗證明使用該方法不僅能夠檢測解除應(yīng)用資源分配過程中的死鎖，與其他方法相比，還能獲得好的資源分配性能。

關(guān)鍵詞：網(wǎng)格技術(shù)；資源協(xié)同分配；死鎖；分配性能

中圖分類號：TP393.7 文獻(xiàn)標(biāo)識碼：A 文章編號：1004373X(2008)1611204

Study on Deadlock Resource Coallocation in Grid

ZHANG Hengyun.1，DUAN Jinrong.2

(1.Sichuan Staff University of Science and Technology，Chengdu，610101，China;2.Mianyang Normal University，Mianyang，621000，China)

Abstract：Applications designed to execute on grid frequently requires the coallocation.In particular，the problem of coallocating grid resources that span multiple administrative domains are complicated by the possibility of deadlock.Motivated by this，the reason for application deadlock is analyzed and the deadlock in grid is characterized.Further，a new algorithm for coallocation of grid resources is developed based on Agent dealing with deadlocks.At last，algorithm is studied by experiment.Experimental results demonstrate that the proposed method yields a significant performance improvement over the other existing deadlock prevention method.

Keywords：grid technology；resource coallocation；deadlock;allocation performance

1 引 言

網(wǎng)格技術(shù)的出現(xiàn)使得在多機構(gòu)之間大規(guī)模的資源共享和合作使用成為可能。在網(wǎng)格環(huán)境，經(jīng)常需要為任務(wù)同時協(xié)同分配多個資源以滿足性能要求，Ian Foster和Czajkowski第一次提出了資源協(xié)同分配（Coallocation）的概念。在資源協(xié)同分配過程中，一個任務(wù)可以請求若干個資源。在資源預(yù)請求和資源即時請求時，都有可能保持某些資源而請求其他資源，這些都使得死鎖的發(fā)生成為可能。由于資源的異構(gòu)性和失敗的不可預(yù)測性，動態(tài)的網(wǎng)格環(huán)境對協(xié)同分配施加了特別的挑戰(zhàn)。

本文根據(jù)死鎖的定義和處理死鎖的策略，提出基于Agent的網(wǎng)格資源協(xié)同分配死鎖處理算法，并對算法進(jìn)行了實驗驗證。

2 資源協(xié)同分配死鎖分析

資源協(xié)同分配問題在Globus中提出，定義為：為單個應(yīng)用所需的資源集合提供分配、配置和管理控制功能。著名的網(wǎng)格計算系統(tǒng)（如Legion和Globus）都在其資源管理中提供了協(xié)同分配機制。當(dāng)多個應(yīng)用同時進(jìn)行資源的協(xié)同分配請求時，由于資源的分配方法的不同和資源使用的競爭，可能會造成應(yīng)用之間資源分配的死鎖現(xiàn)象。

資源協(xié)同分配過程中的死鎖定義如下：若一個應(yīng)用集合中的每一個應(yīng)用都在等待只能由本集合中的另一個應(yīng)用才能引發(fā)的事件，則這種情況被視為資源分配過程中的死鎖。

如圖1所示：假設(shè)應(yīng)用a1需要網(wǎng)格節(jié)點1的3個處理器（資源類型為R1）和節(jié)點2的4個處理器（資源類型為R2）運行，表示為（3，4）；同時a2需要網(wǎng)格節(jié)點1的1個處理器（資源類型為R1）和節(jié)點2的2個處理器（資源類型為R2）運行，表示為(1，2)。而節(jié)點1共享的可分配處理器數(shù)為3個，節(jié)點2共享的可分配處理器數(shù)為4個。則當(dāng)應(yīng)用a1被分配了3個節(jié)點1的處理器，正在向節(jié)點2請求分配4個處理器，同時應(yīng)用a2被分配了2個節(jié)點2的處理器，正在向節(jié)點1請求分配1個處理器時出現(xiàn)死鎖的情況。

Globus和Legion的資源協(xié)同分配機制主要在于實現(xiàn)協(xié)同分配的過程，是一種靜態(tài)調(diào)度。而靜態(tài)方法在遇到挫折的情況下不能很好地工作。為此，本文提出一種基于Agent的網(wǎng)格資源協(xié)同分配機制。

3 基于Agent的資源協(xié)同分配

3.1 基于Agent的網(wǎng)格資源管理體系結(jié)構(gòu)

Cao J 等指出，網(wǎng)格計算系統(tǒng)面臨2個主要挑戰(zhàn)：可擴展性和適應(yīng)性。這里提出一個5層結(jié)構(gòu)處理這2個問題，包括：應(yīng)用層、用戶Agent層、資源管理核心層、資源Agent層和資源層。如圖2所示。

其中，資源層(Physical Resource Layer)是資源的提供者，網(wǎng)格給用戶提供的服務(wù)最終體現(xiàn)在這一層。資源Agent層(Resource Agent Layer)由資源Agent構(gòu)成。每個資源Agent管理一些資源，并負(fù)責(zé)調(diào)度這些資源。資源Agent應(yīng)該具有硬件性能的知識。

資源管理核心層(Resource Management Core Layer)主要提供資源注冊、資源定位、資源發(fā)現(xiàn)、數(shù)據(jù)管理、網(wǎng)格安全等功能。

核心層提供用戶Agent訪問網(wǎng)格服務(wù)及資源Agent的接口，提供查找請求的資源的功能。

用戶Agent層(User Agent Layer)由用戶Agent組成。用戶Agent層接收應(yīng)用層傳來的網(wǎng)格服務(wù)請求，分析處理各個用戶的請求。

應(yīng)用層(Application Layer)有2個功能，一是為用戶使用網(wǎng)格服務(wù)提供圖形界面和命令行方式，使得用戶使用起網(wǎng)格來就和使用Windows操作系統(tǒng)一樣方便；還有是為應(yīng)用程序提供訪問網(wǎng)格的API函數(shù)。應(yīng)用程序無需知道這些函數(shù)的實現(xiàn)方式和網(wǎng)格的處理細(xì)節(jié)，只需要調(diào)用這些函數(shù)即可，就如同使用Windows的系統(tǒng)調(diào)用一樣簡單。

3.2 基于Agent動態(tài)聯(lián)合體的協(xié)同分配

由于網(wǎng)格環(huán)境的分布性、異構(gòu)性和動態(tài)性，使得資源的協(xié)同分配變得非常困難。迄今為止，并沒有一種較好的資源協(xié)同分配方法。各種網(wǎng)格系統(tǒng)對資源的協(xié)同分配要么不支持，要么只是采用一種簡單的方式實現(xiàn)。而能較好地解決資源協(xié)同分配問題的理論模型也沒有被提出來。為此，本文提出一種基于Agent動態(tài)聯(lián)合體的網(wǎng)格資源協(xié)同分配模型。

按照前面提出的基于Agent的分層網(wǎng)格資源管理體系結(jié)構(gòu)原型，資源Agent是資源的代表，而用戶Agent是用戶的代表。資源Agent代表資源擁有者，管理對服務(wù)的訪問，確保合同的完成；用戶Agent代表服務(wù)消費者，查找到合適的資源，達(dá)成資源使用合同，接收和呈現(xiàn)結(jié)果。在資源協(xié)同分配過程中，1個用戶Agent往往需要和多個資源Agent進(jìn)行交互，以實現(xiàn)資源的配合使用和任務(wù)的正常運行。為了完成特定的任務(wù)，相互進(jìn)行通信和協(xié)同工作的1個用戶Agent和1個或多個資源Agent稱為Agent聯(lián)合體。如圖3所示。

3.3 基于Agent網(wǎng)格死鎖的基本理論

本文提出的網(wǎng)格體系結(jié)構(gòu)模型是多Agent系統(tǒng)(Multiagent System，MAS)。在多Agent系統(tǒng)中，由用戶Agent代表任務(wù)提出資源請求，這里將任務(wù)的資源需求表達(dá)為用戶Agent的資源需求。用戶Agent與資源Agent進(jìn)行協(xié)商，最終是為了使用某一種資源。

在網(wǎng)格中，產(chǎn)生死鎖的必要條件與傳統(tǒng)的系統(tǒng)相比，有了一些變化，如下所述：

(1) 互斥條件。用戶Agent對所分配到的資源進(jìn)行排它性使用，在一段時間內(nèi)某個資源只能由1個用戶Agent占有。若此時還有其他用戶Agent請求該資源，請求者必須阻塞以等待資源使用完畢。

(2) 請求和保持條件。用戶Agent已經(jīng)保持了至少1個資源，但又提出了新的一類資源請求，而該類所有的資源均已被其他用戶Agent占有，此時用戶Agent等待，但是又對其他資源保持不放。

(3) 不剝奪條件。用戶Agent已經(jīng)獲得的資源，在沒有使用完之前，不能夠被剝奪，只能在任務(wù)使用完之后自己釋放。

(4) 回路等待條件。在發(fā)生死鎖時，必然會存在一個用戶Agent資源的環(huán)形鏈。

下面的定理進(jìn)一步描述多Agent系統(tǒng)中死鎖與Agent資源回路之間的相互關(guān)系。

定理1 依賴關(guān)系圖中出現(xiàn)了用戶Agent資源回路，且處于環(huán)中的每類資源均只有1個實體，是多Agent系統(tǒng)中存在死鎖依賴的充要條件。

定理2 若依賴關(guān)系圖中出現(xiàn)用戶Agent資源回路，而處于環(huán)中的每類資源的實體不全為1，則回路的存在只是導(dǎo)致死鎖發(fā)生的必要但不充分條件。

4 網(wǎng)格的死鎖檢測算法

網(wǎng)格可以靈活的搭建，其規(guī)模大小不一?，F(xiàn)階段的網(wǎng)格試驗系統(tǒng)多是規(guī)模較小的系統(tǒng)。這種小規(guī)模網(wǎng)格可能是采用某種特殊的策略，為了某種特定的目的，特別是安全性要求非常高的系統(tǒng)。在小規(guī)模網(wǎng)格里，死鎖的處理可以借鑒分布式系統(tǒng)的解決方法。分布式系統(tǒng)的死鎖處理主要有死鎖的預(yù)防、集中式死鎖檢測和分布式死鎖檢測3類。

其中，死鎖的預(yù)防和集中式死鎖檢測都需要全局時間，且有系統(tǒng)瓶頸和較強的限制條件，不適用于網(wǎng)格系統(tǒng)。分布式死鎖檢測算法較為適用。

本算法是Chandy等提出的ChandyMisraHaas算法的擴展。

4.1 算法處理流程設(shè)計

本算法的目標(biāo)是檢測小型網(wǎng)格系統(tǒng)內(nèi)是否出現(xiàn)用戶Agent資源回路。由于回路等待條件是產(chǎn)生死鎖的必要條件，回路的存在常預(yù)示著死鎖的存在。算法采用消息傳遞的方式進(jìn)行回路的發(fā)現(xiàn)。算法處理過程如下所示：

(1) 某一用戶Agent發(fā)現(xiàn)某一種資源無法獲得，將發(fā)送一個探測消息給使用此種資源的各用戶Agent。探測消息由4部分組成：源用戶Agent、發(fā)送消息的用戶Agent、接收消息的用戶Agent和路徑記錄。路徑記錄是在探測消息中加入當(dāng)前Agent的標(biāo)識符，用于死鎖的解除。

(2) 用戶Agent通過資源Agent獲知使用該資源的所有用戶Agent。

(3) 收到探測消息的用戶Agent檢查確認(rèn)自身是否在等待其他資源。若未等待，則探測消息在此處終結(jié)。

(4) 若在等待，則更新探測消息。源用戶Agent保持不變，發(fā)送消息的Agent改為當(dāng)前Agent號，接收消息的Agent改為等待的Agent號，路徑記錄中加入當(dāng)前Agent號。

(5) 將探測消息發(fā)送到等待的Agent。等待的Agent若有多個，則多個探測消息將被發(fā)送。

(6) 若是探測消息回到了最初發(fā)送它的源Agent，網(wǎng)格上Agent資源回路的存在性即得到證實。如圖4所示。為了簡明，在圖中將資源省略。圖4中編號為1，2，4，5的4個Agent形成回路，最后在探測消息經(jīng)過1時被檢測到。

(7) 若是探測到網(wǎng)格上存在了回路，某一個Agent對應(yīng)的任務(wù)會被撤消以釋放資源，打破回路。算法中選擇Agent編號最大的任務(wù)作為撤消的對象。

(8) 源Agent發(fā)送任務(wù)撤消請求給回路中編號最大的Agent，要求其撤消任務(wù)。如圖4中Agent1會發(fā)送消息給Agent5，請求撤消相應(yīng)的任務(wù)。

4.2 算法的實驗驗證

算法運行的網(wǎng)格環(huán)境配置在4臺PC機上。其中3臺PC機性能相對較好，CPU為2 GHz，內(nèi)存為1 024 MB；1臺性能較差，CPU為266 MHz，內(nèi)存160 MB。在4臺PC機上配置Globus Toolkit 3.0軟件包，以搭建一個網(wǎng)格環(huán)境。在此網(wǎng)格環(huán)境上進(jìn)行算法的實驗驗證。

4個用戶Agent隨機發(fā)出資源請求，共進(jìn)行1 000次資源請求實驗。其中共有85次檢測出有環(huán)路。在85次環(huán)路之中，真正的死鎖共有71次，有14次是誤判斷。由此可知，在這里的網(wǎng)格環(huán)境里，在本實驗的條件下，用戶Agent資源環(huán)路出現(xiàn)的概率是8.5%，死鎖出現(xiàn)的概率為7.1%。所有的死鎖均能夠被檢測到，檢測到的環(huán)路真正是死鎖的概率是83.5%，假死鎖的概率是16.5%。

根據(jù)定理2，并非所有的環(huán)路狀態(tài)都是死鎖狀態(tài)。這正如銀行家算法一樣，并不是所有的不安全狀態(tài)都是死鎖狀態(tài)。這里稱并不真正引起死鎖的環(huán)路狀態(tài)為假死鎖狀態(tài)。假死鎖只是使可以不撤消的任務(wù)被撤消，使系統(tǒng)開銷增大，對系統(tǒng)的正確性和穩(wěn)定性，并沒有影響，故系統(tǒng)中一定比例的假死鎖是可以容忍的。

4.3 算法的適用性分析

(1) 小規(guī)模網(wǎng)格。網(wǎng)格規(guī)模的增加會使得系統(tǒng)開銷增大，探測消息沿著Agent資源回路循環(huán)一周所花費的時間增長，不利于死鎖的及時發(fā)現(xiàn)。

(2) 資源數(shù)量不太多的網(wǎng)格。資源數(shù)目越多的網(wǎng)格，假死鎖出現(xiàn)的可能性越大。當(dāng)假死鎖的比例大到一定程度后，算法的有效性必然會降低。

(3) 任務(wù)的資源請求不太多的網(wǎng)格。任務(wù)同時請求的資源越多，發(fā)出的探測報文越多，探測報文所占用的網(wǎng)絡(luò)帶寬越大，從而會降低網(wǎng)格的效率。

這里的實驗網(wǎng)格是滿足上面3個條件的，所以算法取得較好的效果。

5 結(jié) 語

從實驗結(jié)果可以看出，本算法適用于小型網(wǎng)格系統(tǒng)死鎖檢測。由于資源協(xié)同分配和網(wǎng)格死鎖處理等都是很難解決的問題，本算法也存在不足之處，如當(dāng)網(wǎng)格規(guī)模增大時的死鎖問題解決等，則是下一步研究的重點。

參 考 文 獻(xiàn)

［1］Foster I，Kesselman C，Tuecke S.The Anatomy of the Grid:Enabling Scalable Virtual Organizations ［J］.International.Supercomputer Applications，2001，15(3):200222.

［2］Czajkowski K，F(xiàn)oster I，Karoris N，et al.Resource Management Architecture for Metacomputing Systems ［A］.The 4th Workshop on Job Scheduling Strategies for Parallel Processing［C］.Springerverlag LNCS 1459，1998:6282.

［3］Czajkowski K，F(xiàn)oster I，Kesselman C.Resource Coallocation in Conputational Grids ［A］.Proceedings of the Eighth IEEE International Synposium on High Performance Distributed Computing (HPDC-8) ［C］.1999:219228.

［4］Cao J，Jarvis SA.ARMS:An Agentbased Resource Management System for Grid Computing，Scientific Programming ［J］.Special Issue on Grid Computing，2002，10(2):135148.

［5］Jonghum Park.A Deadlock and Livelock Free Protocal for Decentralized Internet Resourec Coallocation ［J］.IEEE Transactions on Systems，man and CuberneticsPart A:Systems and Humans，2004，1 123(34).

［6］Andres S Tanenbaum.分布式操作系統(tǒng)［M］.北京：電子工業(yè)出版社，1999.

［7］Globus Web page［EB/OL］.http://www.globus.org.

［8］Legion Web page［EB/OL］.http://legion.virginia.edu.

［9］王鵬，尤晉元，朱鵬.操作系統(tǒng)：設(shè)計與實現(xiàn)［M］.北京：電子工業(yè)出版社，1998.

［10］呂剛.網(wǎng)格資源協(xié)同分配系統(tǒng)的設(shè)計與分析［D］.成都：電子科技大學(xué)，2005.

［11］張紅君，李慶華，周玉龍.基于Agent聯(lián)盟機制的網(wǎng)格資源協(xié)同分配［J］.計算機應(yīng)用，2004，24(7)：46.

作者簡介 張橫云 女，1974年出生，宜賓人，碩士，講師。主要研究方向為計算機網(wǎng)絡(luò)。

段金蓉 女，1975年出生，蓬溪人，碩士，副教授。主要研究方向為軟件開發(fā)。