基于QoS和能耗协同优化的实时工作流调度方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113722076A(43)申请公布日2021.11.30(21)申请号202111274602.2(22)申请日2021.10.29(71)申请人华南理工大学地址510640广东省广州市天河区五山路381号(72)发明人刘发贵梁桥友(74)专利代理机构广州粤高专利商标代理有限公司44102代理人周春丽(51)Int.Cl.G06F9/48(2006.01)G06F9/50(2006.01)权利要求书4页说明书10页附图1页(54)发明名称基于QoS和能耗协同优化的实时工作流调度方法(57)摘要本发明公开了一种基于QoS和能耗协同优化的实时工作流调度方法。所述方法包括以下步骤：在随机到达的多个工作流中，计算工作流中各个任务的子截止时间，子截止时间越小的任务的优先级越高，每次调度选择优先级最高的任务进行调度；根据选取的任务，通过计算时间‑能耗效率因子，选择目标虚拟机，完成任务到虚拟机的映射。本发明采用任务子截止时间作为任务优先级高低的依据，并提出时间‑能耗权衡因子作为虚拟机选择依据，既解决了QoS中任务时间约束的问题，也保证了任务随机到达的实时应答，同时也兼顾了能耗问题。CN113722076ACN113722076A权利要求书1/4页1.基于QoS和能耗协同优化的实时工作流调度方法，其特征在于，包括以下步骤：S1、在随机到达的多个工作流中，计算工作流中各个任务的子截止时间，子截止时间越小的任务的优先级越高，每次调度选择优先级最高的任务进行调度；S2、根据从步骤S1中选取的任务，通过计算时间‑能耗效率因子，选择目标虚拟机，完成任务到虚拟机的映射；具体包括如下步骤：S2.1、构建系统能耗模型，采用基于系统整体构建任务能耗模型；所述系统能耗模型中，目标环境系统为云计算数据中心，采用表示，其中H表示M个物理主机的集合；VM表示N个虚拟机的集合，，虚拟机运行于物理主机上，如果第个虚拟机运行在第个物理主机上，采用表示；针对物理主机能耗模型，根据CPU利用率，采用线性功耗模型，其计算如下：(1)其中，和分别表示第个物理主机的空闲功耗和满载功耗，为第个物理主机的CPU利用率，是第个物理主机在CPU利用率为时的功耗；由于工作负载的可变性，CPU的利用率可能会随着时间的推移而改变，因此CPU利用率是关于时间的函数，可以表示为，是时间变量，因此，物理主机的总能耗，定义为一段时间内的功率消耗的积分，如下表示：(2)其中，x0、x1分别表示一段时间的起点和终点；是第个物理主机的总能耗，同时的计算方式如下：（3）其中，为第个虚拟机执行任务时的CPU利用率，由于采用的是线性功耗模型，结合公式(1)和(3)，第个虚拟机执行任务时的平均功耗为：（4）S2.2、将从步骤S1中得到的任务，使用步骤S2.1中的任务能耗模型，计算时间‑能耗效率权衡因子，选择可调度的目标虚拟机，完成任务到虚拟机的映射。2.根据权利要求1所述的基于QoS和能耗协同优化的实时工作流调度方法，其特征在于，步骤S1包括以下步骤：S1.1、采用有向无环图表示工作流，并采用自底向上的方式对工作流进行分层；S1.2、根据最早开始时间和最早完工时间计算工作流中各个任务的子截止时间,子截止时间越小，该任务的优先级越高。3.根据权利要求2所述的基于QoS和能耗协同优化的实时工作流调度方法，其特征在2CN113722076A权利要求书2/4页于，步骤S1.1中，所述工作流包括若干个任务，工作流中的任务具有数据依赖，在任务调度中，采用有向无环图来表示工作流；有向无环图用一个二元组来表示，其中，T表示所有节点组成的集合，，每个节点表示工作流中的一个任务，；是节点之间有向边的集合，表示工作流中各个任务之间的依赖关系，即对，任务执行完成后任务才能开始执行，；表示在给定的工作流中，任务的直接前驱任务集合，也称任务的父任务集合；表示在给定的工作流中，任务的直接后继任务集合，也称任务的子任务集合；其中，表示工作流的入口任务，满足表示工作流的出口任务，满足；有向无环图中的每一条边的权值表示处于该条边两端的任务和任务之间的通信时间；由于通信时间需要任务和任务被执行后才能获得，因此采用平均通信代价来表示任务间的通信时间；任务和任务之间的平均通信时间具体如下：(5)其中，表示任务发给任务的数据总量,为物理机之间的平均带宽即平均数据传输速率；当任务和任务被分配到同一个物理机上时，=0。4.根据权利要求3所述的基于QoS和能耗协同优化的实时工作流调度方法，其特征在于，对于任意的工作流，根据所属的各个任务的平行性将工作流分层，以达到同一层的任务不具有依赖关系；同一层的任务共享层值，任务的层值表示着从出口任务到该任务的最长路径，用表示任务对应的层值，对于出口任