Maintaining the feasibility of hard real-time systems with a reduced number of priority levels

Muhammad Bilal Qureshi; Saleh Alrashed; Nasro Min-Allah; Joanna Kołodziej; Piotr Arabas

International Journal of Applied Mathematics and Computer Science (2015)

  • Volume: 25, Issue: 4, page 709-722
  • ISSN: 1641-876X

Abstract

top
When there is a mismatch between the cardinality of a periodic task set and the priority levels supported by the underlying hardware systems, multiple tasks are grouped into one class so as to maintain a specific level of confidence in their accuracy. However, such a transformation is achieved at the expense of the loss of schedulability of the original task set. We further investigate the aforementioned problem and report the following contributions: (i) a novel technique for mapping unlimited priority tasks into a reduced number of classes that do not violate the schedulability of the original task set and (ii) an efficient feasibility test that eliminates insufficient points during the feasibility analysis. The theoretical correctness of both contributions is checked through formal verifications. Moreover, the experimental results reveal the superiority of our work over the existing feasibility tests by reducing the number of scheduling points that are needed otherwise.

How to cite

top

Muhammad Bilal Qureshi, et al. "Maintaining the feasibility of hard real-time systems with a reduced number of priority levels." International Journal of Applied Mathematics and Computer Science 25.4 (2015): 709-722. <http://eudml.org/doc/275982>.

