基于任务执行截止期限的有向无环图实时调度方法  

Real-time DAG scheduling method based on deadline of tasks

作　　者：许荣斌[1,2] 刘鑫[1] 杨壮壮 郭星[1,2] 谢莹[3] 吴建国[1] 

机构地区：[1]安徽大学计算机科学与技术学院,安徽合肥230061 [2]安徽大学信息保障技术协同创新中心,安徽合肥230061 [3]安徽大学计算机教学部,安徽合肥230061

出　　处：《计算机集成制造系统》2016年第2期455-464,共10页Computer Integrated Manufacturing Systems

基　　金：国家973计划资助项目(2015CB351705);国家自然科学基金资助项目(61472001;61300169;61300042);教育部人文社会科学研究青年基金资助项目(14YJCZH169);安徽省自然科学基金资助项目(1608085MF130)~~

摘　　要：为了将任务映射到多个资源中运行,以提高任务的执行效率进而有效管理和组织一个业务流程。在传统有向无环图模型的基础上,首先给出一种新的模型,将调度任务分解成若干串行和可并行调度部分;然后在新的有向无环图模型基础上提取任务调度的一条有效主路径,按照有效主路径将任务并行展开;随后基于任务的执行完成时间和执行截止期限提出一种拉伸调度策略,使任务在满足执行截止期限的同时,尽可能减少对处理器资源的占用,使其他任务能有效地进行调度。通过仿真实例证明所提方法具有很好的适用性。To map tasks into multiple resources for improving the execution efficiency,and to manage a business process effectively,a novel Directed Acyclic Graph（DAG）model was given based on the traditional DAG model,which divided the tasks into serial and parallel scheduling parts.A valid main path for task scheduling was extracted to make the task be expanded into parallel mode based on the novel DAG model.Based on completion time and deadline of the task,a stretch scheduling strategy was put forward to meet the deadline of tasks and reduce the occupation of resources,which made other tasks could be scheduled effectively.A simulation example was provided to prove the excellent feasibility of the proposed method.

关 键 词：有向无环图 实时调度 执行截止期限 有效主路径 并行调度 拉伸调度 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]