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

发布时间：2017-10-04 20:41

  本文关键词：有期限约束的多DAG共享资源的调度及公平费用优化方法

  更多相关文章： 多DAG调度 期限约束 工作流 费用优化 公平性

【摘要】：随着网格和云计算工作流技术的发展,近来关于多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).实验表明:这些方法及算法能够达到较好的性能.
【作者单位】： 北京工业大学计算机学院;新疆工程学院计算机工程系;
【关键词】： 多DAG调度 期限约束 工作流 费用优化 公平性
【基金】：北京市自然科学基金项目(4110001) 国家自然科学基金(61363004,61063042)资助~~
【分类号】：TP393.01
【正文快照】： 1引言很多的工作流任务及任务间的依赖约束关系都可由有向无环图DAG(Directed Acyclic Graph)来表示或者能够转化为DAG任务图.近年来,随着一些异构分布式计算环境下工作流系统技术研究和应用的发展(如网格、云计算或混合云计算工作流系统),作为这些工作流管理系统的关键技术之

【参考文献】

中国期刊全文数据库 前1条

1 田国忠;肖创柏;徐竹胜;肖霞;;异构分布式环境下多DAG工作流的混合调度策略[J];软件学报;2012年10期

【共引文献】

中国期刊全文数据库 前4条

1 刘丹琦;于炯;英昌甜;;云计算环境下多有向无环图工作流的节能调度算法[J];计算机应用;2013年09期

2 陈冬林;付敏;康艳芳;吴钟;;面向数据挖掘的云资源多实例组合购买决策研究[J];计算机应用研究;2013年11期

3 孙月;于炯;朱建波;;云计算中一种多DAG工作流可抢占式调度策略[J];计算机科学;2014年03期

4 谢国琪;李仁发;杨帆;黄卫红;;异构网络化汽车电子系统中多DAG离线任务调度[J];通信学报;2013年12期

中国硕士学位论文全文数据库 前3条

1 张丹闯;分布式环境下基于整体最优的资源分配研究[D];大连理工大学;2013年

2 刘莉;异构集群下并行任务的复制调度算法[D];武汉纺织大学;2013年

3 任丰玲;云环境下多DAG工作流的调度算法研究[D];新疆大学;2013年

【二级参考文献】

中国期刊全文数据库 前1条

1 苑迎春;李小平;王茜;王克俭;;成本约束的网格工作流时间优化方法[J];计算机研究与发展;2009年02期

【相似文献】

中国期刊全文数据库 前7条

1 薛桂香;赵政;马懋德;张世勇;;网格任务调度策略研究[J];微处理机;2007年03期

2 田国忠;于炯;刘洪伟;龚红翠;;基于排队论时间预测的网格工作流调度算法[J];石河子大学学报(自然科学版);2008年03期

3 王磊;夏阳;史强;文艾;;网格环境下基于QoS的协作型任务调度算法研究[J];小型微型计算机系统;2011年08期

4 刘红梅;;网格环境下任务调度算法的分析研究[J];电脑知识与技术;2007年24期

5 唐小勇;唐小勇;李肯立;PADUA Divid;;考虑通信竞争的任意处理机网络表调度算法[J];中国科学(F辑:信息科学);2009年07期

6 刘欣媛;张忠平;雷炳银;;网格环境下的静态启发式任务调度算法[J];广西师范大学学报(自然科学版);2007年04期

7 陈敏;李旺;;计算机网络中的故障定位技术研究[J];国外电子测量技术;2007年07期

中国硕士学位论文全文数据库 前7条

1 唐小勇;基于动态通信竞争的任意处理机网络表调度算法[D];湖南大学;2007年

2 朱玉丹;基于非独立任务优先级的网格调度算法的研究[D];大连理工大学;2010年

3 邢常振;基于虚拟计算环境的元调度器研究[D];中国石油大学;2010年

4 陈杰;面向网格的并行应用接口研究[D];中国石油大学;2011年

5 黄俊一;树形网格任务调度方法研究[D];东北大学;2008年

6 朱耀强;网格安全策略冲突检测及其消解机制的研究[D];长春工业大学;2010年

7 张智民;基于化学反应优化的网格任务调度研究[D];湖南大学;2012年

，

本文编号：972760