@article{MuhammadBilalQureshi2015,
abstract = {When there is a mismatch between the cardinality of a periodic task set and the priority levels supported by the underlying hardware systems, multiple tasks are grouped into one class so as to maintain a specific level of confidence in their accuracy. However, such a transformation is achieved at the expense of the loss of schedulability of the original task set. We further investigate the aforementioned problem and report the following contributions: (i) a novel technique for mapping unlimited priority tasks into a reduced number of classes that do not violate the schedulability of the original task set and (ii) an efficient feasibility test that eliminates insufficient points during the feasibility analysis. The theoretical correctness of both contributions is checked through formal verifications. Moreover, the experimental results reveal the superiority of our work over the existing feasibility tests by reducing the number of scheduling points that are needed otherwise.},
author = {Muhammad Bilal Qureshi, Saleh Alrashed, Nasro Min-Allah, Joanna Kołodziej, Piotr Arabas},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {real-time systems; feasibility analysis; fixed-priority scheduling; rate monotonic algorithm; online scheduling},
language = {eng},
number = {4},
pages = {709-722},
title = {Maintaining the feasibility of hard real-time systems with a reduced number of priority levels},
url = {http://eudml.org/doc/275982},
volume = {25},
year = {2015},
}

TY - JOUR
AU - Muhammad Bilal Qureshi
AU - Saleh Alrashed
AU - Nasro Min-Allah
AU - Joanna Kołodziej
AU - Piotr Arabas
TI - Maintaining the feasibility of hard real-time systems with a reduced number of priority levels
JO - International Journal of Applied Mathematics and Computer Science
PY - 2015
VL - 25
IS - 4
SP - 709
EP - 722
AB - When there is a mismatch between the cardinality of a periodic task set and the priority levels supported by the underlying hardware systems, multiple tasks are grouped into one class so as to maintain a specific level of confidence in their accuracy. However, such a transformation is achieved at the expense of the loss of schedulability of the original task set. We further investigate the aforementioned problem and report the following contributions: (i) a novel technique for mapping unlimited priority tasks into a reduced number of classes that do not violate the schedulability of the original task set and (ii) an efficient feasibility test that eliminates insufficient points during the feasibility analysis. The theoretical correctness of both contributions is checked through formal verifications. Moreover, the experimental results reveal the superiority of our work over the existing feasibility tests by reducing the number of scheduling points that are needed otherwise.
LA - eng
KW - real-time systems; feasibility analysis; fixed-priority scheduling; rate monotonic algorithm; online scheduling
UR - http://eudml.org/doc/275982
ER -

References

top
  1. Audsley, N.C., Burns, A., Tindell, K. and A. Wellings (1993). Applying new scheduling theory to static priority preemptive scheduling, Software Engineering Journal 8(5): 284-292. 
  2. Audsley, N.C. (2001). On priority assignment in fixed priority scheduling, Information Processing Letters 79(1): 39-44. Zbl0998.68018
  3. Bini, E., Buttazzo, G.C. and Buttazzo, G. (2001). A hyperbolic bound for the rate monotonic algorithm, Proceedings of the 13th Euromicro Conference on Real-Time Systems, Washington, DC, USA, pp.59-66. 
  4. Bini, E. and Buttazzo, G.C. (2004). Schedulability analysis of periodic fixed priority systems, IEEE Transactions on Computers 53(11): 1462-1473. 
  5. Bini, E., Natale, M.D. and Buttazzo, G. (2008). Sensitivity analysis for fixed-priority real-time systems, Real-Time Systems 39(1-3): 5-30. Zbl1141.68020
  6. Burns, A. and Wellings, A.J. (2009). Real-Time Systems and Programming Languages, 4th Edn., Addison Wesley, Longmain. Zbl0768.68009
  7. 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. 
  8. Han, C.C. and Tyan, H.Y. (1997). A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms, Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), Washington, DC, USA, p. 36. 
  9. Hong, K.S. and Leung, J.Y.-T. (1992). On-line scheduling of real-time tasks, IEEE Transactions on Computers 41(10):1326-1331. 
  10. Joseph, M. and Pandya, P.K. (1986). Finding response times in a real-time system, The Computer Journal 29(5): 390-395. 
  11. Katcher, D.I., Arakawa, H. and Strosnider, J.K. (1993). Engineering and analysis of fixed priority schedulers, IEEE Transactions on Software Engineering 19(9): 920-934. 
  12. Katcher, D.I., Sathaye, S.S. and Strosnider, J.K. (1995). Fixed priority scheduling with limited priority levels, IEEE Transactions on Computers 44(9): 1140-1144. Zbl1057.68549
  13. Kopetz, H. (1997). Real-Time Systems, Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA. Zbl0930.68148
  14. Laplante, P.A., Kartalopoulos, S.V., Akay,M., El-Hawary, M.E., Periera, F. M.B., Anderson, J. B., Leonardi, R., Singh, C., Baker,R.J., Montrose, M., Tewksbury, S., Brewer, J.E., Newman, M.S. and Zobrist, G. (2004). Real-Time Systems Design and Analysis, 3rd Edition, John Wiley and Sons, Hoboken, NJ. 
  15. Lee, W. Y., Hong, S. J. and Kim, J. (2003). On-line scheduling of scalable real-time tasks on multiprocessor systems, Journal of Parallel and Distributed Computing 63(12): 1315-1324. Zbl1069.68030
  16. Lehoczky, J.P. and Sha, L. (1986). Performance of real-time bus scheduling algorithms, '86 ACM SIGMETRICS Joint International Conference on Computer Performance Modeling, Measurement and Evaluation, New York, NY, USA, pp. 44-53. 
  17. Lehoczky, J.P., Sha, L. and Ding, Y. (1989). The rate monotonic scheduling algorithm: Exact characterization and average case behavior, Proceedings of the IEEE Real-Time Systems Symposium, Santa Monica, CA, USA, pp. 166-171. 
  18. Leung, J.Y.T. and Whitehead, J. (1982). On the complexity of fixed-priority scheduling of periodic, Performance Evaluation 2(4): 237-250. Zbl0496.90046
  19. Liu, C.L. and Layland, J.W. (1973). Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM 20(1): 40-61. Zbl0265.68013
  20. Liu, J.W.S. (2000). Real Time Systems, Prentice Hall, New York, NY. 
  21. Min-Allah, N., Yong-Ji, W., Jian-Sheng, X. and Jiu-Xiang, L. (2007). Revisiting fixed priority techniques, in T.W. Kuo et al. (Eds.), Proceedings of Embedded and Ubiquitous Computing, Lecture Notes in Computer Science, Vol. 4808, Springer, Berlin/Heidelberg, pp. 134-145. 
  22. Min-Allah, N., Khan, S.U. and Yongji, W. (2010). Optimal task execution times for periodic tasks using nonlinear constrained optimization, Journal of Supercomputing 59(3): 1-19. 
  23. Min-Allah, N. and Khan, S.U. (2011). A hybrid test for faster feasibility analysis of periodic tasks, International Journal of Innovative Computing, Information and Control 7(10): 5689-5698. 
  24. Orozco, J., Cayssials, R., Santos, J. and Santos, R. (1998). On the minimum number of priority levels required for the rate monotonic scheduling of real-time systems, Proceedings of the 10th Euromicro Workshop on Real Time Systems, Berlin, Germany. 
  25. Patan, M. (2012). Distributed scheduling of sensor networks for identification of spatio-temporal processes, International Journal of Applied Mathematics and Computer Science 22(2): 299-311, DOI: 10.2478/v10006-012-0022-9. Zbl1283.93298
  26. Santos, J., Gastaminza, M. L., Orozco, J., Picardi, D. and Alimenti, O. (1991). Priorities and protocols in real-time LANs, Computer Communications 14(9): 507-514. 
  27. Sha, L. and Goodenough, J.B. (1988). Real-time scheduling theory and ADA, CMU/SEI-88-TR-33, Software Engineering Institute, Carnegie-Mellon University, Piittsburgh, PA. 
  28. Sha, L., Sprunt, B. and Lehoczky, J.P. (1989). Aperiodic task scheduling for hard real-time systems, Journal of Real-Time Systems 1(1): 27-69. 
  29. Sheng, J., Wang, Y., Liu, J., Zeng,H. and Min-Allah, N. (2007). A static priority assignment algorithm with least number of priority levels, Journal of Software 18(7): 1844-1854. 
  30. Sjodin, M. and Hansson, H. (1998). Improved response-time analysis calculations, Proceedings of the 19th IEEE RealTime Systems Symposium, Madrid, Spain, pp. 399-409. 
  31. Tindell, K.W., Bums, A. and Wellings, A.J. (1994). An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems Journal 6(2):133-151. 
  32. Xuelian, B., Yuhai, Y. and Shiyao, J. (2003). Optimal fixed priority assignment with limited priority levels, Proceedings of the Advanced Parallel Programming Technologies, Xiamen, China, pp. 194-203. Zbl1113.68355
  33. Xu, J. and Parnas, D. (1990). Scheduling processes with release times, deadlines, precedence, and exclusion relations, IEEE Transactions on Software Engineering 16(3): 360-369. 

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.