基于紧急程度的共享异构资源调度策略  

Heterogeneous processor scheduling strategy based on task urgency

作　　者：许荣斌[1,2,3] 刘鑫 程永亮[2] 石军 XU Rongbin 1,2,3 , LIU Xin 1,2 , CHEN Yongliang 2, SHI Jun 2(1.Key Laboratory of Intelligent Computing ＆ Signal Processing, Ministry of Education,Anhui University, Hefei 230039, China;2.School of Computer Science and Technology, Anhui University, Hefei 230601, China;3.Co-Innovation Center for Information Supply ＆ Assurance Technology, Anhui University, Hefei 230601, Chin)

机构地区：[1]安徽大学计算智能与信号处理教育部重点实验室,安徽合肥230039 [2]安徽大学计算机科学与技术学院,安徽合肥230601 [3]安徽大学信息保障技术协同创新中心,安徽合肥230601

出　　处：《计算机集成制造系统》2018年第7期1706-1713,共8页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61602005);教育部人文社科青年基金资助项目(14YJCZH169);安徽省自然科学基金资助项目(1608085MF130;1808085MF199);安徽大学博士启动基金资助项目~~

摘　　要：为了在有限的时间内处理完成大量业务流程,用有向无环图(DAG)进行建模,解决多DAG共享异构资源调度问题。提出结合相对严格程度和宽松度两种权衡DAG时序约束紧急程度的方法,衡量多DAG任务的优先级;基于紧急程度的异构最早完成时间(HEFT)改进算法,对具有时序约束的多个DAG任务进行调度;探测由于DAG调度紧急程度过高产生的过载现象,利用相关策略对任务进行选择性丢弃,在用户截止期限内完成DAG数量最大化的目标。通过仿真实验证明,所提算法对调度性能有极大的提高。To deal with large numbers of business processes in constrained time, Directed Acyclic Graph （DAG） was used for solving the scheduling problem of multiple DAGs shared on heterogeneous distributed resources. Two parameter association methods that included relative strictness and laxity were put forward to balance the priority of constraint DAG. An improved Heterogeneous Earliest Finish Time（HEFT） algorithm based on priority was given to schedule multiple DAGs with deadline constraint. The phenomenon of “overload” was detected due to high emergency degree of DAG scheduling which could be selective discarded with corresponding measures so as to maximize DAG before deadline. Simulations showed that the proposed algorithm could greatly improve the scheduling performance.

关 键 词：业务流程 有向无环图 任务优先级 截止期限 相对严格程度 HEFT算法 

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