会员体验
专利管家(专利管理)
工作空间(专利管理)
风险监控(情报监控)
数据分析(专利分析)
侵权分析(诉讼无效)
联系我们
交流群
官方交流:
QQ群: 891211   
微信请扫码    >>>
现在联系顾问~
首页 / 专利库 / 截止时间 / 一种基于截止时间的具有容错能力的云计算任务流调度方法

一种基于截止时间的具有容错能力的云计算任务流调度方法

申请号 CN201711338393.7 申请日 2017-12-14 公开(公告)号 CN108021435A 公开(公告)日 2018-05-11
申请人 南京邮电大学; 发明人 付雄; 徐永杰; 乔磊; 王俊昌;
摘要 本发明涉及一种基于截止时间的具有容错能力的云计算任务流调度方法,将截止时间按比例分配到每层上,为高优先级的任务选择虚拟机,最终选定的虚拟机要满足该任务的完成时间小于所在层的截止时间;不仅考虑到用户要求的截止时间,在任务执行过程中虚拟机出错的情况也同时被考虑进来,更加接近实际生产环境下的云计算场景,可以有效地发挥虚拟机的计算能力,缩短整个应用的完成时间。
权利要求

1.一种基于截止时间的具有容错能力的云计算任务流调度方法,用于实现目标应用中各个子任务在云计算环境下各个虚拟机上的调度,其特征在于,包括如下步骤:步骤A.根据各个子任务之间的数据依赖关系,针对所有子任务,构建有向无环图,并获得其中各条关键路径,以及确认位于关键路径上的各个节点,然后进入步骤B;

步骤B.以出口任务位于第一层作为依据,分别针对其余各个子任务,根据有向无环图,获得子任务到出口任务路径上的最大边数,作为该子任务所在的层数,进而获得各个子任务分别所在的层数,实现针对所有子任务的分层,然后进入步骤C;

步骤C.基于有向无环图,根据目标应用的截止时间,分别获得各层所对应的截止时间,然后进入步骤D;

步骤D.计算获得目标应用中所有子任务的最早开始时间,并进入步骤E;

步骤E.选择有向无环图中入度为零的各个节点分别所对应的子任务,构建待选子任务序列,并在有向无环图中删除该各个子任务分别所对应的节点,更新有向无环图,然后进入步骤F;

步骤F.根据所有子任务的最早开始时间,按各个子任务的开始时间顺序,以及关键路径上节点所对应子任务优先于非关键路径上节点所对应子任务原则,针对待选子任务序列中的各个子任务进行排序,更新待选子任务序列,然后进入步骤G;

步骤G.由待选子任务序列中依序选择第一个子任务,作为当前处理子任务,在待选子任务序列中删除该子任务,获得当前处理子任务分别对应云计算环境下各个虚拟机的实际完成时间,然后进入步骤H;

步骤H.在小于当前处理子任务所在分层截止时间的各个实际完成时间中,选择最小实际完成时间所对应的虚拟机,将当前处理子任务分配至该虚拟机上进行执行,然后进入步骤I;

步骤I.判断待选子任务序列是否为空,是则进入步骤J;否则返回步骤G;

步骤J.判断有向无环图中是否存在节点,是则返回步骤E;否则针对目标应用中各个子任务实现在云计算环境下各个虚拟机上的调度方法结束。

2.根据权利要求1所述一种基于截止时间的具有容错能力的云计算任务流调度方法,其特征在于,所述步骤B中,以出口任务位于第一层作为依据,分别针对其余各个子任务,根据有向无环图,按如下公式:获得子任务到出口任务路径上的最大边数,作为该子任务所在的层数,进而获得各个子任务分别所在的层数,实现针对所有子任务的分层;其中,N(i)表示第i个子任务到出口任务路径上的最大边数,succ(i)表示第i个子任务的后继子任务集合,N(j)表示第j个子任务到出口任务路径上的最大边数。

3.根据权利要求1所述一种基于截止时间的具有容错能力的云计算任务流调度方法,其特征在于,所述步骤C包括如下步骤:步骤C1.基于有向无环图,由入口任务开始,按预设规则顺序,依次针对各个子任务由1开始顺序编号,然后进入步骤C2;

步骤C2.计算获得所有子任务编号之和Lweight,并根据目标应用的截止时间deadline,按如下公式:获得截止时间分配因子DF,然后进入步骤C3;

