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

为了进一步提高计算资源利用率,提出了工作流在分布式异构环境中的协同调度算法.首先,提出反向异构最早完成时间优先(heterogeneous earliest finish time,HEFH)调度策略,可以快速求出多个工作流中每个子任务的近似最晚开始时间和子期限,并基于最晚开始时间定义了当前任务相对宽松度的衡量指标,通过对比选出所有工作流中优先级最高的任务,在现有资源中寻找具有最早完成时间的时隙进行映射,并在资源不足时根据子期限及时判定出过饱和现象,合理丢弃用HEFT算法单独调度具有最小时隙的工作流,达到吞吐量最大化.结果表明:这种算法综合对比其他3种在吞吐量、浪费时隙率、公平度及时间复杂度方面有着较好性能.

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

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.