Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Reduced computational cost in the calculation of worst case response time for real time systems
Keywords:
RM, DM, Schedulability, Response Time AnalysisAbstract
Modern Real Time Operating Systems require reducing computational costs even though the microprocessors become more powerful each day. It is usual that Real Time Operating Systems for embedded systems have advance features to administrate the resources of the applications that they support. In order to guarantee either the schedulability of the system or the schedulability of a new task in a dynamic Real Time System, it is necessary to know the Worst Case Response Time of the Real Time tasks during runtime. In this paper a reduced computational cost algorithm is proposed to determine the Worst Case Response Time of Real Time tasks.Modern Real Time Operating Systems require reducing computational costs even though the microprocessors become more powerful each day. It is usual that Real Time Operating Systems for embedded systems have advance features to administrate the resources of the applications that they support. In order to guarantee either the schedulability of the system or the schedulability of a new task in a dynamic Real Time System, it is necessary to know the Worst Case Response Time of the Real Time tasks during runtime. In this paper a reduced computational cost algorithm is proposed to determine the Worst Case Response Time of Real Time tasks.
Downloads
Download data is not yet available.
References
[1] C. L. Liu and J. W. Layland, "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment," Journal of the ACM, vol. 20, pp. 46-61, 1973.
[2] M. Barabanov, "Best Practices on Wind River Real-Time Core Application Development," Wind River Systems2008.
[3] J. A. Stankovic, "Misconceptions About Real-Time Computing: A Serius Problem for Next-Generations Systems," IEEE Computer, vol. Octubre, pp. 10-19, 1988.
[4] A. K. Mok and D. Chen, "A Multiframe Model For Real-Time Tasks," IEEE Trans. Software Eng., vol. 23, pp. 635-645, 1997.
[5] A. Burchard, J. Liebeherr, Y. Oh, and S. H. Son, "New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems," IEEE Trans. on Computers, vol. 44, pp. 1429-1442, 1995.
[6] C. C. Han, "A Better Polynomial-Time Schedulability Test for Real-Time Multiframe Tasks," in IEEE 19th Real-Time Systems Symposium, 1998, pp. 104-113.
[7] C.-C. Han and H.-y. Tyan, "A Better Polynomial-Time Schedulability Test for Real-Time Fixed-Priority Scheduling Algorithms," in IEEE 18th Real-Time Systems Symp., 1997.
[8] T.-W. Kuo, Y.-H. Liu, and K.-J. Lin, "Efficient Online Schedulability Tests fo Real-Time Systems," IEEE Transactions on Software Engineering, vol. 29, pp. 734-751, August 2003.
[9] R. Davis and A. Burns, "Response Time Upper Bounds for Fixed Priority Real-Time Systems," in The 29th IEEE Real-Time Systems Symposium, IEEE, Ed. Barcelona, Spain: IEEE Computer Society, 2008, pp. 407-418.
[10] J. Y. T. Leung and J. Whitehead, "On the Complexity of Fixed-Priority Scheduling of Periodic, Real Time Tasks," Perf. Eval. (Netherlands), vol. 2, pp. 237-250, 1982.
[11] N. C. Audsley, A. Burns, M. F. Richarson, and A. J. Wellings, "Hard Real-Time Scheduling: The Deadline Monotonic Approach," in Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, GA, USA 1991.
[12] M. Joseph and P. Pandya, "Finding Response Times in Real-Time System," The Computer Journal (British Computer Society), vol. 29, pp. 390-395, 1986.
[13] J. P. Lehoczky, L. Sha, and Y. Ding, "The Rate Monotonic Scheduling Algorithm: Exact Characterization And Average Case Behavior," in IEEE Real-Time Systems Symposium, 1989, pp. 166-171.
[14] J. Santos, M. L. Gastaminza, J. D. Orozco, D. Picardi, and O. Alimenti, "Priorities and Protocols in Hard Real-Time LANs," Computer Communications, vol. 14, pp. 507-514, 1991.
[15] J. Santos and J. D. Orozco, "Rate Monotonic Scheduling in Hard Real-Time Systems," Information Processing Letters, vol. 48, pp. 39-45, 1993.
[16] N. C. Audsley, A. Burns, M. F. Richardson, K. Tindell, and A. J. Wellings, "Applying New Scheduling Theory to Static Priority Preemptive Scheduling," Software Engineering Journal, vol. 8, pp. 284-292, 1993.
[17] M. Sjödin and H. Hansson, "Improved Response-Time Analysis Calculations," in IEEE 19th Real-Time Systems Symp., 1998, pp. 399-409.
[18] E. Bini and C. B. Giorgio, "Schedulability Analysis of Periodic Fixed Priority Systems," IEEE Trans. on Computers, vol. 53, pp. 1462-1473, November 2004.
[19] Z. Manna, S. Ness, and J. Vuillemin, "Inductive Methods for Proving Properties of Programs," Communications of the ACM, vol. 16, pp. 491-502, August 1973.
[20] L. Sha, R. Rajkumar, and J. P. Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," IEEE TRANSACTIONS ON COMPUTERS, vol. 39, pp. 1175-1185, 1990.
[21] R. I. Davis, "Approximate Slack Stealing Algorithms for Fixed Priority Pre-Emptive Systems," Real-Time Systems Research Group, University of York, York, England, Internal Report1994.
[22] R. I. Davis, K. W. Tindell, and A. Burns, "Scheduling Slack Time in Fixed-Priority Preemptive Systems," Proceedings of the Real Time System Symposium, pp. 222-231, 1993.
[23] J. M. Urriza, J. D. Orozco, and R. Cayssials, "Fast Slack Stealing methods for Embedded Real Time Systems," in 26th IEEE International Real-Time Systems Symposium (RTSS 2005) - Work In Progress Session, Miami, EEUU, 2005, pp. 12-16.
[2] M. Barabanov, "Best Practices on Wind River Real-Time Core Application Development," Wind River Systems2008.
[3] J. A. Stankovic, "Misconceptions About Real-Time Computing: A Serius Problem for Next-Generations Systems," IEEE Computer, vol. Octubre, pp. 10-19, 1988.
[4] A. K. Mok and D. Chen, "A Multiframe Model For Real-Time Tasks," IEEE Trans. Software Eng., vol. 23, pp. 635-645, 1997.
[5] A. Burchard, J. Liebeherr, Y. Oh, and S. H. Son, "New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems," IEEE Trans. on Computers, vol. 44, pp. 1429-1442, 1995.
[6] C. C. Han, "A Better Polynomial-Time Schedulability Test for Real-Time Multiframe Tasks," in IEEE 19th Real-Time Systems Symposium, 1998, pp. 104-113.
[7] C.-C. Han and H.-y. Tyan, "A Better Polynomial-Time Schedulability Test for Real-Time Fixed-Priority Scheduling Algorithms," in IEEE 18th Real-Time Systems Symp., 1997.
[8] T.-W. Kuo, Y.-H. Liu, and K.-J. Lin, "Efficient Online Schedulability Tests fo Real-Time Systems," IEEE Transactions on Software Engineering, vol. 29, pp. 734-751, August 2003.
[9] R. Davis and A. Burns, "Response Time Upper Bounds for Fixed Priority Real-Time Systems," in The 29th IEEE Real-Time Systems Symposium, IEEE, Ed. Barcelona, Spain: IEEE Computer Society, 2008, pp. 407-418.
[10] J. Y. T. Leung and J. Whitehead, "On the Complexity of Fixed-Priority Scheduling of Periodic, Real Time Tasks," Perf. Eval. (Netherlands), vol. 2, pp. 237-250, 1982.
[11] N. C. Audsley, A. Burns, M. F. Richarson, and A. J. Wellings, "Hard Real-Time Scheduling: The Deadline Monotonic Approach," in Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, GA, USA 1991.
[12] M. Joseph and P. Pandya, "Finding Response Times in Real-Time System," The Computer Journal (British Computer Society), vol. 29, pp. 390-395, 1986.
[13] J. P. Lehoczky, L. Sha, and Y. Ding, "The Rate Monotonic Scheduling Algorithm: Exact Characterization And Average Case Behavior," in IEEE Real-Time Systems Symposium, 1989, pp. 166-171.
[14] J. Santos, M. L. Gastaminza, J. D. Orozco, D. Picardi, and O. Alimenti, "Priorities and Protocols in Hard Real-Time LANs," Computer Communications, vol. 14, pp. 507-514, 1991.
[15] J. Santos and J. D. Orozco, "Rate Monotonic Scheduling in Hard Real-Time Systems," Information Processing Letters, vol. 48, pp. 39-45, 1993.
[16] N. C. Audsley, A. Burns, M. F. Richardson, K. Tindell, and A. J. Wellings, "Applying New Scheduling Theory to Static Priority Preemptive Scheduling," Software Engineering Journal, vol. 8, pp. 284-292, 1993.
[17] M. Sjödin and H. Hansson, "Improved Response-Time Analysis Calculations," in IEEE 19th Real-Time Systems Symp., 1998, pp. 399-409.
[18] E. Bini and C. B. Giorgio, "Schedulability Analysis of Periodic Fixed Priority Systems," IEEE Trans. on Computers, vol. 53, pp. 1462-1473, November 2004.
[19] Z. Manna, S. Ness, and J. Vuillemin, "Inductive Methods for Proving Properties of Programs," Communications of the ACM, vol. 16, pp. 491-502, August 1973.
[20] L. Sha, R. Rajkumar, and J. P. Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," IEEE TRANSACTIONS ON COMPUTERS, vol. 39, pp. 1175-1185, 1990.
[21] R. I. Davis, "Approximate Slack Stealing Algorithms for Fixed Priority Pre-Emptive Systems," Real-Time Systems Research Group, University of York, York, England, Internal Report1994.
[22] R. I. Davis, K. W. Tindell, and A. Burns, "Scheduling Slack Time in Fixed-Priority Preemptive Systems," Proceedings of the Real Time System Symposium, pp. 222-231, 1993.
[23] J. M. Urriza, J. D. Orozco, and R. Cayssials, "Fast Slack Stealing methods for Embedded Real Time Systems," in 26th IEEE International Real-Time Systems Symposium (RTSS 2005) - Work In Progress Session, Miami, EEUU, 2005, pp. 12-16.
Downloads
Published
2009-10-01
Issue
Section
Original Articles
License
How to Cite
[1]
“Reduced computational cost in the calculation of worst case response time for real time systems”, JCS&T, vol. 9, no. 02, pp. p. 72–81, Oct. 2009, Accessed: Nov. 15, 2025. [Online]. Available: https://journal.info.unlp.edu.ar/JCST/article/view/720
