一种移动边缘计算环境下面向工作流的容错调度方法   0    0

本发明公开了一种移动边缘计算环境下面向工作流调度的容错方法。本发明步骤：构建移动边缘环境下容错调度框架；建立故障模型；计算复制延迟执行机制和检查点延迟执行机制所需的计算资源；当服务工作流任务到达时，首先将任务放在工作流队列中并且按照先到先服务策略执行，容器调度器判断工作流是否执行执行；选择最佳的容错策略，如果找不到任何调度方案来满足任务的子完工时间，则拒绝执行整个工作流应用；6、如果步骤5没有足够虚拟机执行任务，则采用资源扩展策略新开虚拟机满足资源要求；步骤7、当工作流完成时，则通过资源缩减策略提高资源利用率。本发明在满足工作流的时间约束和存在VM故障情况下使得MEC的资源利用率最大化。

1.一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于包括如下步骤：
步骤1、构建移动边缘环境下容错调度框架；
步骤2、建立故障模型；
通过任务的服务时间和故障到达率计算虚拟机的可靠性；
步骤3、计算复制延迟执行机制所需计算资源；
复制延迟执行机制是通过复制方法产生多个任务副本，然后并行执行这些副本；任务副本分为主副本和备份副本，主副本的执行结果分为成功和失败，通过计算概率统计整个的复制延迟执行的所需的期望计算资源；
步骤4、计算检查点延迟执行机制所需的计算资源；
检查点延迟执行机制的任务执行时间主要由数据接受时间、块执行时间、检查点时间、虚拟机恢复时间和数据传输时间组成；通过计算任务的执行时间得到采用该机制的计算资源；
步骤5、当一批服务工作流任务到达时，首先将任务放在工作流队列中并且按照先到先服务策略执行，容器调度器判断工作流是否执行；根据步骤3和步骤4选择最佳的容错策略，如果找不到任何调度方案来满足任务的子完工时间，则拒绝执行整个工作流应用；
步骤6、如果步骤5没有足够虚拟机(VM)执行任务，则采用资源扩展策略新开虚拟机满足资源要求；
步骤7、当工作流完成时，则通过资源缩减策略提高资源利用率；
检查点延迟执行机制是指将任务任意地分割成独立的块，然后在成功执行每个块之后记录状态；如果在块执行过程中VM发生了故障，则需要重新执行块；任务ti的执行时间为C，Cl表示每个块的执行时间；因此可得公式(17)；在发生VM故障情况下具有检查点方法的任务ti的服务时间表示如公式(18)所示；
其中，Tchec和Treco分别表示执行检查点和VM恢复所需的时间；参数nl表示块Cl执行的次数，此外nl≥1，因为每个块必须至少执行一次。

2.根据权利要求1所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于
当一批服务工作流任务到达时，首先放入到工作流队列中并且按照先到先服务策略执行；然后容器调度器分析工作流的结构，并将截止时间分成若干个子完工时间；子完工时间表示分配给任务的执行时间，首先将服务工作流中任务映射到最大计算单元CU(K)执行；然后根据下面公式计算任务ti的最小执行时间；
假设工作流的任务都在VM(K)上执行，公式(1)能够计算得到整个工作流的最短完工时间 通常服务工作流的指定期限TDL必须大于等于最短完工时间，即 因此
任务ti的子完工时间定义如公式(2)所示，由公式(2)可知如果每个任务的执行时间小于其子完工时间，那么整个工作流的完工时间将不会超过截止时间；

3.根据权利要求2所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于
VM在执行服务工作流任务时可能发生故障导致任务执行失败；通过使用可用的故障信号和测试用例能够立即检测VM的故障；假设VM在任务执行过程中遇到多个故障，通过应用恢复机制在很短时间内恢复执行；VM的可靠性Pvm(T)根据下面的公式计算，其中T表示一个任务服务时间，λvm表示VM故障的到达率且服从泊松分布；
Pvm(T)＝exp(‑λvm·T)         (3)。

