Document Type : Original/Review Paper


Department of Computer Engineering, Golestan University, Gorgan, Iran.


Interest in cloud computing has grown considerably over recent years, primarily due to scalable virtualized resources. So, cloud computing has contributed to the advancement of real-time applications such as signal processing, environment surveillance and weather forecast where time and energy considerations to perform the tasks are critical. In real-time applications, missing the deadlines for the tasks will cause catastrophic consequences; thus, real-time task scheduling in cloud computing environment is an important and essential issue. Furthermore, energy-saving in cloud data center, regarding the benefits such as reduction of system operating costs and environmental protection is an important concern that is considered during recent years and is reducible with appropriate task scheduling.
In this paper, we present an energy-aware task scheduling approach, namely EaRTs for real-time applications. We employ the virtualization and consolidation technique subject to minimizing the energy consumptions, improve resource utilization and meeting the deadlines of tasks. In the consolidation technique, scale up and scale down of virtualized resources could improve the performance of task execution. The proposed approach comprises four algorithms, namely Energy-aware Task Scheduling in Cloud Computing(ETC), Vertical VM Scale Up(V2S), Horizontal VM Scale up(HVS) and Physical Machine Scale Down(PSD). We present the formal model of the proposed approach using Timed Automata to prove precisely the schedulability feature and correctness of EaRTs. We show that our proposed approach is more efficient in terms of deadline hit ratio, resource utilization and energy consumption compared to other energy-aware real-time tasks scheduling algorithms.


