一种云中基于任务后移的容错任务调度方法

摘要

本发明公开了一种云中基于任务后移的容错任务调度方法，其特征在于，获取已到达的依赖任务组信息与虚拟化云的物理主机信息；使用PB模型为依赖任务组中的每个任务建立主版本与副版本；为依赖任务组中的每个任务的每个版本均指定一个最早开始时间与一个最晚完成时间；在每个被激活的物理主机上划分出多个虚拟机，获取每个被激活的物理主机上的每个虚拟机信息；将依赖任务组中的每个任务的每个版本在指定的时间段上加载到每个被激活的物理主机上的每个虚拟机中；按照指定的时间安排运行被加载的依赖任务组中的每个任务的每个版本；使用后移任务方法调整已调度任务的最早开始时间为新到达的依赖任务组中的任务提供时间窗口。

权利要求

1.一种云中基于任务后移的容错任务调度方法，其特征在于，包括：

获取已到达的依赖任务组信息与虚拟化云的物理主机信息；

使用PB模型为所述依赖任务组中的每个任务建立主版本与副版本；

根据所述依赖任务组信息为所述依赖任务组中的每个任务的每个版本均指定一个最早开始时间与一个最晚完成时间；

根据所述依赖任务组信息激活多个所述物理主机，并在每个被激活的所述物理主机上划分出多个虚拟机，获取每个被激活的所述物理主机上的每个所述虚拟机信息；

根据依赖任务组中的每个任务的每个版本的最早开始时间与最晚完成时间、以及每个被激活的所述物理主机上的每个所述虚拟机信息，将所述依赖任务组中的每个任务的每个版本在指定的时间段上加载到每个被激活的所述物理主机上的每个所述虚拟机中；

在每个被激活的所述物理主机上的每个所述虚拟机中按照指定的时间安排运行被加载的所述依赖任务组中的每个任务的每个版本；

获取新到达的依赖任务组，并使用后移任务方法调整已调度任务的最早开始时间为新到达的依赖任务组中的任务提供时间窗口，并且不影响已调度任务的完成情况；

完成依赖任务组的全部任务并返回任务结果。

2.根据权利要求1所述的一种云中基于任务后移的容错任务调度方法，其特征在于：

所述依赖任务组信息包括任务集合、任务间关系集合与任务截止期，所述任务集合记载了所述依赖任务组中每个任务的大小，所述任务间关系集合记载了所述依赖任务组中任意两个任务之间的依赖关系，所述任务截止期为所述依赖任务组的最晚完成时间；

所述物理主机信息包括物理主机集合，所述物理主机集合记载了每个所述物理主机处理能力的大小；

所述虚拟机信息包括每个被激活的所述物理主机上的虚拟机集合，所述虚拟机集合记载了每个所述虚拟机所在的物理主机以及每个所述虚拟机处理能力的大小。

3.根据权利要求2所述的一种云中基于任务后移的容错任务调度方法，其特征在于，所述使用PB模型为所述依赖任务组中的每个任务建立主版本与副版本，为在所述依赖任务组中依次指定每个任务，并为被指定的任务创建一个主版本与一个副版本，其中，同一个任务的主版本与副版本重复进行相同的工作。

4.根据权利要求3所述的一种云中基于任务后移的容错任务调度方法，其特征在于，多个被激活的所述物理主机之间存在传输时延；根据所述依赖任务组信息为所述依赖任务组中的每个任务的每个版本均指定一个最早开始时间与一个最晚完成时间包括：对于任一子任务的主版本，其最早开始时间为其多个父任务中每个父任务的完成时间加上所述父任务所在物理主机与子任务所在物理主机之间的传输时延之和中的最大值；

对于任一子任务的副版本，其最早开始时间为其多个父任务中每个父任务的完成时间加上所述父任务所在物理主机与子任务所在物理主机之间的传输时延之和、以及同一任务的主版本任务长度二者的较大值；

