网格资源管理与定位

摘 要

提出了一种资源管理模型采用分布式的动态层次结构。网格中的资源之间根据通信性能进行结构组织，以树型结构组织资源。采用社区的概念来进行网格资源的逻辑划分，能够反映网络的实际拓扑，可以从资源上合理分配计算任务，有目的性的选择资源，在全局意义上进行最佳调度。在本管理模型上的请求定位策略可以快速定位目标结点，提高效率。

【关键词】网格计算 资源管理 社区 定位

1 引言

网格（Grid）在信息学中是一种用于集成或共享地理上分布的计算机系统、存储系统、通信系统、文件、数据库、程序等资源，使之成为有机的整体，共同完成各种所需任务的机制。网格计算是解决计算、数据或存储资源的短缺的问题，实现高性能计算和共享异构，提高或拓展所有计算资源的效率和利用率。但是网格计算环境较复杂，必须提供高效的资源管理机制，能够快速的定位资源，提高用户与网格计算环境的交互。

本文采用的资源管理模型是分布、动态的结构模型，在该模型下引入了分类社区的概念进行管理和高效的查询。该模型通过同传统的网资源管理模型相比，在资源管理，资源的利用率上都优于传统模型，并且该模型能够在复杂的网格环境中共享资源，提高工作效率。采用了资源目录树来组织资源，定位算法能够快速的定位，可以解决单个资源定位请求和多个资源定位请求问题。

2 资源管理模型

2.1 社区概念

本文在网格资源中引入了社区的概念，社区是网格用户和管理策略的集合，可以快速实时联系资源请求者和资源提供者。社区与社区之间联通，可以进行资源的扩展，资源管理细粒度可以通过社区对资源策略管理。社区定义表示如下：

社区={资源集合，用户集合，规则集合}

客体是资源集合中的成员，主体是用户集合成员。规则集合中是规则的描述，规则描述主体和客体间的关系。每个社区都有自己的社区管理器，不同社区的管理器之间如果遵从相同的数据交换协议是可以连通的。

2.2 资源管理模型与实现

社区的资源管理模型是分布式的动态层次结构。在网格中可以划分不同的社区，可以按类别、负载等进行划分。每个社区的管理通过局部资源管理器进行，可以进行资源的定位和调度。社区中的局部资源管理系统之间采用路由器连接构造更大的资源管理系统，这样并用户减少通讯代价，达到负载平衡，实现任务调度，提高任务的处理时间和效率。社区之间的局部资源管理器中有统一的交互协议，局部资源管理器中邻近结点的信息存储在信息表内，把整个资源连接成整体是利用信息表之间。关联资源管理的请求调度分成四层：用户层、网格安全层、资源管理层、资源层。用户层主要为用户提供接口。网格安全层主要负责用户身份认证。网格管理层负责用户和资源的交互，资源定位、资源匹配、资源调度、资源监控等操作。它的主要任务是找到作业对资源的最佳映射。资源层是资源的提供者。较高层次的组件利用较低层次组件提供的服务实现自身的功能。

网格的四层具体的资源管理的流程如下：

（1）用户在用户层的网格入口处要进行安全身份确认及权限确认。

（2）用户通过身份验证后，向系统提交作业，作业管理器接受作业。

（3）作业管理器接受的作业要进行作业的资源状态匹配，即同网格资源管理器中的网格信息表中的信息比较，成匹配成功后将搜集执行结果和资源信息返回给资源管理器。

（4）控制器接受来自网格监控器的作业执行状态汇报。

（5）最后作业执行状态由网格控制器报告给用户。

通过同其它三类模型的对比，本模型的结构合理，分工明确，能够支持网格环境下资源的定位，提高查询的效率，便于资源的描述。

3 资源定位算法

网格资源的定位是在分层动态的管理模型下进行的定位，资源定位的原则是以优先定位原则，即本社区的匹配的资源可以最先定位，未匹配的請求资源才可以在就近的社区内进行扩散，这样资源定位的时间就会缩短，效率就会提高。我们可以设定一个误差值，在该误差值内，社区内部可以把将少数较好的结果返回给用户的资源定位机制，不需要用户选择比较。

资源树是根据网格中收集的资源信息建立起来。资源树中的每一个结点不论结点本身还是子结点、父结点的相应信息都需要被存储起来；该资源树的子树的状态、历史信息、安全策略等也需要进行保存。当前的某一个结点的信息也存储在父亲结点和孩子结点中进行备份，这样可以提高了系统在受到冲击时具有尽可能强的恢复能力，在遇到非常情况时的应变能力。信息存储、向监控子系统提供系统数据并接受监控子系统发出的命令和并处理资源的动态变更。向调度子系统提供资源处理能力都是资源管理器需要处理的问题。

