research-article

Real-Time Scheduling Theory and Ada

Authors:

Lui Sha,

John B. GoodenoughAuthors Info & Claims

Computer, Volume 23, Issue 4

Pages 53 - 62

https://doi.org/10.1109/2.55469

Published: 01 April 1990 Publication History

Publisher Site

Abstract

Rate monotonic scheduling theory puts real-time software engineering on a sound analytical footing. The authors review the theory and its implications for Ada.

References

[1]

1. R. Rajkumar, L. Sha, and J.P. Lehoczky, "Real-Time Synchronization Protocols for Multiprocessors," Proc. IEEE Real-Time Systems Symp., CS Press, Los Alamitos, Calif., Order No. 894, 1988, pp. 259-269.

Google Scholar

[2]

2. L. Sha et al., "Mode Change Protocols for Priority-Driven Preemptive Scheduling," J. Real-Time Systems, Vol. 1, 1989, pp. 243-264.

Crossref

Google Scholar

[3]

3. C.L. Liu and J.W. Layland, "Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment," J. ACM, Vol. 20, No. 1, 1973, pp. 46-61.

Digital Library

Google Scholar

[4]

4. J.P. Lehoczky, L. Sha, and Y. Ding, "The Rate Monotonic Scheduling Algorithm -- Exact Characterization and Average Case Behavior," Proc. IEEE Real-Time System Symp., CS Press, Los Alamitos, Calif., Order No. 2004, 1989, pp. 166-171.

Google Scholar

[5]

5. L. Sha, J.P. Lehoczky, and R. Rajkumar, "Solutions for Some Practical Problems in Prioritized Preemptive Scheduling," Proc. IEEE Real-Time Systems Symp., CS Press, Los Alamitos, Calif., Order No. 749, 1986, pp. 181-191.

Google Scholar

[6]

6. J.P. Lehoczky, L. Sha, and J. Strosnider, "Enhancing Aperiodic Responsiveness in a Hard Real-Time Environment," Proc. IEEE Real-Time Systems Symp., CS Press, Los Alamitos, Calif., Order No. 815, 1987, pp. 261-270.

Google Scholar

[7]

7. B. Sprunt, L. Sha, and J. Lehoczky, "Aperiodic Task Scheduling for Hard Real-Time Systems," J. Real-Time Systems, Vol. 1, No. 1, 1989, pp. 27-60.

Crossref

Google Scholar

[8]

8. J.B. Goodenough and L. Sha, "The Priority Ceiling Protocol: A Method for Minimizing the Blocking of High Priority Ada Tasks," Ada Letters, Special Issue: Proc. 2nd Int'l Workshop on Real-Time Ada Issues VIII, Vol. 7, Fall 1988, pp. 20-31.

Digital Library

Google Scholar

[9]

9. L. Sha, R. Rajkumar, and J.P. Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," tech. report, Dept. of Computer Science, Carnegie Mellon Univ., 1987. To appear in IEEE Trans. Computers.

Crossref

Google Scholar

[10]

10. L. Kleinrock, Queueing Systems, Vol. I, John Wiley and Sons, 1975.

Crossref

Google Scholar

Cited By

View all

Kim JAbdelzaher TSha LNebel WAtienza D(2015)Schedulability bound for integrated modular avionics partitionsProceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition10.5555/2755753.2755762(37-42)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.5555/2755753.2755762
Yao JLiu XYuan MGu ZGebotys CMartin G(2008)Online adaptive utilization control for real-time embedded multiprocessor systemsProceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis10.1145/1450135.1450155(85-90)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1450135.1450155
Anderson JBud VDevi U(2008)An $\mathsf{EDF}$ -based restricted-migration scheduling algorithm for multiprocessor soft real-time systemsReal-Time Systems10.1007/s11241-007-9035-038:2(85-131)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1007/s11241-007-9035-0
Show More Cited By

Index Terms

Recommendations

Extending Ada's real-time systems annex with the POSIX scheduling services

In this paper we propose extending the scheduling model of the Ada 95 Real-Time Systems Annex with the services specified in the Real-Time POSIX standard. These services include a round robin within priorities scheduling policy, a sporadic server ...
Limitations of Ada for real-time scheduling
IRTAW '87: Proceedings of the first international workshop on Real-time Ada issues

