法律状态公告日
法律状态信息
法律状态
2012-11-21
未缴年费专利权终止 IPC(主分类):G06F9/50 授权公告日:20090708 终止日期:20110920 申请日:20070920
专利权的终止
2009-07-08
授权
授权
2008-04-09
实质审查的生效
实质审查的生效
2008-02-13
公开
公开
技术领域
本发明属于一种网格资源调度方法，特别是一种基于市场经济模型的网格资源调度方法。
背景技术
由于计算机和通信网络技术的迅猛发展，特别是Internet的广泛应用、并行与分布计算技术将朝着基于高速网络的、面向大区域的高性能并行和分布计算-计算网格的技术方向发展。Lan foster、CarlKesselman和Steven Tuecke指出，网格计算是在动态变化的、拥有多个部门或团体的复杂虚拟组织中，进行安全灵活的协同资源共享与问题求解，目前的众多网格系统，例如Globus、Legion在底层通信、异构资源整合、在线控制等方面已经进行了大量的研究，并开发了各种相应的平台和组件。但是这些系统对于资源管理这个关键性问题的投入明显不足。网格环境中的资源管理和调度是个复杂的问题。在网格中，大量地理上分布的资源为不同的组织拥有，这些组织具有不同的使用规则、不同的计费模型、不一样的负荷能力和不同的使用模型，这些都是问题所在；此外生产者(资源拥有者)和消费者(资源使用者)各自具有不同的目标、目的、策略和需求，这也会对网格中的资源共享产生影响。由于网格的这些特点，一些传统的资源管理和调度方式在网格中并不适用。在网格环境中使用经济学原理进行资源管理和调度是网格从理论研究向实际应用所必须跨越的一步。
目前基于经济学的网格资源项目主要有GESA(Grid EconomicServices Architecture)、G-Commerce和GRACE。其中GESA和G-Commerce各项工作刚刚起步，缺乏相关文献和具体实现。澳大利亚Monash大学的Buyya设计的GRACE网格资源框架是一个基于分布式、可计算的经济学体系框架，用于在网格环境中进行资源交易。GRACE架构中定义了一个网格资源代理GRB层，负责资源发现、选择、绑定等关键任务。包括作业控制代理(Job Control Agent)、网格浏览器(Grid Explorer)、资源调度器(Schedule Advisor)交易管理器(Trade Managementer)、部署代理(Deployment Agent)和网格市场目录GMD。Nimord/G是DSTC(分布式系统技术中心)和Monash大学合作开发的一个工具集，主要设计目标是提供基于网格环境的大型分布式实验平台，提供一种简单的声明式参数化建模语言使用户可以规范化他们所要提交的作业和需求，并使用经济学模型进行资源调度和协同分配。Nimrod/G提供了优秀的GUI客户端，方便了用户的使用。
在网格资源调度方法中，Nimrod/G系统基于两项最为重要的QoS需求来设计，即用经济学驱动作业截止期(deadline)和预算约束(budgetconstrained)(DBC)调度算法按照用户的需求来分配资源。为代价、时间和时间变量的最优化策略研究了3种调度算法以支持截止期和预算约束，但是DBC算法并没有考虑到网格中资源的充分利用，使资源的利用效率达到最优化。
基本作业调度过程可以这样来描述作业调度，可视为代理对M个资源提出N个相互独立的作业任务请求的调度，通常情况下，作业的数目N≥M，当用户提交一个包含N个相互独立QoS的作业请求时，代理执行如下步骤：
①确定资源和资源的特性，并选择能够执行作业任务的资源；
②用经济模型建立作业的执行成本；
③使用调度算法选择符合用户需要的资源执行任务；
④将任务部署到资源上，监控；
⑤任务执行完毕，收集结果，返回给用户，记录相关的资源使用记录和支付记录；
⑥反复调度，重复执行③～⑤，确定调度在时间和预算之内完成；
⑦如果需要进行数据清理。
发明内容
本发明的目的是在DBC方法基础上考虑到任务传输时延的资源调度策略，使资源的利用达到最优，减少了系统调度的成本开销，而提供一种基于市场经济模型的网格资源调度方法，该方法在网格资源管理系统中具有很好的性能。
为了实现上述目的，本发明所采用的具体方法是：
第一步骤：调度程序接收系统创建的任务列表；
第二步骤：调度程序接收资源列表；
第三步骤：初始化总的任务长度为0；
第四步骤：获取第一个资源的处理速率MIPS；
第五步骤：用资源的处理速率乘以间隔时间得到第一个任务的长度MI：
第六步骤：创建一个新的任务，其长度等于总的任务长度；
第七步骤：为任务组设置用户的ID；
第八步骤：把任务组添加到任务列表2中；
第九步骤：把资源ID添加到链接表中；
第十步骤：把总的任务长度高置为0；
第十一步骤：获取下一个资源的处理速率MIPS，如果资源列表中的资源都分配了任务组，则继续调度算法过程：在资源列表中取得一个资源的处理速率；
第十二步骤：用资源的处理速率乘以时间间隔，得到下一个任务的长度；
第十三步骤：重复以上步聚，直到任务列表中的任务都打包成组到任务组中；
第十四步骤：当所有的任务打包成组后、每一个任务组都分配给了一个指定的资源后，就把所有的任务组送交给对应的资源去进行计算；
第十五步骤：当所有的任务组被处理完后，处理完后的任务组被送回到调度程序/系统的I/O队列中，然后从I/O队列中收集任务组；
第十六步骤：设置资源ID，每个任务组的作业执行成本；
第十七步骤：把收集到的任务组存贮到任务列表3中；
第十八步骤：获取总的模拟处理时间。
本发明在原有的DBC算法基础上针对网格资源处理任务时没有考虑到传输时延的不足，提出了一种改进的网格资源任务调度算策略，在满足作业截止期，成本预算约束的条件下，充分考虑到网格资源的处理效率，使资源的利用率达到最优，减少了系统调度的成本开销。
附图说明
附图为本发明的流程图。
具体实施方式
下面结合附图对本发明作进一步的详细描述。
在网格计算环境中，调度器选择最合适的机器或计算资源来处理用户的作业从而达到高的系统生产率。如果一个任务由许多作业组成，而每个作业不需要很高的处理能力的资源，这时在作业之间的传递信息的时间比资源处理所有作业的时间要多。因此，在用户层次上一定数量的作业可以聚积在一起组成粗粒度(任务长度大)的任务，然后送交给调度器来分配合适的资源进行处理。对于每个细粒度(任务长度小)的任务，完成任务的时间开销由传送时间、处理时间组成，在网格环境中，消息之间的交互导致很高的时间开销，从而也造成了资源利用效率的降低。因此，根据有效资源的处理能力提出一种基于组作业(把细粒度的作业打包成粗粒度的任务)的调度策略是有必要的，然后进行任务的调度和资源的分配。本发明提出了一种动态任务调度策略使网格资源的效率得到充分的利用，并且减少了执行任务的时间成本。提出的调度策略考虑了(1)根据资源的能力，把作业打包成组的机制；(2)每个作业的处理要求；(3)把粗粒度的任务调度给合适的资源进行处理。
本发明的具体方法是：
1.调度程序接收系统创建的任务列表；
2.调度程序接收资源列表(由用户从资源文件中选择的资源)；
3.初始化总的任务长度为0；
4.获取第一个资源的处理速率MIPS(million instruction persecond)；
5.用资源的处理速率(Resource_MIPS)乘以间隔时间(Granularity_Time)得到第一个任务的长度MI(millioninstruction)、
6.如果资源的处理速率小于或等于任务的长度则
a.使总的任务长度为目前的任务长度
b.转到第8步继续进行。
7.如果资源处理速率大于任务的长度则
7.1当任务总的长度小于或等于资源的处理速率，并且仅当在任务列表中存在未成组的任务则
a.获取下一个任务的长度
b.使总的任务长度为当前任务长度与之前总的任务长度之和
c.重复进行7.1步聚；
7.2如果资源处理速率与总的任务长度之差大于50则计算出总的任务长度中最后一个任务的长度；
8.创建一个新的任务(任务组)，其长度等于总的任务长度；
9.为任务组设置用户的ID；
10.把任务组添加到任务列表2(Gridlet_List_2)中(一个新的任务列表)；
11.把资源ID(当前使用的资源)添加到链接表中；
12.把总的任务长度高置为0；
13.获取下一个资源的处理速率(MIPS)。如果资源列表中的资源都分配了任务组，则继续调度算法过程：在资源列表中取得一个资源的处理速率；
14.用资源的处理速率乘以时间间隔，得到下一个任务的长度；
15.转到第7步聚重复进行；
16.重得以上步聚，直到任务列表中的任务都打包成组到任务组中；
17.当所有的任务打包成组后、每一个任务组都分配给了一个指定的资源后，就把所有的任务组送交给对应的资源去进行计算；
18.当所有的任务组被处理完后，处理完后的任务组被送回到调度程序/系统的I/O队列中，然后从I/O队列中收集任务组；
19.设置资源ID，每个任务组的作业执行成本；
20.把收集到的任务组存贮到任务列表3(Gridlet_List_3)中；
21.获取总的模拟处理时间。
本发明说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。
机译： 有助于引入基于市场的电力经济模型的系统和方法
机译： 通过基于编码单元的滤波网格对视频进行编码的方法，通过基于编码单元的滤波网格对视频进行解码的方法，通过基于编码单元的滤波网格对视频进行编码的视频编码设备，视频解码设备通过基于编码单位执行滤波网格对视频进行解码，并记录计算机可读的记录介质。
机译： 网格网络中资源调度的方法及网格网络节点
