基于价格反馈机制的网格任务管理研究

 1 引言
    网格是继万维网之后出现的一种新型网络计算平台，它已成为信息技术领域的热点研究课题。开发网格中，任务管理是网格计算系统与应用主体交互的关键纽带，是网格研究基础且核心的环节。但是现有的网格任务管理方法在充分、合理利用资源，较好地满足网格用户的任务要求，确保任务的服务质量上仍存在诸多问题，无法很好解决网格环境中资源的异构性、动态性和自治性，以及任务的多样性和动态性所带来的困难。本文依据网格任务管理的这些特点与问题。提出三组件三队列式的分布式任务调度模型，T2DSM(Triple-component and Triple-queue Distributed Schedule Model)，并将经济学中的价格调控机制应用于网格任务的调度策略之中，实现任务的合理调度与资源的科学分配。

2 网格任务调度难点分析
    目前，网格任务调度主要存在以下问题与难点：
    (1)任何一个网格调度器只针对一定范围内的网格资源进行管理，无法面向所有网格资源；
    (2)网格资源动态变化，资源信息的采集和组织对调度影响很大。
    (3)网格中对各种资源的约束很多，有些是非线性的，要达到调度目标也很多，比如要求时间最少、代价最小、资源利用率最高等，有些目标会存在相互矛盾之处，对于这种多目标多约束的问题找到满足所有约束和目标的全局最优解是很困难的。
    (4)由于其他应用引起的资源竞争对性能影响很大，而且出现频率较高。网格资源的复杂多样。不同类型的资源展示不同性能特性，而且相同类型的资源由于共享等原因所展示的性能也随时间变化。网格的调度需要建立随时间变化的性能预测模型，充分利用网格的动态信息，表示网格性能的波动。
    (5)网格的调度必须考虑到资源的多种管理属性以及调用资源所设计的商业交易等因素。后者是指网格的调度还必须考虑到如何协调网格用户和具体资源提供者之间的利益，即如何使用户所需要支付的开销最小且使资源提供者获得效益更大。

3 网格任务调度模型设计
    T2DSM应用场景描述如下：每个站点包括许多节点，且每个节点都有一定量的存储器。有些应用程序需要访问许多数据(数据密集型)，且可能是可并行的。一定量的数据首先被输入到计算网格中的节点，用户任务也提交到该节点。计算网格是由各种不同类型的被连接到局域网和／或广域网的节点组成。应用程序在本地拥有必要的数据后才能开始被执行。当用户请求执行程序时，调度器被启用。图1为T2DSM模型结构图，描述整个T2DSM以及调度器内主要组件和调度器间的互相作用。

    这里调度器分为两级，顶级是全局调度器GS(Clobal Scheduler)，下级是局域调度器Ls(Local Scheduler)。与广域网某段相对应的GS负责被提交的任务应被送到具体的局域调度器。相反LS负责本地局域网的任务调度。整个调度模型采用一种基于非直接全互连通信方式的非集中式结构一分布式结构。每个LS仅在其所在局域网中搜索资源信息，类似地。每个GS仅在其所负责的社区中处理资源信息。在相邻GS节点间直接交换信息，非邻居GS依靠邻居GS间接通信。如果任务没有被调度，调度器将会检索资源、程序和用户信息，然后激活其相应组件协同做出任务执行调度和数据复制的决定。每个调度器都有三个组件和三个队列，其功能和关系描述如下：
    (1)任务调度组件TSC利用特定算法，任务调度组件TSC(Task Scheduling Component)在有关资源和任务信息的基础上做出调度决策，若有必要，将一些有关数据传输的指令消息传送给数据传输组件DTC(Data Fransferring Compo-nent)。TSC保持活动状态且会对提交任务队列ATQ(Arrived Task Queue)中的所有人物制定调度策略，然后将已被调度的任务放进已调度任务队列STQ(Scheduled Task Queue)和指示其任务在被选择的资源上执行。假如局域调度器的。TSC不能给出“最好的”调度，它就会把该任务交付给相关全局调度器的ATO并采用类似方法调度此任务，只是不能完成其调度，它就会把该任务请求传送给相邻全局调度器的TSC，并且这些TSC会采用类似的方法继续下去直到完成任务调度。
    (2)数据传输组件DTC能够追踪每一个数据集的本地有效分布情况，如果条件满足，它就会为任务复制或者移动相应的数据集。
    (3)价格反馈组件PFC根据完成任务的执行信息调整完成该任务所对应的各个资源节点价格参数信息。同时，对于在任务过程中没能履行职责的资源节点进行相应惩罚，令其补偿完成该任务的价格亏损。
    (4)提交任务队列 ATQ和已调度任务队列STQ及其任务反馈队列TFQ(Task Feedback Queue)。ATQ存储被传送到本地调度器的所有未调度任务。当一个任务请求到达时，该任务就会存入ATQ，而当一个任务被调度时它就会从ATQ取出，一旦调度成功将从此队列中移走。STQ存储那些被本调度器所成功调度的任务，而当这些任务执行完成时，将任务转交到TFQ，对任务完成质量进行评价反馈，然后移出队列。