对于任一非子任务的主版本，其最早开始时间为该任务的主版本所在物理主机的所在虚拟机为执行该任务的主版本而准备就绪的时间与该任务所在的依赖任务组信息到达时间中的较大值；

对于任一非子任务的副版本，其最早开始时间为该任务的副版本所在物理主机的所在虚拟机为执行该任务的副版本而准备就绪的时间与该任务所在的依赖任务组信息到达时间中的较大值；

对于任一任务的任意版本，其最晚完成时间为该任务的截止时间；

其中，一子任务与一父任务为一依赖任务对，所述子任务依赖于所述父任务，所述子任务必须获得所述父任务的执行结果才能执行。

5.根据权利要求3所述的一种云中基于任务后移的容错任务调度方法，其特征在于，将所述依赖任务组中的每个任务的每个版本在指定的时间段上加载到每个被激活的所述物理主机上的每个所述虚拟机中，包括：根据所述依赖任务组信息的任务间关系集合与任务截止期，估算所述依赖任务组中的每个任务的截止期；

在所述依赖任务组指定一个非子任务、或所有父任务都已经被调度过的子任务；

调度所述指定任务的主版本到指定主机的指定虚拟机上；

调度所述指定任务的副版本到指定主机的指定虚拟机上；

继续指定并调度下一任务。

6.根据权利要求5所述的一种云中基于任务后移的容错任务调度方法，其特征在于，当所述指定任务的主版本与副版本都在该任务的截止期之前完成时，视为该任务已经成功调度；若该任务未被成功调度，将重新计算其子任务的最早可能开始时间并使该时间适当提前以消除该任务延时造成的影响；若将该任务的子任务也未被成功调度，则停止计算该依赖任务组的所有任务、回收所有该依赖任务组占用的计算资源并返回任务失败信息。

7.根据权利要求5所述的一种云中基于任务后移的容错任务调度方法，其特征在于，获取新到达的依赖任务组，并使用后移任务方法调整已调度任务的开始时间为新到达的依赖任务组中的任务提供时间窗口，为计算所述依赖任务组中所有已调度任务的所有版本的后移时间冗余，并获取新到达的依赖任务组，通过后移已调度任务的开始时间为新到达的依赖任务组中的任务提供时间窗口；其中，一个已调度任务的主版本的后移时间冗余为该已调度任务的主版本所在虚拟机上下一个任务的开始时间减去该任务的完成时间，与将该任务的子任务的开始时间减去该任务所在主机与子任务所在主机之间的传输时延再减去该任务的完成时间中的较小值；一个已调度任务的副版本的后移时间冗余为该副版本后移不会对将该任务的子任务的开始时间与执行状态产生影响的最小值，与该已调度任务的副版本所在虚拟机上下一个任务的开始时间减去该任务的完成时间中的较小值。

说明书

一种云中基于任务后移的容错任务调度方法

技术领域

[0001] 本发明涉及云计算领域，特别地，涉及一种云中基于任务后移的容错任务调度方法。

背景技术

[0002] 由于计算机系统出错的不可预测性，在设计调度算法时加入对容错性的支持至关重要。容错调度算法大体上可以分为两类，即静态容错调度和动态容错调度：静态容错调度在任务提交之前进行调度决策，通常用来调度周期性任务；动态容错调度通常用来调度非周期性任务，其任务到达时间不确定。

[0003] 目前，在分布式计算环境下主要有两种主要的容错调度手段，即重提交和复制。重提交是指当一个任务所分配的计算节点出现故障后，该任务被重新提交。采用重提交方式将会导致一些任务的完成时间推迟，甚至可能会不满足任务的截止期。复制是指通过将一个任务复制成多个版本，之后把每个复制的版本分配到不同的计算节点，以保证即便在资源出现故障的情况下，任务仍能在截止期前成功完成。任务被复制的版本越多，系统的容错能力越强，但这将不可避免地造成大量的资源消耗。因此，采用两个版本的复制方式，即主版本与副版本模型(primary-backup model，下文中简称为PB模型)成为目前广为采用的容错手段。

