有期限约束的多DAG共享资源的调度及公平费用优化方法

• 作者: 田国忠 肖创柏 谢军奇
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 多DAG调度 期限约束 工作流 费用优化 公平性
• 年，卷（期）: 2014,（7）
• 所属期刊栏目: 系统软件与算法
• 页码范围: 1607-1619
• 页数: 13页
• 分类号: TP393
• 字数: 15044字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2014.1607

摘要

随着网格和云计算工作流技术的发展,近来关于多DAG(Directed Acyclic Graph)共享资源调度的研究取得了一些进展,然而,关于具有最晚完成期限约束的多DAG共享一组有限异构资源的调度及其费用最低化等问题还有待进一步研究和解决.针对这些问题,文中首先提出了衡量DAG期限紧急水平的“相对严格程度”的新方法,并在此基础上提出了基于相对严格程度的调度算法MDRS (Scheduling for Multi-DAGs with Deadline based on Relative Stritness).该算法不仅能够合理处理多个DAG之间调度的紧急水平关系,也能对由于DAG期限过于严格而可能产生的“过饱和”情况进行探测和处理.一旦遇到“过饱和”情况,则采用“堆栈”与“调度回溯”相结合的机制尽可能少地丢弃其中的DAG,从而达到DAG吞吐量最大化调度目标.在MDRS算法的基础上,为了满足各DAG期限内完成约束条件,并尽可能公平地降低多个DAG执行的费用,又提出了基于单位相对严格程度变化量的费用降低率最大化方法的费用优化算法CDVRS (Cost Decrease based on Variance of the Relative Strictness).实验表明:这些方法及算法能够达到较好的性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	肖创柏	北京工业大学计算机学院	84	661	12.0	24.0
2	田国忠	北京工业大学计算机学院	7	106	6.0	7.0
6	谢军奇	北京工业大学计算机学院	2	21	2.0	2.0