步骤C3.分别针对各层,获得层中各个子任务编号之和,作为该层的宽度,然后分别针对各层,根据如下公式:deadlinel=DF×weightl

分别获得各层的截止时间deadlinel,其中,l={1、...、L},L表示总层数,deadlinel表示第l层的截止时间,weightl表示第l层的宽度,然后进入步骤D。

4.根据权利要求1所述一种基于截止时间的具有容错能力的云计算任务流调度方法,其特征在于:所述步骤G中,针对当前处理子任务,根据如下公式:实际完成时间=(当前处理子任务所对应指令数/虚拟机CPU频率)*(1-虚拟机故障率)+1.5*(当前处理子任务所对应指令数/虚拟机CPU频率)*虚拟机故障率获得当前处理子任务分别对应云计算环境下各个虚拟机的实际完成时间。

说明书全文

一种基于截止时间的具有容错能力的云计算任务流调度方法

技术领域

[0001] 本发明涉及一种基于截止时间的具有容错能力的云计算任务流调度方法,属于云计算技术领域。

背景技术

[0002] 随着Internet网络技术的发展和计算机技术的不断提高,网络中传输和处理的数据的能力直线增长。人们希望获得一种直接、便捷的计算处理方式,不需要安装应用软件,只要连接互联网,就可以利用连接在网络中的空闲的计算机资源进行任务处理。
[0003] 在此背景之下,云计算应运而生,所谓云计算,就是通过计算机网络去连接由大量服务器、存储设备集群构成的云计算平台,来获取远程客户端所需要的服务。而云计算服务商则是将一项复杂的运算任务分成若干个部分,通过分布在计算机网络中的计算机协同合作,最终将运算结果传输到客户端,从而实现个人数据在远程的计算资源集群的运算。
[0004] 工作流调度是指将工作流中的任务映射到合适的资源并管理其运行。它不同于一般的任务调度,在调度时不仅要考虑为任务选择一个最佳资源,还要考虑各个任务之间的时序与因果的约束条件,以及协调各个任务的执行来获取最终的执行结果。
[0005] 工作流调度问题是云计算中的一个重要问题,直接关系到云服务的稳定性、资源的使用效率、用户的满意程度和运营成本。
[0006] 工作流调度问题可以简化为虚拟机的调度问题,来自终端的用户请求事先被分成多个子任务,这些子任务然后被分配到不同的虚拟机上。一个虚拟机从某种意义上讲可以被当成一个子任务和执行这个子任务所需要的物理资源(RAM,CPU,带宽等)的结合。所有的虚拟机最后都会被放置到特定的计算结点上执行子任务。而且,这些虚拟机可以在计算结点之间进行迁移从而能够提高计算资源的利用率。使用这种方式之后,数以千计的物理主机可以池化为巨大的资源池来服务用户的各种请求。
[0007] 计算资源管理和虚拟机放置一直是云计算系统中的重要问题。虚拟机放置问题是一个N维的装箱问题的变种,也是NP问题。这种问题无法在多项式级的时间内解决。研究者们在这个领域做出了巨大的努力。总的来说,当前的虚拟机放置算法大多专注于提高计算资源使用效率;使用数据管理策略或者缓存或者副本等来缩短数据访问延时;完善服务器负载均衡;减少能耗。
[0008] 云用户可以部署他们自己的应用到云系统上,因为受到单个计算结点的内存空间,CPU能力等因素限制,一个应用通常不能直接分配到一个计算结点上。这些应用通常被分割为多个子任务程序,而且子任务之间的代码长度和文件访问序列都可以不相同。应用的部署问题一直是云计算领域研究的重要课题。

发明内容