[0004] 为了在保障容错的前提下提高系统可调度性和资源利用率，有不少学者在采用PB模型时研究了如何通过重叠技术减少系统开销。目前主要有两种的重叠模式：副版本-副版本重叠(backup-backup overlapping，简称BB重叠)，即多个不同的副版本可在同一个计算单元上进行重叠；主版本-副版本重叠(primary-backup overlapping，简称PB重叠)，即一个主版本可以和其他任务的副版本在同一个计算单元上重叠。在PB模型中，副版本可进一步分为两种类型，即被动副版本(passive backup)和主动副版本(active backup)。被动副版本只在其对应的主版本不能成功完成时开始执行，如果主版本成功完成，副版本将被撤销。尽管上述方法可以减少资源占用，但不能保证所有的任务可在截止期内完成；相反，主动副版本允许一个任务的主版本和副版本在执行时间上有重叠，采用主动副版本执行方式可以减小任务错失截止期的概率，但同时资源利用率也会随之降低。现有技术中已经存在对实时任务进行重叠处理的技术方案，但这些技术方案并未考虑系统的虚拟化，因此仅适用于传统的分布式系统，并不适合虚拟化云计算环境。

[0005] 近来，也有一些云中依赖任务调度方面的研究。但是这些工作都没有在调度时考虑系统出错的情况，不能解决云中容错问题。针对现有技术中缺乏云计算环境下容错任务调度方法的问题，目前尚未有有效的解决方案。

发明内容

[0006] 针对现有技术中缺乏云计算环境下容错任务调度方法的问题，本发明的目的在于提出一种云中基于任务后移的容错任务调度方法，能够在云计算环境下采用PB模型进行容错任务的调度，提高资源利用率与容错任务的可调度性。

[0007] 基于上述目的，本发明提供的技术方案如下：

[0008] 根据本发明的一个方面，提供了一种云中基于任务后移的容错任务调度方法，包括：

[0009] 获取已到达的依赖任务组信息与虚拟化云的物理主机信息；

[0010] 使用PB模型为依赖任务组中的每个任务建立主版本与副版本；

[0011] 根据依赖任务组信息为依赖任务组中的每个任务的每个版本均指定一个最早开始时间与一个最晚完成时间；

[0012] 根据依赖任务组信息激活多个物理主机，并在每个被激活的物理主机上划分出多个虚拟机，获取每个被激活的物理主机上的每个虚拟机信息；

[0013] 根据依赖任务组中的每个任务的每个版本的最早开始时间与最晚完成时间、以及每个被激活的物理主机上的每个虚拟机信息，将依赖任务组中的每个任务的每个版本在指定的时间段上加载到每个被激活的物理主机上的每个虚拟机中；

[0014] 在每个被激活的物理主机上的每个虚拟机中按照指定的时间安排运行被加载的依赖任务组中的每个任务的每个版本；

[0015] 获取新到达的依赖任务组，并使用后移任务方法调整已调度任务的最早开始时间为新到达的依赖任务组中的任务提供时间窗口，并且不影响已调度任务的完成情况；

[0016] 完成依赖任务组的全部任务并返回任务结果。

[0017] 其中，依赖任务组信息包括任务集合、任务间关系集合与任务截止期，任务集合记载了依赖任务组中每个任务的大小，任务间关系集合记载了依赖任务组中任意两个任务之间的依赖关系，任务截止期为依赖任务组的最晚完成时间；物理主机信息包括物理主机集合，物理主机集合记载了每个物理主机处理能力的大小；虚拟机信息包括每个被激活的物理主机上的虚拟机集合，虚拟机集合记载了每个虚拟机所在的物理主机以及每个虚拟机处理能力的大小。

[0018] 并且，使用PB模型为依赖任务组中的每个任务建立主版本与副版本，为在依赖任务组中依次指定每个任务，并为被指定的任务创建一个主版本与一个副版本，其中，同一个任务的主版本与副版本重复进行相同的工作。

[0019] 并且，多个被激活的物理主机之间存在传输时延；根据依赖任务组信息为依赖任务组中的每个任务的每个版本均指定一个最早开始时间与一个最晚完成时间包括：

