網格資源協同分配死鎖處理問題研究

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

關鍵詞：網格技術；資源協同分配；死鎖；分配性能

中圖分類號：TP393.7 文獻標識碼：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 引 言

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

本文根據死鎖的定義和處理死鎖的策略，提出基于Agent的網格資源協同分配死鎖處理算法，并對算法進行了實驗驗證。

2 資源協同分配死鎖分析

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

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

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

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

3 基于Agent的資源協同分配

3.1 基于Agent的網格資源管理體系結構

Cao J 等指出，網格計算系統面臨2個主要挑戰：可擴展性和適應性。這里提出一個5層結構處理這2個問題，包括：應用層、用戶Agent層、資源管理核心層、資源Agent層和資源層。如圖2所示。

其中，資源層(Physical Resource Layer)是資源的提供者，網格給用戶提供的服務最終體現在這一層。資源Agent層(Resource Agent Layer)由資源Agent構成。每個資源Agent管理一些資源，并負責調度這些資源。資源Agent應該具有硬件性能的知識。

資源管理核心層(Resource Management Core Layer)主要提供資源注冊、資源定位、資源發現、數據管理、網格安全等功能。

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

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

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

3.2 基于Agent動態聯合體的協同分配

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

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

3.3 基于Agent網格死鎖的基本理論

本文提出的網格體系結構模型是多Agent系統(Multiagent System，MAS)。在多Agent系統中，由用戶Agent代表任務提出資源請求，這里將任務的資源需求表達為用戶Agent的資源需求。用戶Agent與資源Agent進行協商，最終是為了使用某一種資源。

在網格中，產生死鎖的必要條件與傳統的系統相比，有了一些變化，如下所述：

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

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

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

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

下面的定理進一步描述多Agent系統中死鎖與Agent資源回路之間的相互關系。

定理1 依賴關系圖中出現了用戶Agent資源回路，且處于環中的每類資源均只有1個實體，是多Agent系統中存在死鎖依賴的充要條件。

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

4 網格的死鎖檢測算法

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

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

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

4.1 算法處理流程設計

本算法的目標是檢測小型網格系統內是否出現用戶Agent資源回路。由于回路等待條件是產生死鎖的必要條件，回路的存在常預示著死鎖的存在。算法采用消息傳遞的方式進行回路的發現。算法處理過程如下所示：

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

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

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

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

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

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

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

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

4.2 算法的實驗驗證

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

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

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

4.3 算法的適用性分析

(1) 小規模網格。網格規模的增加會使得系統開銷增大，探測消息沿著Agent資源回路循環一周所花費的時間增長，不利于死鎖的及時發現。

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

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

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

5 結 語

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

參 考 文 獻

［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，Foster 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，Foster 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.分布式操作系統［M］.北京：電子工業出版社，1999.

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

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

［9］王鵬，尤晉元，朱鵬.操作系統：設計與實現［M］.北京：電子工業出版社，1998.

［10］呂剛.網格資源協同分配系統的設計與分析［D］.成都：電子科技大學，2005.

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

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

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