收录:
摘要:
Along with developing of the technology of Grid workflows and Cloud workflows, recent researches into the problem of scheduling multiple DAG (Directed Acyclic Graph) sharing resources have been making progress and have solved some problems. However, the problems of scheduling and cost optimization of multiple DAGs with deadline sharing finite heterogeneous resources need to be solved. To solve the problems, a new method of 'relative strictness' used in measuring urgency level of a DAG's deadline constraint is proposed first, and then, the MDRS algorithm is presented. The algorithm can not only reasonably determine the relationship of multiple DAGs' urgency levels, but also can deal with possible 'oversaturation' which may be caused by rigid deadline constraints of each DAG. Once the 'oversaturation' happens, the algorithm can drop as few DAGs as possible and try to schedule the rest of DAGs to maximize the throughput of DAG through the mechanism of 'Backtracking' combining with 'Stack'. Furthermore, in order to fairly minimize the total cost of these DAG while meeting a user-defined deadline, we propose another algorithm called CDVRS (Cost Decrease based on Variance of the Relative Strictness). Last experiments demonstrate that our algorithms and methods can improve the related performances.
关键词:
通讯作者信息:
电子邮件地址: