(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211390940.7 (22)申请日 2022.11.07 (71)申请人 中山大学 地址 510275 广东省广州市海珠区新港西 路135号 (72)发明人 付青　苏奕星　陈一山　杨航　 (74)专利代理 机构 广州粤高专利商标代理有限 公司 44102 专利代理师 刘俊 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/455(2006.01) G06F 9/50(2006.01) (54)发明名称 基于任务分层与回填最早完成时间的任务 调度方法及系统 (57)摘要 本发明提出一种基于任务分层与回填最早 完成时间的任务调度方法及系统， 涉及变电站任 务调度的技术领域， 通过构建DAG任务图， 将变电 站任务划分为关联任务和独立任务， 将关联任务 分层归类， 形成若干个关联任务层后， 采用 upward rank的计算方式匹配DAG任务图拓扑排 序的顺序， 对各层内的任务进行层内排序， 最后 将各项独立任务分别填入关联任务各层之间的 空闲时间段中， 按照各任务层从上到下、 层内优 先级从大到小的顺序执行关联任务及独立任务， 将具有严格先后顺序的变电站任务进行分层， 考 虑变电站任务执行顺序的同时， 充分利用了空闲 运算资源， 缩短了整体调度时长 。 权利要求书2页 说明书6页 附图3页 CN 115509724 A 2022.12.23 CN 115509724 A 1.一种基于任务分层与回填 最早完成时间的任务调度方法， 其特 征在于， 包括： S1.划分变电站多机任务中的关联任务及独立任务； S2.将关联任务分层归类， 形成若干个关联任务层； S3.计算已分层归类的关联任务的优先级， 基于关联任务的优先级对各层内的任务的 执行次序进行层内排序； S4.将各项独立任务分别填入关联任务各层之间的空 闲时间段中； S5.按照各任务层从上到下、 层内优先级从大到小的顺序执 行关联任务及独立任务。 2.根据权利要求1所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 步骤S1包括以下步骤： S11.将变电站的每一个任务作为一个任务节点， 以任务节点之间的执行序列约束作为 有向弧， 构建DAG任务图， 根据任务节点 ‑任务节点之间的有向弧联系， 得到操作票作业的关 联任务； S12.将与关联任务中的任何一个任务节点都不存在父类或子类关系的任务节点对应 的任务划分为独立任务。 3.根据权利要求2所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 步骤S2包括以下步骤： S21.遍历整个DAG任务图； S22.根据DAG任务图中的入口任务节点至出口任务节点的顺序， 对关联任务进行分层， 使不同层的关联任务无任何关联关系； S23.将每层的关联任务构建一个任务集， 将各层的任务集共同形成关联任务集TI， I＝ 1,2,…,n， 其中n表示任务 集的层数。 4.根据权利要求3所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 步骤S3包括以下步骤： S31.获取 出DAG任务图中每 个任务的平均计算 开销 和平均通信开销 S32.计算任务在不同CPU负载的虚拟机上的执 行时间的方差S2， 方差计算公式如下： 其中， 表示任务i在不同CPU负载的虚拟机上的开销， m表示虚拟机的数量， 方差S2越 大任务的执 行优先级越高； S33.基于 和S2， 采用upwar d rank的计算方式匹配DAG任务图拓扑排序的顺序， 得到每个已分层归类的关联任务的ran ku的值； S34.基于ran ku的值， 对已分层归类的关联任务进行层内的逆序排序。 5.根据权利要求4所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 在步骤S3 3中， upward  rank的定义为： 其中， ti和tj表示关联任务 集中的任意两个任务， suc c(ti)表示任务 i的所有后继任务； upward rank从出口节点任务向上依次迭代产 生， 当任务为DAG任务图中出口节点任务权　利　要　求　书 1/2 页 2 CN 115509724 A 2texit时， 其ran ku的值为： 其中， 为出口节点任务texit的平均计算 开销。 6.根据权利要求5所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 步骤S4包括以下步骤： S41.获取 各项独立任务的预计完成时间； S42.构建独立任务集I{t1,t2,t3…ts}， 其中， s为独立任务的数量， 将独立任务集I中的 任务按预计完成时间降序排列； S43.初始化p＝1； S44.获取独立任务tp在虚拟机中的处 理时间； S45.确定关联任务 集Tk和Tk+1两任务集间的空 闲时间段Gk： S46.设独立任务tp在虚拟机q中的处理时间为T(p,q)， 若T(p,q)>Gk， 则该空闲时间段不符 合插入条件， 令k的值增 加1， 返回步骤S45， 其中k≤n； 若T(p,q)≤Gk， 则该空闲时间段符合插入条件， 将独立任务tp插入空闲时间段Gk中； 将被 插入的独立任务tp从任务列表中删除， 同时更新空 闲时间段 大小； S47.令p的值增加1， 判断p是否大于s， 若是， 则所有独立任务都已被回填； 否则， 令k＝ 1， 返回步骤S4 4。 7.根据权利要求6所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 在步骤S41中， 基于独立任务的PE和MI值等参数， 通过MI和虚拟机上的处理器的MIPS 值获得各项独立任务的预计完成时间。 8.根据权利要求6所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 在步骤S4 4中， 获取独立任务tp在虚拟机中的处 理时间， 计算公式如下： 其中， p表示独立任务的编号， q表示虚拟机编号， T(p,q)代表独立任务tp在虚拟机q中的 执行时间， vmips表示虚拟机的计算能力系数。 9.根据权利要求8所述的基于任务分层与回填最早完成时间的任务调度方法， 其特征 在于， 在步骤S45中， 更新空 闲时间段 大小， 更新公式为： 其中， 分别表示时间段Gk的开始时间和结束时间。 10.一种基于任务分层与回填最早完成时间的任务调度方法的计算机系统， 其特征在 于， 包括： DAG构图模块， 用于划分变电站多机任务中的关联任务及独立任务； 关联任务分层模块， 用于将关联任务分层归类， 形成若干个关联任务层； 排序模块， 用于计算已分层归类的关联任务的优先级， 基于关联任务的优先级对各层 内的任务的执 行次序进行层内排序； 独立任务回填模块， 用于将各项独立任务分 别填入关联任务各层之间的空闲时间段中。权　利　要　求　书 2/2 页 3 CN 115509724 A 3