Computer Science ›› 2014, Vol. 41 ›› Issue (3): 145-148.

Previous Articles     Next Articles

Preemptive Scheduling for Multiple DAGs in Cloud Computing

SUN Yue,YU Jiong and ZHU Jian-bo   

  • Online:2018-11-14 Published:2018-11-14

Abstract: There are different QoS demands on DAG workflow for different users.Three layers multiple DAG dynamic scheduling model was proposed to solve the fairness and the utilization rate problems.In the algorithm,priority division is in the light of the different QoS demand of DAG,and the high priority DAG gives preference to the resources.The same priority DAGs can preempt the resources according to the slowdown with the heuristic information,improving the fairness of the workflow scheduling.In the circumstances of high priority DAGs giving preference to resources,the resource utilization rate must be considered.Modified Backfill algorithm was introduced based on threshold,improving the resources utilization rate with the guarantee of high priority job in preference to resources.

Key words: Multiple DAGs scheduling,Priority,Preemptive,Fairness,Backfill

[1] Gil Y,et al.Examining the Challenges of Scientific Workflows[J].Computer,2007,40(12):24-32
[2] 黄震春.SCO-GADL:一种用于科学计算的网格工作流描述语言[J].计算机科学,2011,8(6):28-30,4
[3] 桑莉莉.一种网格工作流动态调度算法[J].计算机系统应用,2009,7:45-47
[4] Yu Jia,Buyya R.A Taxonomy of Workflow Management Systems for Grid Computing [J].SIGMOD Record,2005,34(3):44-49
[5] Sakellariou R,Zhao He-nan.A Low-Cost Rescheduling Policyfor Efficient Mapping of Workflows on Grid Systems[J].Scientific Programming,2004,2(4):253-262 (下转第168页)(上接第148页)
[6] Haluk T,Salim H,Wu M Y.Performance-effective and Low-complexity Task Scheduling for Heterogeneous Computing[J].Parallel and Distributed Systems,2002,13(3):260-274
[7] Gilbert C S,Edward A L.A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures[J].Parallel and Distributed Systems,1993,4(2):75-87
[8] Cao J W,Stephen A J,Sunhash S,et al.GridFlow:Workflow Management for Grid Computing[C]∥3rd IEEE International Symposium on Cluster Computing and the Grid.Tokyo,IEEE Computer Society,May 2003:198-205
[9] Berman F,et al.New Grid Scheduling and Rescheduling Methods in the GrADS Project[J].Parallel Programming,2005,33(2):209-229
[10] Hnig U,Schiffmann W.A Meta-algorithm for Scheduling Multiple DAGs in Homogeneous System Environments[C]∥ Parallel and Distributed Computing and Systems.Dallas,IEEE Computer Society,November 2006:147-152
[11] Zhao He-nan,Sakellariou R.Scheduling Multiple DAGs ontoHeterogeneous Systems[C]∥ 20th International Parallel and Distributed Processing Symp.Piscataway:IEEE,2006
[12] Yu Zhi-feng,Shi Wersong.A Planner-Guided Scheduling Strategy for Multiple Workflow Applications [C]∥International Conference on Parallel Processing,Portland,2008.IEEE Computer Society,September 2008:1-8
[13] 孔维梁,刘清堂,杨宗凯,等.基于动态QoS的Web服务组合[J].计算机科学,2012,39(2):268-272
[14] Amudha T,Dhibyaprabha T T.QoS Priority Based Scheduling Algorithm and Proposed Framework for Task Scheduling in a Grid Environment[C]∥International Conference on Recent Trends in Information Technology,Chennai,2011.IEEE,June 2011:650-655
[15] Ankur K,Soo-young L.A Stochastic Approach to EstimatingEarliest Start Times of Nodes for Scheduling DAGs on Heterogeneous Distributed Computing Systems [C]∥19th International Parallel and Distributed Processing Symposium,Denver,2005.IEEE Computer Society,April 2005:1530-2075
[16] Kwok Y,Ahmad I.On Multiple Processor Task Scheduling Using Efficient State Space Search Approaches[J].Parallel and Distributed Computing,2005,65(12):1515-1532
[17] 王万森.人工智能原理及其应用(第2版)[M].北京:电子工业出版社,2005:115-120
[18] 付云虹.基于backfill的并行计算作业调度算法研究[D].长沙:湖南大学,2007
[19] 田国忠,肖创柏,徐竹胜,等.异构分布式环境下多DAG工作流的混合调度策略[J].软件学报,2012,23(10):2720-2734

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!