A new sufficient schedulability analysis for hybrid scheduling

Fengxiang Zhang; Yanfeng Zhai; Jianwei Liao

International Journal of Applied Mathematics and Computer Science (2016)

  • Volume: 26, Issue: 3, page 683-692
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Fengxiang Zhang, Yanfeng Zhai, and Jianwei Liao. "A new sufficient schedulability analysis for hybrid scheduling." International Journal of Applied Mathematics and Computer Science 26.3 (2016): 683-692. <http://eudml.org/doc/286733>.

@article{FengxiangZhang2016,
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.},
author = {Fengxiang Zhang, Yanfeng Zhai, Jianwei Liao},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {scheduling algorithms; real-time systems; schedulability analysis; preemptive scheduling; earliest deadline first; fixed priority},
language = {eng},
number = {3},
pages = {683-692},
title = {A new sufficient schedulability analysis for hybrid scheduling},
url = {http://eudml.org/doc/286733},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Fengxiang Zhang
AU - Yanfeng Zhai
AU - Jianwei Liao
TI - A new sufficient schedulability analysis for hybrid scheduling
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 3
SP - 683
EP - 692
AB - 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.
LA - eng
KW - scheduling algorithms; real-time systems; schedulability analysis; preemptive scheduling; earliest deadline first; fixed priority
UR - http://eudml.org/doc/286733
ER -

References

top
  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. Zbl1083.68008
  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. Zbl0768.68009
  7. Buttazzo, G. (2011). Hard Real-Time Computing Systems, Springer US, New York, NY. Zbl1246.68001
  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). Aperiodic 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 RealTime 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. Zbl1322.93094
  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. Zbl0496.90046
  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. Zbl0265.68013
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.