A new sufficient schedulability analysis for hybrid scheduling

Zhang, F. ; Zhai, Y. ; Liao, J.

International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) no. 3, pp. 683-692.

Résumé

Earliest deadline first (EDF) and fixed priority (FP) are the most commonly used and studied scheduling algorithms for real-time systems. This paper focuses on combining the EDF and FP strategies in one system. We provide a new sufficient schedulability analysis for real-time hybrid task systems which are scheduled by EDF and FP. The proposed analysis has a polynomial time complexity and no restrictions on task parameters, where the relative deadline of each task could be less than, equal to, or greater than its period. By extensive experiments, we show that our proposed analysis significantly improves the acceptance ratio compared with the existing results of the sufficient schedulability test for hybrid scheduling systems.

Détail

Keywords: scheduling algorithm, real time system, schedulability analysis, preemptive scheduling, earliest deadline first, fixed priority
Mots-clés : algorytm szeregowania, system czasu rzeczywistego, analiza szeregowalności

Bibliographie

[1] Albers, K. and Slomka, F. (2004). An event stream driven approximation for the analysis of real-time systems, Proceedings of the 16th Euromicro Conference on Real-Time Systems, Catania, Sicily, Italy, pp. 187–195.

[2] Alcorta-Garcia, E., Saucedo-Flores, S. and Diaz-Romero, D.A. (2014). Intelligent fault diagnosis in nonlinear systems, Intelligent Automation and Soft Computing 20(2): 201–212.

[3] Audsley, N.C., Burns, A., Richardson, M., Tindell, K.W. and Wellings, A.J. (1993). Applying new scheduling theory to static priority pre-emptive scheduling, Software Engineering Journal 8(5): 284–292.

[4] Bini, E. and Buttazzo, G.C. (2005). Measuring the performance of schedulability tests, Real-Time Systems 30(1–2): 129–154.

[5] Bini, E., Buttazzo, G.C. and Buttazzo, G.M. (2001). A hyperbolic bound for the rate monotonic algorithm, Proceedings of the 13th Euromicro Conference on Real-Time Systems, Delft, The Netherlands, pp. 59–66.

[6] Burns, A. and Wellings, A.J. (2009). Real-Time Systems and Programming Languages, 4th Edn., Addison Wesley, Boston, MA.

[7] Buttazzo, G. (2011). Hard Real-Time Computing Systems, Springer US, New York, NY.

[8] Chakraborty, S., Kunzli, S. and Thiele, L. (2002). Approximate schedulability analysis, 23rd IEEE Real-Time Systems Symposium, Austin, TX, USA, pp. 159–168.

[9] Davis, R.I. and Burns, A. (2005). Hierarchical fixed priority preemptive scheduling, 26th IEEE Real-Time Systems Symposium, Miami, FL, USA, pp. 389–398.

[10] Davis, R.I., Zabos, A. and Burns, A. (2008). Efficient exact schedulability tests for fixed priority real-time systems, IEEE Transactions on Computers 57(9): 1261–1276.

[11] Dertouzos, M.L. (1974). Control robotics: The procedural control of physical processes, IFIP Congress, Stockholm, Sweden, pp. 807–813.

[12] Devi, M. (2003). An improved schedulability test for uniprocessor periodic task systems, Proceedings of the 15th Euromicro Conference on Real-Time Systems, Porto, Portugal, pp. 23–30.

[13] Ghazalie, T.M. and Baker, T.P. (1995). A periodic servers in a deadline scheduling environment, Real-Time Systems 9(1): 31–67.

[14] Harbour,M.G. and Palencia, J.C. (2003). Response time analysis for tasks scheduled under EDF within fixed priorities, 24th IEEE Real-Time Systems Symposium, Cancun, Mexico, pp. 200–209.

[15] Hwang, I., Kim, S., Kim, Y. and Seah, C.E. (2010). A survey of fault detection, isolation, and reconfiguration methods, IEEE Transactions on Control Systems Technology 18(3): 636–653.

[16] Joseph, M. and Pandya, P.K. (1986). Finding response times in a real-time system, The Computer Journal 29(5): 390–395.

[17] Kuo, T.-W. and Li, C.-H. (1999). A fixed priority driven open environment for real-time applications, 20th IEEE Real-Time Systems Symposium, Phoenix, AZ, USA, pp. 256–267.

[18] López-Estrada, F.-R., Ponsart, J.-C., Theilliol, D., Astorga-Zaragoza, C.-M. and Camas-Anzueto, J.-L. (2015). Robust sensor fault estimation for descriptor-LPV systems with unmeasurable gain scheduling functions: Application to an anaerobic bioreactor, International Journal of Applied Mathematics and Computer Science 25(2): 233–244, DOI: 10.1515/amcs-2015-0018.

[19] Leung, J. and Whitehead, J.W. (1982). On the complexity of fixed priority scheduling of periodic real-time tasks, Performance Evaluation 2(4): 237–250.

[20] Liu, C.L. and Layland, J.W. (1973). Scheduling algorithm for multiprogramming in a hard real-time environment, Journal of the ACM 20(1): 40–61.

[21] Liu, J.W.S. (2000). Real-Time Systems, Prentice-Hall, Upper Saddle River, NJ.

[22] Samy, I., Postlethwaite, I. and Gu, D.-W. (2011). Survey and application of sensor fault detection and isolation schemes, Control Engineering Practice 19(7): 658–674.

[23] Santos, J.A., Jr., Lima, G. and Bletsas, K. (2013). Efficient schedulability tests for real-time embedded systems with urgent routines, Design Automation for Embedded Systems 18(1–2): 19–38.

[24] Tindell, K., Burns, A. and Wellings, A.J. (1994). An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems 6(2): 133–151.

[25] Tindell, K. and Clark, J. (1994). Holistic schedulability analysis for distributed hard real-time systems, Microprocessors and Microprogramming 40(2–3): 117–134.

[26] Zhang, F. and Burns, A. (2007). Analysis of hierarchical EDF pre-emptive scheduling, 28th IEEE Real-Time Systems Symposium (RTSS), Tucson, AZ, USA, pp. 423–434.

[27] Zhang, F. and Burns, A. (2009). Schedulability analysis for real-time systems with EDF scheduling, IEEE Transactions on Computers 58(9): 1250–1258.