一种考虑网格任务重要性和时间紧迫性的网格任务调度方法

摘要

本发明涉及一种考虑网格任务重要性和时间紧迫性的网格任务调度方法，所采用的方法是：建立一种基于代理的网格资源管理模型，其模型中包括：网格用户；网格请求；网格任务；网格资源和网格资源路由器，其网格任务Agent的具体方法是：1.根据任务的特性及任务的预算情况，参与某资源的投标并获得一定比例资源的使用权；2.网格任务的竞标策略明确地定义了它如何竞标以优化其效用函数；3.网格任务的主要目标是在一定资金预算限制下尽可能快地完成任务。本发明考虑了任务调度过程中每个子任务的重要性和时间紧迫性，并且作了定量定义，提出了一种模拟市场经济下的价值规律的模型，这种模型能够指导网格任务投标选择资源，并最终能大致保证任务在预期内完成。

说明书

技术领域

本发明属于计算机网格任务调度方法，特别是一种考虑网格任务重要性和时间紧迫性的网格任务调度方法。

背景技术

网格计算是继Internet、Web技术之后的第三次的技术革命，也是伴随着Internet技术一起发展起来的。随着科技的发展，科学、工程和商业领域中大规模性的计算问题的出现，使得单一的环境(P2P)，单一的技术(集群计算)无能为力，它必须寻求一种价格低廉，处理能力超强的高性能计算环境，网格就是这样应运而生。网格计算的核心思想是寻求一种超级计算能力的虚拟计算机，它利用目前十分流行的Internet技术将地理位置上的分布式的异构资源，如服务器，工作站，局域网，集群，文件系统，处理器，存储器等等全面共享，这种共享不是如今的Internet只是实现信息的上载与下载，它利用各种代理，实现资源透明的访问，使得Internet构成一台超级的，高性能计算能力的虚拟处理机。

在结构上，网格计算实际上是利用互联网将分散在不同地域上的计算资源组织起来，形成一个虚拟的“超级计算机”，每个参与的计算机就是一个“节点”，成千上万的节点组合起来，成为一个网格。网格计算有两个优势：一是超强的计算能力；另一个是能充分利用网络中的闲置的计算能力。从而使得Internet上的计算资源，存储资源，数据资源、信息资源、知识资源、专家资源等全面共享并得到充分的利用。

网格中资源是异构的，主要表现在资源的结构、配置和容量上的不同，它包括共享时间的处理器资源和共享空间的存储器资源以及其他形势的各种资源；网格中资源是属于多管理领域的，并且每个领域都有自己的管理策略，这就使得网格中的资源不可能像集群(Cluster)中资源一样实行集中管理，而必须实行分布式管理策略；网格的资源是动态变化的，因为在这样一个大规模环境中，随时有资源加入其中，也随时有资源退出其中，也有资源可用数量减少等等动态变化的因素，所以网格必须有能够实时监控网格中资源变化的能力。像这样一个规模遍及全球、资源异构并且动态变化的网格结构，对资源的管理和调度势必异常复杂。

由上可见，一方面由于网格环境价格低廉、计算能力超强，使得网格成为解决科学、工程和商业领域中大规模性问题的最佳环境；另一方面由于网格环境中的资源地理位置上的分布性、管理策略的多样性、资源配置的异构性和动态性等特点使得网格计算十分具有挑战性。平衡这两种矛盾的最好办法只能取长补短，克服缺点。因此，网格中的资源管理和调度成为网格计算的核心问题。

发明内容

本发明的目的是提供一种合理调度网格资源，优化网格任务处理的考虑网格任务重要性和时间紧迫性的网格任务调度方法。

为了实现上述目的，本发明所采用的方法是：

建立一种基于代理的网格资源管理模型，其模型中包括：

网格用户：网格环境下，提交网格任务到网格环境中执行的人；

网格请求Agent：每个网格用户对应一个网格请求Agent，其职责如下：

①接收网格用户的资源请求；

②根据资源请求寻找符合要求的资源；

③将用户的请求分解为多个子任务，每个子任务与一个网格任务Agent相对应；

④根据网格请求Agent的资源请求所映射的各个子任务的特性及资源市场的价格，制订出各个任务的费用预算及任务完成时限；

⑤按照任务之间的依赖关系和时间顺序，由每个任务对应的网格任务Agent进行投标获取资源；

