一种基于计算期望的网格资源管理模型

　　随着技术的进步和人类需求的发展，越来越多的应用领域离不开高性能计算。网格正在逐渐成为下一代高性能计算的基础架构。在分布式环境中，资源在对不同的用户在不同的时间有着不同的可用性和代价，优先权和目标也随时间变化。在这样一个分布的环境里，资源管理和应用程序调度必须具有较强的自适应性，才可以满足资源的可用性和用户要求的动态变化。同时它们还必须提供可扩展的、可控的、可量测的以及容易实施的管理调度策略。

　　网格资源管理模型根据用户对计算资源的要求来进行资源调度，可以更好地利用资源。但是在一个庞大的计算环境中，所有的用户都更倾向于更强的运算能力和更丰富的资源，而这将导致资源的不合理分配。基于市场经济的网格资源管理模型通过经济学原理，设定适合的市场规则和价格策略能较好地解决这个问题。

　　本文在在市场经济模型的基础上，设计了一种基于计算期望的网格资源管理模型。该模型通过计算期望来描述用户的计算任务，并对其进行抽象和量化，为实现灵活高效的资源管理和调度提供了基础；在网格市场的资源交易中采用可变价格策略，使网格资源价格根据网格内资源的交易情况上下浮动，反映了网格内的资源供求关系，并实现自适应的负载均衡。

1 模型的结构

　　基于计算期望的网格资源管理模型(简称计算期望模型)，主要由计算期望分析器、资源管理交易器、本地市场信息服务模块、安全认证模块、作业管理器、网格信息转发器等部分组成。模型基本框架如图1所示。

　　在本模型中，将网格计算资源描述为4种属性的集合，记为：R=(RCPU，Rmem，Rstor，RBwidth)。4种属性依次为：处理器计算能力、内存的大小、存储设备容量和网络带宽。计算期望分析器负责将用户提出的“计算期望”转换成对计算资源属性相应的描述。用户在提交作业时，只需要对其作业运行的计算期望，以及保证作业正常运行所需要的最小资源需求进行描述。例如指定“最小作业计算费用”，“最短作业计算时间”等。记网格中资源的价格为P，计算期望分析器将用户计算任务的计算期望转换为对资源R和价格P的描述，并把任务对资源的需求描述提交到资源管理交易器。在保证作业运行所需最小资源的基础上，尽量满足用户的计算期望。

　　资源管理交易器负责本地计算资源的管理与调度，处理本地资源在网格市场中相关的交易事宜，并周期性地更新本地市场信息服务模块中关于本地计算资源与价格的信息，是本模型中的核心组件。

2 网格资源价格策略

　　根据市场经济原则，各自治域内的资源管理交易器应当能够独立地调整本自治域内计算资源的价格。通过价格反映市场的供求关系，实现负载均衡。在本模型中，各计算资源根据自身被使用的状况实现其价格的自主决策。

　　对于自治域内每个独立的计算资源Ri，由其资源提供者设定各自的涨价影响因子ai与降价影响因子bi。资源评估参数的定义如式(1)所示：

　　资源根据其等待作业长度和资源空闲时间决定其价格上涨或下降的幅度。当资源由空闲状态变为执行状态后，提交给该资源的作业进入等待队列。每当新作业jim进入等待队列，资源价格上涨，资源价格上涨幅度如式(2)所示。

　　其中作业的预测执行时间tim越长，说明其占用资源的时间越长，资源供不应求的状态就越严重，因此涨价幅度就越大。涨价影响引子ai决定了价格上涨速度的快慢。资源评估参数Ei用于对资源能力进行评价。资源能力越强，则相应的价格就越高。当资源恢复空闲状态后，若长时间闲置，得不到作业请求，说明资源供大于求。此时，根据市场经济原则，资源价格下跌。从资源变为空闲状态开始，每隔一个固定时间段tint发布一次资源的最新价格。经过第n个时间段发布的资源价格如式(3)所示：

　　其中Pi为资源Ri空闲时的价格。根据市场经济机制，作业总是被调度到价格较低的资源上。通过各个资源对其价格的自主调节，以价格为杠杆，使网格内资源负载达到平衡。

3 网格资源调度算法

　　在本模型中，通过不同的计算期望来描述用户不同类型的计算要求，不同的计算期望对应着不同的资源调度算法。下面介绍本模型中的几种资源调度策略。

3.1 期望为“最小作业计算费用”的资源调度算法

　　设执行用户计算任务所需要最低资源要求为：

　　计算期望分析器从本地市场信息服务模块中查询到的当前本地可用资源为：

