共享有限资源的有期限约束多工作流吞吐量最大化调度方法  

Throughput Maximization Scheduling Method for Multiple Workflows With Deadlines Sharing Finite Resources

作　　者：徐秀杰[1,2] 肖创柏[1] 田国忠[3] 孙婷[1] 

机构地区：[1]北京工业大学计算机学院,北京100124 [2]山东建筑大学管理工程学院,济南370101 [3]常州工学院计算机信息工程系,江苏常州213002

出　　处：《北京工业大学学报》2017年第3期376-385,共10页Journal of Beijing University of Technology

基　　金：国家自然科学基金资助项目(61501008;61363004);北京市自然科学基金资助项目(4162007)

摘　　要：为了进一步提高计算资源利用率,提出了工作流在分布式异构环境中的协同调度算法.首先,提出反向异构最早完成时间优先(heterogeneous earliest finish time,HEFH)调度策略,可以快速求出多个工作流中每个子任务的近似最晚开始时间和子期限,并基于最晚开始时间定义了当前任务相对宽松度的衡量指标,通过对比选出所有工作流中优先级最高的任务,在现有资源中寻找具有最早完成时间的时隙进行映射,并在资源不足时根据子期限及时判定出过饱和现象,合理丢弃用HEFT算法单独调度具有最小时隙的工作流,达到吞吐量最大化.结果表明:这种算法综合对比其他3种在吞吐量、浪费时隙率、公平度及时间复杂度方面有着较好性能.An algorithm on concurrent scheduling multiple complex workflows sharing the distributed heterogeneous resources was proposed to effectively improve the utilization.First,a reverse heterogeneous earliest finish time(HEFT) scheduling policy was proposed,which can quickly get the latest start time(LST) and sub-deadline for each task.Based on LST,a new relative loose degree metrics was defined for all the highest priority tasks in each workflow.By comparing them,the current task to be scheduled was selected and then mapped to the slot with the earliest finish time in all resources.If the resources were not enough,oversaturated workflows can be rapidly determined in accordance with sub-deadline,and such workflow scheduled alone by HEFT algorithm with the minimum idle slot time is reasonably discarded to maximize workflows throughput.Experimental results show that this algorithm has better comprehensive performance about throughput,waste time slot,fairness and time complexity than the other three algorithms.

关 键 词：多工作流调度 任务最晚开始时间 相对宽松度 吞吐量 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP338.8[自动化与计算机技术—计算机科学与技术]