结点基本信息的存储是存在资源树上，我们就可以进行了资源的定位、快速的查找资源，进行分配任务。源结点是发起资源查找请求的结点，目标结点是符合条件的资源结点。从任意的资源结点出发，在资源树上定位符合条件的源结点。我们将树转换成有序树，给定目标资源参数与参考值的大小关系，社区要把相应资源按结构或操作系统分类，为了更好的匹配资源，提高效率，每个社区建立一棵子树，各个社区的实体之间是一个对等的。例如将网格上树是以linux操作系统为主机建立的，在该树下根据每一棵子树中的结点的CPU使用率、作业个数、计算能力划分多棵子树，为了提高查找效率，子树根据CPU使用率、作业个数、计算能力等进行排序。可以定位三种不同的如下解：满意解、局部最优解和全局最优解。

下面以计算机能力建立子树，并排好序来说明如何进行查找的。资源树形态如图1所示，树中的结点数字来表示资源的计算能力。查找条件是“计算能力不小于30的参考值”。任意选定源结点，假设P为源节点，从P出发寻找目标结点，其K=40满意解，R=31为局部最优解，Q=30为全局最优解。endprint

下面我们根据目标结点的查找过程来分析其查找过程时间复杂度。

（1）满意解的求解过程为：满意解只需定位到满足资源条件的第1个资源即可。因资源树按计算机能力排序，根据计算能力向上聚集的原则，如果当前结点的计算能力不满足要求，根据向上汇聚原则，把查找请求上发给父亲结点。设定1个查找步为查找请求被从一个结点发送到其父结点，若存在解，则一定在从源结点到根结点的路径上。图1中求解满意解时，先在资源树上选择任意结点P，先判断P（计算机能力为29）结点的参数不满足条件，立即将查找请求发给父亲结点K，父亲结点K（40）的参数40满足条件，返回满意解K，满意解的查找过程结束。这种方法的优点是简单，可以快速找到匹配结果，缺点是有可能不是最佳的结果

最好的情况：查找步数目为0，是源结点本身的参数就满足条件。

最坏的情况：查找过程要从资源树最底层结点进行到根结点，查找步数为资源树的深度log（N），因此其时间复杂度为O（log（N）），平均情况下的时间复杂度也为O（log（N））。

（2）局部最优解的求解过程为：先找到满意解，在满意解所在结点上的资源子树中的最优解。任何一个结点的计算能力参数不小于其所有子结点的计算能力，因为资源树的计算能力有向上聚集原则。孩子结点的信息都记录在子树的根结点上，可以通过查找根结点查找它另一个孩子，看是否满足匹配条件。不满足匹配条件，则子树的根就是局部最优解。满足匹配条件，把该孩子结点当作下一层子树的根。在依次执行过程（1），用（2）来判断。图1中求解时，在找到满意解S后，在K上维护的资源子树中查找与30最近的且不小于30的结点，在（29，31，25，26）中查找到31，返回结点R，查找过程结束。

最坏的情况：时间复杂度为2×O（Log（N））。

（3）局最优解的求解过程：先查找需求沿资源树向上发送到根结点，再在根结点上的资源树中寻找最优解。图1中，从p结点开始查找需求，没有满足条件的向上发送直到根结点，再在资源树的根结点中查找与30最近而且不小于30的结点，在（70，40，50，29，31，30，40，25，26，15，15）中查找到30，返回结点Q，查找过程结束。

平均时间复杂度：2×O（Log（N））。

参考文献

[1]王良，刘潇，贾宇洁.基于收益率门槛限制考虑的网格资源拍卖问题[J].计算机系统应用，2017（07）.

[2]张相斌，李砚砚.基于无标度网络的制造网格资源配置仿真研究[J].系统仿真学报，2015（02）.

[3]肖迎春，王汉武，李梦雄.基于混合组合双向拍卖的网格资源分配方案[J].計算机科学，2014（05）.

[4]于帆，秦龙.多Agent在政府采购系统中的应用研究[J].计算机与数字工程，2011（04）.

作者简介

刘磊（1975-），女，硕士学位。副教授。主要研究领域为网格计算。

作者单位

吉林建筑大学城建学院 吉林省长春市 130111endprint