　　n为本地市场信息服务模块中记录的可用资源数。

　　最小作业计算费用算法概述如下：

　　步骤1 根据计算期望描述，资源管理交易器查询本地市场信息服务模块，选择满足条件的价格P最低的计算资源。

　　步骤2 资源管理交易器将选择出的计算资源分配给用户作业。

　　步骤3 若本自治域内的资源无法满足用户计算任务的最低资源要求，则资源管理交易器将资源请求发送至本区域的信息转发器。信息转发器查询其数据库中保存的本区域内各自治域计算资源属性的最大值。并选择所有满足式(4)的自治域j，将资源请求发送至这些自治域。

　　步骤4 收到资源请求的自治域执行步骤1，并将满足条件的计算资源信息发送至作业提交者的资源交易管理器。

　　步骤5 若作业提交者所在区域内所有自治域的资源都无法满足用户计算任务的最低资源要求，则由本区域的信息转发器将资源请求发送至相邻的信息转发器。收到资源请求的信息转发器选择满足式(4)的自治域，将请求转发至这些自治域，并执行步骤4。同时，将请求发送到与其相邻的信息转发器(不包括将资源请求转发至该转发器的资源转发器)。重复这一过程，使资源请求在网格全局内转发。

　　步骤6 作业提交者所在的资源管理交易器在收到满足作业最小要求的资源返回的资源信息后，对其按照价格进行排序，并按照作业的要求，选择价格最小的一个或多个资源分配给用户作业。并将交易契约发送至被选择的资源。资源得知自己被选择后，根据价格策略提升其资源价格。为了防止等待时间过长，用户的本地资源管理交易器从将资源请求发送至本区域信息转发器时开始计时，经过一段规定的时间，停止查询，若此时无满足条件的资源信息返回，则本次查询失败。

3.2 期望为“最小作业计算时间”的资源调度算法

　　期望为“最小作业计算时间”的资源调度算法只需将“最小作业计算费用”资源调度算法步骤6中按照价格进行排序改为按照作业等待队列时间丁Twait进行排序，并按照作业的要求，选择价格最小的一个或多个资源分配给用户作业。

3.3 期望为“自定义价格／执行时间”的资源调度算法

　　用户指定的完成时间为Tuser，用户作业在资源i上的预测执行时间为TiPRDCT，资源i上作业等待队列时间为Tiwait，用户指定的作业计算费用为Puser，资源i的价格为Pi。

　　当计算期望为“自定义价格／执行时间”时，用户作业除了要满足作业执行的最小资源要求以外，还需要花费小于指定金额的计算费用，或作业在规定时间内完成。这2种算法的前5步与“最小作业计算费用”资源调度算法相同，它们的第6步简述如下：

　　“自定义执行时间”调度算法步骤6：作业提交者所在的资源管理交易器在收到满足作业最小要求的资源返回的资源信息后，对其按照作业等待队列时间Twait进行排序，选择所有满足式(5)的资源i，并将其结果返回给用户，由用户从1个或多个满足时间约束的资源中选择合适自己作业的资源。

　　“自定义价格”调度算法步骤6：作业提交者所在的资源管理交易器在收到满足作业最小要求的资源返回的资源信息后，对其按照预测执行时间为TPRDCT排序，选择所有满足式(6)的资源i，并将其结果返回给用户，由用户从1个或多个满足时间约束的资源中选择合适自己作业的资源。

4 实验数据及分析

　　实验的仿真环境为：Intel(R)Pentium(R)4 CPU2.66 GHz，512 MB DDR 400 SDRAM，Windows XP professional SP2，Java 2 SDK 1.4.2。所用的仿真软件为Gridsim。

　　图1给出了本文设计的基于计算期望的网格资源管理模型的仿真数据。固定时间为30 000个时问单位，从domain01～domain08每个自治域中各随机抽取1个计算资源，记录其在网格内不同作业数的情况下资源的利用率。其中资源利用率为该资源在某一时间段内处于被占用状态的时间与总时间的比值。

　　图2为传统基于固定价格的网格市场经济模型的仿真数据。固定时间也为30 000个时间单位。从domain01～domain08每个自治域中各随机抽取1个计算资源，对其按照价格从低到高编号。资源1价格最低，资源8价格最高。记录其在网格内不同作业数的情况下资源的利用率。其中资源利用率为该资源在某一时间段内处于被占用状态的时间与总时间的比值。