[0020] 对于任一子任务的主版本，其最早开始时间为其多个父任务中每个父任务的完成时间加上父任务所在物理主机与子任务所在物理主机之间的传输时延之和中的最大值；

[0021] 对于任一子任务的副版本，其最早开始时间为其多个父任务中每个父任务的完成时间加上父任务所在物理主机与子任务所在物理主机之间的传输时延之和、以及同一任务的主版本任务长度二者的较大值；

[0022] 对于任一非子任务的主版本，其最早开始时间为该任务的主版本所在物理主机的所在虚拟机为执行该任务的主版本而准备就绪的时间与该任务所在的依赖任务组信息到达时间中的较大值；

[0023] 对于任一非子任务的副版本，其最早开始时间为该任务的副版本所在物理主机的所在虚拟机为执行该任务的副版本而准备就绪的时间与该任务所在的依赖任务组信息到达时间中的较大值；

[0024] 对于任一任务的任意版本，其最晚完成时间为该任务的截止时间；

[0025] 其中，一子任务与一父任务为一依赖任务对，子任务依赖于父任务，子任务必须获得父任务的执行结果才能执行。

[0026] 同时，将依赖任务组中的每个任务的每个版本在指定的时间段上加载到每个被激活的物理主机上的每个虚拟机中，包括：

[0027] 根据依赖任务组信息的任务间关系集合与任务截止期，估算依赖任务组中的每个任务的截止期；

[0028] 在依赖任务组指定一个非子任务、或所有父任务都已经被调度过的子任务；

[0029] 调度指定任务的主版本到指定主机的指定虚拟机上；

[0030] 调度指定任务的副版本到指定主机的指定虚拟机上；

[0031] 继续指定并调度下一任务。

[0032] 并且，当指定任务的主版本与副版本都在该任务的截止期之前完成时，视为该任务已经成功调度；若该任务未被成功调度，将重新计算其子任务的最早可能开始时间并使该时间适当提前以消除该任务延时造成的影响；若将该任务的子任务也未被成功调度，则停止计算该依赖任务组的所有任务、回收所有该依赖任务组占用的计算资源并返回任务失败信息。

[0033] 同时，获取新到达的依赖任务组，并使用后移任务方法调整已调度任务的开始时间为新到达的依赖任务组中的任务提供时间窗口，为计算依赖任务组中所有已调度任务的所有版本的后移时间冗余，并获取新到达的依赖任务组，通过后移已调度任务的开始时间为新到达的依赖任务组中的任务提供时间窗口；其中，一个已调度任务的主版本的后移时间冗余为该已调度任务的主版本所在虚拟机上下一个任务的开始时间减去该任务的完成时间，与将该任务的子任务的开始时间减去该任务所在主机与子任务所在主机之间的传输时延再减去该任务的完成时间中的较小值；一个已调度任务的副版本的后移时间冗余为该副版本后移不会对将该任务的子任务的开始时间与执行状态产生影响的最小值，与该已调度任务的副版本所在虚拟机上下一个任务的开始时间减去该任务的完成时间中的较小值。

[0034] 从上面所述可以看出，本发明提供的技术方案通过建立虚拟化云中实时容错模型代替传统的PB模型，采用任务后移策略建立了一种充分利用空闲资源的容错任务调度方法，提高容错保障下的资源利用率与容错任务的可调度性。

附图说明

[0035] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0036] 图1为根据本发明实施例的一种云中基于任务后移的容错任务调度方法流程图；

[0037] 图2为根据本发明实施例的一种云中基于任务后移的容错任务调度方法中，强主版本的消息或数据传递关系图；

[0038] 图3为根据本发明实施例的一种云中基于任务后移的容错任务调度方法中，弱主版本的消息或数据传递关系图；

[0039] 图4为根据本发明实施例的一种云中基于任务后移的容错任务调度方法中，强主版本在第三种情况中、子任务主版本开始时间晚于父任务副版本的结束时间的情况下的消息或数据传递关系图；

