A Predictive and Availability-Aware Job Scheduling Algorithm for Resource Management in Cloud
Keywords:
Job scheduler, heterogeneous system, resource availability, clone-based job modelingAbstract
To propose an efficient scheduling algorithm in a large distributed heterogeneous
environment like cloud, resource (CPU cycles, memory) requirement of jobs must be predicted prior
to the execution. An execution history can be maintained to store execution profile of all jobs executed
earlier on the given set of resources. A feedback guided job modelling scheme is proposed earlier [1] to
detect similarity between newly submitted job and previously executed jobs on that resource set. Based
on the similarity the new jobs are categorized as either an exact clone or near-miss clone or miss-clone
to the history jobs. However, in [2], it is shown that the actual resource consumption, and predicted
resource requirement may differ to a great extent, especially for the near-miss-clone and miss-clone jobs.
Furthermore, efficient resource scheduling based on the similarity of new jobs has not been addressed
in [2]. Some studies show that even if the resource requirements of jobs are predicted accurately, it is
nearly impossible to predict the actual execution time on a given resource, and actual execution time is
only available after the completion of the job [3]. Ignoring uncertain facts at the time of scheduling may
lead to unsuccessful completion of jobs, especially, where resources are available for the limited period
of time, like in the case of cloud. In this work, we propose an efficient scheduling approach that selects
a resource for a job based on two critical criteria. Firstly, the selected resource is evaluated to ensure
a faster completion time. Secondly, the availability of the resource until the completion of the assigned
jobs is ensured. In addition, this work proposes optimization of these two criteria during the resource
selection process. Finally, we compare the efficiency of our scheduling algorithm with some well-known
job scheduling algorithms.
References
M. Sarkar, S. Roy, and N. Mukherjee, “Feedback-guided analysis for resource requirements in large distributed system,” in 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, 2010, pp. 596–597.
M. Sarkar, T. Mondal, S. Roy, and N. Mukherjee, “Resource requirement prediction using clone detection technique,” Future Generation Computer Systems, vol. 29, no. 4, pp. 936–952, 2013, special Section: Utility and Cloud Computing. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167739X12001835
H. H. Chen, X. Zhu, G. Liu, and W. Pedrycz, “Uncertainty-aware online scheduling for real-time workflows in cloud service environment,” IEEE Transactions on Services Computing, vol. 14, no. 4, pp. 1167–1178, 2021.
L. Jiang, F. Zhao, and X. Xi, “Matching operation constrained job shop scheduling problem based on backward heuristic scheduling algorithm,” 12 2010.
T. Braun, H. Siegel, N. Beck, L. Oni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, and B. Yao, “A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing systems,” in Proceedings Seventeenth IEEE Symposium on Reliable Distributed Systems (Cat. No.98CB36281), 1998, pp. 330–335.
K. B. Bey, F. Benhammadi, A. Mokhtari, and Z. Guessoum, “Independent task scheduling in heterogeneous environment via makespan refinery approach,” in 2010 International Conference on Machine and Web Intelligence, 2010, pp. 211–217.
Y.-K. Kwok and I. Ahmad, “Static scheduling algorithms for allocating directed task graphs to multiprocessors,” ACM Comput. Surv., vol. 31, no. 4, p. 406–471, Dec. 1999. [Online]. Available: https://doi.org/10.1145/344588.344618
T. D. Braun, H. J. Siegel, N. Beck, L. L. Bölöni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen, and R. F. Freund, “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems,” Journal of Parallel and Distributed Computing, vol. 61, no. 6, pp. 810–837, 2001. [Online]. Available: https: //www.sciencedirect.com/science/article/pii/S0743731500917143
M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, “Dynamic mapping of a class of independent tasks onto heterogeneous computing systems,” Journal of Parallel and Distributed Computing, vol. 59, no. 2, pp. 107–131, 1999. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0743731599915812
Z. A. Khan, I. A. Aziz, N. A. B. Osman, and I. Ullah, “A review on task scheduling techniques in cloud and fog computing: Taxonomy, tools, open issues, challenges, and future directions,” IEEE Access, vol. 11, pp. 143 417–143 445, 2023.
O. L. Abraham, M. A. B. Ngadi, J. B. M. Sharif, and M. K. M. Sidik, “Task scheduling in cloud environment–techniques, applications, and tools: A systematic literature review,” IEEE Access, vol. 12, pp. 138 252–138 279, 2024.
Y. T. H. Hlaing and T. T. Yee, “Static independent task scheduling on virtualized servers in cloud computing environment,” in 2019 International Conference on Advanced Information Technologies (ICAIT), 2019, pp. 55–59.
D. Meiländer, A. Ploss, F. Glinka, and S. Gorlatch, “A dynamic resource management system for real-time online applications on clouds,” in EuroPar 2011: Parallel Processing Workshops. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 149–158.
N. Sasikaladevi, “Minimum makespan task scheduling algorithm in cloud computing,” International Journal of Grid and Distributed Computing, vol. 9, pp. 61–70, 11 2016.
M. A. Alworafi, A. Al-Hashmi, A. Dhari, Suresha, and A. B. Darem, “Task-scheduling in cloud computing environment: Cost priority approach,” in Proceedings of International Conference on Cognition and Recognition, D. S. Guru, T. Vasudev, H. Chethan, and Y. S. Kumar, Eds. Singapore: Springer Singapore, 2018, pp. 99–108.
R. K. Jena, “Task scheduling in cloud environment: A multiobjective abc framework,” Journal of Information and Optimization Sciences, vol. 38, no. 1, pp. 1–19, 2017. [Online]. Available: https://doi.org/10.1080/02522667.2016.1250460
P. Zhang and M. Zhou, “Dynamic cloud task scheduling based on a twostage strategy,” IEEE Transactions on Automation Science and Engineering, vol. 15, no. 2, pp. 772–783, April 2018.
M. S. Sanaj and P. M. Joe Prathap, “An enhanced round robin (err) algorithm for effective and efficient task scheduling in cloud environment,” in 2020 Advanced Computing and Communication Technologies for High Performance Applications (ACCTHPA), 2020, pp. 107–110.
Y. Yu and Y. Su, “Cloud task scheduling algorithm based on three queues and dynamic priority,” in 2019 IEEE International Conference on Power, Intelligent Computing and Systems (ICPICS), 2019, pp. 278–282.
A. Younes, A. Salah, T. Farag, F. Alghamdi, and U. Badawi, “Task scheduling algorithnm for heterogeneous multi processing computing systems,” Journal of Theoretical and Applied Information Technology, vol. 97, pp. 3477–3487, 07 2019.
A. Belgacem, K. Beghdad-Bey, H. Nacer, and S. Bouznad, “Efficient dynamic resource allocation method for cloud computing environment,” Cluster Computing, vol. 23, no. 4, pp. 2871–2889, 2020.
X. Chen, L. Cheng, C. Liu, Q. Liu, J. Liu, Y. Mao, and J. Murphy, “A woa-based optimization approach for task scheduling in cloud computing systems,” IEEE Systems Journal, vol. 14, no. 3, pp. 3117–3128, 2020.
S. A. Alsaidy, A. D. Abbood, and M. A. Sahib, “Heuristic initialization of pso task scheduling algorithm in cloud computing,” Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 6, Part A, pp. 2370–2382, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1319157820305279
S. Lipsa, R. Dash, N. Ivkovic, and K. Cengiz, “Task scheduling in cloud ´ computing: A priority-based heuristic approach,” IEEE Access, vol. 11, pp. 27 111–27 126, 2023.
Y. Yang, F. Ren, M. Zhang, J. Yan, F. Xie, and W. Gao, “A bdi agent-based asynchronous scheduling framework for cloud computing,” in 2024 IEEE International Conference on Agents (ICA), 2024, pp. 1–6.
Q. Li, Z. Peng, D. Cui, J. Lin, and H. Zhang, “UDL: a cloud task scheduling framework based on multiple deep neural networks,” Journal of Cloud Computing, vol. 12, no. 1, p. 114, 2023. [Online]. Available: https://doi.org/10.1186/s13677-023-00490-y
T. Selvi Somasundaram, B. R. Amarnath, R. Kumar, P. Balakrishnan, K. Rajendar, R. Rajiv, G. Kannan, G. Rajesh Britto, E. Mahendran, and B. Madusudhanan, “Care resource broker: A framework for scheduling and supporting virtual resource management,” Future Generation Computer Systems, vol. 26, no. 3, pp. 337–347, 2010. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167739X09001551
S. Singh, M. Sarkar, S. Roy, and N. Mukherjee, “Genetic algorithm based resource broker for computational grid,” Procedia Technology, vol. 10, pp. 572–580, 2013, first International Conference on Computational Intelligence: Modeling Techniques and Applications (CIMTA) 2013. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2212017313005598
R. Buyya and M. Murshed, “Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing,” Concurrency and Computation: Practice and Experience, vol. 14, 11 2002.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