[0009] 本发明所要解决的技术问题是提供一种基于截止时间的具有容错能力的云计算任务流调度方法,能够缩短整个应用的总体完成时间,提高云计算任务流的调度效率。
[0010] 本发明为了解决上述技术问题采用以下技术方案:本发明设计了一种基于截止时间的具有容错能力的云计算任务流调度方法,用于实现目标应用中各个子任务在云计算环境下各个虚拟机上的调度,包括如下步骤:
[0011] 步骤A.根据各个子任务之间的数据依赖关系,针对所有子任务,构建有向无环图,并获得其中各条关键路径,以及确认位于关键路径上的各个节点,然后进入步骤B;
[0012] 步骤B.以出口任务位于第一层作为依据,分别针对其余各个子任务,根据有向无环图,获得子任务到出口任务路径上的最大边数,作为该子任务所在的层数,进而获得各个子任务分别所在的层数,实现针对所有子任务的分层,然后进入步骤C;
[0013] 步骤C.基于有向无环图,根据目标应用的截止时间,分别获得各层所对应的截止时间,然后进入步骤D;
[0014] 步骤D.计算获得目标应用中所有子任务的最早开始时间,并进入步骤E;
[0015] 步骤E.选择有向无环图中入度为零的各个节点分别所对应的子任务,构建待选子任务序列,并在有向无环图中删除该各个子任务分别所对应的节点,更新有向无环图,然后进入步骤F;
[0016] 步骤F.根据所有子任务的最早开始时间,按各个子任务的开始时间顺序,以及关键路径上节点所对应子任务优先于非关键路径上节点所对应子任务原则,针对待选子任务序列中的各个子任务进行排序,更新待选子任务序列,然后进入步骤G;
[0017] 步骤G.由待选子任务序列中依序选择第一个子任务,作为当前处理子任务,在待选子任务序列中删除该子任务,获得当前处理子任务分别对应云计算环境下各个虚拟机的实际完成时间,然后进入步骤H;
[0018] 步骤H.在小于当前处理子任务所在分层截止时间的各个实际完成时间中,选择最小实际完成时间所对应的虚拟机,将当前处理子任务分配至该虚拟机上进行执行,然后进入步骤I;
[0019] 步骤I.判断待选子任务序列是否为空,是则进入步骤J;否则返回步骤G;
[0020] 步骤J.判断有向无环图中是否存在节点,是则返回步骤E;否则针对目标应用中各个子任务实现在云计算环境下各个虚拟机上的调度方法结束。
[0021] 作为本发明的一种优选技术方案,所述步骤B中,以出口任务位于第一层作为依据,分别针对其余各个子任务,根据有向无环图,按如下公式:
[0022]
[0023] 获得子任务到出口任务路径上的最大边数,作为该子任务所在的层数,进而获得各个子任务分别所在的层数,实现针对所有子任务的分层;其中,N(i)表示第i个子任务到出口任务路径上的最大边数,succ(i)表示第i个子任务的后继子任务集合,N(j)表示第j个子任务到出口任务路径上的最大边数。
[0024] 作为本发明的一种优选技术方案,所述步骤C包括如下步骤:
[0025] 步骤C1.基于有向无环图,由入口任务开始,按预设规则顺序,依次针对各个子任务由1开始顺序编号,然后进入步骤C2;
[0026] 步骤C2.计算获得所有子任务编号之和Lweight,并根据目标应用的截止时间deadline,按如下公式:
[0027]
[0028] 获得截止时间分配因子DF,然后进入步骤C3;
[0029] 步骤C3.分别针对各层,获得层中各个子任务编号之和,作为该层的宽度,然后分别针对各层,根据如下公式:
[0030] deadlinel=DF×weightl
[0031] 分别获得各层的截止时间deadlinel,其中,l={1、…、L},L表示总层数,deadlinel表示第l层的截止时间,weightl表示第l层的宽度,然后进入步骤D。
[0032] 作为本发明的一种优选技术方案,所述步骤G中,针对当前处理子任务,根据如下公式:
[0033] 实际完成时间=(当前处理子任务所对应指令数/虚拟机CPU频率)*(1-虚拟机故障率)+1.5*(当前处理子任务所对应指令数/虚拟机CPU频率)*虚拟机故障率[0034] 获得当前处理子任务分别对应云计算环境下各个虚拟机的实际完成时间。
[0035] 本发明所述一种基于截止时间的具有容错能力的云计算任务流调度方法,采用以上技术方案与现有技术相比,具有以下技术效果:本发明所设计基于截止时间的具有容错能力的云计算任务流调度方法,将截止时间按比例分配到每层上,为高优先级的任务选择虚拟机,最终选定的虚拟机要满足该任务的完成时间小于所在层的截止时间;不仅考虑到用户要求的截止时间,在任务执行过程中虚拟机出错的情况也同时被考虑进来,更加接近实际生产环境下的云计算场景,可以有效地发挥虚拟机的计算能力,缩短整个应用的完成时间。

附图说明

[0036] 图1是本发明基于截止时间的具有容错能力的云计算任务流调度方法的流程图。

具体实施方式