4 基于价格反馈机制的调度策略
    在提交任务队列ATQ中，改变传统的先来先服务(FCFS)和短作业优先(SJFS)的调度思想，在任务进入提交队列时，对任务的执行时间进行估算，具体实现为：

  
式中，k为任务需求资源的数量；mi为该资源的任务需求量；fi为需求资源量级权重，是由资源的需求量的范围等级决定；vi为该资源的平均执行速率。
    在得到任务的预算时间后，根据任务描述的时间要求，进行差值运算，所得到的剩余时间作为调度任务的依据。每次选取提交队列中剩余时间最少的任务进行调度。
    在TSC的调度策略中引入经济学的价格凋控机制，在任务调度时，选择可满足任务的价格最低资源进行调度。在任务的调度过程中，主要有两个关键因素：一个是有效资源，其定义为：对于各个资源节点，根据任务描述，过滤该节点的所有空闲资源，凡是符合任务需求的资源称为有效资源；二是价格制定。价格的形成取决于诸多因素，对于一个任务来说，其定价公式：

  
式中，A是资源的价格因子；M是资源的基本因子；η1、η2、η3、η4分别是任务完成好、中、差及未完成的质量因子；n、m、k、l是与质量因子对应的次数：α是资源的服务等级；P是当前资源的调度价格；ω是资源联合工作方式系数，β是联合工作资源节点的数量；t为该资源节点的网络传输状态权重。
    根据这两个关键因素，TSC在每次任务调度时，首先对各个资源节点的资源进行筛选，获取具有有效资源的资源节点信息，然后根据各个资源节点的资源价格参数、服务质量参数及其当前各节点的网络状态等参数制定任务调度价格，然后选取价格最小的资源分配方案进行任务调度。如果没有任何一个资源节点可以满足任务中单一资源需求，则先获取每个资源节点该资源的单位价格，然后按照由低到高的顺序，将任务发放到各个资源节点直到完全满足需求为止。
    经过TSC调度过的任务从ATQ中移出投放到STQ队列中去。此时，DTC根据各个任务的调度安排，将相应的数据集的副本传输到相应的资源节点。任务在各个资源节点执行时，如果发生异常，并在规定的时间内无法继续执行，则中断任务，向该任务的任务调度节点发送错误报告。该任务调度节点根据错误报告，首先重新调度STQ队列中的中断任务，此时该任务的调度优先级大于ATQ中任何任务的优先级。成功调度后，在STQ队列中恢复该任务的执行，同时在TFO队列中加入中断任务信息及其相应中断错误信息。若任务成功完成，则将STQ队列中的对应任务移出，同时将任务及其相关完成状况信息加入到TFQ队列中。
    TFQ队列即任务反馈队列，主要记录各个已完成任务的反馈信息。PFC根据这些信息，调整各个节点的价格参数，其主要功能是将完成质量好、执行效率高的资源节点的价格参数降低，使其更容易被调度；提升完成质量低、执行效率低的资源节点的价格参数，使其难以调度；在执行任务时，由于自身异常发生错误而中断任务执行的资源节点。不仅大幅度提升其价格参数，还要对其在该任务执行中造成价格亏损进行惩罚处理。价格反馈机制虽然改变资源节点的价格参数，但它对任务调度的选取没有绝对决定作用，因为在调度过程中，资源的选取不仅与各个资源节点的一系列价格参数有关，还与网络状态、资源空闲率以及是否是有效资源等因素有关。对于由联合参数决定的价格，它不仅反映当前时间段内各个资源节点的服务质量(QoS)，而且反映各个资源节点间的负载均衡及其网络传输效应。这样服务质量不好，价格参数高的资源节点也会伴随着网格环境中任务的数量增加而重新被调度，从而通过任务执行，改变自身的价格参数。因此，各个资源节点同类资源的价格参数不尽相同，也是动态变化，它总是随着任务的执行而不断改变，是资源站点服务近期服务质量的标志。
    在该调度模型中，资源的选取所依据的价格并不等同于网格服务计费中的实际价格。它只是一种服务质量与负载平衡反应的测度。通过价格的调控，使需调度的任务总是选取当前综合性能最合理的资源节点，而不是单一的性能最好或是资源空闲率最大的节点。

5 结束语
    T2DSM网格调度模型的设计以及基于价格反馈机制的调度策略，是将网格任务调度时的各个要素通过经济学中的价格机制来反应，通过不同时刻下各个资源节点的价格的动态变化以及任务完成后资源的价格反馈调整，实现任务与资源的实时、科学合理匹配，符合网格环境下资源使用的负载平衡及用户对任务的服务质量需求。