⑥将各个网格任务Agent的计算结果汇总，最后将结果返回网格用户。

网格任务Agent：每个任务在计算网格中都有网格任务Agent与之对应，网格任务Agent通过竞标向一个或多个网格资源Agent购买资源，完成计算任务，其功能包括：

①根据任务的特性及任务的预算情况，参与某资源的投标并获得一定比例资源的使用权；

②网格任务Agent的竞标策略明确地定义了它如何竞标以优化其效用函数；

③网格任务Agent的主要目标是在一定资金预算限制下尽可能快地完成任务。

网格资源Agent：网格资源Agent的主要任务是：

①申请将资源描述发布到网格资源路由器；

②以一定的价格向网格请求代理出售资源，其中每个网格任务Agent都将获得一定时间段的一定份额的资源，资源的价格由拍卖与竞标决定；

③向网格请求Agent提供使用该资源的调用接口。

网格资源路由器：网格资源路由器完成以下功能：

①资源注册/注销：资源路由器是网格计算资源的接入设备，计算资源在资源路由器上注册之后，相当于在网格中分配了一个唯一的身份标示，可以被全网格系统共享；

②资源路由信息收集/更新：资源路由信息是有关资源所在位置的信息，作为对资源请求进行路由和转发的依据，由于资源的动态变化，资源路由器之间，路由器和资源之间需要周期性地进行路由信息的更新；

③资源请求的路由/转发：当资源路由器收到一个资源请求后，它需要根据资源路由信息为该请求选择一条路经并将其转发给相应的资源路由器。

本发明充分考虑到网格资源的距离，及网格任务调度过程中充分考虑网格任务的传输时间和传输费用。并且根据子任务的重要性和时间紧迫性特点，提出一种资源调度模型：这种模型模拟市场经济下的商品的价值规律，网格任务Agent根据子任务的重要性因子和时间紧迫性因子有针对性的投标网格资源，使得得到的资源的处理费用和执行速度处在任务的平均费用和速度预算上下浮动，从而既能兼顾子任务的特性(重要性和时间紧迫性)，又能大致保证最终的总的费用和时间仍然在预期的费用和时间之内。本发明与传统网格资源调度相比，其优点表现如下：1、本发明提出了一种基于代理的网格资源管理模型(AGRM)，并且简要的介绍了每个模块的功能；2、充分考虑了网格体系中资源的距离，及考虑了网格任务分派中的传输时间和传输费用，对于实际的基于市场经济模型的网格系统，这是很合理也是很有必要的，而在目前网格资源管理中很少考虑的；3、任务调度过程中考虑了每个子任务的重要性和时间紧迫性，并且作了定量定义，这是目前网格任务调度很少考虑的；而这种考虑很有现实意义，因为每个子任务之间不是等同的，而是有时间紧迫性和重要性区别的；4、提出了一种模拟市场经济下的价值规律的模型，这种模型能够指导网格任务投标选择资源，并最终能大致保证任务在预期内完成。

附图说明

图1为本发明基于代理的网格资源管理模型图。

图2为本发明费用和时间曲线。

图3为本发明投标方法流程图。

具体实施方式

下面结合附图对本发明作进一步的详细描述。

本发明提出的的调度方法是建立在市场经济模型下，首先描述网格环境中的任务、资源的属性，充分考虑任务的重要性和时间紧迫性以及的资源与任务之间的距离等因素；然后模拟市场经济下商品的价值规律，提出一种任务Agent投标选择网格资源的模型，这种模型能够保证选择的网格资源价格和速度浮动于任务的平均费用和速度上下，从而保证任务能够在预期内完成。其具体方法是：

1、网格用户提交给任务代理的一组任务T＝(T₁ T₂，......，T_m)，每个子任务都有一定的长度MI_i(i＝1，2...m)，整个任务有预算(Budget)和截止期限(DeadLine)两个QoS约束(B，D)，也就是说该组子任务必须在费用B内，D时间之内完成，否则无效。其中，任务的长度用MI(Million Instruct，百万指令)表示，预算B用CU(Cost Unit，费用单位)表示；截止期限D用S(Second，秒)表示。并且由于每个子任务的重要性和时间紧迫性不一样，子任务定义如下：

子任务T_i(MI_i，Q_i*B，Z_i*D)

其中MI_i是子任务的长度，Q_i表示子任务重要性因子，Z_i是任务时间紧迫性因子，满足下面要求：

