A new sufficient schedulability analysis for hybrid scheduling

Zhang, Fengxiang; Zhai, Yanfeng; Liao, Jianwei

doi:10.1515/amcs-2016-0047

Abstract

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.

References

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.
Search in Google Scholar Back to article
Alcorta-Garcia, E., Saucedo-Flores, S. and Diaz-Romero, D.A. (2014). Intelligent fault diagnosis in nonlinear systems, Intelligent Automation and Soft Computing20(2): 201–212.10.1080/10798587.2013.861963
Search in Google Scholar Back to article
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 Journal8(5): 284–292.10.1049/sej.1993.0034
Search in Google Scholar Back to article
Bini, E. and Buttazzo, G.C. (2005). Measuring the performance of schedulability tests, Real-Time Systems30(1–2): 129–154.10.1007/s11241-005-0507-9
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Burns, A. and Wellings, A.J. (2009). Real-Time Systems and Programming Languages, 4th Edn., Addison Wesley, Boston, MA.
Search in Google Scholar Back to article
Buttazzo, G. (2011). Hard Real-Time Computing Systems, Springer US, New York, NY.10.1007/978-1-4614-0676-1
Search in Google Scholar Back to article
Chakraborty, S., Kunzli, S. and Thiele, L. (2002). Approximate schedulability analysis, 23rd IEEE Real-Time Systems Symposium, Austin, TX, USA, pp. 159–168.
Search in Google Scholar Back to article
Davis, R.I. and Burns, A. (2005). Hierarchical fixed priority preemptive scheduling, 26th IEEE Real-Time Systems Symposium, Miami, FL, USA, pp. 389–398.
Search in Google Scholar Back to article
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.10.1109/TC.2008.66
Search in Google Scholar Back to article
Dertouzos, M.L. (1974). Control robotics: The procedural control of physical processes, IFIP Congress, Stockholm, Sweden, pp. 807–813.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Ghazalie, T.M. and Baker, T.P. (1995). Aperiodic servers in a deadline scheduling environment, Real-Time Systems9(1): 31–67.10.1007/BF01094172
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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 Technology18(3): 636–653.10.1109/TCST.2009.2026285
Search in Google Scholar Back to article
Joseph, M. and Pandya, P.K. (1986). Finding response times in a real-time system, The Computer Journal 29(5): 390–395.10.1093/comjnl/29.5.390
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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 Science25(2): 233–244, DOI: 10.1515/amcs-2015-0018.10.1515/amcs-2015-0018
Search in Google Scholar Back to article
Leung, J. and Whitehead, J.W. (1982). On the complexity of fixed priority scheduling of periodic real-time tasks, Performance Evaluation2(4): 237–250.10.1016/0166-5316(82)90024-4
Search in Google Scholar Back to article
Liu, C.L. and Layland, J.W. (1973). Scheduling algorithm for multiprogramming in a hard real-time environment, Journal of the ACM20(1): 40–61.10.1145/321738.321743
Search in Google Scholar Back to article
Liu, J.W.S. (2000). Real-Time Systems, Prentice-Hall, Upper Saddle River, NJ.
Search in Google Scholar Back to article
Samy, I., Postlethwaite, I. and Gu, D.-W. (2011). Survey and application of sensor fault detection and isolation schemes, Control Engineering Practice19(7): 658–674.10.1016/j.conengprac.2011.03.002
Search in Google Scholar Back to article
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 Systems18(1–2): 19–38.10.1007/s10617-013-9113-6
Search in Google Scholar Back to article
Tindell, K., Burns, A. and Wellings, A.J. (1994). An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems6(2): 133–151.10.1007/BF01088593
Search in Google Scholar Back to article
Tindell, K. and Clark, J. (1994). Holistic schedulability analysis for distributed hard real-time systems, Microprocessors and Microprogramming40(2–3): 117–134.10.1016/0165-6074(94)90080-9
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Zhang, F. and Burns, A. (2009). Schedulability analysis for real-time systems with EDF scheduling, IEEE Transactions on Computers58(9): 1250–1258.10.1109/TC.2009.58
Search in Google Scholar Back to article

A new sufficient schedulability analysis for hybrid scheduling

Abstract

Paradigm

My account