一种基于统计信息的网格资源组织及任务调度

　　摘 要：对分布的网格资源进行有效地组织与调度是实现网格计算的关键。基于分层的思想，提出了一种改进的网格资源组织方式，引入了资源统计信息表及负载信息表。在资源调度的过程中，通过维护并匹配相关的统计信息，能够快速地查找资源，避免了资源发现的盲目性，缩短了资源的查找时间，同时兼顾了网格系统内部的负载平衡，有效地提高了网格系统的性能。
　　关键词：统计信息; 网格; 资源管理; 调度
　　中图分类号：TN915-34文献标识码：A
　　文章编号：1004-373X(2011)01-0138-03
　　
　　Grid Resource Organization and Task Scheduling Based on Statistical Information
　　QIAO Ping-an, ZHU Guang-hua, YANG Li-fa
　　(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)
　　Abstract： The resource scheduling and effective organization for the distributed grid is the key to realize the grid computation. Based on hierarchy theory, an improved grid resource organization mode is proposed, and the resource statistical information table and load information table are introduced. Through maintaining and matching related statistical information in resource scheduling process, it can not only avoid the blindness of resource discovery and quickly find resources, but also realize the load balancing within grid systems, and effectively improve the performance of grid system.
　　Keywords： statistical information; grid; resource organization; scheduling
　　
　　0 引 言
　　所谓网格，就是把整个因特网整合成一台巨大的超级计算机，实现计算资源、存储资源、数据资源、信息资源、知识资源和专家资源的全面共享。这种计算模式是利用互联网将分散在不同地理位置的计算机组织成一个“虚拟的超级计算机”，其中每一台参与计算的计算机就是一个“节点”，而整个计算机系统由成千上万个“节点”组成“一张网格”［1］。在网格计算环境下，由于资源的异构性、动态性、自治性以及网格任务的多样性，使得资源的组织与调度成为网格计算效率的关键问题。如何有效地对网格资源进行组织与调度，本文结合网格资源调度过程中的相关统计信息，提出了一种分层资源组织方式及调度方法，有效地缩短了资源的查找时间，提高了资源的利用率，同时兼顾了网格系统的负载平衡。
　　1 网格资源管理及调度
　　网格中的资源具有广域分布、异构和动态的特性。当前还没有一种模型能够处理所有的网格应用需求。目前，网格资源管理模型主要分为分层模型、抽象所有者模型和经济/市场模型三类［2］。其中，分层模型已被大部分的网格计算系统所采用(如 Globus，Legion,CCS等)，是目前主流的资源管理模型，它的基本思想是将整个资源管理系统分成若干功能层，较高层次的组件可以利用较低层次组件提供的服务实现自身的功能，有利于对具有站点自治性和底层异构性资源进行管理，并具有较强的适用性［3］。
　　资源发现是网格资源调度的核心内容，它根据一个任务对资源需求的描述，通过发现机制返回一个或多个与描述相匹配的资源位置。在该过程中，资源发现机制从网格资源信息服务(Grid Resource Information Services,GRIS)机构获得资源信息，逐次查询，找到满足任务需求的资源［4］。网格资源信息服务可分为集中式和分布式两种机制。集中式机制查询效率高，但扩展性不足，并存在单点失效和访问瓶颈问题；分布式机制具有较高的自治性和可扩展性，节点可以随时加入网络或离开，但在资源发现时具有一定的盲目性，基于泛洪或广播的资源发现效率较低，缺乏全局性的控制协调能力［5］。总之，从资源发现过程来看，无论是采用集中式还是分布式，在资源调度中均占有很大的开销，是影响资源调度的关键所在。
　　2 一种网格资源分层组织结构
　　基于网格环境的异构性、动态性和自治性特点，提出一种分层的资源组织方式，其结构如图1所示。
　　图1 网格分层组织结构
　　该结构主要由根服务器、域代理服务器和资源节点层三个层次组成。其中每一层可以由若干个组件来实现其功能，每个域代理服务器与其下面的节点构成一个独立的资源自治域。
　　根服务器主要用于管理域的划分,管理分布在网格内的各个资源自治域，负责收集各个域的资源情况以及把用户作业分配给各个自治域执行。域的划分遵循同构的原则，即把具有相同或相似属性和功能的资源划分到同一个域。其主要功能如下：集中接收用户的应用请求；监控各个自治域的当前状况；将用户作业分发给各域代理服务器；监控用户作业执行情况，接收执行结果，对于由于某种原因导致作业无法正常执行而中断的作业进行重新调度；向用户提交执行结果。
　　域代理服务器主要用于向根服务器报告域内资源情况和作业执行情况以及管理该资源自治域内的网格资源。其主要功能如下：接收根服务器(或上级域代理服务器)分发的用户作业，若作业不符合要求，则将作业退回给根服务器(或上级域代理服务器)；进行资源匹配、定位资源并进行调度，若有下级域代理服务器，则向下级域代理服务器分发用户作业；监控用户作业执行情况，接收执行结果，并向根服务器或上级域代理服务器提交执行结果。
　　网格资源层是将地理上分布的、功能相对集中的、在异构平台上协同工作的资源(包含各种类型的网格资源和服务资源)，根据其功能和类型，组建成不同的虚拟组织［6］(Virtual Organization,VO )，VO的建立基于资源属性分类并结合地理位置，由域代理服务器管理。每个资源节点都只受它所对应的代理服务器的管理。
　　3 资源组织方式
　　为了提高资源调度的成功率，缩短资源查找的时间，保证网格内的负载平衡，在根服务器和域代理服务器各增加两个表：负载信息表和资源统计信息表。负载信息表用于统计下级域代理服务器的负载信息，若没有下级域代理服务器，则该表直接统计每个资源节点的负载信息，主要包括资源节点当前各项资源的使用情况，如CPU利用率、内存使用情况等；资源统计信息表用于记录最近调度成功的相关信息。对于根服务器，主要记录一段时间内通过各代理服务器调度成功过且访问频率高的代理服务器信息；对于域代理服务器，记录该自治域内近期成功调度的资源信息，如资源ID、资源类型、访问时间、访问频率等。对于两个表中的所有记录信息按访问时间和访问频率进行排序。当表中记录满时，使用近期最少使用算法(Least Resently Used,LRU)将一段时间内使用最少的记录信息项替换出去。
　　
　　4 调度机制
　　对于分层结构进行资源分配任务调度时采用的是多层次的资源协作的策略。首先，根服务器集中接收所有用户提交的作业请求，依据Min-min算法确定作业的优先级，然后根据任务性质、通信状况、各个域代理服务器提供的自治域内的资源情况和各域代理服务器的资源负载情况进行粗粒度调度，最后再由域代理服务器根据自治域内的资源情况以及各个资源的负载信息进行作业调度。具体算法如下：
　　(1) 根服务器接收用户提交的作业请求，通过资源统计信息表查找调度成功率高的域代理器，同时兼顾代理服务器的负载信息，若域代理服务器负载较轻，则将用户作业分发给该域代理服务器；若域代理服务器负载较重，则重新在资源统计信息表中查找下一个域代理服务器，直到找到一个负载较轻的域代理服务器。主要算法思想描述如下：
　　初始化；
　　依据Min-min算法确定作业的优先级，选定作业；
　　do(资源统计信息表未空)
　　在资源统计信息表中查找最近使用且调度成功率高的域代理服务器；
　　if (该域代理服务器的负载较轻) then
　　将用户作业分配给该域代理服务器；
　　修改资源统计信息表；
　　修改负载信息表；
　　exit do
　　 else
　　重新在资源统计信息表中查找下一个域代理服务器；
　　 endif
　　enddo
　　(2) 域代理服务器接收到根服务器分发的作业，若有下级域代理服务器，则对作业进行下一级的分发，方法同根服务器；否则，根据作业的特性，如CPU要求、内存使用量、操作系统版本、磁盘空间等信息在资源统计信息表中查找相关资源节点信息并进行资源匹配，同时兼顾资源节点的负载情况。若满足，则执行作业，并将作业执行情况及结果报告给根服务器或上级域代理服务器；若匹配不到合适的资源节点，则到GRIS进行查找获取资源。当二者中均找不到合适资源时，则告知根服务器进行重新调度。主要算法思想描述如下：
　　初始化；
　　do while .t.
　　if (有来自上一级的作业) then
　　 if (有下级域代理服务器) then
　　 继续向下分发作业；
　　else
　　 do while (资源统计信息表未空)
　　根据作业的特性在资源统计信息表中查找资源节点信息并进行资源匹配；
　　if (资源节点负载较轻)then
　　修改节点负载表；
　　将作业调度给该资源节点执行；
　　if (执行成功) then
　　 修改资源统计信息表；
　　 向根服务器或上级域代理服务器报告结果；
　　else
　　 域代理服务器重新调度；
　　endif
　　endif
　　 enddo
　　endif
　　 enddo
　　5 结 语
　　针对网格环境下的资源特点，提出了一种分层的网格资源组织与任务调度方式，并在此基础上引入了负载信息表和资源统计信息表。在资源查找方式上，改变了传统资源查找的盲目性，提高了资源查找效率，同时兼顾了网格系统内部的负载平衡，使网格环境的性能得以提高。以后将进一步研究如何在网格系统结构上更好地实现相应的QoS保证。
　　参 考 文 献
　　［1］许光男.网格计算中任务调度策略研究［J］.软件导刊,2008,7(12):137-139.
　　［2］尚明生.网格计算中的任务调度算法研究［D］.成都:电子科技大学,2007.
　　［3］宋之迎,刘厚泉.基于树形的网格资源管理研究［J］.微计算机信息,2009,25(15):82-83,59.
　　［4］LI Mao-zhen,BAKER Mark.网格计算核心技术［M ］.王相林，张善卿，王景丽,译.北京:清华大学出版社,2006.
　　［5］王静.一种快速的网格资源发现机制［J］.广西轻工业,2008(12):95-96.
　　［6］FOSTER I, KESSELMAN C. The grid 2: blueprint for a new computing infrastructure ［M］ . San Francisco: Morgan Kaufmain Publishers Inc., 2004.
　　［7］徐武,吴克捷,周卫东,等.一种基于策略的可扩展网格资源管理机制［J］.计算机应用研究,2007,24(7):211-213.
　　［8］段丽艳,刘波,罗兰花.网格资源发现机制研究与设计［J］.海南大学学报:自然科学版,2009,27(2):169-172.
　　［9］何琨,赵勇.网格资源管理与调度研究综述［J］.武汉理工大学学报,2005,27(4):179-183.
　　［10］杨长兴,吕祯恒.一种统一的资源预留策略［J］.计算机工程与应用,2005,41(24):144-146.
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文