　　由图2可看出在计算期望模型中，相同作业数的情况下，资源基本处于负载均衡状态，没有出现忙闲不均的情况。随着作业数的增加，资源利用率迅速上升，在作业数为200时，各资源已处于饱和状态。此外，资源1，2，3的利用率比较接近，资源4，5，以及资源6，7，8也有相同的情况。这是由于资源调度算法优先选择位于作业提交者所在网格区域内资源造成的。相比之下，图3显示系统处于负载不均的状态。这是由于模型基于固定价格策略，调度器总是将作业调度到价格低的资源上，直至该资源饱和。

　　图4为基于固定价格的市场经济模型中作业执行时间与计算期望模型中作业执行时间的比较。设定10个作业，作业长度从10 000到50 000，调度策略为最小资源价格策略。将这10个作业分别运行于上述2种模型的模拟程序中，统计在系统内总共运行着50，100，150，200个作业的状态下这10个作业各自的运行时间，并去掉1个最大值和1个最小值后对剩余运行结果求平均值，得到图中数据。

　　由图4可知，在系统内作业总数为50个的情况下，系统负载较轻，几乎每个作业不用经过长时间等待就可被执行，因此二者的执行时间比较接近。当系统内作业总数为100个和150个时，系统内负载开始加重，资源等待队列中处于等待状态的资源开始增多。由于固定价格的市场经济模型将作业优先调度到价格低的资源上，导致大量作业在低价资源的作业等待队列中堆积，增加了作业执行前的等待时间。而计算期望模型中通过价格浮动，确保作业被相对均衡地分配到资源上，减少了资源等待队列的长度，因此计算期望模型下作业执行时间较短。当系统内总作业数为200个时，系统处于饱和状态，各资源的等待队列都被作业占满，因此两个模型中作业执行时间相差不多。

　　图5，反映了相同的作业在网格内作业数不同的情况下运行时间的差异。用来测试的作业分别为：作业1，长度为10 000；作业2，长度为25 000；作业3，长度为50 000。3个作业的调度策略都为“最小作业执行时间”。为了不受偶然情况的影响，对每个作业运行10次，去掉其中1个最大的执行时间和1个最小的执行时间，对剩余的时间求平均值。

　　图5显示随着作业数量的增加，相同的作业其执行时间也随之增加。特别是当系统内的作业数在100个以上时，系统性能下降加快。表明此时系统内处于等待队列的作业开始增多。

　　图6显示在“自定义价格／执行时间”策略下系统内的作业总数和成功配到资源的作业数之间的关系。分别在系统内总共有50，100，150，200个作业的情况下，随机生成50个作业，统计其成功分配到资源数与总作业数的百分比。

　　从图6可见，当系统内作业数大于100时，自定义价格策略和自定义执行时间策略的作业成功分配比率都下降的很快。这说明当系统内作业数大于100时，各资源的等待作业队列长度开始快速增加，导致系统内资源价格上涨，作业等待时间增加，所以满足一定的价格／最大执行时间约束的资源数减少，导致资源成功分配数减少。

　　以上实验数据说明本模型所设计的价格浮动机制，相比传统基于固定价格的网格市场经济模型，能够更加准确的反映网格市场内的供求关系，实现网格内的资源负载均衡，有着更高的调度效率。模型设计的不同的资源调度算法的调度结果，与其“计算期望”所要求的结果相吻合。“计算期望”结合相应的调度算法，实现了灵活、准确的资源描述与分配，满足了用户个性化的计算需求，简化了用户的工作量，在系统负载不饱和的情况下，有着较高的调度效率。但是不足之处在于随着系统内作业数趋向饱和，调度效率下降较快。在系统饱和状态下的调度效率还有待加强。

5 结 语

　　本文设计的一种基于计算期望的网格资源管理模型，通过计算期望来描述用户作业的执行要求，由系统自动将计算期望映射成对网格计算资源属性的描述，简化了用户在提交作业时的工作量；根据不同的计算期望，设计了不同的资源调度算法，以实现灵活的资源调度。

　　在本模型中，通过资源价格在市场内根据其供需情况的变化自主浮动，实现网格资源的负载均衡。模型的资源发现策略采用基于数据库查询的层次式结构，以实现查询效率与系统开销的折衷。采用网格模拟器Gridsim对本文所设计的模型进行仿真。实验结果表明本模型能够有效实现资源的负载均衡，在常规条件下的资源调度具有较高的效率。

　　虽然本模型实现了资源的负载均衡，且在负载不重的情况下有较高的调度效率，但是在网格内作业处于饱和状况下资源调度性能下降较快。应当在资源发现策略与资源调度策略方面做进一步的研究。