[0040] 图5为根据本发明实施例的一种云中基于任务后移的容错任务调度方法中，强主版本在第三种情况中、子任务主版本开始时间早于父任务副版本的结束时间的情况下的消息或数据传递关系图。

具体实施方式

[0041] 为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进一步进行清楚、完整、详细地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员所获得的所有其他实施例，都属于本发明保护的范围。

[0042] 根据本发明的实施例，提供了一种云中基于任务后移的容错任务调度方法。

[0043] 如图1所示，根据本发明实施例的提供的一种云中基于任务后移的容错任务调度方法包括：

[0044] 步骤S101，获取已到达的依赖任务组信息与虚拟化云的物理主机信息；

[0045] 步骤S103，使用PB模型为依赖任务组中的每个任务建立主版本与副版本；

[0046] 步骤S105，根据依赖任务组信息为依赖任务组中的每个任务的每个版本均指定一个最早开始时间与一个最晚完成时间；

[0047] 步骤S107，根据依赖任务组信息激活多个物理主机，并在每个被激活的物理主机上划分出多个虚拟机，获取每个被激活的物理主机上的每个虚拟机信息；

[0048] 步骤S109，根据依赖任务组中的每个任务的每个版本的最早开始时间与最晚完成时间、以及每个被激活的物理主机上的每个虚拟机信息，将依赖任务组中的每个任务的每个版本在指定的时间段上加载到每个被激活的物理主机上的每个虚拟机中；

[0049] 步骤S111，在每个被激活的物理主机上的每个虚拟机中按照指定的时间安排运行被加载的依赖任务组中的每个任务的每个版本；

[0050] 步骤S113，获取新到达的依赖任务组，并使用后移任务方法调整已调度任务的最早开始时间为新到达的依赖任务组中的任务提供时间窗口，并且不影响已调度任务的完成情况；

[0051] 步骤S115，完成依赖任务组的全部任务并返回任务结果。

[0052] 其中，依赖任务组信息包括任务集合、任务间关系集合与任务截止期，任务集合记载了依赖任务组中每个任务的大小，任务间关系集合记载了依赖任务组中任意两个任务之间的依赖关系，任务截止期为依赖任务组的最晚完成时间；物理主机信息包括物理主机集合，物理主机集合记载了每个物理主机处理能力的大小；虚拟机信息包括每个被激活的物理主机上的虚拟机集合，虚拟机集合记载了每个虚拟机所在的物理主机以及每个虚拟机处理能力的大小。

[0053] 并且，使用PB模型为依赖任务组中的每个任务建立主版本与副版本，为在依赖任务组中依次指定每个任务，并为被指定的任务创建一个主版本与一个副版本，其中，同一个任务的主版本与副版本重复进行相同的工作。

[0054] 并且，多个被激活的物理主机之间存在传输时延；根据依赖任务组信息为依赖任务组中的每个任务的每个版本均指定一个最早开始时间与一个最晚完成时间包括：

[0055] 对于任一子任务的主版本，其最早开始时间为其多个父任务中每个父任务的完成时间加上父任务所在物理主机与子任务所在物理主机之间的传输时延之和中的最大值；

[0056] 对于任一子任务的副版本，其最早开始时间为其多个父任务中每个父任务的完成时间加上父任务所在物理主机与子任务所在物理主机之间的传输时延之和、以及同一任务的主版本任务长度二者的较大值；

[0057] 对于任一非子任务的主版本，其最早开始时间为该任务的主版本所在物理主机的所在虚拟机为执行该任务的主版本而准备就绪的时间与该任务所在的依赖任务组信息到达时间中的较大值；

[0058] 对于任一非子任务的副版本，其最早开始时间为该任务的副版本所在物理主机的所在虚拟机为执行该任务的副版本而准备就绪的时间与该任务所在的依赖任务组信息到达时间中的较大值；

[0059] 对于任一任务的任意版本，其最晚完成时间为该任务的截止时间；