4.根据权利要求3所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于
所述的计算复制延迟执行机制是指通过复制方法产生多个任务副本然后并行执行任务副本；假设复制系数为∈，∈是一个预设的很小的正整数，从而得到公式(4)不等式，其中N(ti)表示任务ti的副本的个数；公式(4)表示在采用复制技术情况下Nrepl(ti)个副本在VM上执行，成功的概率至少为1‑∈；
将N(ti)个任务副本划分为主副本和备份副本，其中主副本优先执行，然后执行备份副本，主副本和备份副本在不同的VM上执行，主副本的数量根据公式(5)计算，备份副本数量Nb(ti)可由公式(6)计算得到；
Nb(ti)＝N(ti)‑Np(ti)        (6)
所述的计算复制延迟执行机制有两种延迟执行的情况；第一种情况：当Tserv(ti，VM(k))≤TsubM(ti)＜2·Tserv(ti，VM(k))时，备份副本在主副本执行过程中开始执行，如果有一个主副本执行成功，备份副本则立即停止执行；第二种情况：当TsubM(ti)≥2·Tserv(ti，VM(k))时，如果所有的主副本执行失败，备份副本才开始执行。

5.根据权利要求4所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于在第一种情况下计算复制延迟执行机制(R‑CE)的具体实现如下：
当Tserv(ti，VM(k))≤TsubM(ti)＜2·Tserv(ti，VM(k))，主副本的执行结果分为成功和失败，接下来计算这两种情况的计算资源；假设至少有一个主副本执行成功，发生的概率为公式(7)；在这种情况下，备份副本只执行一段时间就被中断执行，R‑CE的计算资源如公式(8)；
假设所有主副本都执行失败；发生概率如公式(9)所示，这时所有备份副本都需要执行，在这种情况下计算资源通过公式(10)得到；
根据公式(7)、(8)、(9)和(10)，第一种情况下所需要的计算资源如下：

6.根据权利要求4或5所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于在第二种情况下计算复制延迟执行机制(R‑CE)的具体实现如下：
当TsubM(ti)≥2·Tserv(ti，VM(k))，主副本的执行结果也有两种情况，假设至少有一个主副本执行成功，那么发生的概率为公式(12)；同第一种情况不同，第二种情况的备份副本不需要全部执行，根据公式(13)得到计算资源；
21 11
P ＝P           (12)
假设所有主副本都执行失败，概率如公式(14)所示，这时所有备份副本都需要执行，在这种情况计算资源通过公式(15)得到；
22 12
P ＝P           (14)
因此第二种情况下所需要的总计算资源表示如下：

7.根据权利要求6所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于每个任务的执行时间分为数据接受时间、块执行时间、检查点时间、VM恢复时间和数据传输时间；如果在任务执行过程没有发生VM故障，则VM恢复时间为0；T(C|τ)用来测量成功执行C个单元的工作量所需时间的随机变量；C1表示第一块的大小，从而得到如下递归方程；
任务的期望服务时间如公式(20)所示，此外根据上述理论分析，计算检查点延迟执行机制(C‑DE机制)所需的预期计算资源根据公式(21)计算；
*
Tserv(ti，VM(k))＝E{T(C)}+Trece(ti)+Ttrans(ti)   (20)

8.根据权利要求7所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于如果任务的主副本或者备份副本无法映射到现有的VM，则资源扩展策略需要从现有活动主机创建一组新的VM来执行多个任务副本；对于给定任务ti，首先根据R‑DE机制和C‑DE机制选择最佳VM类型，然后计算最小预期计算资源需求，最后从现有活动主机创建新的VM实例；如果没有满足VM分配要求的主机，则需打开新的主机。

9.根据权利要求7或8所述的一种移动边缘计算环境下面向工作流调度的容错方法，其特征在于如果虚拟机有一小段时间空闲时，系统将通过动态电压频率调整技术降低CPU频率来节省计算资源和能耗；如果VM在长时间内处于空闲状态，则会关闭VM以提高资源利用率；此外，如果主副本执行成功，那么备份副本会被回收，回收的VM将用来执行其他副本任务或者降低CPU频率又或者会被回收。