(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210534598.7 (22)申请日 2022.05.17 (71)申请人 南京邮电大 学 地址 210012 江苏省南京市栖霞区文苑路9 号 (72)发明人 江凌云　刘洋睿　宋程豪　杨乾龙　 (74)专利代理 机构 南京纵横知识产权代理有限 公司 32224 专利代理师 刘艳艳 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/455(2006.01) G06F 9/50(2006.01) (54)发明名称 基于动态资源选择策略的微服务工作流调 度方法及装置 (57)摘要 本发明公开了一种基于动态资源选择策略 的微服务工作流调度方法。 该方法包括： 对微服 务工作流进行预处理， 获得工作流中各个任务的 子截止期参数以及排序优先级； 利用动态资源选 择策略为每一个微服务任务选择最合适的虚拟 机实例， 通过综合考虑所使用的虚拟机实例的单 价以及使用数量完成微服务工作流的调度， 获得 任务执行的最优资源， 并在此基础上更新任务状 态以及虚拟 机实例的资源向量。 该方法解决了 现 有微服务工作流调度方法中因不合理的资源选 择策略所导 致的调度成本过高的问题。 权利要求书3页 说明书10页 附图3页 CN 115033357 A 2022.09.09 CN 115033357 A 1.一种微 服务工作流调度方法， 其特 征在于， 包括： 获取输入的工作流应用信息； 对工作流应用信 息进行预处理， 得到工作流中各个微服务任务的子截止期以及调度优 先级， 并将此时的就 绪任务按照调度优先级放入到就 绪队列之中； 从就绪队列中依次取出就绪任务， 在保证资源需求方面和任务子截止期的限制下， 为 任务寻找可用的资源虚拟机实例， 并存入可以虚拟机实例集合中； 通过动态资源选择策略 在虚拟机实例可用集合中为任务选择合适的虚拟机实例， 并将任务放置到虚拟机实例上执 行， 得到任务的真实执行时间； 响应于任务分配完成， 使用任务的真实执行时间来代替预 处 理过程中使用的平均执行时间， 通过在线调整过程对这个任务的后续任务的参数进行更 新， 并将由于此任务完成所产生的新 就绪任务放置到就绪队列之中； 响应于就 绪队列为空， 调度完成。 2.根据权利要求1所述的微服务工作流调度方法， 其特征在于， 所述对工作流应用信 息 进行预处理， 包括： 将用户输入的工作流应用转换成有向无环图的形式， 并将各个任务的平均 执行时间以 及有依赖关系的任务之间的数据传输时间填入有向无环图中； 使用任务的平均执 行时间代替实际执 行时间， 计算各个任务的最 早开始时间； 通过任务的最早开始时间以及任务之间的数据传输时间来计算任务的升秩， 并计算出 任务的子截止期； 将就绪任务的放入到就绪队列中， 通过得到的子截止期参数计算就绪任务的调度优先 级。 3.根据权利要求2所述的微服务工作流调度方法， 其特征在于， 所述将用户输入的工作 流应用转换成有向无环图的形式， 包括： 工作流模型可以用一个有向无环图DAG来表示， DAG＝(T,E)； T＝{t1,t2,…,tn}是有向 无环图中节 点的集合， 每一个节点都代表一个计算任务； E是DAG中边的集合， 任务之间的数 据依赖关系由相应节点的边 eij来进行表示， eij＝{ti,tj}代表了任务ti和任务tj之间的依赖 关系， 即任务tj必须在任务ti完成之后方可执行， 此时任务ti被称作任务tj的直接前驱任 务， 而任务tj被称作任务ti的直接后继任务； 如果任务之间存在数据传输， 在边eij上加上 datai,j属性， 表示任务之间 需要传输的数据量； 此时， 对任务ti而言， 只有当ti的直接前驱任 务集合pred(ti)中所有的任务都执行完， 且数据都被传输完之后， ti才可以开始执行； 所有 微服务任务都事先给定执行任务中所需要的计算资源， 用需求资源向量 表 示， 其中m是计算资源种类的数目。 4.根据权利要求2所述的微服务工作流调度方法， 其特征在于， 所述使用任务的平均 执 行时间代替实际执 行时间， 计算各个任务的最 早开始时间， 包括： 任务的最 早开始时间定义如下： 其中， EST(ti)代表任务ti的最早开始时间， tentry表示有向无环图中的入 口任务， pred权　利　要　求　书 1/3 页 2 CN 115033357 A 2(ti)表示ti的直接前驱任务， ET(tk,vl)表示任务tk在虚拟机实例vl上的执行时间； TT(ti,tk) 来表示任务ti与任务tk间的数据 传输时间； 两个任务如果在同一个虚拟机实例上执行， 则它 们之间的数据传输时间为0； 否则， 数据传输时间为任务ti与任务tk间需要传输的数据量和 数据中心的平均带宽的比值； 采用任务在所有虚拟机实例上的平均执行时间AETi来替代ET (tk,vl)进行初始计算。 5.根据权利要求2所述的微服务工作流调度方法， 其特征在于， 所述通过任务的最早开 始时间以及任务之间的数据传输时间来计算任务的升秩， 并计算出任务的子截止期， 包括： 任务ti的升秩ran ku(ti)表示任务ti到出口任务texit之间的关键路径的长度， 定义如下： 其中ET(ti,vl)表示任务ti在虚拟机实例vl上的执行时间； TT(ti,tk)来表示任务ti与任 务tk间的数据传输时间； succ(ti)表示任务ti的后续任务集合； 对于出口任务texit， ranku (texit)＝0； 通过这个值， 递归的求出每一个任务的升秩； 通过升秩这个概念， 任务ti的子截 止期sdi的定义为： 其中D指的是用户提交的截止期， ET(ti,vl)表示任务ti在虚拟机实例vl上的执行时间， tentry指的是有向无环图中的入口任务。 6.根据权利要求2所述的微服务工作流调度方法， 其特征在于， 所述将就绪任务的放入 到就绪队列中， 通过 得到的子截止期参数计算 就绪任务的调度优先级， 包括： 就绪任务的定义为： 当一个任务的所有前驱任务都已经被分配到虚拟机实例上执行完 毕， 且所有数据都已经接 收， 该任务就被认为是就绪任务； 任务一旦成为就绪任务， 就会被 放入到就 绪队列； 计算出就 绪队列中每 个就绪任务的调度紧急度 其中， ui值表示就绪队列中就绪任 务的调度紧急度， sdi表示任务ti的子截止期， EST(ti) 代表任务ti的最早开始时间， ET(ti,vl)表示任务ti在虚拟机实例vl上的执行时间； ut(ti)表 示任务ti到出口任务texit之间的未调度的任务数。 7.根据权利要求1所述的微服务工作流调度方法， 其特征在于， 所述在保证资源需求方 面和任务子截止期的限制下， 为任务 寻找可用的资源虚拟机实例， 包括： 合适的虚拟机实例需要满足： 在容器生命周期内， 虚拟机的可用空闲资源一直都满足 任务的计算需求， 并且 任务的完成时间在子截止期之前； 即满足： EST(tcur)+ET(tcur,vl)≤sdcur 其中， 代表虚拟机实例总可用资源向量， 代表虚拟机实例在t时刻的可用资源权　利　要　求　书 2/3 页 3 CN 115033357 A 3