[0060] 其中，一子任务与一父任务为一依赖任务对，子任务依赖于父任务，子任务必须获得父任务的执行结果才能执行。

[0061] 同时，将依赖任务组中的每个任务的每个版本在指定的时间段上加载到每个被激活的物理主机上的每个虚拟机中，包括：

[0062] 根据依赖任务组信息的任务间关系集合与任务截止期，估算依赖任务组中的每个任务的截止期；

[0063] 在依赖任务组指定一个非子任务、或所有父任务都已经被调度过的子任务；

[0064] 调度指定任务的主版本到指定主机的指定虚拟机上；

[0065] 调度指定任务的副版本到指定主机的指定虚拟机上；

[0066] 继续指定并调度下一任务。

[0067] 并且，当指定任务的主版本与副版本都在该任务的截止期之前完成时，视为该任务已经成功调度；若该任务未被成功调度，将重新计算其子任务的最早可能开始时间并使该时间适当提前以消除该任务延时造成的影响；若将该任务的子任务也未被成功调度，则停止计算该依赖任务组的所有任务、回收所有该依赖任务组占用的计算资源并返回任务失败信息。

[0068] 同时，获取新到达的依赖任务组，并使用后移任务方法调整已调度任务的开始时间为新到达的依赖任务组中的任务提供时间窗口，为计算依赖任务组中所有已调度任务的所有版本的后移时间冗余，并获取新到达的依赖任务组，通过后移已调度任务的开始时间为新到达的依赖任务组中的任务提供时间窗口；其中，一个已调度任务的主版本的后移时间冗余为该已调度任务的主版本所在虚拟机上下一个任务的开始时间减去该任务的完成时间，与将该任务的子任务的开始时间减去该任务所在主机与子任务所在主机之间的传输时延再减去该任务的完成时间中的较小值；一个已调度任务的副版本的后移时间冗余为该副版本后移不会对将该任务的子任务的开始时间与执行状态产生影响的最小值，与该已调度任务的副版本所在虚拟机上下一个任务的开始时间减去该任务的完成时间中的较小值。

[0069] 下面根据具体实施例进一步阐述本发明的技术特征。

[0070] 由于任务到达通常不具有周期性，在本实施例中，我们考虑动态到达的依赖任务。一组依赖任务可以表示为一个有向无环图(Directed Acyclic Graph，下文中简称为DAG)。
一个DAG可被定义为G＝{T,E}，其中，T＝{t1,t2,…,tn}表示实时的非周期任务集合，E表示任务间的关系集合。eij＝(ti,tj)表示任务tj依赖于任务ti，即只有tj获得ti的执行结果或者消息才能执行。因此，我们称ti为tj的父任务，tj为ti的子任务。对任一任务ti∈T，P(ti)和C(ti)分别表示任务ti的父任务集合和子任务结合。 表示任务ti没有父任务，表示任务ti没有子任务。一个DAG的达到时间和截止期分别表示为a(G)和d(G)。
任务ti可以描述成一个三元组ti＝(ai,di,si)，其中，ai、di和si分别表示任务ti的达到时间、截止期和任务大小。任务ti的截止期di可以通过其所在DAG的截止期d(G)计算得到。任务大小用百万指令数(million instructions，下文中简称为MI)衡量。在PB模型中，对于任一任务ti∈T，存在两个版本，分别表示为主版本 和副版本 和 被分配到不同的主机上以实现容错。 和 分别表示主版本 的开始时间和完成时间。类似地， 和 分别表示副版本 的开始时间和完成时间。 和 分别表示 和 的父任务集合，
和 分别表示 和 的子任务集合。

[0071] 虚拟化云可描述为一个物理主机的无限集合H＝{h1,h2,…}。虽然云中的主机数量是无限的，但活动主机的数量是有限的。集合 表示云中活动主机集合，H-Ha表示关闭主机集合。对任一主机hk∈H，其处理能力pk用每秒百万指令数(million instructions per  second，下文中简称为MIPS)衡量。每个主机hk上有多个虚拟机，用集合表示，每个虚拟机vjk∈Vk有不同的处理能力pjk。对于主机hk上的虚拟机，其处理能力满足 vjk的就绪时间表示为rjk。

