网格资源协同分配死锁处理问题研究

摘 要：网格中资源协同分配是资源组织和调度的一个重要组成部分，如何检测应用之间的死锁是资源协同分配过程中需要解决的重要问题。通过对网格中死锁原因的分析，对死锁的特点进行描述。提出基于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］..

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

［9］王鹏，尤晋元，朱鹏.操作系统：设计与实现［M］.北京：电子工业出版社，1998.

［10］吕刚.网格资源协同分配系统的设计与分析［D］.成都：电子科技大学，2005.

［11］张红君，李庆华，周玉龙.基于Agent联盟机制的网格资源协同分配［J］.计算机应用,2004,24(7)：46.

作者简介 张横云 女，1974年出生，宜宾人，硕士，讲师。主要研究方向为计算机网络。

段金蓉 女，1975年出生，蓬溪人，硕士，副教授。主要研究方向为软件开发。