Fair multiple-workflow scheduling with different quality-of-service goals
Tóm tắt
Cloud schedulers that allocate resources exclusively to single workflows are not work-conserving as they may be forced to leave gaps in their schedules because of the precedence constraints in the workflows. Thus, they may lead to a waste of financial resources. This problem can be mitigated by multiple-workflow schedulers that share the leased cloud resources among multiple workflows or users by filling the gaps left by one workflow with the tasks of other workflows. This solution may even work when users have different performance objectives for their workflows, such as budgets and deadlines. As an additional requirement, we want the scheduler to be fair to all workflows regardless of their performance objectives. In this paper, we propose a multiple-workflow scheduler that is able to target different quality of service goals for different workflows and that considers fairness among different users. To this aim, we propose an unfairness metric and four workflow selection policies. We prove that the resource selection that decides based on a task’s sub-budget, sub-deadline, finish time, and cost on different resources is selecting the best resource based on the given information, while using the smallest number of calculations. Simulations show that there is a trade-off between overall cost, makespan, and fairness. We conclude that the best workflow selection policy to reduce unfairness is the direct policy, which explicitly selects the workflow that minimizes the value of the proposed unfairness metric in each round.
Tài liệu tham khảo
Ullman JD (1975) Np-complete scheduling problems. J Comput Syst Sci 10(3):384–393
Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17(2):416–429
Topcuoglu H, Hariri S (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13:260–274. https://doi.org/10.1109/71.993206
Abrishami S, Naghibzadeh M, Epema DHJ (2010) Cost-driven scheduling of grid workflows using partial critical paths. In: Proceedings of the 11th IEEE/ACM International Conference on Grid Computing (Grid2010)
Bittencourt LF, Madeira ERM (2011) HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds. J Internet Serv Appl 2(3):207–227
Hirales-Carbajal A, Tchernykh A, Yahyapour R, González-García JL, Röblitz T, Ramírez-Alcaraz JM (2012) Multiple workflow scheduling strategies with user run time estimates on a grid. J Grid Comput 10:325–346. https://doi.org/10.1007/s10723-012-9215-6
Yu Z, Shi W (2008) A planner-guided scheduling strategy for multiple workflow applications. In: Proceedings of the International Conference on Parallel Processing Workshops, pp 1–8. https://doi.org/10.1109/ICPP-W.2008.10
Zhao H, Sakellariou R (2006) Scheduling multiple DAGs onto heterogeneous systems. In: 20th International Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. IEEE, p 14
Bittencourt LF, Madeira ERM (2010) Towards the scheduling of multiple workflows on computational grids. J Grid Comput 8:419–441
Naghibzadeh M (2016) Modeling and scheduling hybrid workflows of tasks and task interaction graphs on the cloud. Future Gen Comput Syst 65:33–45
Zheng W, Sakellariou R (2012) Budget-deadline constrained workflow planning for admission control in market-oriented environments. In: Economics of Grids, Clouds, Systems, and Services, Springer, pp 105–119
Bittencourt LF, Madeira ERM (2008) A performance-oriented adaptive scheduler for dependent tasks on grids. In: Concurrency Computation Practice and Experience, vol 20, pp 1029–1049. https://doi.org/10.1002/cpe.1282
Buyya R, Pandey S, Vecchiola C (2009) Cloudbus toolkit for market-oriented cloud computing. In: Cloud Computing. Springer, pp 24–44
Bessai K, Youcef S, Oulamara A, Godart C, Nurcan S (2012) Resources allocation and scheduling approaches for business process applications in cloud contexts. In: 2012 IEEE 4th International Conference on Cloud Computing Technology and Science (CloudCom), pp 496–503. https://doi.org/10.1109/CloudCom.2012.6427530
Abrishami S, Naghibzadeh M, Epema DH (2013) Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Gen Comput Syst 29(1):158–169
Bittencourt LF, Madeira ER, Cicerre FR, Buzato LE (2005) A path clustering heuristic for scheduling task graphs onto a grid. In: 3rd International Workshop on Middleware for Grid Computing (MGC05)
Bharathi S, Chervenak A, Deelman E, Mehta G, Su M-H, Vahi K (2008) Characterization of scientific workflows. In: Third Workshop on Workflows in Support of Large-scale Science, 2008. WORKS 2008. IEEE, pp 1–10
Juve G, Chervenak A, Deelman E, Bharathi S, Mehta G, Vahi K (2013) Characterizing and profiling scientific workflows. Future Gen Comput Syst 29(3):682–692
Livny J (2012) Bioinformatic discovery of bacterial regulatory rnas using sipht. Methods and Protocols, Bacterial Regulatory RNA, pp 3–14
Berriman GB, Deelman E, Good JC, Jacob JC, Katz DS, Kesselman C, Laity AC, Prince TA, Singh G, Su M-H (2004) Montage: a grid-enabled engine for delivering custom science-grade mosaics on demand, vol 5493, pp 221–232. https://doi.org/10.1117/12.550551
Abramovici A, Althouse W, Drever R, Gürsel Y, Kawamura S, Raab F, Shoemaker D, Sievers L, Spero R, Thorne K (1992) Ligo: the laser interferometer gravitational-wave observatory. Science (New York, NY) 256(5055):325–333
LIGO Project. Ligo—laser interferometer gravitational wave observatory. http://www.ligo.caltech.edu/. Accessed 30 Mar 2016
Maechling P, Deelman E, Zhao L, Graves R, Mehta G, Gupta N, Mehringer J, Kesselman C, Callaghan S, Okaya D, et al (2007) Scec cybershake workflowsautomating probabilistic seismic hazard analysis calculations. In: Workflows for e-Science. Springer, pp 143–163
da Silva RF, Chen W, Juve G, Vahi K, Deelman E (2014) Community resources for enabling research in distributed scientific workflows. In: 2014 IEEE 10th International Conference on e-Science (e-Science), vol 1. IEEE, pp 177–184
Ilyushkin A, Ghit B, Epema D (2015) Scheduling workloads of workflows with unknown task runtimes. In: 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid). IEEE, pp 606–616
Calheiros RN, Buyya R (2012) Cost-effective provisioning and scheduling of deadline-constrained applications in hybrid clouds. In: Web Information Systems Engineering-WISE Springer, pp 171–184
Garg SK, Yeo CS, Anandasivam A, Buyya R (2011) Environment-conscious scheduling of hpc applications on distributed cloud-oriented data centers. J Parallel Distrib Comput 71(6):732–749