[0072] 在一个虚拟化云中，一个主机可以有一个或多个虚拟机在其上运行，因此任务被分配到每个虚拟机而非直接分配到某个主机。我们假设，虚拟机的处理能力具有异构性，即虚拟机可以有不同的处理能力。一个任务的主版本和副版本在这些虚拟机上的执行时间可分别用矩阵EP和EB表示，其中元素 和 分别表示 和 在虚拟机vjk上的执行时间。我们用 和 分别表示任务主版本 和副版本 与虚拟机vjk之间的映射关系：如果 被分配到虚拟机vjk上则 否则 类似地，如果 被分配到虚拟机vjk上则否则 和 分别表示 和 所分配到的虚拟机， 和
则表示 和 所分配到的主机。因此， 意味着 意味着

[0073] 表示 和 之间的边，其中X,Y∈{P,B}，即 可以是 也可以是 同样，既可以是 也可以是 对每个边 从 到 的数据或消息传输时间表示为若 和 具有依赖关系且被分配到同一主机，则 此外，令dvij表示任务ti
到任务tj的数据或消息传输量， 表示主机 到 的传输速度，可知
其中 任务tj主版本和副版本最早开始时间
可分别计算为：

[0074]

[0075]

[0076] 的最晚完成时间 由任务的截止期决定，因此有：

[0077]

[0078] 的实际开始时间 是 被调度后开始执行的时间。 可以放置在由 和限定的空闲时间槽内。我们的调度目标即找到合适的任务开始时间，尽量接受更多的实时DAG，提高系统的吞吐量。

[0079] 需要特别指出的是，本发明的技术方案所述的错误为针对主机出错，主机出错导致其他层级如虚拟机和应用的中断运行。错误既可以是暂时的也可以是永久的，但各个错误相互独立，一台主机的出错不会影响其他主机。同时，由于两个主机同时出错的概率很小，因此假设在任一时间，至多一台主机出错。一台主机出错后，主版本在该主机上的任务可在另一个主机出错之前由其副版本成功完成。并且，系统中存在一个出错探测机制，可以提供出错信息，新任务不会被调度到已出错的主机上。系统还采用回收机制，即如果主版本成功完成，那么副版本的执行被中断，所占用的资源被回收。

[0080] 针对多个主机同时失效的情况，该失效模型可以通过下面两个步骤进行扩展。首先，将云中主机分为若干组；之后，在每个组内采用上述错误模型。可通过在各个组内采用本文所提出的容错机制，以解决多主机失效的情况。

[0081] 下文将给出采用PB模型实现的容错任务调度算法与任务后移策略。

[0082] 为方便分析，我们首先定义强主版本与弱主版本。

[0083] 定义1，强主版本：对任意一个任务主版本 如果其所在的主机 不出错，一定可以执行，则称 为强主版本。

[0084] 图2给出了强主版本的一个例子。如图2所示，ti是tj的父任务，即tj必须接收到ti传来的消息或数据才能开始执行，带箭头的虚线表示从主版本到副版本的消息传递关系及方向。由图2可知，只要 所在的主机h3不出错， 就能成功执行， 可以收到其父任务传来的消或数据。因此， 是一个强主版本。

[0085] 定义2，弱主版本：对任意一个任务主版本 如果其所在的主机 不出错，也不一定可以执行，则称 为弱主版本。

[0086] 图3给出了弱主版本的一个例子。如图3所示，假设 所在的主机h1在 完成之前出错，那么 将执行。但是由于 不能接收到 传来的消息或数据，尽管 所在的主机不出错， 仍不能执行。因此， 是一个弱主版本。

[0087] 根据定义1与定义2，我们有如下命题：

[0088] 命题1， 如果以下三种情况中有任意一种成立，则 是强主版本：

[0089] (1)

[0090] (2)

[0091] (3)