[0037] 下面结合说明书附图对本发明的具体实施方式作进一步详细的说明。
[0038] 本发明设计了一种基于截止时间的具有容错能力的云计算任务流调度方法,用于实现目标应用中各个子任务在云计算环境下各个虚拟机上的调度,如图1所示,实际应用中,具体包括如下步骤:
[0039] 步骤A.根据各个子任务之间的数据依赖关系,针对所有子任务,构建有向无环图,并获得其中各条关键路径,以及确认位于关键路径上的各个节点,然后进入步骤B。
[0040] 步骤B.以出口任务位于第一层作为依据,分别针对其余各个子任务,根据有向无环图,按如下公式:
[0041]
[0042] 获得子任务到出口任务路径上的最大边数,作为该子任务所在的层数,进而获得各个子任务分别所在的层数,实现针对所有子任务的分层,然后进入步骤C。其中,N(i)表示第i个子任务到出口任务路径上的最大边数,succ(i)表示第i个子任务的后继子任务集合,N(j)表示第j个子任务到出口任务路径上的最大边数。
[0043] 步骤C.基于有向无环图,根据目标应用的截止时间,分别获得各层所对应的截止时间,然后进入步骤D。
[0044] 上述步骤C包括如下步骤:
[0045] 步骤C1.基于有向无环图,由入口任务开始,按预设规则顺序,依次针对各个子任务由1开始顺序编号,然后进入步骤C2。
[0046] 步骤C2.计算获得所有子任务编号之和Lweight,并根据目标应用的截止时间deadline,按如下公式:
[0047]
[0048] 获得截止时间分配因子DF,然后进入步骤C3。
[0049] 步骤C3.分别针对各层,获得层中各个子任务编号之和,作为该层的宽度,然后分别针对各层,根据如下公式:
[0050] deadlinel=DF×weightl
[0051] 分别获得各层的截止时间deadlinel,其中,l={1、...、L},L表示总层数,deadlinel表示第l层的截止时间,weightl表示第l层的宽度,然后进入步骤D。
[0052] 步骤D.计算获得目标应用中所有子任务的最早开始时间,并进入步骤E。
[0053] 步骤E.选择有向无环图中入度为零的各个节点分别所对应的子任务,构建待选子任务序列,并在有向无环图中删除该各个子任务分别所对应的节点,更新有向无环图,然后进入步骤F。
[0054] 步骤F.根据所有子任务的最早开始时间,按各个子任务的开始时间顺序,以及关键路径上节点所对应子任务优先于非关键路径上节点所对应子任务原则,针对待选子任务序列中的各个子任务进行排序,更新待选子任务序列,然后进入步骤G。
[0055] 步骤G.由待选子任务序列中依序选择第一个子任务,作为当前处理子任务,在待选子任务序列中删除该子任务,针对当前处理子任务,根据如下公式:
[0056] 实际完成时间=(当前处理子任务所对应指令数/虚拟机CPU频率)*(1-虚拟机故障率)+1.5*(当前处理子任务所对应指令数/虚拟机CPU频率)*虚拟机故障率[0057] 获得当前处理子任务分别对应云计算环境下各个虚拟机的实际完成时间,然后进入步骤H。
[0058] 步骤H.在小于当前处理子任务所在分层截止时间的各个实际完成时间中,选择最小实际完成时间所对应的虚拟机,将当前处理子任务分配至该虚拟机上进行执行,然后进入步骤I。
[0059] 步骤I.判断待选子任务序列是否为空,是则进入步骤J;否则返回步骤G。
[0060] 步骤J.判断有向无环图中是否存在节点,是则返回步骤E;否则针对目标应用中各个子任务实现在云计算环境下各个虚拟机上的调度方法结束。
[0061] 上述技术方案所设计基于截止时间的具有容错能力的云计算任务流调度方法,将截止时间按比例分配到每层上,为高优先级的任务选择虚拟机,最终选定的虚拟机要满足该任务的完成时间小于所在层的截止时间;不仅考虑到用户要求的截止时间,在任务执行过程中虚拟机出错的情况也同时被考虑进来,更加接近实际生产环境下的云计算场景,可以有效地发挥虚拟机的计算能力,缩短整个应用的完成时间。
[0062] 上面结合附图对本发明的实施方式作了详细说明,但是本发明并不限于上述实施方式,在本领域普通技术人员所具备的知识范围内,还可以在不脱离本发明宗旨的前提下做出各种变动。