[1] M. Kumar, S.C. Sharma, A. Goel, A. and S.P. Singh, “A comprehensive survey for scheduling techniques in cloud computing” Journal of Network and Computer Applications, vol. 143, pp. 1-33, October 2019.
[2] M. Tajamolian and M. Ghasemzadeh, “Analytical evaluation of an innovative decision-making algorithm for VM live migration” Journal of AI and Data Mining, vol. 7, no. 4, pp. 589-596, November 2019.
[3] A. Amini Motlagh, A. Movaghar and A. M. Rahmani, “Task scheduling mechanisms in cloud computing: A systematic review” International Journal of Communication Systems, vol. 33, no. 6, pp. 1-23, April 2020.
[4] Y. Saadi and S. El Kafhali, “Energy-efficient strategy for virtual machine consolidation in cloud environment” Soft Computing, pp. 1-15, March 2020.
[5] H. Chen, X. Zhu, J. Zhu and J. Wang, “Eres: An energy-aware real-time elastic scheduling algorithm in clouds”. In IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, 2013, pp. 777-784.
[6] X. Zhu, L.T. Yang, H. Chen, J. Wang, S. Yin, and X. Liu, “Real-time tasks oriented energy-aware scheduling in virtualized clouds” IEEE Transactions on Cloud Computing, vol.2, no. 2, pp. 168-180, April 2014.
[7] G. Chen, N. Guan, K. Huang, and W. Yi, “Fault-tolerant real-time tasks scheduling with dynamic fault handling”. Journal of Systems Architecture, vol. 102, January 2020.
[8] S. Wimmer and J. Mutius, “Verified certification of reachability checking for timed automata”. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2020, pp. 425-443.
[9] J. Singh, “Schedulability Analysis of Probabilistic Real-Time Systems” Doctoral dissertation, UNIVERSITE DE TOULOUSE. 2020.
[10] B. Keshanchi, A. Souri, and N.J. Navimipour, “An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing” Journal of Systems and Software, vol.124, pp. 1-21, February 2017.
[11] H. Chen, G. Liu, S. Yin, X. Liu and D. Qiu, “ERECT: Energy-efficient reactive scheduling for real-time tasks in heterogeneous virtualized clouds” Journal of computational science, vol. 28, pp. 416-425, September 2018.
[12] Z. Deng, G. Zeng, Q. He, Y. Zhong, and W. Wang, “Using priced timed automaton to analyse the energy consumption in cloud computing environment” Cluster computing, vol.17, no. 4, pp. 1295-1307, December 2014.
[13] N. Akhter and M. Othman, “Energy aware resource allocation of cloud data centre: review and open issues” Cluster Computing, vol. 19, no. 3, pp. 1163-1182, September 2016.
[14] A.A.S. Ahmad and P. Andras, “Scalability analysis comparisons of cloud-based software services” Journal of Cloud Computing, vol. 8, no. 1, pp. 1-17, December 2019.
[15] J. Yang, C. Liu, Y. Shang, B. Cheng, Z. Mao, C. Liu and J. Chen, “A cost-aware auto-scaling approach using the workload prediction in service clouds” Information Systems Frontiers, vol.16, no.1, pp.7-18, March 2014.
[16] A. David, J. Illum, K.G. Larsen and A. Skou, “Model-based framework for schedulability analysis using UPPAAL 4.1.” Model-based design for embedded systems, vol.1, no.1, pp. 93-119, January 2009.
[17] M. Mikučionis, K.G. Larsen, J.I. Rasmussen, B. Nielsen, A. Skou, S.U. Palm and P. Hougaard, “Schedulability analysis using Uppaal: Herschel-Planck case study” In International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, Springer, Berlin, Heidelberg, 2010, pp. 175-190.
[18] N. Saeedloei and F. Kluźniak, “Synthesizing clock-efficient timed automata” In International Conference on Integrated Formal Methods, Springer, Cham, 2020, pp. 276-294.
[19] H. Chen, X. Zhu, H. Guo, J. Zhu, X. Qin and J. Wu, “Towards energy-efficient scheduling for real-time tasks under uncertain cloud computing environment” Journal of Systems and Software, vol.99, pp. 20-35, January 2015.
[20] Y. Jun, M. Qingqiang, W. Song, L. Duanchao, H. Taigui and D. Wanchun, “Energy-aware tasks scheduling with deadline-constrained in clouds” In IEEE International Conference on Advanced Cloud and Big Data (CBD), 2016, pp. 116-12.
[21] Y. Zhang, L. Chen, H. Shen and X. Cheng, “An energy-efficient task scheduling heuristic algorithm without virtual machine migration in real-time cloud environments”. In International Conference on Network and System Security, Springer, Cham, 2016, pp. 80-97.
[22] S. Hosseinimotlagh, F. Khunjush and R. Samadzadeh, “Seats: smart energy-aware task scheduling in real-time cloud computing” The Journal of Supercomputing, vol. 71, no. 1, pp. 45-66, January 2015.
[23] J. Wang, W. Bao, X. Zhu, L.T. Yang and Y. Xiang, “FESTAL: fault-tolerant elastic scheduling algorithm for real-time tasks in virtualized clouds” IEEE Transactions on Computers, vol. 64, no. 9, pp. 2545-2558, November 2014.
[24] H. Chen, X. Zhu, H. Guo, J. Zhu, X. Qin and J. Wu, “Towards energy-efficient scheduling for real-time tasks under uncertain cloud computing environment” Journal of Systems and Software, vol. 99, 20-35, January 2015.
[25] K.G. Larsen, P. Pettersson and W. Yi, “UPPAAL in a nutshell” International journal on software tools for technology transfer, vol. 1, no 1-2, pp. 134-152, December 1997.
[26] J. Bengtsson, K.G. Larsen, F. Larsson, P. Pettersson and W. Yi, “UPPAAL—a tool suite for automatic verification of real-time systems. In International hybrid systems workshop, Springer, Berlin, Heidelberg, October 1995, pp. 232-243.
[27] Y.A.K. Chaudhry and M. Hammed, “Formal Verification of Cloud based Distributed System using UPPAAL” In IEEE International Conference on Innovation and Intelligence for Informatics, Computing, and Technologies, 2019, pp. 1-4.
[28] G. Behrmann, A. David and K.G. Larsen, “A tutorial on uppaal” In Formal methods for the design of real-time systems, Springer, Berlin, Heidelberg, September 2004, pp. 200-236.
[29] Fersman, E., Mokrushin, L., Pettersson, P., & Yi, W. (2006). Schedulability analysis of fixed-priority systems using timed automata. Theoretical Computer Science, Vol. 354, No. 2, pp. 301-317.
[30] R.N. Calheiros, R. Ranjan, A. Beloglazov, C.A. De Rose and R. Buyya, “CloudSim: a toolkit for modelling and simulation of cloud computing environments and evaluation of resource provisioning algorithms” Software: Practice and experience, vol. 41, no. 1, pp. 23-50, January 2011.