[0092] 否则， 是弱主版本。

[0093] 第一种情况可以直接根据定义1推出。第二种情况可根据图2推出。对于第三种情况，图4与图5给出了两个例子，其中主版本被分配到同一主机，副版本被分配到不同的主机。其中，图4为子任务主版本开始时间晚于父任务副版本的结束时间的情况，图5为子任务主版本开始时间早于父任务副版本的结束时间的情况。

[0094] 从图4与图5中，我们可以发现，不管 是否能够收到 的消息或数据， 都能收到 的消息或数据。根据定义1，若主机h1在 完成之前不出错，则 一定可以成功执行完成。因此 是强主版本。

[0095] 本实施例提出了一种虚拟化云中实时依赖任务动态容错调度与资源弹性供给策略，被称为FASARD。在FASARD中，当一组依赖任务到达时，该组内的所有任务都会被复制为两个版本，即主版本与副版本。FASARD根据先到先服务(First Come First Service)的规则依次调度各组依赖任务，在调度一个任务时，首先调度该任务的主版本，而后调度其副版本。考虑到一个任务超过截止期并不一定意味着整组任务无法在截止期前完成，当出现一个任务超过截止期时，FASARD尝试调度其子任务让其更早地完成。为了降低算法复杂性，若其子任务也无法在截止期前成功完成，那么系统拒绝该依赖任务组。一旦依赖任务组被拒绝，该任务组内所有已分配的资源都将被收回。

[0096] 具体地，FASARD的任务调度方法在算法1中以伪代码的形式示出。在算法1中，当一个依赖任务组到达系统时，FASARD首先根据任务组(DAG)的截止期估算各个任务的截止期。当一个任务没有父任务，或者父任务都已被调度时，先调度该任务的主版本，后调度副版本。只有当一个任务的主版本与副版本都被调度到截止期前完成时，该任务才可被视为已成功调度。如果一个任务没有被成功调度，那么系统将重新计算其子任务的最早可能开始时间并使该时间适当提前以消除该任务延时造成的影响。然而，如果其子任务再次超时，则拒绝该依赖任务组，并回收所有已分配的资源。

[0097]

[0098] 为了提高系统的可调度性与资源利用率，FASARD还会使用任务后移策略，根据一定的调度目标将任务的主版本与副版本插入到合适的时间槽内。任务后移策略可将一个任务应被插入到已调度任务之间的空闲时间槽内，能充分利用空闲资源，并尽早执行任务。

[0099] 定义7，后移时间冗余：一个已调度任务在不影响后续任务的执行时间以及执行状态(执行状态指主版本的强弱)的情况下，可向后移动的最长时间。

[0100] 对于主版本 其后移时间冗余 可按下式计算得到：

[0101]

[0102] 其中，sx表示同一个虚拟机上 后一个任务的开始时间。等式(6)右边第一项保证了任务 所有子任务能按时开始执行，第二项避免了对同一虚拟机上后续任务的影响。

[0103] 对于副版本 其后移时间冗余 可按下式计算得到：

[0104]

[0105]

[0106] 其中，等式(7)中 项确保了副版本的后移不会对子任务的开始执行时间与执行状态产生影响。等式(7)中第一种情况 表明 没有导致 成为弱主版本，因此， 不能大于 否则会导致 成为弱主版本。第二种情况
表明 导致 成为弱主版本，因此 可以在 之后完成，
保证了 可以在开始执行之前接收到 的结果数据。

[0107] 在得到各个已调度任务的后移时间冗余后，调度系统可以通过后移已调度任务来为新到达任务提供可行的时间插入槽，并且不对其他任务产生影响，从而有效地提高资源利用率与可调度性。

[0108] 综上所述，借助于本发明的上述技术方案，通过建立虚拟化云中实时容错模型代替传统的PB模型，实现容错的任务调度算法与任务后移策略，能够充分利用已调度任务之间的空闲时间槽，提高容错保障下的资源利用率与容错任务的可调度性。

[0109] 所属领域的普通技术人员应当理解：以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。