$\underset{i=1}{\overset{n}{\Sigma }}\mathrm{Qi}=\mathrm{1,0}<\mathrm{Qi}<1,$$\underset{i=1}{\overset{n}{\Sigma }}\mathrm{Zi}=\mathrm{1,0}<\mathrm{Zi}<1$

对子任务重要性定义如下：

Q_iB/MI_i＞B/M……………………………………………(1)

及子任务的单位指令的费用比总任务的平均费用越高，表明子任务越重要，否则越不重要；

对子任务的时间紧迫性定义如下：

MI_i/Z_iD＞MI/D……………………………………………………(2)

及子任务期望完成速度比总任务的平均速度越快，表明子任务越紧迫，否则越不紧迫；

并且一般认为，对于重要的性比较高的子任务，应当尽量让其执行完；对于时间比较紧迫的任务可以选择资源费用比较高，同时速度比较快的资源执行。

2、网格中的一组资源集：(R₁，R₂，...，R_n)，每个资源都有(距离，处理速度，使用价格)(D_i，MIPS_i，CUPMI_i)属性，分别表示从网格任务代理到网格资源之间距离，资源的执行速度和执行费用，其单位分别用：距离单位DU，MI/S，CU/MI表示。并且假设网格中单位距离上的平均资源路由器个数为m(个/DU)，每个路由器的单位(百万)指令的转发时间为n(S)，单位(百万)指令的转发费用为k(CU)。

3、网格任务调度方法

网格任务Agent投标选择资源方法：

网格任务Agent根据自己分配的子任务特点(重要性，时间紧迫性)进行投标选择网格资源，并与其讨价还价。假设i任务Agent对应的任务T_i(MI_i，Q_iB，Z_iD)选择j资源R_j(D_i，MIPS_i，CUPMI_i)

那么，执行费用：

MI_i*D_j*k/m+MI_i*CUPMI_j

执行时间：

MI_i*D_j*n/m+MI_i/MIPS_j

如果子任务时间紧迫度高(Z_i*D/MI_i很小的)，那么允许该任务Agent投标那些执行速度快的资源，即使其执行费用很高，及本任务超出了其费用预算；否则就投标那些执行速度低的资源，平衡整体任务的时间预算；如果子任务重要性高(Q_i*B/MI很大的)，那么允许该任务Agent投标那些执行费用高的(一般认为，执行费用高的资源可能更稳定，质量更好)，即使执行速度慢些，及本任务超出了其时间预算；否则就投标执行费用低些的资源，平衡整体任务的费用预算。不管上述那种情况，整个任务的费用曲线和时间曲线应该满足图2所示曲线：也就是说所有的任务Agent的资源费用和资源速度应该在平均费用和速度预算上下波动，从而保证最后整体费用和时间在预期之内，及对于时间紧迫性高的任务，其执行费用可以高出自己的费用预算，否则应该低于自己的预算；对于重要性高的任务，其执行时间可以长于自己的时间预算，否则应该短于自己的时间预算，整体任务应当满足：

$\underset{i=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{n}{\Sigma }}(\mathrm{MIi}*\mathrm{Dj}*k/m+\mathrm{MIi}*\mathrm{CUPMIj})\approx B$

$\underset{j=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{n}{\Sigma }}(\mathrm{MIi}*\mathrm{Dj}*n/m+\mathrm{MIi}/\mathrm{MIPSj})\approx D$

任务Agent投标选择网格资源方法：

①对每个子任务Agent，根据自己分派的任务分析其重要性和时间紧迫性特点，具体参照式1和式2；

②任务Agent投标选择网格资源，对于重要性高的任务，可以投标选择执行费用高的资源，即使其执行速度慢，让其费用和时间在平均速度/费用预算线之上，反之，在平均速度/费用预算线之下。对于时间紧迫性高的任务，可以投标选择执行速度快的资源，即使其执行费用高出自己的费用预算，反之，投标那些执行速度低的、费用也低的资源；

③重复①②直至所有的任务Agent投标选择完成。

任务Agent投标结果评判：

上述所有任务Agent投标选择的资源是否合理，就是看所有的资源费用和速度分布情况：越是分布在平均速度/费用预算两边，曲线越是对称对称就越好，表明本次投标选择的资源既能满足任务本身的特征(时间紧迫性和重要性)要求，又能使整体任务能在预期的约束内完成；反之，就越不合理。

本说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。