The goal in real-time scheduling is to satisfy the timing requirements of application jobs which often have hard deadlines. There are two aspects to Ada's scheduling policies which are detrimental to achieving this goal. First, Ada's constraints on the ...
Extending Ada's real-time systems annex with the POSIX scheduling services
IRTAW '00: Proceedings of the 10th international workshop on Real-time Ada workshop

In this paper we propose extending the scheduling model of the Ada 95 Real-Time Systems Annex with the services specified in the Real-Time POSIX standard. These services include a round robin within priorities scheduling policy, a sporadic server ...

Reviews

Reviewer: Marian Gheorghe

After reviewing some basic results in the rate monotonic scheduling theory, this paper presents their implications for Ada. The first section contains an overview of some of the important results of rate monotonic scheduling theory. First, the authors present the problem of ensuring that independent periodic tasks, scheduled by the rate monotonic algorithm, meet their deadlines. Then they examine how to ensure that critical tasks meet their deadlines under overload conditions. They also consider the important problem of scheduling both periodic and aperiodic tasks. The last part of this section discusses the rate monotonic scheduling theory applied to real-time tasks that must interact. It also reviews real-time synchronization and communication issues. The final section reviews the Ada tasking model and considers in more detail problems concerning the suitability of Ada's t asking model to support the requirements of rate monotonic scheduling algorithms. This approach is of great interest in the development and maintenance of real-time systems and in the design of useful real-time applications in Ada.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Computer Volume 23, Issue 4

April 1990

89 pages

ISSN:0018-9162

Editor:
Bruce D. Shriver
Univ. of Southwestern Louisiana, Lafayette

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 April 1990

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kim JAbdelzaher TSha LNebel WAtienza D(2015)Schedulability bound for integrated modular avionics partitionsProceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition10.5555/2755753.2755762(37-42)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.5555/2755753.2755762
Yao JLiu XYuan MGu ZGebotys CMartin G(2008)Online adaptive utilization control for real-time embedded multiprocessor systemsProceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis10.1145/1450135.1450155(85-90)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1450135.1450155
Anderson JBud VDevi U(2008)An $\mathsf{EDF}$ -based restricted-migration scheduling algorithm for multiprocessor soft real-time systemsReal-Time Systems10.1007/s11241-007-9035-038:2(85-131)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1007/s11241-007-9035-0
Cheng ARas J(2007)The implementation of the Priority Ceiling Protocol in Ada-2005ACM SIGAda Ada Letters10.1145/1274610.1274611XXVII:1(24-39)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1145/1274610.1274611
Sabeghi MDeldari HKhajouei S(2006)A fuzzy algorithm for scheduling periodic tasks on multiprocessor soft real-time systemsProceedings of the 17th IASTED international conference on Modelling and simulation10.5555/1167113.1167191(436-442)Online publication date: 24-May-2006
https://dl.acm.org/doi/10.5555/1167113.1167191
Sha LAbdelzaher TÅrzén KCervin ABaker TBurns AButtazzo GCaccamo MLehoczky JMok A(2004)Real Time Scheduling TheoryReal-Time Systems10.1023/B:TIME.0000045315.61234.1e28:2-3(101-155)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1023/B%3ATIME.0000045315.61234.1e
Real JCrespo A(2004)Mode Change Protocols for Real-Time SystemsReal-Time Systems10.1023/B:TIME.0000016129.97430.c626:2(161-197)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1023/B%3ATIME.0000016129.97430.c6
Lev-Ami TTyszberowicz S(2003)Reactive and Real-Time Systems CourseReal-Time Systems10.1023/A:102518031065925:2-3(231-253)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1023/A%3A1025180310659
Stoyen AMarlowe TYounis MPetrov P(1999)A Development Environment for Complex Distributed Real-Time ApplicationsIEEE Transactions on Software Engineering10.1109/32.74891825:1(50-74)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1109/32.748918
Lee CPotkonjak MWolf W(1999)Synthesis of Hard Real-Time Application Specific SystemsDesign Automation for Embedded Systems10.1023/A:10089653045674:4(215-242)Online publication date: 1-Oct-1999
https://dl.acm.org/doi/10.1023/A%3A1008965304567
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Extending Ada's real-time systems annex with the POSIX scheduling services

Limitations of Ada for real-time scheduling

Extending Ada's real-time systems annex with the POSIX scheduling services

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations